The following problem appeared in one of the mini-projects in the coursera course Principles of Computing 2 which is a part of the Specialization Fundamentals of Computing, taught by RICE university. The following problem description is taken from the project description from the course itself:
For this assignment, the task is to implement a machine player for TicTacToe that uses a Minimax strategy to decide its next move. Tic-tac-toe is a zero-sum-game with perfect information. Although the game is played on a 3×3 grid, the implemented version should be able to handle any square grid (however, the time it will take to search the tree for larger grid sizes will be prohibitively slow).
In this project, Minimax will be used to search the entire game tree and no pruning will be used (since the full game tree is relatively of small size, exploring the entire game tree without pruning will not be inefficient on a 3×3 board). If we start with an empty TicTacToe board, it will take a long time for the strategy to search the tree. Therefore, it’s strongly suggested to write tests that start with a partially full board. This will allow the code to run much faster and will lead to a more pleasant development and debugging experience.
Machine Player Strategy
Both the players are machine players and will use Minimax strategy to choose the next move from a given TicTacToe position. The general idea on Minimax is to search the entire game tree alternating between minimizing and maximizing the score at each level. For this to work, we need to start at the bottom of the tree and work back towards the root. However, instead of actually building the game tree to do this, should use recursion to search the tree in a depthfirst manner. The recursive function should call itself on each child of the current board position and then pick the move that maximizes (or minimizes, as appropriate) the score. If this is done, the recursive function will naturally explore all the way down to the bottom of the tree along each path in turn, leading to a depth first search that will implement Minimax. The following page https://class.coursera.org/principlescomputing2-002/wiki/minimax describes the process in more detail.
The following animation shows how each of the machine players play the game by using Minimax at every state of the board, in order to choose its next move.
The following figures show the game tree explored by the player (along with the scores evaluated) at a given state to choose the best move (MAX player chooses the move corresponding to the maximum of the minimum scores down the tree, where MIN player chooses the move corresponding to the minimum of the maximum scores down the tree, as shown next).
As can be seen, each of the state of the game tree is color-coded in w.r.t. the score, e.g.,
- green in favor of the MAX player
- red in favor of the MIN player
- gray neutral
(1) Starting State (next turn Player X, the MAX player)
Game Tree Explored by Player X (Zoom to see)
As can be seen from the above game tree, the next move chosen by the MAX player will be corresponding to the gray state, since all other next moves results in a red state.
(2) Next State (next turn Player O, the MIN player)
Game Tree Explored by Player O
As can be seen again from the above game tree, the next move chosen by the MIN player will be corresponding to the gray state, since all other next moves results in a green state.
(3) Next State (next turn Player X, the MAX player)
Game Tree Explored by Player X
As can be seen again from the above game tree, the next move chosen by the MAX player will be corresponding to the gray state, since all other next moves results in a red state.
(4) Next State (next turn Player O, the MIN player)
Game Tree Explored by Player O
As can be seen again from the above game tree, all of the moves result in a gray state, so the MIN player arbitrarily chooses one of them.