Next: 0.11.2 Alpha-Beta pruning
Up: 0.11 Game-Playing Algorithms
Previous: 0.11 Game-Playing Algorithms
Minimax is a game-playing algorithm which is used to search a game
tree. In games where opponents alternate taking turns which affect
a board position (chess, checkers, etc...), a given position can be
thought of as a node on a tree. All positions reachable from a given
position are, therefore, children nodes on the game tree. Minimax
recursively evaluates positions on a tree with the intent of
selecting the best move for a given player in a given position.
In order for a minimax routine to work a function that maps a
board position into a ``score'' is needed. In two-player games
often this evaluation function returns real values between -1 and 1.
A value of -1 means that one side has won outright, 0 indicates an
even position, and 1 is returned when the other side has achieved