= Game tree
A <game tree> is a rooted <tree> whose nodes are possible histories of play and whose edges are legal next actions. Internal nodes specify the acting player or a chance move; <terminal nodes> carry outcomes or <payoffs>. In an <extensive-form game>, <information sets> additionally say which decision histories the acting player can distinguish.
Distinct histories may reach the same board position, so a <game tree> can contain repeated states that a state <graph> would merge. For finite two-player <zero-sum games> with perfect information, <minimax search> propagates terminal values upward. <Chance nodes> require expectations instead of maximizing or minimizing their outcomes.
Back to article page
