Hubbry Logo
logo
Game complexity avatar
Game complexity
Community hub

Game complexity

logo
0 subscribers
Read side by side
Game complexity
View on Wikipedia
from Wikipedia

Combinatorial game theory measures game complexity in several ways:

  1. State-space complexity (the number of legal game positions from the initial position)
  2. Game tree size (total number of possible games)
  3. Decision complexity (number of leaf nodes in the smallest decision tree for initial position)
  4. Game-tree complexity (number of leaf nodes in the smallest full-width decision tree for initial position)
  5. Computational complexity (asymptotic difficulty of a game as it grows arbitrarily large)

These measures involve understanding the game positions, possible outcomes, and computational complexity of various game scenarios.

Measures of game complexity

[edit]

State-space complexity

[edit]

The state-space complexity of a game is the number of legal game positions reachable from the initial position of the game.[1]

When this is too hard to calculate, an upper bound can often be computed by also counting (some) illegal positions (positions that can never arise in the course of a game).

Game tree size

[edit]

The game tree size is the total number of possible games that can be played. This is the number of leaf nodes in the game tree rooted at the game's initial position.

The game tree is typically vastly larger than the state-space because the same positions can occur in many games by making moves in a different order (for example, in a tic-tac-toe game with two X and one O on the board, this position could have been reached in two different ways depending on where the first X was placed). An upper bound for the size of the game tree can sometimes be computed by simplifying the game in a way that only increases the size of the game tree (for example, by allowing illegal moves) until it becomes tractable.

For games where the number of moves is not limited (for example by the size of the board, or by a rule about repetition of position) the game tree is generally infinite.

Decision trees

[edit]

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

[edit]

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

[edit]

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.[1] 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 , where b is the game's average branching factor and d is the number of plies in an average game.

Computational complexity

[edit]

The computational complexity of a game describes the asymptotic difficulty of a game as it grows arbitrarily large, expressed in big O notation or as membership in a complexity class. This concept doesn't apply to particular games, but rather to games that have been generalized so they can be made arbitrarily large, typically by playing them on an n-by-n board. (From the point of view of computational complexity, a game on a fixed size of board is a finite problem that can be solved in O(1), for example by a look-up table from positions to the best move in each position.)

The asymptotic complexity is defined by the most efficient algorithm for solving the game (in terms of whatever computational resource one is considering). The most common complexity measure, computation time, is always lower-bounded by the logarithm of the asymptotic state-space complexity, since a solution algorithm must work for every possible state of the game. It will be upper-bounded by the complexity of any particular algorithm that works for the family of games. Similar remarks apply to the second-most commonly used complexity measure, the amount of space or computer memory used by the computation. It is not obvious that there is any lower bound on the space complexity for a typical game, because the algorithm need not store game states; however many games of interest are known to be PSPACE-hard, and it follows that their space complexity will be lower-bounded by the logarithm of the asymptotic state-space complexity as well (technically the bound is only a polynomial in this quantity; but it is usually known to be linear).

  • The depth-first minimax strategy will use computation time proportional to the game's tree-complexity (since it must explore the whole tree), and an amount of memory polynomial in the logarithm of the tree-complexity (since the algorithm must always store one node of the tree at each possible move-depth, and the number of nodes at the highest move-depth is precisely the tree-complexity).
  • Backward induction will use both memory and time proportional to the state-space complexity, as it must compute and record the correct move for each possible position.

Example: tic-tac-toe (noughts and crosses)

[edit]

For tic-tac-toe, a simple upper bound for the size of the state space is 39 = 19,683. (There are three states for each of the nine cells.) This count includes many illegal positions, such as a position with five crosses and no noughts, or a position in which both players have a row of three. A more careful count, removing these illegal positions, gives 5,478.[2][3] And when rotations and reflections of positions are considered identical, there are only 765 essentially different positions.

To bound the game tree, there are 9 possible initial moves, 8 possible responses, and so on, so that there are at most 9! or 362,880 total games. However, games may take less than 9 moves to resolve, and an exact enumeration gives 255,168 possible games. When rotations and reflections of positions are considered the same, there are only 26,830 possible games.

The computational complexity of tic-tac-toe depends on how it is generalized. A natural generalization is to m,n,k-games: played on an m by n board with winner being the first player to get k in a row. This game can be solved in DSPACE(mn) by searching the entire game tree. This places it in the important complexity class PSPACE; with more work, it can be shown to be PSPACE-complete.[4]

Complexities of some well-known games

[edit]

Due to the large size of game complexities, this table gives the ceiling of their logarithm to base 10. (In other words, the number of digits). All of the following numbers should be considered with caution: seemingly minor changes to the rules of a game can change the numbers (which are often rough estimates anyway) by tremendous factors, which might easily be much greater than the numbers shown.

Game Board size

(positions)

State-space complexity

(as log to base 10)

Game-tree complexity

(as log to base 10)

Average game length

(plies)

Branching factor Ref Complexity class of suitable generalized game
Tic-tac-toe 9 3 5 9 4 PSPACE-complete[5]
Sim 15 3 8 14 3.7 PSPACE-complete[6]
Pentominoes 64 12 18 10 75 [7][8] ?, but in PSPACE
Connect Four 42 12 (4,531,985,219,092) 21 36 4 [1][9][10] ?, but in PSPACE
Kalah[11] 14 13 18 50 [7] Generalization is unclear
Domineering (8 × 8) 64 15 27 30 8 [7] ?, but in PSPACE; in P for certain dimensions[12]
Congkak 14 15 33 [7]
English draughts (8x8) (checkers) 32 20 or 18 40 70 2.8 [1][13][14] EXPTIME-complete[15]
Awari[16] 12 12 32 60 3.5 [1] Generalization is unclear
Qubic 64 30 34 20 54.2 [1] PSPACE-complete[5]
Double dummy bridge[nb 1] (52) <17 <40 52 5.6 PSPACE-complete[17]
Fanorona 45 21 46 44 11 [18] ?, but in EXPTIME
Nine men's morris 24 10 50 50 10 [1] ?, but in EXPTIME
Tablut 81 27 [19]
International draughts (10x10) 50 30 54 90 4 [1] EXPTIME-complete[15]
Chinese checkers (2 sets) 121 23 180 [20] EXPTIME-complete[21]
Chinese checkers (6 sets) 121 78 600 [20] EXPTIME-complete[21]
Reversi (Othello) 64 28 58 58 10 [1] PSPACE-complete[22]
OnTop (2p base game) 72 88 62 31 23.77 [23]
Lines of Action 64 23 64 44 29 [24] ?, but in EXPTIME
Gomoku (15x15, freestyle) 225 105 70 30 210 [1] PSPACE-complete[5]
Hex (11x11) 121 57 98 50 96 [7] PSPACE-complete[5]
Chess 64 44 123 70 35 [25] EXPTIME-complete (without 50-move drawing rule)[26]
Bejeweled and Candy Crush (8x8) 64 <50 70 [27] NP-hard
GIPF 37 25 132 90 29.3 [28]
Connect6 361 172 140 30 46000 [29] PSPACE-complete[30]
Backgammon 28 20 144 55 250 [31] EXPTIME-Hard (for the real life setting where the opponent's strategy and dice rolls are unknown)[32]
Xiangqi 90 40 150 95 38 [1][33][34] ?, believed to be EXPTIME-complete
Abalone 61 25 154 87 60 [35][36] PSPACE-hard, and in EXPTIME
Havannah 271 127 157 66 240 [7][37] PSPACE-complete[38]
Twixt 572 140 159 60 452 [39]
Janggi 90 44 160 100 40 [34] ?, believed to be EXPTIME-complete
Quoridor 81 42 162 91 60 [40] ?, but in PSPACE
Carcassonne (2p base game) 72 >40 195 71 55 [41] Generalization is unclear
Amazons (10x10) 100 40 212 84 374 or 299[42] [43][44] PSPACE-complete[45]
Shogi 81 71 226 115 92 [33][46] EXPTIME-complete[47]
Thurn and Taxis (2 player) 33 66 240 56 879 [48]
Go (19x19) 361 170 505 211 250 [1][49][50]

[51]

EXPTIME-complete (without the superko rule)[52]
Arimaa 64 43 402 92 17281 [53][54][55] ?, but in EXPTIME
Stratego 92 115 535 381 21.739 [56]
Infinite chess infinite infinite infinite infinite infinite [57] Unknown, but mate-in-n is decidable[58]
Magic: The Gathering [59] AH-hard[60]
Wordle 5 4.113 (12,972) 6 [61] NP-hard, unknown if PSPACE-complete with parametization

Notes

[edit]

References

[edit]

See also

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Game complexity

View on Grokipedia
from Grokipedia
Game complexity is the study of the computational resources required to determine optimal strategies, winning outcomes, or other decision problems in combinatorial games, which are two-player, perfect-information games without elements of chance or hidden information.[1] These games, such as Nim, Chess, and Go, are analyzed under rules like normal play (where the last player to move wins) or misère play (where the last player loses), and their complexity often falls into standard computational classes like P, NP-complete, PSPACE-complete, or EXPTIME-complete.[1] The field draws from combinatorial game theory (CGT), which provides tools like Sprague-Grundy theorem for impartial games (where both players have identical moves) and surreal numbers for valuing positions in partizan games (with asymmetric moves).[1] In CGT, the complexity of a game is typically measured by the time or space needed to solve its game tree, which can grow exponentially with board size or game length.[1] For impartial games, the Sprague-Grundy theorem assigns a nimber (Grundy number) to each position, reducing the problem to Nim-heap equivalents solvable via XOR operations, though computing these values can still be hard for complex rules.[1] Partizan games require more advanced analysis, often using recursive definitions of game values as {left options | right options}, leading to challenges in automation and evaluation.[1] Notable results highlight the hardness of many classic games: for instance, generalized Chess on an n×n board is EXPTIME-complete, meaning it requires exponential time in the worst case, while connection games like Hex are PSPACE-complete, solvable in polynomial space but potentially exponential time.[1] Puzzle variants, such as single-player games like Sudoku or Minesweeper, often land in NP-complete, where verifying a solution is efficient but finding one is hard.[1] These classifications inform AI development, algorithm design, and theoretical bounds, with ongoing research exploring quantum-inspired variants and approximations for intractable cases.[1][2]

Measures of Game Complexity

State-Space Complexity

State-space complexity refers to the total number of distinct legal positions or configurations that can be reached in a game from its initial state, often denoted as |S| to represent the cardinality of the state space.[3] This measure captures the breadth of possible game states, excluding duplicates or unreachable configurations due to game rules. The concept was introduced in the context of combinatorial game theory by Claude Shannon in his seminal 1950 analysis of chess, where he estimated the state-space complexity to highlight the challenges of computational simulation.[4] Shannon's work laid the foundation for evaluating game scale in artificial intelligence and theoretical computer science. For board games like chess, state-space complexity is typically calculated through combinatorial enumeration, approximating the product of possible placements for each piece type while subtracting illegal positions (e.g., those violating rules like pawn promotion or king exposure).[3] In Shannon's chess estimation, this yielded roughly 104310^{43} positions, derived from arrangements of up to 32 pieces on 64 squares, adjusted for symmetries and constraints such as castling rights.[4] Exact counts often require sophisticated algorithms to enumerate valid states, as naive products overestimate due to rule-based invalidations. This metric is crucial as it quantifies the "breadth" of the game world, serving as a prerequisite for assessing search spaces in AI solvers, where exhaustive exploration becomes infeasible beyond small |S|.[3] A larger state space generally implies a potentially expanded game tree, though the latter accounts for sequential paths rather than unique positions alone. For rough estimations in games with average branching factor bb and maximum depth dd, |S| is sometimes approximated as bdb^d, but precise enumeration is preferred when computationally viable to avoid under- or overestimation.[4]

Branching Factor

The branching factor, denoted as $ b $, represents the average number of legal moves available from any given position in a game, serving as a key metric for assessing the breadth of the search space in game trees.[5] In formal terms, it is calculated as the total number of edges in the game tree divided by the total number of non-leaf nodes, where edges correspond to legal transitions between positions.[6] This distinguishes the effective branching factor, which counts only valid legal moves under the game's rules, from a raw branching factor that might consider all conceivable actions without constraints, though the former is standard in game analysis due to its relevance to actual play.[5] For instance, in chess, Claude Shannon estimated the average branching factor at approximately 30 legal moves per position, drawing from empirical data on typical games.[7] This figure, sometimes cited as 30–35 to account for variations, underscores the rapid expansion of possibilities in complex games.[5] Branching factors vary across a game's phases: the initial branching factor is often higher due to more open positions and piece mobility, the average reflects overall play, and the terminal branching factor decreases near endgame as fewer moves remain viable.[8] These variations contribute to the exponential growth of the game tree, where the number of positions at depth $ d $ scales roughly as $ b^d $, amplifying search challenges in deeper explorations.[9] The branching factor is a critical parameter in algorithms like minimax search, where the time complexity is $ O(b^d) $, with $ d $ as the search depth, highlighting the computational effort required for evaluating moves.[10] This metric, introduced in early AI literature during the 1950s, enabled foundational analyses of game solvability.[7] However, it assumes a uniform branching factor across the tree, an idealization that rarely holds in practice, as actual values fluctuate by position, game stage, and rules, potentially leading to over- or underestimations of complexity.[5]

Game-Tree Size

In combinatorial game theory and artificial intelligence, the game-tree size refers to the total number of nodes in the full game tree, which encompasses all possible sequences of moves from the initial position to terminal states in a finite, perfect-information game. This measure captures the exhaustive structure of decision paths, where each node represents a position after a sequence of moves, and the tree branches according to legal actions available to players. For finite games without cycles, the game tree is acyclic, and its size is exact; however, approximations are often used for practical estimation, such as bdb^d for the number of leaf nodes, where bb is the average branching factor and dd is the maximum depth (or average game length in plies).[3][11] Unlike state-space complexity, which counts the number of unique positions regardless of how they are reached, game-tree size accounts for all paths through the tree, including duplicates arising from transpositions—situations where different move sequences lead to the same board position. This distinction arises because the game tree models the sequential nature of play, preserving the order of moves, whereas the state space abstracts away path history to focus on positional configurations. As a result, game-tree size can be exponentially larger than the state space due to these redundant paths, emphasizing the combinatorial explosion of possible playouts rather than just distinct configurations.[11][12] The size of the game tree can be computed exactly for small games but is typically approximated for larger ones assuming a uniform branching factor. For a uniform tree of depth dd, the total number of nodes is given by the geometric series:
∑k=0dbk=bd+1−1b−1 \sum_{k=0}^{d} b^k = \frac{b^{d+1} - 1}{b - 1}
This formula provides the full tree volume, including internal and leaf nodes; the leaf nodes alone, representing complete games, approximate to bdb^d. A seminal example is chess, where Claude Shannon estimated the game-tree size (number of possible games) at approximately 1012010^{120}, known as the Shannon number, based on an average branching factor of 30 and a typical game length of 40 moves per player. This approximation connects directly to the branching factor, as higher bb or dd dramatically increases the size.[13][14] In theoretical analyses of perfect-information games, game-tree size serves as a key metric for the "volume" of decision paths, quantifying the scale of exhaustive search required for perfect play and highlighting the infeasibility of brute-force solving for complex games. It underscores the challenges in adversarial search algorithms like minimax, where exploring the full tree becomes computationally prohibitive. The concept gained prominence in AI research during the 1970s, as researchers evaluated the feasibility of game-solving programs amid growing computational power, influencing developments in pruning techniques and heuristic search to manage this vast space.[11][15]

Computational Complexity

Computational complexity in game theory refers to the computational resources, specifically time and space, required to determine an optimal strategy for a game, including computing the game's value under perfect play and the corresponding moves from any position. This analysis classifies the problem of solving a game within standard complexity classes, such as PSPACE or EXPTIME, based on the input size (e.g., board dimensions). For trivial games with a fixed, small number of positions, such as those solvable by exhaustive enumeration in constant time, the complexity is O(1)O(1). In contrast, many finite, perfect-information games without chance elements are EXPTIME-complete, requiring exponential time in the worst case relative to the input size.[16] A landmark classification is the proof that generalized chess on an n×nn \times n board is EXPTIME-complete, implying that computing a perfect strategy demands time at least exponential in nn.[17] Retrograde analysis, a backward induction method commonly used to solve endgames by propagating values from terminal positions, has a time complexity of O(∣S∣⋅b)O(|S| \cdot b), where ∣S∣|S| denotes the number of reachable states and bb the average branching factor; since ∣S∣|S| grows exponentially with board size, the overall complexity remains exponential. Space complexity in such analyses is typically O(∣S∣)O(|S|), directly tied to storing values for each state, though optimizations like bit-packing can reduce this. Briefly, this space requirement scales with the underlying state-space size, underscoring the memory challenges in large games. Key factors influencing computational complexity include the choice of search strategy and memory management techniques. Depth-first search algorithms, such as minimax, explore the game tree recursively and achieve a time complexity of O(bd)O(b^d), where bb is the effective branching factor and dd the maximum depth to terminal positions; this contrasts with breadth-first search, which demands O(bd)O(b^d) space for storing all nodes at the frontier, rendering it infeasible for deep trees. Transposition tables address redundancies by hashing positions to store and reuse previously computed values, potentially reducing both time and space by avoiding recomputation of equivalent subtrees, with space usage bounded by the table size (often a fraction of ∣S∣|S| via hashing).[10] These complexities explain why most non-trivial games, including chess, remain unsolved despite advances in hardware: exhaustive evaluation of the game tree would require approximately 1012010^{120} operations, exceeding feasible computational limits even with optimizations like alpha-beta pruning.[7] Parallel computing has provided practical speedups, enabling distributed evaluation of subtrees across multiple processors and reducing wall-clock time for partial solutions, as demonstrated in scalable algorithms for game-tree search. However, such parallelism yields at most polynomial speedups and does not alter the fundamental exponential theoretical lower bounds for classes like EXPTIME.[18]

Decision Tree Measures

Decision Complexity

Decision complexity measures the minimal computational effort required to determine the optimal outcome from the initial position in a game under perfect play by both players. It is defined as the number of leaf nodes in the smallest decision tree that establishes the value (win, loss, or draw) of the starting position, representing only the essential evaluations needed after applying optimal pruning techniques. This metric is substantially smaller than the full game-tree size, as it eliminates irrelevant branches that do not influence the final decision.[11] The concept was introduced in the early 1990s to differentiate the resources for optimal decision-making from those for exhaustive exploration, highlighting how strategic insights reduce search demands in two-player zero-sum games.[19] Pruning in this tree relies on game rules, such as terminal conditions for wins, losses, or draws, to cut off subtrees where bounds on possible outcomes exceed or undercut the current best, ensuring focus on decision-relevant paths. In practice, alpha-beta pruning approximates this structure by maintaining lower (alpha) and upper (beta) bounds during minimax search, dynamically discarding branches that cannot improve the result.[20] Calculating decision complexity exactly involves constructing the minimal proof tree, often via dynamic programming methods like retrograde analysis, which evaluates positions backward from terminals for small games such as Connect-Four or Awari. For larger games, approximations assume perfect move ordering in alpha-beta search, yielding a time complexity of roughly $ b^{d/2} $, where $ b $ is the average branching factor and $ d $ is the effective depth to a decision; this provides a theoretical lower bound on evaluations needed.[11][20] In AI applications, decision complexity underpins the efficiency of game-playing agents, where static evaluation functions approximate leaf values in the pruned tree to enable deeper searches within computational limits, balancing accuracy against resource constraints in algorithms like minimax with alpha-beta. This measure informs the scalability of perfect-information game solvers and guides heuristic developments for complex domains.[11]

Game-Tree Complexity

Game-tree complexity measures the scale of the search space in a game under the assumption that both players pursue optimal strategies, focusing on the effective number of nodes in the minimax search tree rather than all possible sequences of moves. This concept arises in the context of two-player zero-sum games, where the minimax algorithm evaluates positions by maximizing one player's score while assuming the opponent minimizes it, effectively pruning irrelevant branches to determine the value of a position. The theoretical foundation stems from John von Neumann's minimax theorem, which proves that in finite two-player zero-sum games with perfect information, there exists a value of the game and optimal strategies for both players, enabling the construction of such decision trees.[21] In a naive minimax search without optimizations, the game tree size grows exponentially as $ b^d $, where $ b $ is the average branching factor and $ d $ is the depth in plies (half-moves). However, alpha-beta pruning, which eliminates branches that cannot influence the final decision, significantly reduces this under optimal move ordering. Analysis shows that with perfect ordering, the number of nodes examined approximates $ b^{\lceil d/2 \rceil} + b^{\lfloor d/2 \rfloor} - 1 $; for typical cases with good but imperfect ordering, the effective complexity is bounded by $ O(b^{3d/4}) $, providing a substantial reduction compared to the unpruned tree while still capturing optimal play.[22] This measure is particularly suited to games like chess, where Claude Shannon estimated the unpruned game-tree complexity at approximately $ 10^{120} $ for a full game, but pruning makes deeper searches feasible in practice.[14] The approach inherently handles two-player zero-sum scenarios with perfect information, where each decision anticipates the opponent's best response. Transposition tables further refine the tree by detecting and merging equivalent positions reached via different move sequences, avoiding redundant evaluations and lowering the effective node count.[22] Limitations include its reliance on perfect information; in imperfect-information games like poker, the complexity escalates due to the need to average over hidden states and information sets, often requiring alternative methods beyond standard minimax trees.[14]

Examples of Game Complexity

Tic-Tac-Toe Analysis

Tic-tac-toe, also known as noughts and crosses, is a two-player abstract strategy game played on a 3×3 grid. Players alternate turns placing their distinct symbols—typically X for the first player and O for the second—in empty cells, with the goal of forming an unbroken line of three symbols horizontally, vertically, or diagonally. The game ends in a win for the player achieving this, a loss for the opponent, or a draw if the board fills without a winner; it is finite, impartial, and features perfect information with no element of chance. As a solved game, its outcome under optimal play is predetermined, providing a foundational example for studying game complexity.[23] The state-space complexity of tic-tac-toe measures the number of distinct legal board positions reachable from the start, which totals 5,478 distinct legal board positions. When accounting for symmetries like rotations and reflections, this reduces to 765 unique positions. This figure excludes invalid configurations, such as those with unequal numbers of symbols beyond one or multiple winners. The average branching factor, the mean number of legal moves available per position across the game, is approximately 5, reflecting the decreasing options as the board fills (starting at 9 and dropping to around 4 by mid-game). The full game-tree size, representing the total number of possible play sequences or leaf nodes, is 255,168, capturing all valid paths to terminal states. Decision complexity, which evaluates the reduced tree after applying symmetries and basic pruning to eliminate redundant or invalid branches, yields about 26,830 nodes essential for determining optimal decisions.[24][25][26][27] Retrograde analysis solves tic-tac-toe by starting from terminal positions and propagating outcomes backward: wins are positions from which any move leads to a loss for the opponent, losses are those where all moves allow an opponent win, and draws are the remainder. This backward induction reveals that perfect play forces a draw, as the first player cannot secure a win against optimal responses. A simplified game tree diagram illustrates this, with the root node branching to three symmetry classes (center, corner, edge), each leading to subtrees that converge on drawing lines under best play. Tic-tac-toe was solved by hand in the 19th century through manual enumeration of all possibilities, confirming the draw outcome long before computational aids. It became one of the earliest games implemented on computers in the 1950s, with A. S. Douglas's OXO program in 1952 demonstrating automated play on the EDSAC machine, marking a milestone in AI and game-solving history.[28][29]

Complexities of Well-Known Games

The complexities of well-known combinatorial games span orders of magnitude, reflecting differences in board size, rules, and move options that impact computational solvability. State-space complexity quantifies reachable positions, branching factor the average moves per position, and game-tree size the total possible playouts, with estimates serving as proxies for search effort required. These metrics, derived from combinatorial bounds and simulations, reveal why some games like checkers and Othello have been solved while others like chess and Go resist full analysis.[11]
GameState-Space ComplexityBranching FactorGame-Tree SizeComputational Status
Chess104610^{46}351012010^{120}Unsolved
Checkers102010^{20}8103110^{31}Solved (draw, 2007)
Go1017010^{170}2501036010^{360}Unsolved
Othello102810^{28}10105810^{58}Solved (draw, 2023)
These figures represent standard approximations, with state-space often bounded by 3b3^b (where bb is board cells) adjusted for legality, branching factors averaged over game phases, and game-tree sizes via bdb^d ( dd as average depth).[11] Checkers' solution, achieved after nearly two decades of computation, confirmed perfect play yields a draw.[30] Othello's recent proof similarly established a draw under optimal strategy, marking it as the most complex board game fully solved to date with its vast state space.[31] Complexity escalates exponentially with board dimensions, as seen in variants like n×n tic-tac-toe, where state-space approximates 3n23^{n^2} due to per-cell occupancy, rendering even modest enlargements intractable.[11] Such trends emphasize how modest rule expansions amplify search spaces, informing AI development in these domains.

Modern Games and AI Implications

While traditional combinatorial game complexity focuses on perfect-information games, modern AI research in game solving extends to imperfect-information settings such as heads-up no-limit Texas hold'em poker, which features an estimated 1016010^{160} private states due to hidden cards, chance elements in dealing, and betting strategies.[32] This game was computationally solved in 2017 using counterfactual regret minimization (CFR), an iterative algorithm that approximates Nash equilibria by minimizing regret over billions of simulated hands, enabling the AI Libratus to outperform top human professionals. Video games, particularly real-time strategy (RTS) titles, introduce even greater challenges through partial observability, continuous time, and multi-unit control, rendering classical exhaustive search infeasible. StarCraft II exemplifies this, with an approximate state space of 1016810^{168} configurations arising from unit positions, resource allocations, and map interactions, alongside a branching factor of around 10510^5 possible actions per decision cycle. DeepMind's AlphaStar, unveiled in 2019, achieved grandmaster-level performance by combining reinforcement learning with a transformer-based neural architecture that processes raw screen pixels and issues multi-unit commands, partially mastering the game through self-play in a league of evolving agents. Such systems rely on approximations like Monte Carlo Tree Search (MCTS), which samples promising paths in the vast tree rather than exploring all branches. Advancements in artificial intelligence have profoundly impacted how game complexity is navigated, particularly through deep learning techniques that prune ineffective exploration. In Go, a perfect-information game with a state-space complexity of approximately 1017010^{170} legal positions, AlphaGo's 2016 victory over world champion Lee Sedol demonstrated how policy and value neural networks integrated with MCTS could evaluate positions and guide search, reducing the effective complexity from intractable to solvable within hardware constraints. This approach effectively compresses the search space by prioritizing high-value moves, achieving superhuman play with far fewer simulations than brute-force methods would require. To adapt traditional metrics like branching factor to these modern contexts, researchers increasingly employ empirical simulations that estimate effective branching through sampled trajectories, avoiding the need for exact enumeration in hyper-large spaces. In the 2020s, neural enhancements to MCTS—such as those incorporating learned priors from deep reinforcement learning—have further advanced this, enabling scalable planning in domains like multi-agent environments by dynamically adjusting exploration based on neural predictions. However, persistent challenges arise from multi-agent dynamics, where opponents' strategies introduce adversarial uncertainty, and real-time constraints demand decisions in milliseconds, amplifying complexity beyond static classical measures and necessitating hybrid AI architectures for practical viability.

Theoretical and Practical Considerations

Factors Influencing Complexity

Rule variations significantly affect game complexity by altering the structure of the game tree and state space. In alternating-turn games, players move sequentially, allowing for predictable branching in the decision tree, whereas simultaneous-move games require players to select actions concurrently, leading to a product of action spaces at each turn and exponentially larger joint decision spaces. For instance, algorithms for computing optimal strategies in two-player simultaneous-move games must account for correlated equilibria or Nash equilibria, increasing computational demands compared to minimax search in alternating setups.[33] The introduction of chance elements, such as random events or dice rolls, further inflates the effective state space by incorporating probabilistic transitions, transforming deterministic games into stochastic ones where chance nodes expand the exploration requirements for value iteration or policy computation.[34] Board size and scaling parameters drive exponential growth in complexity measures, as larger dimensions multiply the number of possible configurations and moves. In chess variants, increasing the board from 8x8 to nxn results in state-space complexity that grows exponentially with n, due to the combinatorial explosion of piece placements and legal positions. Similarly, in the n-queens puzzle, the number of potential states scales approximately as $ n! $, reflecting the factorial growth in permutation-based placements needed to avoid attacks, which underscores the rapid escalation in search space for larger n.[35] Symmetries inherent in game boards or rules enable reductions in complexity through group theory, where equivalent states are quotiented to eliminate redundancies. Rotational and reflectional symmetries, for example, form a symmetry group that can halve or more the counted states in symmetric games like tic-tac-toe by identifying isomorphic positions under transformations. This approach, applied in general game playing, uses automorphism detection to prune the game tree, directly lowering the effective state-space complexity without altering the game's outcomes.[36] Player asymmetry, particularly in non-zero-sum games, introduces additional layers of complexity by decoupling individual utilities from a single zero-sum payoff, requiring computation of correlated or mixed Nash equilibria rather than simple minimax values. Unlike zero-sum settings where one player's gain equals the other's loss, non-zero-sum structures allow for cooperative or competitive alignments that expand the solution space, with finding equilibria proven PPAD-hard even for concise representations.[37] Environmental factors, such as time limits in practical play, contrast with theoretical analyses assuming infinite computation, forcing heuristic approximations that bound search depth and increase vulnerability to suboptimal decisions under pressure. In real-time scenarios, players or algorithms shift to shallower tree explorations, amplifying the impact of branching factors on effective complexity compared to exhaustive theoretical solving.[38]

Methods for Reducing Complexity

One key approach to reducing the effective complexity of game trees involves search algorithms that prune unnecessary branches while preserving optimality. Alpha-beta pruning, an enhancement to the minimax algorithm, eliminates subtrees that cannot influence the final decision by maintaining lower (alpha) and upper (beta) bounds on the minimax value during the search.[20] This technique can reduce the time complexity from the full minimax's O(b^d), where b is the branching factor and d is the depth, to approximately O(b^{d/2}) in the best case, assuming good move ordering.[20] Iterative deepening, another search strategy, combines the space efficiency of depth-first search with the completeness of breadth-first search by performing successive depth-limited searches, increasing the depth limit incrementally until the desired horizon is reached.[39] This method mitigates the overhead of uniform-depth searches and adapts well to time constraints in real-time game playing.[39] Heuristic methods further alleviate computational demands by approximating values at internal nodes, allowing earlier cutoffs. Evaluation functions provide static estimates of a position's desirability, typically based on material balance, positional features, and king safety in games like chess, enabling the search to terminate before reaching leaves and focus on promising branches. Transposition tables address repeated state evaluations across different search paths by storing and reusing previously computed values for identical positions, often using Zobrist hashing to map board states to unique keys for efficient lookup and collision avoidance.[40] This reuse can dramatically cut redundant computations, especially in games with high transpositions like chess, where the same position may arise via multiple move sequences. Parallelization techniques distribute the search workload across multiple processors or machines, particularly effective for building exhaustive endgame databases. In the case of checkers, solving the full game required constructing databases for all positions with 10 or fewer pieces, totaling about 13 trillion positions, which demanded distributed computing on hundreds of processors and approximately 148 GB of storage for the compressed tables. This approach enabled backward induction from terminal positions to determine perfect play outcomes, confirming checkers as a draw under optimal conditions.[41] Exploiting symmetries in game states reduces the search space by identifying and merging equivalent positions under transformations like rotations or reflections. Canonical forms represent states in a standardized way, eliminating isomorphic duplicates; for instance, in general game playing, automated detection of symmetries via group theory or constraint solving can prune up to 90% of equivalent subtrees in symmetric boards. This method is particularly valuable in abstract strategy games, where board symmetries lead to redundant explorations. More recent advancements leverage reinforcement learning to approximate optimal policies, bypassing exhaustive search in high-complexity games. Post-2010 methods, such as those combining deep neural networks with Monte Carlo tree search, learn value and policy functions from self-play, achieving superhuman performance in Go by focusing on high-probability moves rather than full enumeration. These approximations scale to games with branching factors exceeding 200, like Go, by prioritizing informative simulations over complete trees.

Open Problems in Game Complexity

One of the central open problems in game complexity is determining the exact game-tree size for major board games such as chess and Go, where current estimates rely on approximations like Claude Shannon's lower bound of approximately 10^{120} possible games for chess, but precise counts remain computationally infeasible and theoretically unresolved.[42] Similarly, Go's game-tree complexity is estimated at around 10^{360}, vastly exceeding chess, yet exact enumeration eludes exact calculation due to the exponential growth in branching factors.[43] These uncertainties highlight the practical limits of exhaustive search methods, with implications for fully solving these games to find optimal strategies. Generalizing complexity measures to broader game classes presents further challenges, particularly for multiplayer games beyond two players and stochastic variants incorporating chance elements. While many two-player perfect-information games like Go are proven EXPTIME-complete, multiplayer noncooperative games of incomplete information exhibit lower bounds suggesting at least EXPTIME-hardness, but exact classifications for specific multiplayer settings remain open.[44] For stochastic games, the problem of computing values in simple stochastic games—two-player zero-sum games with probabilistic transitions—has unknown polynomial-time solvability, with the best algorithms still requiring subexponential but superpolynomial time, leaving its precise placement in complexity classes like PPAD or beyond unresolved.[34] The potential role of quantum computing in addressing game complexity introduces speculative yet promising frontiers, with recent work demonstrating algorithmic quantum speedups for solving zero-sum games through improved dynamic programming techniques that achieve near-optimal Nash equilibria faster than classical methods.[45] Post-2020 research has shown quadratic speedups for quantum zero-sum games using multiplicative weight updates, hinting at exponential advantages for game-tree search in quantum settings, though fault-tolerant quantum hardware remains a barrier to practical application.[46] These developments raise open questions about whether quantum algorithms can reduce effective complexity for EXPTIME-complete games like Go. Measurement gaps persist in standardizing "effective" complexity, especially integrating AI-driven approximations that prune search spaces without exhaustive enumeration. Traditional metrics like game-tree size overlook AI heuristics that achieve superhuman play in unsolved games, prompting calls for new benchmarks that quantify human-AI hybrid complexity, yet no unified framework exists as of 2025.[47] Infinite games, such as infinite chess on an unbounded board, pose unique challenges; while the mate-in-n problem is decidable via ordinal analysis up to transfinite lengths like ω^4, determining the full decision complexity for arbitrary winning strategies remains open, potentially linking to higher recursion-theoretic degrees.[48] As of 2025, neither chess nor Go has been theoretically solved to identify perfect play, with ongoing AI benchmarks like those from AlphaZero variants providing strong empirical strategies but no guarantees of optimality, underscoring persistent frontiers in computational game theory.[34]

References

  1. [PDF] Algorithmic Combinatorial Game Theory - Erik Demaine
  2. [PDF] Solving games - CMU School of Computer Science
  3. XXII. Programming a computer for playing chess
  4. Branching Factor - Chessprogramming wiki
  5. [PDF] Branching factor - Model AI Assignments
  6. [PDF] Estimates for the Branching Factors of Atari Games - NSF PAR
  7. Programming a Computer for Playing Chess
  8. Calculation of branching factor - TalkChess.com
  9. 3.2 Minimax | Introduction to Artificial Intelligence
  10. Minimax Algorithm in Game Theory | Set 1 (Introduction)
  11. [PDF] Searching for Solutions in Games and Artificial Intelligence - Free
  12. [PDF] Depth in Strategic Games
  13. Game Tree Evaluation - UC Irvine
  14. [PDF] XXII. Programming a Computer for Playing Chess1
  15. [PDF] Lecture 1 1 Introduction 2 Game Trees and the Value of a Game
  16. Computational Complexity Theory
  17. Computing a perfect strategy for n × n chess requires time ...
  18. Limits of quantum computation in solving chess
  19. [PDF] SCALABLE ALGORITHMS FOR PARALLEL TREE SEARCH
  20. Which games will survive? - Tilburg University Research Portal
  21. An analysis of alpha-beta pruning - ScienceDirect.com
  22. [PDF] John von Neumann's Conception of the Minimax Theorem
  23. [PDF] An Analysis of Alpha-Beta Priming'
  24. Tic-Tac-Toe - GamesCrafters :: Games
  25. What are the symmetries of a tic tac toe game board?
  26. [PDF] Cooperative and Adaptive Algorithms
  27. Canonical and Reduced Game Trees for Tic-Tac-Toe - Justin Skycak
  28. How to find the complexity of decision trees in Tic Tac Toe by hand?
  29. [PDF] Tic-tac-toe and retrograde analysis - Alain Brobecker
  30. First videogame | Guinness World Records
  31. Checkers Is Solved - Science
  32. [2310.19387] Othello is Solved - arXiv
  33. [PDF] Measuring the Size of Large No-Limit Poker Games
  34. Algorithms for computing strategies in two-player simultaneous ...
  35. [PDF] The Complexity of Simple Stochastic Games - arXiv
  36. [PDF] A Note on the Computational Complexity of Selfmate and ... - arXiv
  37. [PDF] Symmetry Detection in General Game Playing
  38. [PDF] Nash Equilibrium Solving for General Non-Zero-Sum Games from ...
  39. Complexity, Attention, and Choice in Games Under Time Constraints
  40. Depth-first iterative-deepening: An optimal admissible tree search
  41. Zobrist Hashing - Chessprogramming wiki
  42. State Space Complexity of Chess
  43. Complexity of Go, Chess and Checkers games - ResearchGate
  44. Lower bounds for multiplayer noncooperative games of incomplete ...
  45. [PDF] Quantum Speedups for Zero-Sum Games via Improved Dynamic ...
  46. A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero ...
  47. Important future directions in computational game theory - Medium
  48. [1201.5597] The mate-in-n problem of infinite chess is decidable
User Avatar
No comments yet.