Motivated partly by this MO question, I am wondering if it's possible to design a board game where there is a simple winning strategy but it's hard to find. For example, the game of picking a random number, applying your public crypto key to it and asking what the original number was, would be a trapdoor game, but I am looking for something more like a board game. For example, chess with different rules about how the pieces can move, or some Nim like game.

To make the question more clear - what I am looking for is a simple recipe using which I can generate myself a board game in which I can beat everyone and playing many times won't reveal my strategy. (Yes, I've recently been beaten too many times by my wife in memory...)

  • $\begingroup$ I guess it's the logical follow-up to the recent line of research proving different board/video games are NP-hard.... $\endgroup$ – usul Nov 17 '14 at 22:16
  • $\begingroup$ @domotorp : $\:$ Your idea would only work if it's hard to find coins for different $\hspace{.9 in}$ messages that result in the same ciphertext. $\;\;\;\;$ $\endgroup$ – user6973 Nov 18 '14 at 2:35
  • $\begingroup$ I think the difficulty with this question is that the mechanism to encode any known trapdoor function into any chess-like board game will probably have more overhead due to the board-encoding procedure than the trapdoor function itself (which would already somewhat high on its own). That makes the key word in the question "simple," I suppose. =) $\endgroup$ – Daniel Apon Nov 18 '14 at 13:44
  • 1
    $\begingroup$ I think many games (and currently most game apps on mobile devices) fall into this category. Most of the fun is figuring out a dominant winning strategy. However, unlike board games, the reason the strategy is hard to find is often because the rules are not explicitly laid out. So the key characteristics you seek seem to be: rules are completely known and clear, but their interactions only become apparent with some experience. This leaves a smaller set of categories of games, such as tower defense, block matching, card-type games, and many Euro-style board games (e.g. by Reiner Knizia). $\endgroup$ – András Salamon Nov 18 '14 at 14:40
  • $\begingroup$ Just a side note: In general games, finding the winning strategy is PSPACE Complete $\endgroup$ – M.S. Dousti Nov 18 '14 at 21:08

Your Answer

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

Browse other questions tagged or ask your own question.