Slashdot Mirror
Can You Beat a Computer At Rock-Paper-Scissors?
tekgoblin writes "The New York Times has created a game that uses artificial intelligence to outsmart you. It uses a simple game called Rock-Paper-Scissors which is pretty much known by everyone on the planet by now. The computer tries to mimic human reasoning by building on simple rules and statistical averages. So based on the rules of the game and your previous moves, the computer tries to make predictions on your next move. The game has 2 modes, the first being Novice, where the computer learns the game from scratch, and Veteran, where the computer has experience of over 200,000 rounds of previous experience."
... in the slightly modified version:
Rock-paper-scissors-control-alt-delete.
__ Someday, but not this morning, I'll finally learn to use the preview button.
Slap the paper over the intake fan, cut the Ethernet cable with the scissors, then bash it with the rock, easy.
--
Pass
At 10-3-2 I feel like I can say yes. Now do my dishes computer!
I wasted 10 minutes of my day playing this yesterday. I then looked at others who were playing Farmville, made it feel like they were doing something productive for a change.
Your choices aren't truly random though.
It's been argued many times, that people make choices in patterns.
- Don't do what I do, it's probably not healthy nor safe. -
Bart: Good ol' rock, nothing beats that!
2000: Andreas Junghanns writes: "Check out the Second International RoShamBo Programming Competition for a completely different experience! If you think you know everything about Rock-Paper-Scissors -- here is your chance to prove it against some stiff international competition. At the Web site you can find rules, sample programs and a report of the first contest, complete with results and program descriptions." This looks pretty cool, and it might make a neat first project for someone, too.
Exactly. They aren't random at all. Laugh if you want but there is actually a RPS strategy guide. Its mostly determining what kind of person your opponent is and knowing what that person is likely to pick from what they know of you. it's much more like the battle of wits in The Princess Bride than random guessing.
Us nerds have already moved on to Rock-Paper-Scissors-Spock-Lizard a long time ago.
Been there, done that, got the shirt.
For an intro (and I mean intro) course in Computer Science at uni, we were assigned to write a Java client in a game called Paper Rules. Establish TCP connection, wait for the master server to find an opponent (another client) for you, and then repeatedly send either ROCK, PAPER or SCISSORS to the server and read the result of the match. To make it interesting, the rules were enhanced so winning a round yielded 1 point, losing -1 point, except when paper won, in which case 2 points were assigned to the winner and -2 to the loser. Our task was to write an "AI" to outsmart the other students' AI.
I wrote a simple algorithm that kept track of the statistics for each of the 18 combinations of [my choice in round n, round n result, opponent's choice in round n+1] and chose based on what the opponent had picked the most in the past. In a match, the winner was declared after 1000 rounds.
Of course, the so-called PaperServer was a <1000-SLOC inefficient by-students-for-students Java one-system-thread-per-connection server running in a Java VM inside a Java VM (yes, really - an IDE called BlueJ) on a terribly underpowered virtual server, so it didn't last long, and anything educational was lost on us that day. Fun times.
If it's designed to outsmart me, I'm guessing unless I really learnt its algorithms, and there was a limit placed on its memory/analysis, that I couldn't.
Don't mean to brag, but I'm pretty fucking awesome when it comes to Paper-Rock-Scissors (it's like Rock-Paper-Scissors with ROT1). The reason I was good, was I was good at gauging the intelligence of my opponent, and emulating how they would emulate me, then moving to the next level.
The best experience of this was a competition at school, where you had to beat one person, advance to level 2, beat a level 2, advance to level 3, until I think it was level 6 or 7. If you lost, you got demoted, if you won, you advanced. It was the best of 3. This was done in quick succession, eg, the entire game took about 5 minutes for me, 30 minutes to an hour for others.
I won by beating level 1 (easy), people think you go rock, so they go paper, so I go scissors. Next they chase scissors, not sure why, but this round is in quick succession to the first, and maybe its being unable to come up with anything else, so I go rock. BAM! LEVEL UP!
Next level was relatively easy, they must have had a similar thought process to me, so I go rock (remembering the decision process for level 1). Next they go 2 moves ahead from rock, because that's their level of emulation. This means they go scissors again. So I go rock. BAM! LEVEL UP!
Next level was harder, first round they had the level 2 decision process, but the second round they've caught on, so I need to go scissors, which is 1 move ahead (or could also be seen as taking the level 2 decision process, but I modeled it in my mind as taking 1 move ahead). They go paper! BAM! LEVEL UP!
Next level was much harder, but by now I got a good idea of what I should be doing. Following on from before, I emulate them as my last turn, and BAM! LEVEL UP!
Did this a few times.
At the end had a collision, I went rock, they went rock. WHOAH! FIRST LOSS/DRAW! I realized that this person was doing exactly as I was doing, the hard problem then became, modelling my own process. I remember we did the count down 1..2.. and I said stop. Wait. Because I couldn't walk through the chain of previous decisions fast enough in my mind, to come at the one I want. Once I had it, I went, okay go. 1...2...3...BAM! I WIN! Next round, 1...2...3...BAM! I WIN! LEVEL UP!
I'm now crowned king of all students and get to go sit on the benches and wait for the idiots. When I talked to the people who finished next, and asked them what they did, they explained it exactly how I did. In the end, I was able to predict their capability one further though. A large part of why the decision processes above would have worked was also because I was the first to level up, and get out, if I messed up early on, and got stuck amongst the riffraff I'd likely be unable to apply the same reasoning, as each level would follow that process less, and be less refined. Also, give I sort of knew these people, I probably had a reasonable feeling on their ability to think like me, which probably helped quite a lot.
As you may be able garner by now, this was the greatest moment of my life. Now some might say, the law of large numbers applies here, and that what I achieved, was just randomness in action. Well fuck you! Given their explanations later, my ability to repeat this a few other times, and my ego, I come to the conclusion that this was not random.
Wait... what was I saying. Oh yeah.
Anyhow, because of this, I'd likely be unable to defeat the computer over and over again, as its ability to estimate my thought process (give it's simple like above), would be far greater as it can store a lot more of "if I go x he goes y after I went x and he went y and I went...", while also applying statistical analysis to it. Though, I do however think I'd be able to give it a good enough run for its money, that we'd diverge towards 50% win rate, as my thought process would devolve to random, in the long run.
Ergo, could you beat a computer at Paper-Rock-Scissors? No, no I fucking couldn't, that's a stupid question. Next you'll be fucking asking me "Could you beat a computer at calculating and verifying primes?".
This is my footer. There are many like it, but this one is mine.
Back in my youth, programming in BASIC and 6502 assembler on the Apple ][, I wrote a "learning" game of "23 matches". The object of this 2-person game (in this case, human v. computer) is to avoid taking the last match. Each round, the player can take 1, 2 or 3 matches.
Although written in about 100 lines of Woz's Integer BASIC, the learning algorithm was simplicity itself: Each round, the computer kept track of its moves (and only its moves) in a table that was indexed by how many matches were left (a 22-row by 3 column table). The table started out with all "zeros" in each of 3 X 22 "weighting" columns (1 column for each possible "move" at each point). If the computer won a round, it incremented the "weight" of each "choice" that was made as the "pile of matches" for that round dwindled. Conversely, if the computer lost a round, it decremented all the "weight" cells at the junctures of "how many left?" X "how many did I take?".
And the algorithm was "predisposed" to "favor" the move that was the "most successful" at any given "how many left?" point.
That was it. No statistical math. No deep AI. Nothing. Just sort of a "path of evolutionary success" that formed a kind of "groove" that guided the correct answer at any given point, without regard to the past moves in a round, nor with any "forward-looking" capability, either. Just stimulus-response.
It was fascinating to watch just how quickly this algorithm "learned". During the first 5 or 6 rounds, it hardly ever won. By the 12th or 13th round, it was pretty hard to beat. By about the 20th round, it was no fun to play anymore, because it was simply unbeatable at that point, and had to be "lobotomized" (lose its "experience").
And, just like those walking robotic "insects" that teach themselves to walk in a matter of minutes with only 2 simple rules (IIRC, standing up is better than laying down; and moving forward is better than standing still), this was a real eye-opener as to just how simple a "learning" algorithm can be, and still achieve results that are both impressive and effective.
You may have won in a specific case, that doesn't mean it is a winning strategy. Mathematically, a strategy based on pure randomness can't be more or less likely to win on average. Why? Because you can effectively ignore what the non-random player selects. There is a 1/3 chance you will randomly pick the same, 1/3 that you will randomly pick the one that beats them and 1/3 that you will pick the one that loses.
Your theory about patterns is wrong. Even if they are incorrectly detecting a pattern it doesn't change the odds of your random choice winning/losing/drawing.
A good strategy would mix random choices with selectively picked moves. Effectively you would need to double-guess what the computer system thinks your pattern is. Very good systems would then track if they are being tracked etc. Two 'perfect' systems would trade increasingly rare attempts to score, as they realise that the best reliable result they can hope for is a draw. This is because any winnning strategy must be based on predicting your opponents choices, the more you act upon your predictions the more a good opponent can learn about how your algorithm works and how to defeat it.
If your pattern is completely random, the opponent can easily win by favoring one.
For example, random against always rock, rock wins 2 out of 3 times.
He wasn't cheating -- he never said only one was poisoned. He asked, "Where is the poison? The game ends when you choose and we both drink."
If Vencini wasn't so full of himself, he might have reasoned that there were four possibilities:
Once you realize that, you can reason about it. Poison in neither cup would be compeltely pointless -- we both drink, and then we're in the same position we were before. Poison in one of the cups? Very risky. Essentially random, with a 50% chance of him dying. At any rate, it's certainly only a game of chance, not a game of wits. Poison in both cups? Seems pretty crazy -- then we both die. Ah -- but do we both die? What if he has an immunity or an antidote? Then if I fall for his trick, it's 100% -- I die no matter what I pick, and he lives. No, you bastard -- the poison is in both cups; I'm not drinking. I win the battle of wits by not falling for your trick.
TCP: Why the Internet is full of SYN.
You were wrong.
You are welcome on my lawn.
For example, random against always rock, rock wins 2 out of 3 times.
Sounds like "New Math" to me. I suggest you run a simulation to verify just how wrong you are.
The other interesting thing about that scene is that Vizzini does his own clever trick. He switches the cups and waits to see if Wesley is comfortable drinking (what he thinks is) his cup. Since he is, and Vizzini has Wesley's original cup, he feels safe drinking it. Which is perfectly rational and a good way to beat the game if you assume there is poison in exactly one cup.