Minimax Algorithm - Explanation + Solving the Minimax tree with Game Example скачать в хорошем качестве

Minimax Algorithm - Explanation + Solving the Minimax tree with Game Example

In our AI Series, video’s so far, we have been trying to understand theory around AI. I was thinking if we can supplement this theory with practical experience. This video will form the basis on practical experience that will comeup in future videos. Lets understand what is minimax algorithm first before we start coding. We will take a example of game that I created just to help with understanding of algorithm in itself. What is a minimax algorithm? The Minimax algorithm is a popular algorithm used to create two-player games. One of the players is the computer which is essentially Artificial Intelligence. This algorithm is only used in games where there is always a winner. Have you ever played a game where you have played against the computer and it is almost impossible to win? Like solitaire, chess, This is what the minimax algorithm helps to achieve. 1. Competitive Zero Sum game: This minimax algorithm is used in competitive zero-sum games, Zero-sum means that when one of the players wins the other player loses. There can’t be two winners. So there is one winner OR there is a tie or a draw. So games like chess, tic-tac-toe are examples of games that come under these conditions. One player wins and the other player loses. That is what we will be creating with our minimax algorithm. 2. The second condition the minimax algorithm uses is a fully observable environment. So the game must always show all the previous moves made by all players and the current state of the game at every step. For example in chess, everything is out there on the board. Previous moves made by each player are completely seen at all times. So when the other player is making a move, they are making a fully informed decision. This is how humans play this game. Imagine AI playing this game using the minimax algorithm. How? That is what we are trying to understand and achieve here. We are trying to simulate a human player who is at the expert level. Minimax algorithm allows AI to look into the future. To look into the final result of every possible move at every turn. Then it will tally the results of all moves and decide which of those moves will produce the most optimal result for AI. This is how we can make an unbeatable AI in a two-player adversarial game with a minimax algorithm. It looks well into the future until the end of the game and always makes the right choice. This way the only possible ending states of the game are either the AI winning or a draw. We will be looking into how to create an unbeatable AI tic tac toe game in further videos. Here are certain things we need to know before we move forward. 1. The minimax algorithm is used by the AI player or the computer to determine which move it should make next. This algorithm is not used by Human players at all at any point in the game. 2. Therefore the results of using the minimax algorithm are always going to favor AI and no one else. So it will move the final stage of the game to a stage where either AI will win or it is a draw. When you have many moves to make in the game, you can easily see that AI players will have an advantage over human players. AI will have a higher chance of winning than humans when the game involves many moves, it gets difficult and almost impossible for humans to see the end state and choose the optimum result well ahead in the game. In complex games, the human player starts making mistakes and you will see that every time AI wins the game.