Editing Game tree (section)

{{Short description|Combinatorial game theory concept to represent all possible game states}}
{{for|game tree as it is used in game theory (not combinatorial game theory)|Extensive-form game}}
[[Image:Tic-tac-toe-game-tree.svg|thumb|upright=1.35|The diagram shows the first two levels, or ''[[ply (game theory)|plies]]'', in the game tree for [[tic-tac-toe]]. The rotations and reflections of positions are equivalent, so the first player has three choices of move: in the center, at the edge, or in the corner. The second player has two choices for the reply if the first player played in the center, otherwise five choices. And so on.]]

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]], [[Draughts|checkers]], [[Go (board game)|Go]], and [[tic-tac-toe]].

A game tree can be used to measure the [[Game complexity|complexity of a game]], as it represents all the possible ways that the game can pan out. Due to the large game trees of [[Game complexity#Complexities of some well-known games|complex games]] such as chess, algorithms that are designed to play this class of games will use partial game trees, which makes computation feasible on modern computers. Various methods exist to solve game trees. If a complete game tree can be generated, a [[deterministic algorithm]], such as [[backward induction]] or [[retrograde analysis]] can be used. [[Randomized algorithm]]s and [[minmax]] algorithms such as [[Monte Carlo tree search|MCTS]] can be used in cases where a complete game tree is not feasible.