## Scissor-paper-stone algorithm

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Larson, Moderators General, Prelates

### Scissor-paper-stone algorithm

Here's a rock-paper-scissors robot
http://www.nytimes.com/interactive/science/rock-paper-scissors.html
it beats me most of the time, but, however, the algorithm can be improved

Consider two strategies(assuming i can my opponent's preference, as the robot does):
a) i hate losing so much, so i want to be beaten only by the throw that the opponent will least likely to make
i don't know if my english is correct, so here's an example

i know from the database that the opponent's next move will be 60%scissor 30%paper 10%stone
i don't want to lose, so i throw a scissor, which is beaten by stone, with a possibility of 10%

b) winning is fun, so i always beat the opponent's most-possible throw. So in the example above, i will throw a stone to beat the scissor

seeing that Plan a and b sometimes give different suggestion, we can combine these two strategies like this:
take winning as 1, draw as 0, and losing as -1, we can calculate the expectation(is this the right term?) of each strategy, and decide which to adopt

in this way, i promoted the winning rate to 72.9%, which is better than Plan A(68.7%), but worse than Plan B(73.5%), and the optimal case(in which i always choose correctly between Plan A and B, winning 90.0% of the games)

then i came up with another optimization method. i tried not to hate losing as much as i love winning. Later i found the optimal degree of hateness should be -0.6567. After this the winning rate climbed to 73.94%(still poor compared to 90.0%)

Now it seems like a bottleneck situation. I can't think of any other method? any ideas?

cesium14

Posts: 23
Joined: Fri Jun 01, 2012 9:44 am UTC

### Re: Scissor-paper-stone algorithm

No strategy is the best strategy, isn't it?

I play 3 times. All I win a lot.

I found when computer lose, computer likes to change.
runner2011

Posts: 1
Joined: Sat Jun 02, 2012 7:57 am UTC

### Re: Scissor-paper-stone algorithm

runner2011 wrote:No strategy is the best strategy, isn't it?

Not if there is a pattern in your opponent's strategy...

freakish777

Posts: 328
Joined: Wed Jul 13, 2011 2:14 pm UTC

### Re: Scissor-paper-stone algorithm

The strategy that loses the least is random play. The strategy that wins the most is to figure out your opponent's strategy and counter it.
Carnildo

Posts: 1958
Joined: Fri Jul 18, 2008 8:43 am UTC

### Re: Scissor-paper-stone algorithm

well, a strategy doesn't hurt, does it? i'm starting to think it's a stupid question to think about, cuz the game depends mostly on luck but not strategy.
P.S. to beat the robo-player, just make the throw that's beaten by your last one, and occasionally make two same throws on end

cesium14

Posts: 23
Joined: Fri Jun 01, 2012 9:44 am UTC

### Re: Scissor-paper-stone algorithm

cesium14 wrote:well, a strategy doesn't hurt, does it?

It could, if the opponent can guess it. Being random makes the outcome perfectly balanced no matter what the opponent does.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

jestingrabbit

Posts: 5187
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Scissor-paper-stone algorithm

So, I found an infinite win loop (well, 3 wins and a tie) that isn't hard to get to: (veteran AI)
Spoiler:
Rock vs Scissors
Paper vs Paper
Paper vs Rock
Paper vs Rock

As the AI only has a 4 game lookback, once you are "in" the above loop, the AI will continue playing it for a long time. I found it by "cheating" and "looking at what the AI is thinking".

However, by simply playing a game where I refused to play scissors (which seems to really confuse the AI), I managed to first get into a chain stalemate (PPRR for both of us), then bootstrap myself back into that cycle. (Basically, whenever I win RvS, I try to start the script (playing paper, hoping to get a Tie, Win, Win pattern). Similarly, if you get two Paper wins in a row, always play Rock.

3rd try took me 163 rounds to reach the infinite score loop I found.

So it isn't hard to reach.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk

Posts: 10039
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Scissor-paper-stone algorithm

Come up with as many different strategies as you can think of, and code a bot for each one, then play each bot off against every other bot (say 1000 rounds between each pair) and format the results as a matrix.
philip1201 wrote:Not everything which maps countable infinities onto finite areas is a Lovecraft reference.
Oktalist

Posts: 69
Joined: Thu Apr 22, 2010 10:13 pm UTC

### Re: Scissor-paper-stone algorithm

"calculate the expectation(is this the right term?) of each strategy"
"Expected utility" is what you are calculating. The "Utility function" is how you calculate it.

On interesting thing you can consider is that since you don't have all of the information on your opponent's decision, and your opponent is attempting to predict your actions, information on your next move has predictive power for your opponent's next move.

For example your data says: given the last throws, if I throw rock, my opponent will 30% rock, 40% paper, and 30% scissors. If I throw paper, my opponent will 40% rock, 22% paper, 38% scissors. You calculate the utility of each throw and of a random throw, and select the throw with the highest utility.

So if you have an opponent like yacc, who simply outclasses you, you can resort to a random move to at least make sure you're not systemically beaten. Also if the the "What is the computer thinking" section you just display the averages without accounting for your next move (which it does now), it will be possible to beat people who "cheat" by knowing what the computer's data seems to predict.
So if you don't believe you have a cat, that's actually evidence that you have an infinite cat.

Posts: 458
Joined: Sun Oct 19, 2008 5:28 pm UTC
Location: Space Florida

### Re: Scissor-paper-stone algorithm

Quizatzhaderac wrote:"calculate the expectation(is this the right term?) of each strategy"
"Expected utility" is what you are calculating. The "Utility function" is how you calculate it.

On interesting thing you can consider is that since you don't have all of the information on your opponent's decision, and your opponent is attempting to predict your actions, information on your next move has predictive power for your opponent's next move.

For example your data says: given the last throws, if I throw rock, my opponent will 30% rock, 40% paper, and 30% scissors. If I throw paper, my opponent will 40% rock, 22% paper, 38% scissors. You calculate the utility of each throw and of a random throw, and select the throw with the highest utility.

So if you have an opponent like yacc, who simply outclasses you, you can resort to a random move to at least make sure you're not systemically beaten. Also if the the "What is the computer thinking" section you just display the averages without accounting for your next move (which it does now), it will be possible to beat people who "cheat" by knowing what the computer's data seems to predict.

This is really enlightening thx

cesium14

Posts: 23
Joined: Fri Jun 01, 2012 9:44 am UTC

### Re: Scissor-paper-stone algorithm

The NYT article mentions a database with 200000 games. Is this database aviailable somewhere? Or is it just based on games played against the NYT bot?
opisthokonta

Posts: 2
Joined: Sat Jul 07, 2012 3:32 pm UTC

### Re: Scissor-paper-stone algorithm

Hasn't this been done already? And with actual winners
http://webdocs.cs.ualberta.ca/~darse/rsbpc.html
fuzzy

Posts: 2
Joined: Wed Jan 27, 2010 7:28 am UTC