<p>Motivated partly by <a href="https://mathoverflow.net/questions/187356/are-the-moves-rules-of-standard-chess-delicately-balanced">this MO question</a>, 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.</p>

<p>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...)</p>

CC BY-SA 3.0
2014-11-17T22:16:19.787Z
I guess it's the logical follow-up to the recent line of research proving different board/video games are NP-hard....
usul
CC BY-SA 3.0
2014-11-18T13:44:09.150Z
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. =)
Daniel Apon
CC BY-SA 3.0
2014-11-18T14:40:32.787Z
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).
András Salamon
CC BY-SA 3.0
2014-11-18T21:08:14.530Z
Just a side note: In general games, [finding the *winning strategy* is PSPACE Complete](https://en.wikipedia.org/wiki/PSPACE-complete#Puzzles_and_games)
Sadeq Dousti
<cr.crypto-security><board-games>
Is it possible to make trapdoor board games?
domotorp
# Is it possible to make trapdoor board games?

(Asked by: username_0 on 2014-11-17)

Motivated partly by [this MO question](https://mathoverflow.net/questions/187356/are-the-moves-rules-of-standard-chess-delicately-balanced), 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...)

**Tags:** cr.crypto-security, board-games
> **Comments:**
> **username_1**: I guess it's the logical follow-up to the recent line of research proving different board/video games are NP-hard....  
> **username_2**: 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. =)  
> **username_3**: 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).  
> **username_4**: Just a side note: In general games, [finding the *winning strategy* is PSPACE Complete](https://en.wikipedia.org/wiki/PSPACE-complete#Puzzles_and_games)  

---

## 0 answers

