Lecture 27
A strategy when playing so called
zero-sum two person games, is to do a depth first traversal of an implicit game
tree. We saw how game trees can be used to play Tic-Tac-Toe using the minimax
algorithm. Searching the entire game tree is usually not feasible. We saw two
heuristics that allow an abbreviated search.
Alpha-beta pruning is a method
of deciding that there is no point traversing the next child of the current
node, because the current child has returned a result that can't possibly be
bettered.
Transposition tables
are a map that are used to store the value of Tic-Tac-Toe boards that have
already been seen. We discussed implementing this map using a hash table.
Posted: Fri - March 18, 2005 at 09:51 PM