[bmdldyed] Absurdly complicated simple rules

Create a game with a small number of rules which interact in complicated and interesting ways making gameplay one or more of the following:

1. Difficult to find any legal move
2. Difficult to determine whether a given move is legal
3. Difficult to find any good move

All of these, especially #1 and #2, would make the game so impractical to play as to be a joke, which is the point.  #1 could be done with a problem of a complexity class outside of P.  #2 could be done with a problem of a complexity class outside of NP.  (Previously, legal contracts.)

Cryptography might be useful in providing inspiration: "the only legal moves (from some large or infinite space of possible moves) are those for which the cryptographic hash of its string representation is all-zeroes" would satisfy #1, though one could argue over whether the specification of the particular cryptographic hash function satisfies the constraint of "a small number of rules", or whether such a game is "interesting".

For #3 we would like good moves to definitely exist but be difficult to find.  Previously, cryptographic puzzles vaguely similar.