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?
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
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).
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.
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.
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.