Picking the best move: Minimax Trees

We have played a lot of board games when we were kids. Chess, checkers, connect four and so on.

Some of these games are addictive to play. Regardless, you must have thought of predicting what can be the next best move. Who will win if both players play the best move they can think up?

Now some games like chess, it is computationally infeasible to predict the best move given that all the possible combinations are searched. Chess has a state space of 1047  .

In English, it means the no. of different lines of play can go till that huge number. Games like Connect 4, Gomoku are more tractable.

These games form a class called two player zero sum games. Either one player will win or a draw will happen. Also they are deterministic, there is only a fixed number of moves that a player can pick from. There is no randomness inherent in it.

So how do we predict the best line of play or pick the best move? There are a class of search methods called informed search. There are many methods that can be used. But one which we will use is the minimax search method.

What is Minimax?

The minimax algorithm works on the principle that the first player(A) will try to maximize its ‘winnings’ by choosing the best move. The second player(B) will correspondingly try to minimize that same ‘score’ and pick the best move for itself.

The concept is to reduce the loss yet incurred in the game for each player. Both the players work toward opposite goals. They want to reach the goal that is favorable for themselves.

Introducing the Minimax Tree.

A tree is used to represent the minimax data structure on which the algorithm will start the search.

Each node represents the game state. A node’s child nodes represent the possible, valid states that is reached by taking one move.

Every node will have a score or a heuristic value. This score is usually returned as a result of a position evaluation function.

The nodes which represent the end of the game are terminal nodes of the tree. So the game will result in a win for A, loss for A or a draw.

Player A will maximize the score. Player B will minimize the score.

f3 (1)
Illustration from ACM magazine

The Minimax Algorithm

The minimax algorithm operates on a tree starting from a given node to pick the best move. It will look at each child of the given node and start running the minimax algorithm for that branch. It will return the score of the node — the score of the best choice.

If it is a max node i.e. player A’s turn then the max score will be chosen. Else it is a min node i.e. player B’s turn then the min score is chosen.

In this manner, the whole tree is visited till all the outcomes are reached. The least worst outcome is chosen. The line of moves required to reach that outcome is the one picked.

MINIMAX( node, player )
{

 if node is terminal game state:
   return EVALUATE(node)
 if player is maximizing:
  bestValue = -INF
  for each child of node:
   (childValue,childBoard) = MINIMAX(child, FALSE)
   if childValue < bestValue
    bestValue = childValue
    bestBoard = childBoard
 else player is minimizing:
  bestValue = +INF
  for each child of node:
   (childValue,childBoard) = MINIMAX(child, TRUE)
   if childValue < bestValue
    bestValue = childValue
    bestBoard = childBoard
 return (bestValue,bestBoard)
}

Note that the best next board position value and board is returned. That move needs to be played.

A function to generate valid board positions reachable from the current board position should be implemented. It will vary from game to game of course.

The idea is pretty simple. It just is mind blowing how much this algorithm can predict moves for play.

Limitations

The plain jane Minimax will visit the whole tree before any answer is returned. For games like checkers and chess, this is prohibitive. Also consider that visiting many branches can be repetitive when the game can revisit the same board position. A good example is chess in endgames. A rook endgame can end in visiting the same board state many times.

Depth Limited Minimax

Considering the limitations above, there is a variant of minimax that will keep searching till the cutoff depth is reached. It is the same as minimax except there will be depth as a parameter. For a node, its child nodes is searched with that depth minus 1.
If the depth is 0, then a heuristic function is called to evaluate the position. Since the node isn’t leaf node, some rules need to be defined in the heuristic function.

Investigation on a game

Let us apply this algorithm on a game as an example. Tic tac toe is a prime example for its simplicity. But it does have a large no. of possibilities – 9!.

To use Tic Tac Toe, first I’ll need to define a heuristic to evaluate board positions.

Heuristic function possibilities

One way to go about making a heuristic is to count the no. of immediate wins for the given player in the board. If there are two x’s in a row with the third one unfilled, then count this as one point for x. This goes vice versa for o.

The other way is to grade different positions of tic tac toe board and sum them up.
I tried using both approaches in a Python project here.
The minimax with the board position heuristic ran faster. You might be wondering how much time must have gone – it takes about a minute to run with the first heuristic while for the second one takes half that time.

Game-tree-for-Tic-Tac-Toe-game-using-MiniMax-algorithm

The plain Minimax algorithm took quite some time around 140sec. On the other hand the depth limited version was able to finish fairly quickly. It takes 6.35s for a depth limit of 6.

Analysis

Assume there are N possible moves for each node. Say the game ends in D moves.

Then the branching factor is N. The algorithm will expand the root node. The node will generate N child nodes. Each node will be visited and will generate N nodes. Thus, N nodes will generate N child nodes which equals N2 nodes. So those N2 nodes will each generate N nodes – resulting in total N * N2 =  N3 nodes.

Continuing in this manner the last move will have ND child nodes.

The worst case time complexity will be O(ND).

If you don’t understand time complexity, don’t worry –  look in the links below. There are some lovely resources to help you out.

Conclusion

We looked at the concept of Minimax and understood the minimax tree. We also went through the algorithm and got to apply it on tic tac toe. The variant of minimax of depth limited minimax was also explained. There is a version of minimax which eliminates branches that are not needed called alpha beta pruning. It helps to limit the time taken to search huge game trees like those in chess.

Hope that you have understood and enjoyed the article. Please drop a comment if you have any suggestions and tips for improvement!

Additional Resources

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close