|
Data Structures and Algorithms
|
| 13 Games
|
Although games like chess require analysis of extraordinarily
large numbers of moves - and thus are placed in the
intractable class - dramatic improvements can be made
in the running time with the best algorithm.
The Naive Approach
A naive chess program simply determines the moves that can be made
from any position and then,
for each of the possible moves:
- applies the move to the current position,
- evaluates the new position and then
- determines how many moves can be made from the new position
and applies the same procedure ..
This algorithm is set to terminate at some fixed depth -
the search depth - and return a "score" for the best position it
can get to at that depth.
With of the order of 20 moves able to be made at any position,
the number of moves which need to be evaluated for a search depth
of m is ~20m.
For reasonable m - good human players manage to
"look ahead" 10 or more moves - this number soon becomes
prohibitively large - beyond the capabilities of any modern
computer in any reasonable time.
The Alpha-Beta Algorithm
Application of the Alpha-Beta algorithm enables many "unprofitable"
branches in the tree of moves which need to be considered to be
cut off and not considered
further.
This dramatically improves the time taken to determine the best
move and has the effect that a much deeper search can be made
in the same time.
© John Morris, 1998