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:

## TicTacToe (Minimax)

### Overview

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.

### Results

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.

### (5) Next State (next turn Player X, the MAX player)

### Game Tree Explored by Player X

**tie**.