Editing Game complexity (section)

=== Decision trees ===
A [[decision tree]] is a subtree of the game tree, with each position labelled "player A wins", "player B wins", or "draw" if that position can be proved to have that value (assuming best play by both sides) by examining only other positions in the graph. Terminal positions can be labelled directly—with player A to move, a position can be labelled "player A wins" if any successor position is a win for A; "player B wins" if all successor positions are wins for B; or "draw" if all successor positions are either drawn or wins for B. (With player B to move, corresponding positions are marked similarly.)

The following two methods of measuring game complexity use decision trees:

==== Decision complexity ====
''Decision complexity'' of a game is the number of leaf nodes in the smallest decision tree that establishes the value of the initial position.

==== Game-tree complexity ====
''Game-tree complexity'' of a game is the number of leaf nodes in the smallest ''full-width'' decision tree that establishes the value of the initial position.<ref name="Allis1994"/> A full-width tree includes all nodes at each depth. This is an estimate of the number of positions one would have to evaluate in a [[minimax]] search to determine the value of the initial position.

It is hard even to estimate the game-tree complexity, but for some games an approximation can be given by <math>GTC \geq b^d</math>, where {{Mvar|b}} is the game's average [[branching factor]] and ''{{Mvar|d}}'' is the number of [[Ply (chess)|plies]] in an average game.