Game complexity

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 the game positions, possible outcomes, and computational complexity of 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. 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.

Complexities of some well-known games

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.

{| class="wikitable sortable sticky-header"

!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

|style="text-align:right;"|9

|style="text-align:right;"|3

|style="text-align:right;"|5

|style="text-align:right;"|9

|style="text-align:right;"|4

|style="text-align:right;"|

|PSPACE-complete

|Pentominoes

|style="text-align:right;"|64

|style="text-align:right;"|12

|style="text-align:right;"|18

|style="text-align:right;"|10

|style="text-align:right;"|75

|style="text-align:right;"|

| , but in PSPACE

|Connect Four

|style="text-align:right;"|42

|style="text-align:right;"|12 (4,531,985,219,092)

|style="text-align:right;"|21

|style="text-align:right;"|36

|style="text-align:right;"|4

|style="text-align:right;"|

| , but in PSPACE

|Kalah

|style="text-align:right;"|14

|style="text-align:right;"|13

|style="text-align:right;"|18

|style="text-align:right;"|

|style="text-align:right;"|50

|style="text-align:right;"|

|Congkak

|style="text-align:right;"|14

|style="text-align:right;"|15

|style="text-align:right;"|33

|style="text-align:right;"|

|English draughts (8x8) (checkers)

|style="text-align:right;"|32

|style="text-align:right;"|20 or 18

|style="text-align:right;"|40

|style="text-align:right;"|70

|style="text-align:right;"|2.8

|style="text-align:right;"|

|EXPTIME-complete

|Awari

|style="text-align:right;"|12

|style="text-align:right;"|32

|style="text-align:right;"|60

|style="text-align:right;"|3.5

|style="text-align:right;"|

|Fanorona

|style="text-align:right;"|45

|style="text-align:right;"|21

|style="text-align:right;"|46

|style="text-align:right;"|44

|style="text-align:right;"|11

|style="text-align:right;"|

| , but in EXPTIME

|Nine men's morris

|style="text-align:right;"|24

|style="text-align:right;"|10

|style="text-align:right;"|50

|style="text-align:right;"|10

|style="text-align:right;"|

|International draughts (10x10)

|style="text-align:right;"|50

|style="text-align:right;"|30

|style="text-align:right;"|54

|style="text-align:right;"|90

|style="text-align:right;"|4

|style="text-align:right;"|

|EXPTIME-complete

|Chinese checkers (6 sets)

|style="text-align:right;"|121

|style="text-align:right;"|78

|style="text-align:right;"|

|style="text-align:right;"|600

|style="text-align:right;"|

|OnTop (2p base game)

|style="text-align:right;"|72

|style="text-align:right;"|88

|style="text-align:right;"|62

|style="text-align:right;"|31

|style="text-align:right;"|23.77

|style="text-align:right;"|

|Lines of Action

|style="text-align:right;"|64

|style="text-align:right;"|23

|style="text-align:right;"|64

|style="text-align:right;"|44

|style="text-align:right;"|29

|style="text-align:right;"|

| , but in EXPTIME

|Gomoku (15x15, freestyle)

|style="text-align:right;"|225

|style="text-align:right;"|105

|style="text-align:right;"|70

|style="text-align:right;"|30

|style="text-align:right;"|210

|style="text-align:right;"|

|Chess

|style="text-align:right;"|64

|style="text-align:right;"|44

|style="text-align:right;"|123

|style="text-align:right;"|70

|style="text-align:right;"|35

|style="text-align:right;"|

|EXPTIME-complete (without 50-move drawing rule)

|Bejeweled and Candy Crush (8x8)

|style="text-align:right;"|64

|style="text-align:right;"|<50

|style="text-align:right;"|

|style="text-align:right;"|70

|style="text-align:right;"|

|NP-hard

|GIPF

|style="text-align:right;"|37

|style="text-align:right;"|25

|style="text-align:right;"|132

|style="text-align:right;"|90

|style="text-align:right;"|29.3

|style="text-align:right;"|

|Connect6

|style="text-align:right;"|361

|style="text-align:right;"|172

|style="text-align:right;"|140

|style="text-align:right;"|30

|style="text-align:right;"|46000

|style="text-align:right;"|

|PSPACE-complete

|Backgammon

|style="text-align:right;"|28

|style="text-align:right;"|20

|style="text-align:right;"|144

|style="text-align:right;"|55

|style="text-align:right;"|250

|style="text-align:right;"|

|EXPTIME-Hard (for the real life setting where the opponent's strategy and dice rolls are unknown)

|Xiangqi

|style="text-align:right;"|90

|style="text-align:right;"|40

|style="text-align:right;"|150

|style="text-align:right;"|95

|style="text-align:right;"|38

|style="text-align:right;"|

| , believed to be EXPTIME-complete

|Abalone

|style="text-align:right;"|61

|style="text-align:right;"|25

|style="text-align:right;"|154

|style="text-align:right;"|87

|style="text-align:right;"|60

|style="text-align:right;"|

|PSPACE-hard, and in EXPTIME

|Havannah

|style="text-align:right;"|271

|style="text-align:right;"|127

|style="text-align:right;"|157

|style="text-align:right;"|66

|style="text-align:right;"|240

|style="text-align:right;"|

|PSPACE-complete

|Twixt

|style="text-align:right;"|572

|style="text-align:right;"|140

|style="text-align:right;"|159

|style="text-align:right;"|60

|style="text-align:right;"|452

|style="text-align:right;"|

|Janggi

|style="text-align:right;"|90

|style="text-align:right;"|44

|style="text-align:right;"|160

|style="text-align:right;"|100

|style="text-align:right;"|40

|style="text-align:right;"|

| , but in PSPACE

|Carcassonne (2p base game)

|style="text-align:right;"|72

|style="text-align:right;"|>40

|style="text-align:right;"|195

|style="text-align:right;"|71

|style="text-align:right;"|55

|style="text-align:right;"|

|Generalization is unclear

|Amazons (10x10)

|style="text-align:right;"|100

|style="text-align:right;"|40

|style="text-align:right;"|212

|style="text-align:right;"|84

|style="text-align:right;"|374 or 299

|style="text-align:right;"|

|PSPACE-complete

|Shogi

|style="text-align:right;"|81

|style="text-align:right;"|71

|style="text-align:right;"|226

|style="text-align:right;"|115

|style="text-align:right;"|92

|style="text-align:right;"|

|EXPTIME-complete

|Thurn and Taxis (2 player)

|style="text-align:right;"|33

|style="text-align:right;"|66

|style="text-align:right;"|240

|style="text-align:right;"|56

|style="text-align:right;"|879

|style="text-align:right;"|

|Go (19x19)

|style="text-align:right;"|361

|style="text-align:right;"|170

|style="text-align:right;"|505

|style="text-align:right;"|211

|style="text-align:right;"|250

|style="text-align:right;"|

|EXPTIME-complete (without the superko rule)

|Arimaa

|style="text-align:right;"|64

|style="text-align:right;"|43

|style="text-align:right;"|402

|style="text-align:right;"|92

|style="text-align:right;"|17281

|style="text-align:right;"|

| , but in EXPTIME

|Stratego

|style="text-align:right;"|92

|style="text-align:right;"|115

|style="text-align:right;"|535

|style="text-align:right;"|381

|style="text-align:right;"|21.739

|style="text-align:right;"|

|Infinite chess

|style="text-align:right;"|infinite

|style="text-align:right;"|

|, but mate-in-n is decidable

|Magic: The Gathering

|style="text-align:right;"| <math>\aleph_0</math>

|style="text-align:right;"| at least <math>\aleph_0</math>

|style="text-align:right;"| <math>2^{\aleph_0}</math>

|style="text-align:right;"| infinite

|style="text-align:right;"| at least <math>\aleph_0</math>

|style="text-align:right;"|

|AH-hard

|Wordle

|style="text-align:right;"|5

|style="text-align:right;"|4.113 (12,972)

|style="text-align:right;"|

|style="text-align:right;"|6

|style="text-align:right;"|

|NP-hard, unknown if PSPACE-complete with parametization

Notes

References

External links

David Eppstein's Computational Complexity of Games and Puzzles

Measures of game complexity

State-space complexity

Complexities of some well-known games

Notes

References

See also

External links