|
Data Structures and Algorithms
|
| 14 Games
|
Naive Solutions
A naive program attempting to play a game like chess will:
- 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.
Because there are usually at least 20 possible moves from any given chess
position, to search to a depth of m requires ~20m
moves.
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.
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.
Alpha-Beta Algorithm
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.
© 
, 1998