0
$\begingroup$

Is there a way to play rock, paper and scissors fairly over internet chat? By this, I mean that both players cannot play their hands simultaneously, one of them has to go first and the second player should have no way of cheating.

One possibility is to use complexity to buy time. Encrypt messages and send messages before the codes can be reasonably broken. Exchange keys afterwards as described by Asaf below (and what I originally wrote here somewhat messily).

This is pretty inelegant and kind of vague but I am not sure one can do better...

$\endgroup$
  • $\begingroup$ You could just use something like code.google.com/p/gmail-delay-send $\endgroup$ – Antitheos Sep 13 '15 at 5:57
  • $\begingroup$ I am not actually interested in playing rock-paper-scissors, just in the mathematical question behind it :) $\endgroup$ – Asvin Sep 13 '15 at 5:58
  • $\begingroup$ Alice and Bob want to play a game of rock, paper, scissors... $\endgroup$ – Alex S Sep 13 '15 at 5:59
  • 2
    $\begingroup$ All in all, this is probably better suited for the Cryptography.SE website. $\endgroup$ – Asaf Karagila Sep 13 '15 at 6:00
  • $\begingroup$ I wasn't aware of that website! $\endgroup$ – Asvin Sep 13 '15 at 6:01
1
$\begingroup$

This assumes that the players have to play within, say, a second of each other.

Generate a list of the numbers $1-999$. $333$ of them are randomly chosen to represent rock, $333$ represent paper, and $333$ represent scissors. You'll end up with lists like:

  • Rock: $697,442,21,31,\dots$
  • Paper: $69,889,614,924\dots$
  • Scissors: $855,523,877,644,\dots$

Each player simply chooses a random number from among the desired list and sends that. Since the players must play within a second of each other, there's no way the second player can look up what the first player's number represents before playing.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think this is just an implementation of what I described in my second paragraph. $\endgroup$ – Asvin Sep 13 '15 at 6:06
  • $\begingroup$ Oh, I think I might have missed that paragraph... $\endgroup$ – Akiva Weinberger Sep 13 '15 at 6:07
  • $\begingroup$ What if I write code to do this automatically and choose the appropriate move? $\endgroup$ – Asaf Karagila Sep 13 '15 at 6:07
  • $\begingroup$ My second paragraph is a bit of a mess anyway... $\endgroup$ – Asvin Sep 13 '15 at 6:07
  • $\begingroup$ @AsafKaragila Choose something bigger than 999, I guess. (Also, there's no reason that the numbers in each list should be in order. In fact, it's probably a good idea to rearrange them.) $\endgroup$ – Akiva Weinberger Sep 13 '15 at 6:09
1
$\begingroup$

Each player encrypts their move, and keys are exchanged only after both moves have been played.

If you set a time window in which the exchange happens, and you use sufficiently secure keys and ciphers this will ensure no cheating was involved.

Another option IA using a trusted third party to hold the moves. Why should you trust them is a whole other thing, though.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This depends on the existence of a secure encryption correct? Thinking a bit more, isn't my question identical to the question about the existence of a secure encryption? $\endgroup$ – Asvin Sep 13 '15 at 6:02
  • $\begingroup$ This can be done with SHA1, for example. I hash "move+key", then I simply send the plain text to prove the authenticity of my hashed message. Assuming moves can only be exchanged within a 5 seconds window, and the key is a sufficiently difficult string to guess, it should be fine. $\endgroup$ – Asaf Karagila Sep 13 '15 at 6:05
  • $\begingroup$ Isn't that the idea I described in my second paragraph? Using complexity to buy time. $\endgroup$ – Asvin Sep 13 '15 at 6:07
  • $\begingroup$ The only winning move is not to play. $\endgroup$ – Asaf Karagila Sep 13 '15 at 6:08
  • $\begingroup$ All encryption is using complexity to buy time. $\endgroup$ – Asaf Karagila Sep 13 '15 at 6:10
0
$\begingroup$

I looked at this problem once as an assignment in a post-graduate Computer Science course... Well, I was trying to work out how to play Battleships without a central trusted authority, but the principle is the same.

My solution was very similar to the one suggested in the question - sending encrypted versions of your moves (in Battleships: of your ship positions) first, and then revealing.

However, there were still two challenges I could not work around:

  1. The Internet is unreliable, and players might drop out of the game at any time through no fault of their own (or even due to sabotage by the other player). In that situation, they should not be punished. The game should be cancelled. However, that situation is indistinguishable from a player receiving the decryption key from the other player, immediately realising they have lost, and deliberately disconnecting before sending their own key.

  2. If the game completed, and one player could mathematically prove that they had won, the other player could (dishonestly) deny it and simply refuse to pay. At that point, the dispute needs to be escalated to some trusted authority (e.g. the tournament manager or a government court) to resolve. If there is such an authority trusted by both sides, it would likely be easier for them to host such a game, rather than forensically examine the results.

Even an encryption-based solution has flaws.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.