Scissor-paper-stone algorithm

[cesium14]

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?

[runner2011]

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.

[freakish777]

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

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

[Carnildo]

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.

[cesium14]

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

[jestingrabbit]

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.

[Yakk]

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.

[Oktalist]

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.

[Quizatzhaderac]

"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.

[cesium14]

"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

[opisthokonta]

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?

[fuzzy]

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