Game Trees, Part 2
(Up to Basic
Computer Science : Data Trees)
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.