This essay is a detailed explanation of one of the most important data structures ever created for Game Artificial Intelligence. The minimax tree is at the heart of almost every board game program in existence.
The Minimax Game Tree is used for programming computers to play games in which there are two players taking turns to play moves. Physically, it is just a tree of all possible moves.
game trees
Game Trees: Alpha-Beta Search
We will set up a framework for playing a two-person game in which the two players alternate making moves.
The game can normally be represented as a tree where the nodes represent the current status of the game and the arcs represent the moves. The game tree consists of all possible moves for the current players starting at the root and all possible moves for the next player as the children of these nodes, and so forth, as far into the future of the game as desired. The leaves of the game tree represent terminal positions as one where the outcome of the game is clear (a win, a loss, a draw, a payoff). Each terminal position has a score. High scores are good. For example, we may associate 1 with a win, 0 with a draw and -1 with a loss.
The game can normally be represented as a tree where the nodes represent the current status of the game and the arcs represent the moves. The game tree consists of all possible moves for the current players starting at the root and all possible moves for the next player as the children of these nodes, and so forth, as far into the future of the game as desired. The leaves of the game tree represent terminal positions as one where the outcome of the game is clear (a win, a loss, a draw, a payoff). Each terminal position has a score. High scores are good. For example, we may associate 1 with a win, 0 with a draw and -1 with a loss.
Category: tutorial from http://www.cs.mcgill.ca
« previous1 next »
