<p>If by 'show computational theories in them' you mean correspond to complexity classes or fit nicely within complexity classes, then you first have to generalize the game to depend on some parameter $n$. For instance, for a game of Chess with a clock (and maybe a 50-move no checkmate rule) on an 8-by-8 board there are only a finite number of possible games. Thus, everything about the game is solvable in $O(1)$.</p>

<p>To overcome this, complexity theorists usually define a generalized game. So for instance a variant of chess on $n$-by-$n$ boards, then standard complexity questions can be asked. In that case, a lot of the 'fun' two player games become PSPACE-complete or EXPTIME-complete. For instance Reversi and Hex are PSPACE-complete and Chess, Go, and Chinese Checkers are EXPTIME-complete. You can learn more on <a href="http://en.wikipedia.org/wiki/Game_complexity">wikipedia</a></p>

<p>In terms of NP-completeness, sometimes end-games become NP-complete. In particular, in a really fun game called <a href="http://en.wikipedia.org/wiki/Phutball">phutball</a> deciding if a player has a win in one move is NP-complete. Solving who will win the game in general is <a href="http://arxiv.org/abs/0804.1777">PSPACE-hard</a> given arbitrary initial configuration</p>

CC BY-SA 2.5
2011-02-09T20:34:20.393Z
I'm having difficulty with the $O(1)$ claim about chess. Posed as a search problem, this would seem to be harder and we know the combinatorial explosion is daunting in practice. So we might need a better characterization of computations that are somehow related in useful ways to the game of chess. I suggest that makes Chess a good candidate on the list of games that are revealing with respect to computer science, although a game with simpler rules, like Go, should suffice.
orcmid
CC BY-SA 2.5
2011-02-09T21:09:26.463Z
I think what is misleading about $O(1) for chess is that it is true every finitely-determined property of the game should have some sort of constant (minimum) measure. In that regard, chess and go (which is easier to generalize) are two very good examples for illustrating complexity and also what a complexity class does not reveal. It then becomes interesting to show how a complexity upper bound is easy and how it may not have any improvement even in the face of speed-ups (and how the P=NP question is sometimes relevant).
orcmid
CC BY-SA 2.5
2011-02-12T19:12:59.187Z
@Philip I get that it is O(1) because of the constant values of the measures people offer.  That just demonstrates that O(1) doesn't tell an useful story in this case.  [Actually, there are also specific exceptions to the 50-move-rule in tournament play, but that is irrelevant - there is still a bound on the number of moves in official play.]  My objection is that the combinatorial complexity of the game play is not captured this way.
orcmid
CC BY-SA 2.5
2011-02-09T19:47:45.817Z
2011-02-09T19:47:45.817Z
Artem Kaznatcheev
<p>My favourite is <a href="http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm" rel="nofollow">Minesweeper</a> (which is NP-complete)</p>

<p>Then comes <a href="http://en.wikipedia.org/wiki/Sokoban" rel="nofollow">Sokoban</a> (which is PSPACE-complete)</p>

<p>... and last but not least <a href="http://tuvalu.santafe.edu/~moore/peg.pdf" rel="nofollow">One dimensional peg</a> which is nothing but a regular language (DSPACE(O(1)))</p>

<p>But <strong>tons of games</strong> have been studied from the the point of view of Complexity Theory ... you can find a big list on Wikipedia: <a href="http://en.wikipedia.org/wiki/Game_complexity" rel="nofollow">Game Theory</a> (with some good references at the bottom, if you want to go into more depth).</p>

<p>For a more formal (deeper) approach, you can download Robert Aubrey Hearn's thesis "<a href="http://groups.csail.mit.edu/mac/users/bob/hearn-thesis-final.pdf" rel="nofollow">Games, Puzzles, and Computation</a>" (which - in 2009 - became a book with the same title).</p>

CC BY-SA 2.5
2011-02-09T22:58:28.863Z
The funny thing about Minesweeper is that it cannot be solved by a deterministic algorithm.
Raphael
CC BY-SA 2.5
2011-02-10T04:49:02.093Z
@Raphael - What do you mean? It can certainly be solved by a deterministic algorithm through exhaustive search just like any other NP-complete problem. Maybe you're claiming that hitting a bomb "stops" your search, but I don't think that makes sense for this interpretation of minesweeper.
Huck Bennett
CC BY-SA 2.5
2011-02-10T12:05:08.007Z
@Huck, @Raphael The NP-completeness of the game is related to the **Minesweeper Consistency Problem**: given a Minesweeper configuration decide if it is consistent or not (i.e. doesn't require guesses). The proof is a reduction from SAT. Perhaps Raphael means that when a Minesweeper configuration is not consistent then it cannot be solved by a deterministic algorithm.
Marzio De Biasi
CC BY-SA 2.5
2011-02-10T12:27:01.083Z
Yes, thanks Vor. If you actually play Minesweeper, you can get so scenarios were you have to guess which field hides a bomb. Therefore, I find the phrasing in your answer misleading.
Raphael
CC BY-SA 2.5
2011-02-09T20:15:33.390Z
2011-02-09T20:25:41.680Z
2011-02-09T20:25:41.680Z
Marzio De Biasi
<p>The n-discs 3-Towers of Hanoi problem shows a number of characteristics, but I don't know if it fits with what you mean by computational theories.  </p>

<ol>
<li><p>The number of moves that are required to move the full stack to a different tower and the demonstration that an algorithm is correct is an interesting exercise in elementary analysis and proof of algorithms.</p></li>
<li><p>The usual recursive-descent, divide-and-conquer algorithm requires storage that can be corresponded with the maximum recursion depth for n discs.  There is a "speed-up" in which the algorithm is iterative and uses constant storage as it enumerates all of the moves.  That is also a nice pragmatic demonstration, requiring proof that the same sequence is produced (that is, the same function is computed) as in (1).  Note that the time complexity (in terms of the number of moves required) is the same either way and it is exact.</p></li>
</ol>

<p>[The iterative solution may not be so well known.  Both are described in Chapter Review problems of the Algorithms chapter of my copy of Brookshear's "Computer Science: An Overview."]</p>

<p>I have gone from games to puzzles, but I think this illustrates how such things can be illustrative.</p>

CC BY-SA 2.5
2011-02-09T20:56:05.210Z
2011-02-09T20:56:05.210Z
orcmid
<p>I heard that <a href="http://en.wikipedia.org/wiki/Cluedo" rel="nofollow">Clue</a> is a board game that is related to the NP-complete traveling salesman problem.   What are other games that relate to important computational problems?</p>

CC BY-SA 2.5
2011-02-09T19:36:35.293Z
what is N-incomplete? do you mean NP-complete? And by 'show computational theories in them' do you mean correspond to complexity classes?
Artem Kaznatcheev
CC BY-SA 2.5
2011-02-09T19:36:40.670Z
What is Clue?  What is N-incomplete?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-09T19:51:23.347Z
I think Clue is probably this: http://en.wikipedia.org/wiki/Cluedo 

I assume that the generalized version has $n$ people, $n$ murder weapons, and $m > n$ rooms.
Artem Kaznatcheev
CC BY-SA 2.5
2011-02-09T21:06:25.410Z
I still have trouble understanding the question, but have you looked at [Computational Complexity of Games and Puzzles](http://www.ics.uci.edu/~eppstein/cgt/hard.html)?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-09T21:17:23.263Z
See also [How to ask good a question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question).
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-09T21:29:03.393Z
@Philip: Are you sure that your version of the question is exactly what @Albert wanted to ask?
Jukka Suomela
CC BY-SA 2.5
2011-02-09T22:38:22.553Z
I do not know if Philip’s edit captures Albert’s intent.  I added the tag [big-list] because it seems that in any case the question is asking for a list of games satisfying some criteria.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-10T04:02:21.807Z
Random comment: I've heard a quote said: "Any game that is *interesting* enough is NP-hard." Of course, *interesting* is an undefined word. Maybe we can define it as - NP-hard?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-12T00:25:48.360Z
I think it shows the intent of the question.   I was trying to relate to non-Comp Sci people what we Comp Sci people do.   Part of that is to find the optimal solution to a problem - the value of algorithms and to find games that people grew up with as a way to relate.
Albert T. Wong
<big-list><gt.game-theory><board-games>
What games best represent well-known computer science problems?
Albert T. Wong
# What games best represent well-known computer science problems?

(Asked by: username_0 on 2011-02-09)

I heard that [Clue](http://en.wikipedia.org/wiki/Cluedo) is a board game that is related to the NP-complete traveling salesman problem. What are other games that relate to important computational problems?

**Tags:** big-list, gt.game-theory, board-games

> **Comments:**
> **username_1**: what is N-incomplete? do you mean NP-complete? And by 'show computational theories in them' do you mean correspond to complexity classes?  
> **username_2**: What is Clue?  What is N-incomplete?  
> **username_1**: I think Clue is probably this: http://en.wikipedia.org/wiki/Cluedo   I assume that the generalized version has $n$ people, $n$ murder weapons, and $m > n$ rooms.  
> **username_2**: I still have trouble understanding the question, but have you looked at [Computational Complexity of Games and Puzzles](http://www.ics.uci.edu/~eppstein/cgt/hard.html)?  
> **username_2**: See also [How to ask good a question](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question).  
> **username_3**: @Philip: Are you sure that your version of the question is exactly what @Albert wanted to ask?  
> **username_2**: I do not know if Philip’s edit captures Albert’s intent.  I added the tag [big-list] because it seems that in any case the question is asking for a list of games satisfying some criteria.  
> **username_4**: Random comment: I've heard a quote said: "Any game that is *interesting* enough is NP-hard." Of course, *interesting* is an undefined word. Maybe we can define it as - NP-hard?  
> **username_0**: I think it shows the intent of the question.   I was trying to relate to non-Comp Sci people what we Comp Sci people do.   Part of that is to find the optimal solution to a problem - the value of algorithms and to find games that people grew up with as a way to relate.  

---

## 3 answers

### Answer by username_1 on 2011-02-09. Score: 5

If by 'show computational theories in them' you mean correspond to complexity classes or fit nicely within complexity classes, then you first have to generalize the game to depend on some parameter $n$. For instance, for a game of Chess with a clock (and maybe a 50-move no checkmate rule) on an 8-by-8 board there are only a finite number of possible games. Thus, everything about the game is solvable in $O(1)$.

To overcome this, complexity theorists usually define a generalized game. So for instance a variant of chess on $n$-by-$n$ boards, then standard complexity questions can be asked. In that case, a lot of the 'fun' two player games become PSPACE-complete or EXPTIME-complete. For instance Reversi and Hex are PSPACE-complete and Chess, Go, and Chinese Checkers are EXPTIME-complete. You can learn more on [wikipedia](http://en.wikipedia.org/wiki/Game_complexity)

In terms of NP-completeness, sometimes end-games become NP-complete. In particular, in a really fun game called [phutball](http://en.wikipedia.org/wiki/Phutball) deciding if a player has a win in one move is NP-complete. Solving who will win the game in general is [PSPACE-hard](http://arxiv.org/abs/0804.1777) given arbitrary initial configuration

> **Comments:**
> **username_5**: I'm having difficulty with the $O(1)$ claim about chess. Posed as a search problem, this would seem to be harder and we know the combinatorial explosion is daunting in practice. So we might need a better characterization of computations that are somehow related in useful ways to the game of chess. I suggest that makes Chess a good candidate on the list of games that are revealing with respect to computer science, although a game with simpler rules, like Go, should suffice.  
> **username_5**: I think what is misleading about $O(1) for chess is that it is true every finitely-determined property of the game should have some sort of constant (minimum) measure. In that regard, chess and go (which is easier to generalize) are two very good examples for illustrating complexity and also what a complexity class does not reveal. It then becomes interesting to show how a complexity upper bound is easy and how it may not have any improvement even in the face of speed-ups (and how the P=NP question is sometimes relevant).  
> **username_5**: @Philip I get that it is O(1) because of the constant values of the measures people offer.  That just demonstrates that O(1) doesn't tell an useful story in this case.  [Actually, there are also specific exceptions to the 50-move-rule in tournament play, but that is irrelevant - there is still a bound on the number of moves in official play.]  My objection is that the combinatorial complexity of the game play is not captured this way.  

---

### Answer by username_6 on 2011-02-09. Score: 5

My favourite is [Minesweeper](http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm) (which is NP-complete)

Then comes [Sokoban](http://en.wikipedia.org/wiki/Sokoban) (which is PSPACE-complete)

... and last but not least [One dimensional peg](http://tuvalu.santafe.edu/~moore/peg.pdf) which is nothing but a regular language (DSPACE(O(1)))

But **tons of games** have been studied from the the point of view of Complexity Theory ... you can find a big list on Wikipedia: [Game Theory](http://en.wikipedia.org/wiki/Game_complexity) (with some good references at the bottom, if you want to go into more depth).

For a more formal (deeper) approach, you can download Robert Aubrey Hearn's thesis "[Games, Puzzles, and Computation](http://groups.csail.mit.edu/mac/users/bob/hearn-thesis-final.pdf)" (which - in 2009 - became a book with the same title).

> **Comments:**
> **username_7**: The funny thing about Minesweeper is that it cannot be solved by a deterministic algorithm.  
> **username_8**: @username_7 - What do you mean? It can certainly be solved by a deterministic algorithm through exhaustive search just like any other NP-complete problem. Maybe you're claiming that hitting a bomb "stops" your search, but I don't think that makes sense for this interpretation of minesweeper.  
> **username_6**: @Huck, @username_7 The NP-completeness of the game is related to the **Minesweeper Consistency Problem**: given a Minesweeper configuration decide if it is consistent or not (i.e. doesn't require guesses). The proof is a reduction from SAT. Perhaps username_7 means that when a Minesweeper configuration is not consistent then it cannot be solved by a deterministic algorithm.  
> **username_7**: Yes, thanks Vor. If you actually play Minesweeper, you can get so scenarios were you have to guess which field hides a bomb. Therefore, I find the phrasing in your answer misleading.  

---

### Answer by username_5 on 2011-02-09. Score: 3

The n-discs 3-Towers of Hanoi problem shows a number of characteristics, but I don't know if it fits with what you mean by computational theories.

1. The number of moves that are required to move the full stack to a different tower and the demonstration that an algorithm is correct is an interesting exercise in elementary analysis and proof of algorithms.
2. The usual recursive-descent, divide-and-conquer algorithm requires storage that can be corresponded with the maximum recursion depth for n discs. There is a "speed-up" in which the algorithm is iterative and uses constant storage as it enumerates all of the moves. That is also a nice pragmatic demonstration, requiring proof that the same sequence is produced (that is, the same function is computed) as in (1). Note that the time complexity (in terms of the number of moves required) is the same either way and it is exact.

[The iterative solution may not be so well known. Both are described in Chapter Review problems of the Algorithms chapter of my copy of Brookshear's "Computer Science: An Overview."]

I have gone from games to puzzles, but I think this illustrates how such things can be illustrative.


---

