next up previous contents index Search
Next: 0.11.2 Alpha-Beta pruning Up: 0.11 Game-Playing Algorithms Previous: 0.11 Game-Playing Algorithms

0.11.1 Minimax Search

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 victory.

Scott Gasch
1999-07-09