3
$\begingroup$

I heard that Clue is a board game that is related to the NP-complete traveling salesman problem. What are other games that relate to important computational problems?

$\endgroup$
6
$\begingroup$

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

In terms of NP-completeness, sometimes end-games become NP-complete. In particular, in a really fun game called 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 given arbitrary initial configuration

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – orcmid Feb 9 '11 at 20:34
  • $\begingroup$ 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). $\endgroup$ – orcmid Feb 9 '11 at 21:09
  • 2
    $\begingroup$ @orcmid: Chess is O(1). The rules are set up so that if 50 moves take place without a piece being captured or a pawn advancing, the game ends. (There are other conditions too, but let's focus on this one for now). There are a max of 16x7 = 112 pawn moves, and 30 possible piece captures. So, if you could make 49 moves and then have a pawn move or piece captured, you could still only have (112+30)x50 = 142x50 = 7100 moves total. Given only a finite number of moves per turn and a finite number of possible moves total, we have a finite number of possible games and positions. Thus it's O(1). $\endgroup$ – Philip White Feb 9 '11 at 21:59
  • $\begingroup$ (Note, there are actually only 16x6=96 pawn moves. So I think it's: 126x50=6300 moves total.) $\endgroup$ – Philip White Feb 10 '11 at 0:38
  • $\begingroup$ @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. $\endgroup$ – orcmid Feb 12 '11 at 19:12
5
$\begingroup$

My favourite is Minesweeper (which is NP-complete)

Then comes Sokoban (which is PSPACE-complete)

... and last but not least One dimensional peg 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 (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" (which - in 2009 - became a book with the same title).

$\endgroup$
  • $\begingroup$ The funny thing about Minesweeper is that it cannot be solved by a deterministic algorithm. $\endgroup$ – Raphael Feb 9 '11 at 22:58
  • $\begingroup$ @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. $\endgroup$ – Huck Bennett Feb 10 '11 at 4:49
  • 2
    $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Feb 10 '11 at 12:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Feb 10 '11 at 12:27
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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