Minimax Search Algorithm
The standard algorithm for two-player perfect-information games such as chess, checkers or othello is minimax search with heuristic static evaluation.
Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss while maximizing the potential gain.
Minimax Explained
Discusses how search can be applied to logic games with full information. Game trees are described, as well as an algorithm that can search them. Pseudo code is given and optimisations like alpha-beta are explained.
Minimax Conclusion
In conclusion, let me put the algorithm into a stepped form:
Generate the game tree to depth d.
The final nodes should have a value assigned to them, denoting how close to a winning scenario they are.
Minimaxing assigns one player a positive value and the other a negative value.
minimax 1. an algorithm for determining the backed-up value of a node in a game tree from the values of child nodes one move below: if it is the player's move, the maximum of the values below is taken; if the opponent's move, the minimum.
Minimax. An algorithm to assign linear scaling coefficients for a set of numbers. The minimum and maximum of the set are found, and scaling factors selected so that these are mapped to desired minimum and maximum values. See also, Neural Networks.
The Minimax Game Tree. From AI Horizon. "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 function MINIMAX-VALUE goes through the whole game tree, all the way to the leaves,
to determine the backed-up value of a state.
1948 - Norbert Wiener's book Cybernetics describes how a chess program could be developed using a depth-limited minimax search with an evaluation function.
1950 - John von Neumann develops a chess program (on a bishopless 6x6 board) on the MANIAC I.
Alpha-beta pruning is a search algorithm that reduces the number of nodes that need to be evaluated in the search tree by the minimax algorithm. ... Look up Premise in Wiktionary, the free dictionary. ...
-and then 'backing-up' or 'minimaxing' from the terminal positions, won, lost, or drawn. But in practice, the full exploration of the resulting colossal 'move-tree' is out of the question.
For example, in computer chess, rather than computing the full minimax tree of all possible moves for the remainder of the game, a more limited tree of minimax possibilities is computed, with the tree being pruned at a certain number of moves, ...
John von Neumann introduced the minimax theorem, which is still used as a basis for game-playing programs.
1931
Vannevar Bush's mechanical differential analyzer (a mechanical analog computer) was able to solve differential equations.
Problem-solving through Search: forward and backward, state-space, blind, heuristic, problem-reduction, A, A*, AO*, minimax, constraint propagation, neural, stochastic, and evolutionary search algorithms, sample applications.
After the recovery teams have done their job we talk about solving such games with minimax and then alpha-beta search. We also discuss the dynamic programming approach, used most commonly for end-games.
 See also: Pruning, Neural network, Classification, Data mining, Percept
  
|
RSS
