Concept

Game complexity

Summary
Combinatorial game theory measures game complexity in several ways: #State-space complexity (the number of legal game positions from the initial position), #Game tree size (total number of possible games), #Decision complexity (number of leaf nodes in the smallest decision tree for initial position), #Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position), #Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large). These measures involve understanding game positions, possible outcomes, and computation required for various game scenarios. Measures of game complexity State-space complexity The state-space complexity of a game is the number of legal game positions reachable from the initial position of the game. When this is too hard to calculate, an upper bound can often be computed by also counting (some) illegal positions, meaning positions that can ne
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading