Data Structures and Algorithms
A naive program attempting to play a game like chess will:
Because there are usually at least 20 possible moves from any given chess
position, to search to a depth of m requires ~20m
Since good human players usually look 10 or more moves ahead,
the simple algorithm would severely tax the capabilities of even the
fastest modern computer.
- Determine the number of moves which can be made from the current position,
- For each of these moves,
- Apply the move to the current position,
- Calculate a "score" for the new position,
- If the maximum search "depth" has been reached,
return with this score as the score for this move,
- else recursively call the program with the new position.
- Choose the move with the best score and return its score
and the move generating it to the calling routine.
However, with a little cunning, the number of moves which needs to be
searched can be dramatically reduced - enabling a computer to search
deeper in a reasonable time and, as recent events have shown,
enable a computer to finally be a match for even the best human players.
The Alpha-Beta algorithm reduces the number of moves which need to be
explored by "cutting off" regions of the game tree which cannot produce
a better result than has already been obtained in some part of the
tree which has already been searched.
© John Morris, 1998