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.