Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Game complexity
open-in-new
<p><a href="/facts/Combinatorial_game_theory/fF4l0om2">Combinatorial game theory</a> measures game complexity in several ways: </p> <ol><li>State-space complexity (the number of legal game positions from the initial position)</li> <li>Game tree size (total number of possible games)</li> <li>Decision complexity (number of leaf nodes in the smallest decision tree for initial position)</li> <li>Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position)</li> <li>Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large)</li></ol> <p>These measures involve understanding the game positions, possible outcomes, and <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity</a> of various game scenarios. </p>