A variation can refer to a specific sequence of successive moves in a turn-based game, often used to specify a hypothetical future state of a game that is being played. Although the term is most commonly used in the context of
Chess
Chess is a board game for two players. It is an abstract strategy game that involves Perfect information, no hidden information and no elements of game of chance, chance. It is played on a square chessboard, board consisting of 64 squares arran ...
analysis, it has been applied to other games. It also is a useful term used when describing computer
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
-search algorithms (for example
minimax
Minimax (sometimes Minmax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy for ''minimizing'' the possible loss function, loss for a Worst-case scenari ...
) for playing games such as
Go[{{cite web , url=http://www.andromeda.com/people/ddyer/go/search.html, title=Searches, tree pruning and tree ordering in Go, date=21 December 2007] or
Chess
Chess is a board game for two players. It is an abstract strategy game that involves Perfect information, no hidden information and no elements of game of chance, chance. It is played on a square chessboard, board consisting of 64 squares arran ...
.
A variation can be any number of steps as long as each step would be legal if it were to be played. It is often as far ahead as a human or computer can calculate; or however long is necessary to reach a particular position of interest. It may also lead to a terminal state in the game, in which case the term "winning variation" or "losing variation" is sometimes used.
Principal variation
The principal variation refers to the particular variation that is the most advantageous to the current player, assuming each other player will respond with the move that best improves their own position. In other words, it is the "best" or "correct" line of play. In the context of
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...
-searching game
artificial intelligence
Artificial intelligence (AI) is the capability of computer, computational systems to perform tasks typically associated with human intelligence, such as learning, reasoning, problem-solving, perception, and decision-making. It is a field of re ...
– in which this term is most common – it may also refer to the sequence of moves that is currently ''believed'' to be the most advantageous, but is not guaranteed due to the technical limitations of the algorithm.
See also
*
Game tree
In the context of combinatorial game theory, a game tree is a graph representing all possible game states within a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe.
A game tree can be us ...
*
Backtracking
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...
*
Minimax
Minimax (sometimes Minmax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, combinatorial game theory, statistics, and philosophy for ''minimizing'' the possible loss function, loss for a Worst-case scenari ...
*
Negamax
Negamax search is a variant form of minimax search that relies on the Zero-sum (Game theory), zero-sum property of a two-player game.
This algorithm relies on the fact that to simplify the implementation of the minimax algorithm. More precisely, ...
*
Alpha-beta pruning Alphabeta or Alpha Beta may also refer to:
* Alphabeta, an Israeli musical group
* Alpha Beta, a former chain of Californian supermarkets
* The Greek alphabet, from ''Alpha'' (Αα) and ''Beta'' (Ββ), the first two letters
* Alpha and beta anome ...
*
Negascout
Principal variation search (sometimes equated with the practically identical NegaScout) is a negamax algorithm that can be faster than alpha–beta pruning. Like alpha–beta pruning, NegaScout is a directional search algorithm for computing the mi ...
References
Variations
Combinatorial game theory
Game artificial intelligence
Search algorithms
Computer chess
Trees (graph theory)