Suitably generalized to $n \times n$ boards, Checkers, Chess, and Go are each EXPTIME-Complete. (See the Wikipedia Game Complexity table.) Each of these two-person games of perfect information has a simple, finite set of move / capture / promotion / win rules. Presumably there are an infinite number of sets of rules that lead to games of complexity (at least) EXPTIME-Complete.

Q. Are the rules of {Checkers, Chess, Go} historical accidents among an infinite variety of similarly difficult but potentially interesting games that just haven't been explored or 'caught on'? Or do the rule sets of popular games have special properties that make them especially attractive for human play?

I realize this is not a sharp cstheory question, and perhaps has no definitive answer.

  • 1
    $\begingroup$ Notice that for Go, only the ill-formed Japanese rule makes it EXPTIME-complete. The complexity for the more elegant and natural set of rules using superko (such as Chinese rules, New Zealand rules, French rules) has not been solved yet, it is only known to be PSPACE-hard and in EXPSPACE. $\endgroup$
    – Denis
    May 7, 2018 at 12:52

1 Answer 1


I've spent a lot of time on problems related to the computational complexity of (puzzle) games and I think there are many orthogonal aspects that can make a two-players or a one-player (puzzle) game attractive and fun:

  • simple rules;
  • simple "physical elements" needed to play it (e.g. a bounch of stones like in Mancala) ... clearly nowadays this condition is meaningless if the game can be played on a computer;
  • a clear ending/winning condition;
  • a well balanced (usually short) duration;
  • as game proceeds the "current position" should get simpler and should soon or later clearly reflect a draw or winning/losing condition;
  • the game contains tactical aspects (usually short term) or long term strategic aspects (usually long-term);
  • many games are played using dice, so a random component can make the game more balanced and attractive;
  • it abstracts an aspect of reality (war, conquer, destroy, survive, escape, build, ...);
  • the difficulty should be balanced and the players must have the sensation that if they play more games they can improve their playing skills and/or discover new (tactical/strategical) aspects of the game;
  • the game offers many strategies that can be chosen to win (a human player should not be able to learn a perfect winning strategy) and each match can lead to completely different positions and "situations";
  • errors are "scaled": if a player makes small error then he can recover if he plays well or the other player makes a similar error.

Two-players games usually share some basic settings or meta-rules (some of them also apply to one-player puzzles):

  • the board is finite and (usually) doesn't change during the game;
  • a move is well defined; and it is (usually) local;
  • player A and player B alternate during the game and a turn is usually a single move;
  • there is usually an initial position (if the elements of the game are not placed on th eboard during the game);
  • during the game there are some elements on the board (they are placed on the board at the beginning or during the game) and there is a clear distinction between elements owned by player A and elements owned by player B, i.e. both players have their avatars on the board :-)). A move can change the ownership of an element or kick it out of the baord;
  • there is a winner;
  • initially both players have allmost the same winning chances.

There are a lot of classic and popular two player games (that were invented before the computer age); and most of them have very different rules and settings: e.g. chess, go, card games, mancala, othello, hex, risk, master mind, scrabble, and so on. Many of them have been proved to be at least PSPACE-complete (the generalized version).

So, returning to your question, I think that there are enough evidences that:

  1. there are no "special rules" (exept for some common meta-rules), but there is a mix of elements involved (the list above can probably be further extended);
  2. there is a a clear connection between the (underlaying) computational complexity and the addictiviness/fun of a game;

Though point 2. is also related to the age of the players (or how much a player "want to think" while playing); e.g. simpler games like "game of the goose" (which is purely random) or the $O(n^2)$ "connect the dots" are funny for children.

Oldest games like chess, checkers and go satisfy many of the (orthogonal) aspects underlined above, but each in a different way: e.g. chess has harder rules than checkers, but it is deeper from a tactical/strategical viewpoint.

I'm not an expert of their history, but I'm sure that initially there were many variations of them, and their rules/settings have "slowly been tuned" to better satisfy the above aspects. For example, in order to shorten the duration of a chess game and enter the middle game faster, rules were changed (see history of chess or History of chess variants). Go rules in ancient times were always passed on by word of mouth, and were usually not clear; and even nowadays there are many variants (two main variations are about scoring, i.e. winning conditions) (see for example The History of Go rules). Even draughts has many national variants.

As a further confirmation of point 1. and 2. you can examine how many addictive video games (most of them are single player puzzles) have been created in the last years and have become "classics": candy crush, sokoban, snake, minesweeper, atomix, tetris, portal, ... they have completely different rules and settings, but they share a common point: they are theoretically hard :-)

From a theoretical point of view; a game is simply a path on a state graph (or state space) in which each node is a valid position and many of the above aspects are closely related to the structure of such a graph. We could write pages about such relation, but I think that a key concept is:

  • the players don't play (theoretical) perfect strategies, so a game is addictive if they can perceive the state space in a strategical/tactical way exactly like on a battlefield with hills, valleys, hidden parts that will be discovered later, positions that look good, positions that look bad, one or more target to reach, temporary disadvantages that will lead to future advantages, different ways to reach a target, the possibility of hindering the opponent's strategy, and so on ...
  • $\begingroup$ Thanks for your thorough answer. This is an important clue: "their rules/settings have "slowly been tuned" to better satisfy the above aspects." $\endgroup$ May 7, 2018 at 11:49
  • $\begingroup$ @JosephO'Rourke: I added a few more references. A few years ago I had in mind to build a puzzle game generator: a new game with slightly different random rules that I would have published weekly on my online game site (but I abandoned both the project and the site and switched to tcs :-); and I'm sure that it could work even for two-players games, mixing randomly some basic orthogonal elements (like [board size/type], [a cell can contain 0/1 pieces of player A/B or both], [1/2/... types of pieces],[conquer vs destroy],[set of simple moves allowed],[set of caputure conditions], and so on... $\endgroup$ May 7, 2018 at 12:29
  • $\begingroup$ @JosephO'Rourke ... and learning techniques could be used to initially evaluate the goodness of the generated rules ... e.g. to check that equally skilled players have the same chances to win, if a more skilled player can beat a less skilled one, the average duration of a game, and so on ... $\endgroup$ May 7, 2018 at 12:35
  • 1
    $\begingroup$ The key word in your answer seems to be "balanced". The evolution of rules seems to be toward balance in difficulty, between being too hard or too easy (both are boring). $\endgroup$ May 7, 2018 at 13:49
  • $\begingroup$ @AndrásSalamon: I think that also very simple rules (moves) can lead to addictive games (e.g. hex, five in a row, rush hour) and this is related to the fact that you have an underlying theoretical hardness even with simple settings that can resemble "real world situations". For what regards the tactical/strategical aspects and winning conditions, 2 player games that are very easy can be addictive as well (most people don't want to think while playing and they can still win:-); for puzzles, the difficulty of reaching the goal is more crucial;and for computer puzzles, it should smoothly increase $\endgroup$ May 7, 2018 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.