14. Games

Naive Solutions

A naive program attempting to play a game like chess will:

1. Determine the number of moves which can be made from the current position,
2. For each of these moves,
   1. Apply the move to the current position,
   2. Calculate a "score" for the new position,
   3. If the maximum search "depth" has been reached, return with this score as the score for this move,
   4. else recursively call the program with the new position.
3. 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^m 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. requires ~20

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. 

 Alpha-Beta pruning Algorithm