Minimax Game Trees, Part 2
(Up to Basic Computer Science : Data Trees)

[Part 1] [Part 2]

The strategy behind the Minimax algorithm is that the computer assumes that both players will play to the best of their ability. So, if the opponent has the choice of a bad move or a good move, the computer will have the opponent choose the good move.

This simple and relatively obvious concept is the secret behind the minimax tree. Let's say the computer was programmed to play as Max. The best move or series of moves for the computer to make are those moves that result in the highest point value, no matter what Min does. Min will obviously try to choose the moves that result in the lowest point value.

In a sense, the bottom nodes of the tree are the only ones that need to be evaluated for a positional value, becuse they are the end product. Let's say the bottom nodes are always a position in which it is Max's turn to play. The computer would assume that Min would play the lowest-point move as possible, so the minimax value of any Max node would be equivilent to the point value of Min's lowest-point child node.

In the end, the computer's strength comes from the computer's ability to evaluate a position, and how deep the computer can read, just like in human board game playing. A chess grandmaster would often be able to evaluate slight differences better than an amateur, and the grandmaster will also be able to look ahead further. So, the computer looks ahead as far as it can, and it won't play grossly bad moves because it will see the crushing response from its opponent.

There are many algorithms that will help the efficiency of the Minimax tree search. One such algorithm is called Alpha-Beta Tree pruning. In a search using the Alpha-Beta pruning technique, the computer only has to search approximately the square root of the number of nodes it would have searched without the technique. Thus, when the computer would normally examine 400 nodes, the new program might only examine 20.

Other tools include the Transposition table, which records the results of searches in a small, fast table. Often, the same positions can be reached with a different sequence of moves. These two positions are said to transpose to each other. The table helps the computer recognize a board position it has already examined, and thus save time at the expense of memory.

Together, these techniques allow the computer to search through many, many nodes and thus simulate tactical thought. Although other techniques are coming into the spotlight (noticeably Neural Networks), the minimax tree is at the heart of the best programs.