Design Goals for a Board Game Rulebook Langauge

I spent today drawing things for Rktcr, so it's definitely time to unwind with some recreational math. And the problem that has been on my mind recently is how to design a language for describing board games.

But before I get into that, I'd like to take a detour into the problem that got me started thinking about this.

The Motivation: A Cryptographic Primitive for Deck Shuffling

Some time ago, I spent a little bit of time thinking about a relatively basic cryptography design problem: design an protocol that allows a group of agents to collaboratively shuffle a deck of cards, such that no person in the group knows the final ordering, all cheating is detectable, and the ordering will be random as long as at least one person is acting honestly.

I don't remember the full algorithm I came up with at the time, but loosely, it involved each player obscuring (in a Diffie-Hellman-like way) each card, shuffling the cards together, and handing them to the next player. Once all the players have done this, any player wishing to draw a card receives (securely) the information required to un-obscure the top card from the other players, and is thus able to "draw" the card by revealing it to themselves.

Obviously there are some details here that I've glossed over, but they are not germaine.

The Challenge: Extending to General Games

So, while it's interesting to think of this sort of primitive, or other primitives (passing a card, say) in isolation, it seems yet more interesting to try to come up with a complete and nicely composable set of primitives that can be used for general board and card games.

Another name for a nicely composable set of primitives is, of course, a language. So, the goal becomes: design a language that can be used (ideally, by a human without an advanced degree) to express the rules of any board or card game, in such a way that they can be interpreted (by a collection of computers -- one per player) to enforce these rules and play the described game.

If such a language existed, I could write a general board-game app using it; new games would be packages consisting of a rulebook (written in the proposed language), along with some UI scripts (which would handle displaying visible portions of the game state). The core of the app would be a rulebook interpreter, which would handle communicating state updates with other players' devices, and all the crypto to make sure that hidden state stayed appropriately hidden.

Language Features

What would a good language for describing board and card games look like? Well, my first impulse (mostly due to Chris' excellent ideas -- though I can't find the exact write-up I'm thinking of at the moment) is to work in a find-replace/linear logic setting. This means that we view the state of the game as consisting of some universe of things, and actions in the game involve consuming some of those things in order to produce other things.

This works well for basic turn-taking (a player's "ability to take a turn" is a thing that can be consumed by their turn). However, it doesn't always work at a high enough level to obscure the nifty crypto tricks we'd like to effectively "build in." Here's what I think needs to be added, either to the core language or as syntactic sugar:

• Visibility -- tokens should be able to be obscured, either from all players or from some players. They must be able to be revealed to some (or all) players. However, facts about obscured tokens should still persist (e.g. an obscured sapphire card in Scepter of Zavandor has an unknown actual value, but it is known to be a sapphire card).
• Ownership -- tokens should be able to be acted upon only by certain players. This is required to prevent arbitrary players for taking actions for other players. There needs to be a way to transfer ownership of tokens as a result of actions.
• Stacking -- this would just be "nice to have", except for...
• Shuffling -- stacks of obscured tokens should be able to be mixed, drawn from, cards added, etc; just as a real stack of cards (and hearkening to my initial motivation).
• Dice -- basically syntatic sugar on top of shuffling; but a common enough feature in games that it might be good to support it.
• Pattern Matching -- some sort of generalized reasoning so one doesn't have to, e.g., enumerate all possible melds in rummy.
• Integer Math -- gotta count victory points somehow.

One thing that can't be built in, given that I want all games to be able to work in a distributed way, is simultaneous player potential to act in a way that denies other players the ability to take the same action (e.g. calling "set" in Set). This is because collusion between players can mess up any consistent ordering.

What Next?

This is more of a problem statement than any sort of conclusion or proposal of a solution. I think the next step is to actually start to put together a syntax, and start trying to write some rulebooks. From there I can see how it is convenient to express ownership and visibility. Perhaps they are simply predicates that can come into existence through special rules and be consumed by others. Perhaps they involve moving tokens between different domains (with fixed ownership rules).

As always, feedback is welcome; I especially encourage those of you with PL background to cozy your brain up and figure out the language you would want to use to, e.g., write down the rulebook for Agricola.