*Post by Tim Chow*The only surefire way to block accusations of cheating is to make your AI a

weak player, or to cheat *in the human's favor*.

Having said that, I have sometimes wondered whether there is any practical

way to implement the following protocol for rolling a die. My opponent and

I simultaneously submit a number between 1 and 6 inclusive. To obtain the

actual die value, add the two submitted numbers together, take the remainder

after dividing by 6, and finally add 1. For example if the two submitted

numbers are 5 and 4, we add them together to get 9; the remainder after

dividing by 6 is 3, and adding 1 yields a final answer of 4.

The advantage of this system is that even if your opponent is cheating and

submitting a sequence of numbers that is not random, *you* can ensure that

the dice are random by making your own submissions random. So if the dice

are not random then you have only yourself to blame.

Well, almost. There are some implementation issues. It's important that

neither player gets to see the other player's submission before making their

own submission. If there is some cryptographic hash function f that both

players trust is secure, then this can be accomplished as follows. Alice

picks a number A and Bob picks a number B. Alice reveals f(A) to Bob and

Bob reveals f(B) to Alice; this doesn't have to happen simultaneously. Then

they reveal A and B (again, this doesn't have to happen simultaneously) and

compute the die value as explained above. Alice can then compute f(B) and

verify that Bob really did select B, and similarly Bob can compute f(A) and

verify that Alice really did select A.

This all works in principle, but of course in reality no human is going to

be doing all these computations manually and waiting around for the other

to finish, so it's going to have to be implemented in a computer program,

and you have to trust that the program is operating correctly. People who

are suspicious about random-number generators are going to be suspicious of

software that implements this protocol, so it may not be a win. I guess you

could maybe make the interface simple enough that a suspicious player could

write their own program to do their half of the protocol.

---

Tim Chow