Weeble (clockworksaint) wrote,

Alice and Bob play a game

I thought I'd discuss a problem that I've been thinking about, on and off, for quite a while now. I will warn you now, if you aren't interested in maths, cryptography or games, there is probably very little for you in here. Caveat lector.

I'm trying to devise a system whereby two players can play some arbitrary card-game together online, where it is not possible to cheat without being detected. After some thought I decided that it is acceptable to keep a detailed log of decisions and postpone the detection of cheating until after the game. After all, this is how many actual card-games have to work - you don't get to see your opponent's cards until after the fact.

Now, things seem to be workable for those cards that one or both players can see. If only Alice can see a card, then she can encrypt its identity and reveal that to Bob. Bob then doesn't know the identity of the card, but can be sure that Alice can't cheat by deciding that the card is a different one after all. At the end of the game, or at some point when the card is revealed, Alice reveals the key used for encryption and any cheating can be detected.

The problem is in cards that neither player can see. If both players know the same facts about the card, then it can kind of work. Suppose five cards are face-up to both players. They are then turned over and shuffled. It isn't necessary to determine their order until either player finds out something about one of the cards. If Alice draws a card and looks at it, then it's still not too hard to work this out. She can encrypt the identities of all five cards (that are known to both players to be in the pile) with a hidden key, and show them to Bob. Bob picks one at random, but does not at this time know which card it represents. Alice now considers that to be the card drawn.

The problem is, of the remaining four cards, Alice and Bob know different things. Alice knows their identities, although not their order. Bob only knows that they are some set of four cards from the five originally shuffled, and also has no idea of their order. This is a tricky situation, but can still be worked around, I believe.

The situation I am currently struggling with is when both players know a bit about a pile of shuffled cards, but neither has complete knowledge. Suppose that we started with seven cards, face-up to both Alice and Bob. They were turned face-down and shuffled. Now, Alice has drawn and identified two cards, and Bob has drawn and identified two cards. Three cards remain. Supposing that we have successfully simulated the game thus far online, is it possible to fairly decide what the next card might be without Alice learning the identity of Bob's cards or Bob learning the identity of Alice's cards?

I would like to have Bob draw a card like this: First, Alice should virtually write down the identities of all the cards she does not have. There would then need to be some way for her to shuffle these identities and feed them, one at a time, to Bob, without knowing which one she is showing him. If this works then Bob just has to accept the first card identity that he doesn't already hold. Because both players are recording everything they do to be checked later, Bob can't cheat and ask for another card when the one given to him is not in his hand. My problem currently is whether there is any way for Alice to provide the card identities to Bob one at a time without knowing which ones he's seeing.

Of course, things may become more convoluted when players do more complicated things involving shuffling and redistributing face-down cards, or the nightmare of a situation introduced by having more than two players but I am not going to worry about them for the time being.

So, for those (one? two? any?) of you still reading, is this a solvable problem? Is it solved? Beyond "cryptography" and perhaps "game", I'm really not sure what keywords to search for to find out more about this kind of problem.
Tags: computers, cryptography, games, maths
  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened