TicTacToe game can be framed into a typical search problem involving game trees with each node representing a game state (or game position) and each edge representing a move made by a player.
The levels of the tree can be thought of as the number of total moves made by either player until that point. Didn’t get it, huh! Well, let me make it more clear by correlating the game with the tree.
Imagine playing tictactoe on a game-board with your friend. Either, you or your friend can make the first move (let’s call it move0). After that, both of you will alternatively make moves until one of you wins or the game ends in a draw. These moves (move0, move1, move2….) can be correlated to the levels of the aforementioned tree. So, at level0 move0 is made, at level1 move1 is made and so on.
Here on, you are Player1 and your friend is Player2. At the beginning of the game, the tree is at level0 and the root node represents the initial state of the game. You, being Player1, make the first move (move0) and the game state changes to one of the subsequent states represented by the root’s children. Now, tree is at level1. Player2 then makes a move (move1. Game state and tree level change again. By the time, last move is made on the game-board, tree would have reached one of its leaf nodes. Each of the leaf nodes represent an end state of the game. It could be a win for Player1, a win for Player2 or a draw. The objective of each player when they make a move at any level is to maximize their chances of reaching a leaf node that guarantees a win for them or a draw. Now, since you have a fair idea about how the game and a search tree are related, lets discuss an algorithm to traverse the tree.
Recursive Minimax algorithm is used to dynamically evaluate a state in the game. As discussed before, the nodes in the search tree represent these states. A node is a “max” node if it describes a state where the “maximizer” (Player1) is to make a move. It is a “min” node if it describes a state where the “minimizer” (Player2) is to make a move. The children of a node are all the possible states that can be reached after one move. With each state ‘x’, we associate the value ‘Vx’. The function evaluate(x) gives a static evaluation(Vx) of the state.
Note : – Try to understand the below functions keeping in mind that the computer is playing against an opponent. This opponent could be a human or another computer. It does not concern us here. The functions below have been explained from the computer’s perspective.
The function nextBestMove() determines the next best move given a game state. So , imagine it is either the beginning of the game or it is mid-game and the opponent has already played. Now it is the computer’s turn to play. Computer looks at each of the next possible moves and chooses the one with the maximum static estimate (Vx returned by evaluate(x)). If you correlate it to the tree, the current game state is a node in the tree. So the computer chooses a child-node that returns the maximum static estimate out of all the node’s children.
def nextBestMove(self):
ret = -10
rowBest = -1
columnBest = -1
for row in range(0,3):
for column in range(0,3):
if self.board[row][column] == ' ':
self.board[row][column] = 'x'
temp = self.miniMax(self.board,0)
if temp > ret:
rowBest = row
columnBest = column
ret = temp
self.board[row][column] = ' '
return [rowBest,columnBest]
The following function miniMax() forms the crux of the algorithm. It considers both the players’ moves and recursively calls itself. This function simulates both the players’ moves until it reaches a leaf node. It works based on the assumption that when one player tries to maximize his chances of winning, the other player tries to minimize the opponent’s chances. So in this case, the computer is trying to maximize its chances of winning, so the function miniMax() assumes that the opponent will also try to do the same and therefore simulates optimum moves for the opponent.
def miniMax(self,board,flag):
temp = self.evaluate(board)
if temp == 1:
return 1
elif temp == -1:
return -1
elif temp == 0:
return 0
else:
if flag == 0:
ret = 10
for row in range(0, 3):
for column in range(0, 3):
if board[row][column] == ' ':
board[row][column] = 'O'
ret = min(ret, self.miniMax(board, 1))
board[row][column] = ' '
return ret
else:
ret = -10
for row in range(0, 3):
for column in range(0, 3):
if board[row][column] == ' ':
board[row][column] = 'x'
ret = max(ret, self.miniMax(board, 0))
board[row][column] = ' '
return ret
Function evaluate() returns a static estimate for a given game state. It returns a value of 1 if it is a win for the computer, returns -1 if it is a lose, returns 0 if it is a draw.
def evaluate(self,board):
# check rows
if (board[0][0] == 'x' and board[0][1] == 'x' and board[0][2] == 'x') or
(board[1][0] == 'x' and board[1][1] == 'x' and board[1][2] == 'x') or
(board[2][0] == 'x' and board[2][1] == 'x' and board[2][2] == 'x'):
return 1
if (board[0][0] == 'O' and board[0][1] == 'O' and board[0][2] == 'O') or
(board[1][0] == 'O' and board[1][1] == 'O' and board[1][2] == 'O') or
(board[2][0] == 'O' and board[2][1] == 'O' and board[2][2] == 'O'):
return -1
# check columns
if (board[0][0] == 'x' and board[1][0] == 'x' and board[2][0] == 'x') or
(board[0][1] == 'x' and board[1][1] == 'x' and board[2][1] == 'x') or
(board[0][2] == 'x' and board[1][2] == 'x' and board[2][2] == 'x'):
return 1
if (board[0][0] == 'O' and board[1][0] == 'O' and board[2][0] == 'O') or
(board[0][1] == 'O' and board[1][1] == 'O' and board[2][1] == 'O') or
(board[0][2] == 'O' and board[1][2] == 'O' and board[2][2] == 'O'):
return -1
# check diagonals
if (board[0][0] == 'x' and board[1][1] == 'x' and board[2][2] == 'x') or
(board[0][2] == 'x' and board[1][1] == 'x' and board[2][0] == 'x'):
return 1
if (board[0][0] == 'O' and board[1][1] == 'O' and board[2][2] == 'O') or
(board[0][2] == 'O' and board[1][1] == 'O' and board[2][0] == 'O'):
return -1
# If board is full, return 0 else return -2
for row in range(0,3):
for column in range(0,3):
if board[row][column] == ' ':
return -2
return 0
The function makeMove() is just a helper function that actually makes the move. It is called after nextBestMove() determines the next best move.
def makeMove(self,bestMove,flag):
if flag==0:
self.board[int(bestMove[0])][int(bestMove[1])] = 'O'
else:
self.board[int(bestMove[0])][int(bestMove[1])] = 'x'
return self.evaluate(self.board)
I wrote this game in Python and you can play it here. As you will soon find out, you will never be able to beat the computer at this game. The reason is because the computer is able to simulate all the possible moves and choose the best out of them. But do keep in mind that you can make the game more interesting by bringing in certain degree of randomness to the moves made by the computer. I just chose not to do it:)
Now you know that it is fairly straightforward to write a computer program using game trees to play tictactoe perfectly. Tictactoe’s game tree is fairly simple compared to the game tree for games like chess. Although, tictactoe game is generally considered as an example of computer AI (weak AI), there are people who don’t support this view due to its relative simplicity. But, in my opinion it should fall under AI. After all, AI is all about making machines as intelligent as humans and that is exactly what we have done here.
Yet Another Compsci guy 