Each time a random number is needed, everybody generates a random real between 0 and 1 and publishes a one-way hash of it. When all hashes are received, everybody publishes the generated number and the number used is the decimal part of the sum. (the "sum mod 1").

If you need a number from 1 to 6, compute 1+int(6*(consolidated random number)).

The number must have enough bits to prevent brute-force searching of the other's random numbers. Or it must be padded with additional random bits.

This way, everybody can guarantee the randomness of the number.

If you need to pick a card, instead of ordering them from the start, keep track of the set of unused cards. To pick a card, choose it by picking a random number between 1 and the number of remaining cards.

OK, the problem is, it is very intensive in mail exchanges. So if you really want to play by mail, you better automate the part that deals with generating a distributed random number.

]]>Lets say our two people are A and B.

Both A and B will set up a board. The Chance and Community Chest cards will be ordered into a standard order (alphabetical based on their wording, for example), so that both parties have everything in the exact same order.

Both parties will also obtain a random number generator. The generator will take a seed number and can be used to generate a stream of random numbers. There are numerous examples of such generators on the web - some simple, and some complex. It would be simpler if they used the same generator, but it is not necessary.

Finally, both parties will generate a Private and Public key pair using utilities easily found on the web. They will initialize their random number generator with their private key.

Before play begins, each player will send a message to the other player with the following information:

- the algorithm for the random number generator (if they are not using the same generator)

- the public key

To determine who goes first, a function of the two public keys is made. Say, count the number of instances of '7' in their sum. If the result is odd, player A goes first. If it is even, player B.

Now, a turn progresses as follows (assume it is player A's turn):

1. Player A will query their random number generator for a number. Lets say the result is X.

2. Player A will then send a message to player B including:

- The value of X

- Any non-random moves being made (building houses, etc)

- Their intent (i.e. roll the dice to move, pay to get out of jail, etc).

3. When Player B receives the message, they will advance their random number generator by X and then use the next 2 numbers to get numbers between 1 and 6. This will be the dice roll of the player.

4. Player B will then make the move for Player A on their own copy of the board. Additional numbers are generated as needed, if no further input is required from the other player. For example:

- If this roll puts them on Chest or Chance, another number is selected to determine which card was drawn. If there are Y cards remaining in the pile, then the number is requested between 1 and Y and that card is then selected and played.

- If they rolled doubles and can do nothing further, then the next roll can be made

5. The results of the move and the dice rolls made are then sent back to Player A.

- For efficiency, if there was nothing further that A might do, then B can include in the message the start of his turn (i.e. by including a new random number X in the message, and stating the intent of their move)

Play will proceed until the end of the game.

After the game, or at any point during the game, a player can request an "audit". During an audit, the player will send their private key to the other player. They can each create a new private+public key pair if play is to continue (i.e. if they are audited in the middle of the game). Once in possession of the other player's private key, it can be validated that all of the random numbers generated by the opponent were fair by using their private key and algorithm to re-play all the moves so far. If any discrepancies are found, then one of the players was cheating. By using the opponent's public key (provided at the beginning of the game), it can be verified that the given private key is in fact authentic - i.e. the one that was decided upon at the beginning of the game.

Using this method, one cannot force the outcome of any role. An attempt to do so would be detectable by their opponent when they are audited. For added security, they could basically perform an audit every turn. Thus the message would include the private key used to generate the rolls, and a new public from the private/public key pair to be used for subsequent numbers.

Notes:

- The reason for sending 'X' to each other is to prevent the person from tailoring their private keys at the beginning of the game (or after an audit) to give random numbers that would provide you a disadvantage. For example, it wouldn't be very difficult to generate a private key that when used as a seed, results in a roll of 8 right off the bat. This would land the other player on the tax on their first move, putting them at a disadvantage. By including X in the message, the other player is forced to pass the first X numbers, virtually eliminating the possibility of them tailoring the results.

It got me thinking though: is there a way to truly play Monopoly by mail? How could two people ensure the integrity of the dice rolls? After all, if I'm four spaces away from a property I really need, what's stopping me from sending in the mail "Yay, I rolled a 4!"

So here's the challenge: You need to come up with a way to generate a number between 2 and 12 whose outcome neither party can predict in advance. (EDIT: It technically has to be two numbers between 1 and 6, because if you roll a "4" the game will differ whether it's two 2's or a 3 and a 1. Rolling doubles lets you roll again.)

You also need to simulate the Chance and Community Chest decks (16 cards in each): at the beginning of the game, the decks are shuffled and placed face down. Once the game begins, there is a set order to the cards (they aren't shuffled once the deck runs out, merely the whole deck is placed face down again). You need to find a way to establish an order for the Chance and Community Chest cards, but neither player can know the order in advance. When one player lands on a Chance or Community Chest Space, he has to "draw" the top card, but neither player can know in advance what that card will be.

Only written snail mail can be used: no Internet, no video (so no sending a video tape of Player A rolling the dice).

I have devised a solution to this problem, but I want to see what other people come up with!

]]>