game tree
In plain wordsA branching diagram of every way a game could unfold: each point is a position, each branch a possible move, and the tips of the branches are wins, losses or draws.
A tree whose nodes represent game states and whose edges represent legal moves, with the root as the current position and the leaves as terminal positions labeled with outcomes or payoffs; in two-player games the levels alternate between players. Game trees are the substrate of minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best., alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep. and Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average.. Their size rules out exhaustive search for most interesting games — Claude Shannon estimated about 10^120 possible chess games, and Go's tree is far larger — so programs search a partial tree and estimate leaf values with an evaluation functionevaluation function, n.: In a game-playing program, a formula that looks at a board position and gives it a score saying how good it is, without playing the game out to the end. or a learned value functionvalue function, n.: An estimate of how promising a situation is for an AI agent, judged by the rewards it is likely to collect from that point on, the way a chess player sizes up a board.. Games with dice or hidden information add chance nodes and information sets; in game theory the game tree is called the extensive form.
Origin
John von Neumann and Oskar Morgenstern formalized games in extensive (tree) form in Theory of Games and Economic Behavior (1944), and Harold Kuhn refined the formalism in 1953. Claude Shannon's 1950 chess paper made searching the game tree the central technique of computer game playing.
Related
- minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best.
- alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep.
- Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average.
- evaluation functionevaluation function, n.: In a game-playing program, a formula that looks at a board position and gives it a score saying how good it is, without playing the game out to the end.
- combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers.
- AlphaGoAlphaGo, prop. n.: A DeepMind program that in 2016 beat Lee Sedol, one of the world's best players of the board game Go, a decade or more before many experts expected a computer to manage it.
Sources
- von Neumann, J. & Morgenstern, O. (1944). Theory of Games and Economic Behavior. Princeton University Press.
Mentioned in
Arthur SamuelArthur Samuel, prop. n.: An American IBM engineer whose checkers program improved by playing against itself, and whose 1959 paper helped make 'machine learning' the name of a field., combinatorial explosioncombinatorial explosion, n.: The way the number of possible combinations — moves, routes, schedules — grows so quickly as a problem gets bigger that checking them all becomes impossible, even for the fastest computers., Deep BlueDeep Blue, prop. n.: IBM's chess computer that beat world champion Garry Kasparov in 1997, the first time a machine defeated a reigning world champion in a match under standard tournament conditions., Garry KasparovGarry Kasparov, prop. n.: A Russian chess world champion whose 1997 loss to IBM's Deep Blue computer became the symbol of machines overtaking people, and who later championed humans and computers working together., minimaxminimax, n.: A way for a game-playing program to choose moves by assuming the opponent will always make their best reply, and picking the move whose worst-case outcome is best., Monte Carlo tree searchMonte Carlo tree search, n.: A way for a game-playing program to choose a move by simulating many possible continuations, focusing on the most promising lines, and picking the move that worked out best on average., multi-agent reinforcement learningmulti-agent reinforcement learning, n.: Reinforcement learning with several AI agents learning at once in a shared world, where each must adapt to the others — as teammates, rivals or both., state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal., alpha–beta pruningalpha–beta pruning, n.: A shortcut for game programs: tracking the best result each side is already sure of, it ignores lines of play that could only do worse, and when promising moves come first it searches about twice as deep., ChinookChinook, prop. n.: A checkers program from the University of Alberta that in 1994 became the first program crowned world champion in a contest against people, and in 2007 proved that perfect checkers always ends in a draw., counterfactual regret minimizationcounterfactual regret minimization, n.: A method for working out near-unbeatable strategies in games with hidden information, like poker, by repeatedly playing against itself and shifting each decision toward the moves it most regrets not making., evaluation functionevaluation function, n.: In a game-playing program, a formula that looks at a board position and gives it a score saying how good it is, without playing the game out to the end., general game playinggeneral game playing, n.: Building AI players that are handed the rules of a game they have never seen and must work out how to play it well on their own, with no game-specific help from their programmers., Samuel's checkers programSamuel's checkers program, prop. n.: A 1950s IBM program by Arthur Samuel that learned to play checkers better than its author, partly by playing against itself. It was among the first programs to learn, and its 1959 paper popularized the phrase 'machine learning'.