What if our search space is large? (like in chess game a possible number of states are nearly 10²⁰). For Tic-Tac-Toe we are using a 3x3 grid then a possible number of states are (3⁹= 196839) which is a very small search space. As minimax is a search algorithm, it goes to the terminal state in order to select the best move. Now, you should be able to understand the principles behind the Minimax algorithm that allowed us to create an unbeatable Tic Tac Toe AI agent. What’s Next… Tic-Tac-Toe using Alpha Beta Pruning Search Algorithm? In this way, for every move AI agent search for the best move and remain unbeatable. At depth 1 again we are maximizing the score to +1 and it gets propagated to current state and now we will choose move associated with the +1 score we’ve ended up with.At depth 2 we are minimizing the score to -1 and it gets propagated to depth 1.At depth 3 we are maximizing the score to +1 and it gets propagated to depth 2.We are going to calculate the minimax score from the bottom that is from the terminal state. Look the current situation of the board and we are trying to solve for O’s. If both the 3 and 4 points not follow then the game will be a draw (Line 31).įor better understanding what’s going on let’s take the example! Unbeatable AI agent.If all elements of the row are “X” or all elements of the column is”X” or if all elements of diagonals are “X” then user will win.If all elements of the row are “O” or all elements of the column are ”O” or if all elements of diagonals are “O” then AI agent will win (Line 29).User’s turn is max and AI agent’s turn is always min. Alternatively, user and AI agent call Best_Move() (Line 28). The best move of AI agent will selected by comparing the best value with a move. The AI agent will take the second move (Line 14) and search for the best move by expanding the whole search space.The user can put “X” in any 9 positions on the board. User will take the first move (Line 6) always.As it is the Minimax Algorithm and it makes use of Depth First Search (Search Space) for finding the best move. We just start the game by calling Start_Game() and the current state (Line 2) of the board is that there are no X’s and O’s. Minimax is called so because it helps in minimizing the loss when the other player chooses the strategy having the maximum loss. It is similar to how we think when we play a game: “if I make this move, then my opponent can only make only these moves,” and so on. Minimax is a recursive algorithm that is used to choose an optimal move for a player assuming that the other player is also playing optimally. Now let’s move to the Minimax Algorithm! □ About Minimax Algorithm With perfect play, it always ends in a draw. It means it is possible to see all the possible moves of a particular game. The game is perfect information (one can easily analyze what step should be taken so that opponent can’t win) and zero-sum (mathematical representation of a situation in which each participant’s gain or loss of utility is exactly balanced by the losses or gain) game. The player who succeeds first to claim three squares on a single row, column or diagonal wins the game.Īs far as the games go, we need to think about how to solve the Tic-Tac-Toe game from the given current state of the grid. It is a two-player game where the players take alternative turns on a 3x3 grid. It is a 3x3 grid-based game also known as X’s and O’sor noughts and crosses. What’s Next… Tic-Tac-Toe using Alpha Beta Pruning Search Algorithm?īefore jumping to the minimax algorithm, first understand the Tic-Tac-Toe Game.
0 Comments
Leave a Reply. |