{
  "id": "enwiki-001377305033",
  "slug": "game-complexity",
  "title": "Game complexity",
  "qid": "",
  "lead": "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.",
  "body": "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== ==Example: tic-tac-toe (noughts and crosses)== For tic-tac-toe, a simple upper bound for the size of the state space is 3 9 = 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. 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. ==Notes== ==References== ==See also== Go and mathematics Solved game Solving chess Shannon number list of NP-complete games and puzzles list of PSPACE-complete games and puzzles ==External links== David Eppstein's Computational Complexity of Games and Puzzles",
  "categories": [
    "10639794",
    "22954297",
    "23603337",
    "26189903",
    "26220375",
    "28269685",
    "48128016"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1377305033",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1790619905.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001377305033",
    "type": "webpage",
    "title": "Game complexity",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/game-complexity",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          19
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001377305033",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1377305033",
    "note": "Immutable snapshot enwiki-001377305033"
  }
}