Optimal Strategy for Scissors, Paper, Stone Game
Charlie-Boo
In honor of the Scissors, Paper, Stone tournament, I think it would be
nice if we developed an optimal – meaning as good as possible –
strategy for playing.
There are a lot of strategies. So many, in fact, that I would say
first list all of the possible strategies.
C-B
Charlie-Boo
We can also add a slot machine strategy. Assume you have a set of
tokens and the slot machines give out a single fixed coin or nothing,
and you have 2 slot machines to choose from.
C-B
David C. Ullrich
<shyma...@gmail.com> wrote:
>
>In honor of the Scissors, Paper, Stone tournament, I think it would be
>nice if we developed an optimal
Exactly what do you mean by "optimal"?
>� meaning as good as possible �
Ah, thanks. As good as possible in exactly what sense?
I ask the question because with the standard meaning of
"optimal strategy" this is utterly trivial.
>strategy for playing.
>
>There are a lot of strategies. So many, in fact, that I would say
>first list all of the possible strategies.
>
>C-B
>
>http://www.worldrps.com/
David C. Ullrich
"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)
William Hughes
> On Tue, 10 Nov 2009 09:00:03 -0800 (PST), Charlie-Boo
>
>
> >In honor of the Scissors, Paper, Stone tournament, I think it would be
> >nice if we developed an optimal
>
> Exactly what do you mean by "optimal"?
>
> >– meaning as good as possible –
>
> Ah, thanks. As good as possible in exactly what sense?
>
> I ask the question because with the standard meaning of
> "optimal strategy" this is utterly trivial.
Indeed, but the minimax strategy is pretty much guaranteed
to lose in a tournament. (Not last, but not first either).
On the other hand, since any strategy but the minimax
strategy can be dominated, there is no optimum tournament
strategy.
- William Hughes
Virgil
<shyma...@gmail.com> wrote:
>
>In honor of the Scissors, Paper, Stone tournament, I think it would be
>nice if we developed an optimal
Is there anything suboptimal about choosing one's play according to some
random process giving each of Scissors, Paper and Stone equal
probability?
Unless one can winkle out one's opponent's strategy, there is no
strategy giving a better expected result, and not even then, if the
oppenent uses that same strategy.
James Dow Allen
> Is there anything suboptimal about choosing one's play according to some
> random process giving each of Scissors, Paper and Stone equal
> probability?
With this strategy, you expect a score of zero and to
finish exactly average.
> Unless one can winkle out one's opponent's strategy,
Yes, that's the whole idea! I've no idea how Scissors/Paper/Stone
tournaments work, but presumably you play a longish match,
try to guess opponent's strategy (while he's guessing yours);
if it's not working for you, fall back to random.
With random, you can't take advantage of opponent weakness.
A similar idea applies in, for example, the doubling-cube
in backgammon. Some consider a "perfect double" to be when
you don't care whether opponent takes or folds, but if all
your doubles are "perfect" you're getting *no* advantage
from a weak opponent's bad take/fold decisions.
James
William Hughes
> On Tue, 10 Nov 2009 09:00:03 -0800 (PST), Charlie-Boo
>
>
> >In honor of the Scissors, Paper, Stone tournament, I think it would be
> >nice if we developed an optimal
>
> Is there anything suboptimal about choosing one's play according to some
> random process giving each of Scissors, Paper and Stone equal
> probability?
>
> Unless one can winkle out one's opponent's strategy, there is no
> strategy giving a better expected result, and not even then, if the
> oppenent uses that same strategy.
True, but random play is not a good strategy
if the goal is to win
a tournament. So random play cannot be considered an
optimal tournament strategy. So, we can assume that everyone
in the tournament is not in fact using random play, but
is trying to outguess opponents who are trying to outguess them.
It is no wonder that the winner of the first RoShamBo
computer tournament was called "Iocaine Poweder" and
used "Sicilian reasoning". On the other hand
the existence of a strategy that even though it
will not win cannot be beaten tends to limit
things.
As a final word, note that any good strategy
should have a random fallback (if it's losing,
start playing randomly). It's not possible to
beat such a strategy by very much, so a
competition populated by entries designed by people
who realize this basic fact would be quite boring.
Since it's the "dumb" entries that make RoShamBo
interesting, so the challenge is mostly to figure
out the things entrants who are not very bright
will think of.
-Dan Egnor (Author of Iocaine Powder
winner of the 1999 RoShamBo
tournament)
- William Hughes
David C. Ullrich
<wpih...@hotmail.com> wrote:
>On Nov 11, 6:44�am, David C. Ullrich <dullr...@sprynet.com> wrote:
>> On Tue, 10 Nov 2009 09:00:03 -0800 (PST), Charlie-Boo
>>
>> <shymath...@gmail.com> wrote:
>>
>> >In honor of the Scissors, Paper, Stone tournament, I think it would be
>> >nice if we developed an optimal
>>
>> Exactly what do you mean by "optimal"?
>>
>> >� meaning as good as possible �
>>
>> Ah, thanks. As good as possible in exactly what sense?
>>
>> I ask the question because with the standard meaning of
>> "optimal strategy" this is utterly trivial.
>
>
>Indeed, but the minimax strategy is pretty much guaranteed
>to lose in a tournament. (Not last, but not first either).
Is it? It seems to me, not having worked anything out
carefully, that if there are n players it should give a
probability of 1/n of winning. That's not very good,
but I don't see how one can expect to do better.
>On the other hand, since any strategy but the minimax
>strategy can be dominated, there is no optimum tournament
>strategy.
>
> - William Hughes
David C. Ullrich
William Hughes
> On Wed, 11 Nov 2009 06:14:25 -0800 (PST), William Hughes
>
>
>
> <wpihug...@hotmail.com> wrote:
> >On Nov 11, 6:44 am, David C. Ullrich <dullr...@sprynet.com> wrote:
> >> On Tue, 10 Nov 2009 09:00:03 -0800 (PST), Charlie-Boo
>
> >> <shymath...@gmail.com> wrote:
>
> >> >In honor of the Scissors, Paper, Stone tournament, I think it would be
> >> >nice if we developed an optimal
>
> >> Exactly what do you mean by "optimal"?
>
> >> >– meaning as good as possible –
>
> >> Ah, thanks. As good as possible in exactly what sense?
>
> >> I ask the question because with the standard meaning of
> >> "optimal strategy" this is utterly trivial.
>
> >Indeed, but the minimax strategy is pretty much guaranteed
> >to lose in a tournament. (Not last, but not first either).
>
> Is it? It seems to me, not having worked anything out
> carefully, that if there are n players it should give a
> probability of 1/n of winning. That's not very good,
> but I don't see how one can expect to do better.
>
The problem is that random play cannot do well.
This is easiest to see if there is a very weak
player (e.g. a player that always plays scissors).
Random play will tie such a player, but much better
can be done. Thus in a tournament between three
players (dumb, random, smart) random will finish
in the middle (with very high probability).
So the only way to win is to play smart.
Consider a tournament between
(random, smart1, smart2).
One of smart1 and smart2 will defeat the other
but random will tie both. Again, random finishes
in the middle. So we don't need the very
weak player (except perhaps to get things
started).
See
http://www.cs.ualberta.ca/~darse/rsb-results1.html
Especially
Myth: Random (Optimal) can't be beat.
and
Myth: Since all non-optimal strategies can,
in theory, be exploited, the result of a
tournament will be a crapshoot. At the very
least, the outcome will be highly sensitive
to the exact composition of players
(algorithms) in the tournament.
- William Hughes
David C. Ullrich
I don't see the point to assuming there's a dumb
player. In almost any game there are strategies
that work better than the optimal strategy
against a dumb player.
>So the only way to win is to play smart.
Was hoping for a definition of "play smart".
I gather that's at least supposedly what's
being investigated in these tournaments.
>Consider a tournament between
>(random, smart1, smart2).
>One of smart1 and smart2 will defeat the other
>but random will tie both.
Are we using "will" in two different senses
in that sentence?
I don't see why "one of smart1 and smart2
will defeat the other". If they're using the
same strategy then they should tie each other
(and if they're not using the same strategy
one of them is not so smart).
I think a person needs to know how the tournament
is organized (single elimination, round robin,
etc) to say anything definitive. But here's an
empirical question: When random players play
in an n-person tournament do they win 1/n of the time?
> Again, random finishes
>in the middle. So we don't need the very
>weak player (except perhaps to get things
>started).
>
>See
>
>http://www.cs.ualberta.ca/~darse/rsb-results1.html
>
>Especially
> Myth: Random (Optimal) can't be beat.
>and
> Myth: Since all non-optimal strategies can,
> in theory, be exploited, the result of a
> tournament will be a crapshoot. At the very
> least, the outcome will be highly sensitive
> to the exact composition of players
> (algorithms) in the tournament.
>
> - William Hughes
>
David C. Ullrich
William Hughes
If it is known that there is a dumb player,
then it is known that only a "smart" player
is likely to win the tournament. Without knowing this
there is no way to know that the tournament
must contain player who is not playing randomly.
> >So the only way to win is to play smart.
>
> Was hoping for a definition of "play smart".
> I gather that's at least supposedly what's
> being investigated in these tournaments.
>
By "play smart" I mean attempt to detect and exploit
non-random strategies. However, since "playing smart"
is itself non-random it can itself be detected and
exploited. It is clear there is no optimal
"smart" strategy, but there are better and worse.
> >Consider a tournament between
> >(random, smart1, smart2).
> >One of smart1 and smart2 will defeat the other
> >but random will tie both.
>
> Are we using "will" in two different senses
> in that sentence?
>
> I don't see why "one of smart1 and smart2
> will defeat the other". If they're using the
> same strategy then they should tie each other
> (and if they're not using the same strategy
> one of them is not so smart).
>
Indeed, if they are using the same strategy
they will tie. However, in practice they do not,
thus in practice one is "not so smart"
> I think a person needs to know how the tournament
> is organized (single elimination, round robin,
> etc) to say anything definitive.
Indeed.
> But here's an
> empirical question: When random players play
> in an n-person tournament do they win 1/n of the time?
>
No. See the attached link.
http://www.cs.ualberta.ca/~darse/rsb-results1.html
The random player placed in the middle of the pack
(as expected). The best and worst players were
very stable.
- William Hughes
>
David C. Ullrich
Hmm. I guess I just don't understand this at all.
I'm used to that.
>The random player placed in the middle of the pack
>(as expected). The best and worst players were
>very stable.
>
>
> - William Hughes
>
>
>>
David C. Ullrich
William Hughes
> On Thu, 12 Nov 2009 07:56:35 -0800 (PST), William Hughes
>
>
>
The trick is that in a tournament, suboptimal
play may be needed to win.
Take a very simple game with two stategies
A: win 2 100% of the time
B: win 1 75% of the time, win 3 25% of the time
Strategy A has higher expectation.
Now, suppose you are in a tournament with 10
people, one round, high score wins, ties
broken by lot. What strategy should you play?
Suppose everyone else plays A. If you play
A your chance of winning is 1/10, If you play
B your chance of winning is 1/4. So you play
B. Everyone will think like this so maybe
everyone will play B. Suppose everyone else
plays B. If you play A your chance of
winning is (3/4)^9 ~ .08. If you play B your
chance of winning is .1 so you play B.
Similar reasoning works here. The only way
to win the tournament is to pick a suboptimal
strategy that may do very well. There are
many such strategies, none of which dominates
all others, and everyone who is trying to win
will choose one. Question, is there a strategy
that will dominate many other strategies?
The empirical answer seems to be yes.
- William Hughes
Don Stockbauer
Today RPS, tomorrow tic-tac-toe.
Jesse F. Hughes
> The trick is that in a tournament, suboptimal
> play may be needed to win.
>
> Take a very simple game with two stategies
>
> A: win 2 100% of the time
>
> B: win 1 75% of the time, win 3 25% of the time
>
> Strategy A has higher expectation.
>
> Now, suppose you are in a tournament with 10
> people, one round, high score wins, ties
> broken by lot. What strategy should you play?
> Suppose everyone else plays A. If you play
> A your chance of winning is 1/10, If you play
> B your chance of winning is 1/4. So you play
> B. Everyone will think like this so maybe
> everyone will play B. Suppose everyone else
> plays B. If you play A your chance of
> winning is (3/4)^9 ~ .08. If you play B your
> chance of winning is .1 so you play B.
Cute example.
--
Jesse F. Hughes
"The American people would have been incredibly proud of watching our
military folks dispense with basic health care needs to people who
needed help." --George W. Bush, March 13, 2007
David C. Ullrich
Well I do understand _that_ much. Any backgammon
player understands that the play maximising expected
value (optimal in "money play") is not optimal in
match play, where you're trying to maximize your
probability of winning a certain number of points
before your opponent does.
Yes, it's a cute example below. To understand the optimal
strategy in those roshambo tournaments we need to know
how the tournament is set up - I still haven't seen that
explained anywhere. (Not that we could actually solve
the problem given that information, but without that
information we don't yet know what problem we're
trying to solve!)
(A nit: Yes, everyone seems to use this language, not
just you, but "suboptimal strategy may be needed
to win" is incoherent. A strategy optimizing your
expectation in a single game is not the optimal
strategy in a tournament, where the objective is
different. We're talking about two different
"games" - in any given game suboptimal strategy
(for _that_ game) is not a good thing.
Never mind...)
>Take a very simple game with two stategies
>
> A: win 2 100% of the time
>
> B: win 1 75% of the time, win 3 25% of the time
>
>Strategy A has higher expectation.
>
>Now, suppose you are in a tournament with 10
>people, one round, high score wins, ties
>broken by lot. What strategy should you play?
>Suppose everyone else plays A. If you play
>A your chance of winning is 1/10, If you play
>B your chance of winning is 1/4. So you play
>B. Everyone will think like this so maybe
>everyone will play B. Suppose everyone else
>plays B. If you play A your chance of
>winning is (3/4)^9 ~ .08. If you play B your
>chance of winning is .1 so you play B.
>
>Similar reasoning works here. The only way
>to win the tournament is to pick a suboptimal
>strategy that may do very well. There are
>many such strategies, none of which dominates
>all others, and everyone who is trying to win
>will choose one. Question, is there a strategy
>that will dominate many other strategies?
>The empirical answer seems to be yes.
>
> - William Hughes
David C. Ullrich
William Hughes
Sorry for teaching my grandmother to suck eggs.
Anyway we are now on the same page.
> Yes, it's a cute example below. To understand the optimal
> strategy in those roshambo tournaments we need to know
> how the tournament is set up - I still haven't seen that
> explained anywhere.
Indeed. Note that in the rules section (look under links)
does explain the tournament for the 1999 and 2000
University of Alberta events.
There are three obvious types.
A: Round robin, total score
B: Round robin most wins
C: Knock out (each round the losers are eliminated)
(The UofA tournament used A and a mixture of B and C)
If the tournament is of type A or B, then random play
will almost certainly not win. If the tournament
is of type C, then random play has about a 1/n chance
of winning. However, it is possible to do much better.
Assume that all players but one use a deterministic
strategy, and one, dominator, dominates the others.
Since dominator will almost certainly win if random
does not (random knock out dominator in an early
round but does not ulitimately win),
dominator has about and (n-1)/n chance
of winning.
Now will anyone who thinks they cannot produce
dominator play random and increase their chance
of winning. No, because there is a nice mixed
strategy. Play a bit. If you are losing, switch
to random. This means you can win, even against a
"stronger" program. Your chance of winning is not
.5 because you start from behind. Say you win
1/3 of the time against "stronger" opponents,
and 2/3 of the time agains "weaker" opponents.
Then if your progam is stronger more than half
time time (about, I do not have a full analysis)
you are better off with your program than with
random play. Since most people consider themselves
above average drivers, there will be a lot of
programs that are not purely random.
> (Not that we could actually solve
> the problem given that information, but without that
> information we don't yet know what problem we're
> trying to solve!)
>
> (A nit: Yes, everyone seems to use this language, not
> just you, but "suboptimal strategy may be needed
> to win" is incoherent.
Indeed. File it under abuse of notation.
- William Hughes
David Bernier
> On Nov 14, 9:25 am, David C. Ullrich <dullr...@sprynet.com> wrote:
>> On Fri, 13 Nov 2009 04:35:06 -0800 (PST), William Hughes
>>
>>
>>
>> <wpihug...@hotmail.com> wrote:
>>> On Nov 13, 7:19 am, David C. Ullrich <dullr...@sprynet.com> wrote:
>>>> On Thu, 12 Nov 2009 07:56:35 -0800 (PST), William Hughes
>>>> <wpihug...@hotmail.com> wrote:
>>>>> On Nov 12, 11:11 am, David C. Ullrich <dullr...@sprynet.com> wrote:
>>>>>> On Thu, 12 Nov 2009 04:35:26 -0800 (PST), William Hughes
>>>>>> <wpihug...@hotmail.com> wrote:
>>>>>>> On Nov 12, 7:45 am, David C. Ullrich <dullr...@sprynet.com> wrote:
>>>>>>>> On Wed, 11 Nov 2009 06:14:25 -0800 (PST), William Hughes
>>>>>>>> <wpihug...@hotmail.com> wrote:
>>>>>>>>> On Nov 11, 6:44 am, David C. Ullrich <dullr...@sprynet.com> wrote:
>>>>>>>>>> On Tue, 10 Nov 2009 09:00:03 -0800 (PST), Charlie-Boo
>>>>>>>>>> <shymath...@gmail.com> wrote:
>>>>>>>>>>> In honor of the Scissors, Paper, Stone tournament, I think it would be
>>>>>>>>>>> nice if we developed an optimal
>>>>>>>>>> Exactly what do you mean by "optimal"?
This is interesting. Also, a mixed strategy could include
Random and two or more non-random strategies.
David Bernier
David C. Ullrich
<wpih...@hotmail.com> wrote:
>On Nov 14, 9:25�am, David C. Ullrich <dullr...@sprynet.com> wrote:
>> On Fri, 13 Nov 2009 04:35:06 -0800 (PST), William Hughes
>>
>>
>>
>> <wpihug...@hotmail.com> wrote:
>> >On Nov 13, 7:19�am, David C. Ullrich <dullr...@sprynet.com> wrote:
>> >> On Thu, 12 Nov 2009 07:56:35 -0800 (PST), William Hughes
>>[...]
>
>> Yes, it's a cute example below. To understand the optimal
>> strategy in those roshambo tournaments we need to know
>> how the tournament is set up - I still haven't seen that
>> explained anywhere.
>
>Indeed. Note that in the rules section (look under links)
>does explain the tournament for the 1999 and 2000
>University of Alberta events.
Oh. Sorry.
(Heh - I said I hadn't seen it, didn't say I'd looked...)
David C. Ullrich
Ilmari Karonen
An iterated tic-tac-toe tournament could be interesting if ties were
assigned a sufficiently low score (less than the mean of the win and
loss scores). Then pairs of mutually reciprocating players who traded
wins and losses could outscore players who always followed the
classically optimal strategy (which always leads to a tie against an
optimal opponent).
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
George Greene
> Well I do understand _that_ much. Any backgammon
> player understands that the play maximising expected
> value (optimal in "money play") is not optimal in
> match play, where you're trying to maximize your
> probability of winning a certain number of points
> before your opponent does.
That was not the point.
He was asking what you could expect "if other people play A"
or "if other people play B". Since you cannot in fact know
what strategies other people are playing, to factor that
into your decision is sort of impossible in any case.
Can you design a strategy that takes strategies-chosen-
by-others into account?? That is a broader DEFINITION of
"strategy" than is normally contemplated, but WH is invoking
it all the time.
> (A nit: Yes, everyone seems to use this language, not
> just you, but "suboptimal strategy may be needed
> to win" is incoherent. A strategy optimizing your
> expectation in a single game is not the optimal
> strategy in a tournament,
It was A ONE-ROUND tournament.
That is NOT different from a single game.
George Greene
>
> Yes, that's the whole idea! I've no idea how Scissors/Paper/Stone
> tournaments work, but presumably you play a longish match,
> try to guess opponent's strategy (while he's guessing yours);
> if it's not working for you, fall back to random.
The goal would seem to be to have a strategy that, despite not
being random, is not in fact going to get predicted (despite
the fact that, if it is algorithmic as opposed to random, it must
"eventually" be predictABLE).
Ostap S. B. M. Bender Jr.
Better yet, let's first list all of the possible kooks who inundate
sci.math with their "profundities".
David C. Ullrich
<gre...@email.unc.edu> wrote:
>On Nov 14, 8:25�am, David C. Ullrich <dullr...@sprynet.com> wrote:
>> Well I do understand _that_ much. Any backgammon
>> player understands that the play maximising expected
>> value (optimal in "money play") is not optimal in
>> match play, where you're trying to maximize your
>> probability of winning a certain number of points
>> before your opponent does.
>
>That was not the point.
>He was asking what you could expect "if other people play A"
>or "if other people play B". Since you cannot in fact know
>what strategies other people are playing, to factor that
>into your decision is sort of impossible in any case.
It is? Huh. So there's no such thing as game theory.
Fascinating - I didn't know that.
>Can you design a strategy that takes strategies-chosen-
>by-others into account?? That is a broader DEFINITION of
>"strategy" than is normally contemplated,
It is? Huh.
>but WH is invoking
>it all the time.
>
>> (A nit: Yes, everyone seems to use this language, not
>> just you, but "suboptimal strategy may be needed
>> to win" is incoherent. A strategy optimizing your
>> expectation in a single game is not the optimal
>> strategy in a tournament,
>
>It was A ONE-ROUND tournament.
>That is NOT different from a single game.
David C. Ullrich
George Greene
> > Since you cannot in fact know
> >what strategies other people are playing, to factor that
> >into your decision is sort of impossible in any case.
>
> It is? Huh. So there's no such thing as game theory.
Damn, I had almost forgotten how destructive you can be
when you truly put your mind to it.
> Fascinating - I didn't know that.
Liar.
What you also don't know is a relevant definition of game theory.
>
> >Can you design a strategy that takes strategies-chosen-
> >by-others into account?? That is a broader DEFINITION of
> >"strategy" than is normally contemplated,
>
> It is? Huh.
It is in any context where you do not know what strategies are
available, YES.
You know, you could just back your shit up instead of sniping
and taking potshots.
George Greene
> first list all of the possible strategies.
Well, first you would have to get David Ullrich to define
"strategy" in a way that somehow both respected game
theory AND respected the parameters of THIS game.
No, we are not holding our breath.
Ostap S. B. M. Bender Jr.
Excuse me, but isn't this a simple zero-sum matrix game, represented
by the matrix
S P R
S 0 1 -1
P -1 0 1
R 1 -1 0
The optimal randomized strategy is (1/3, 1/3, 1/3) for both players.
Virgil
<3d972211-22d8-4048...@o10g2000yqa.googlegroups.com>,
George Greene <gre...@email.unc.edu> wrote:
Perhaps David is thinking of something along the lines of
http://en.wikipedia.org/wiki/Strategy#Strategies_in_game_theory
For example, using a random number generator hidden from one's opponent,
say secretly rolling a die, and choosing to play rock or scissors or
paper depending on the result of the roll is one possible strategy.
And there is no other strategy which is guaranteed to outperform this
one.
Virgil
<8f9c9a16-e56b-44d2...@j9g2000prh.googlegroups.com>,
It is optimal against an opponent whose next moves you cannot predict.
But if it transpires that you can predict your opponents next moves
better than sheer chance would, there is a better strategy.
Ostap S. B. M. Bender Jr.
> In article
> <8f9c9a16-e56b-44d2-b3b4-e86406c76...@j9g2000prh.googlegroups.com>,
Let me know when you develop a mathematical theory of how to predict
your opponent's psychology.
Ostap S. B. M. Bender Jr.
And by "let me know.." I mean that when you develop your theory and
your strategy, just let me know what it is, and i will be happy to
play this game with you for very big stakes, especially if you
guarantee me that you will stick to your strategy.
Virgil
<48fecefa-4b1e-49ff...@j9g2000prh.googlegroups.com>,
That might be neither necessary nor sufficient to find a strategy better
than random play.
However little of your opponent's psychology you understand, if you can
guess his next play. You can beat him.
And knowing everything about his psychology might not be enough if he
includes randomization in his strategy.
Ostap S. B. M. Bender Jr.
> In article
Well, why wouldn't he? Why do you expect your opponent to be
incredibly dumb? When I play games like backgammon or chess against
even the easiest opponents, I always plan for the worst case. Hope for
the best, but plan for the worst.
jbriggs444
> > And knowing everything about his psychology might not be enough if he
> > includes randomization in his strategy.
>
> Well, why wouldn't he?
Relevance?
Only a great fool or a Sicilian would refrain from falling back on
randomization upon realizing that he is outclassed. Yes, that is
true.
But the opponent has got to come to that realization. That's your
chance to out-guess him.
And his chance to out-guess you.
> Why do you expect your opponent to be
> incredibly dumb?
Not dumb. Arrogant. In order to attempt a non-random strategy one
merely needs to think that ones own abilities might exceed those of
the opponent.
Not dumb. Smart. Opponents who run the uniform mixed strategy from
the outset are uninteresting. Any strategy is equally effective
against them. So if you are competent you will choose a strategy
tuned for opponents not running the uniform mixed strategy. [Of
course if you are neither arrogant nor above-average, the counter-
strategy you select might be the uniform mixed one]
Go to Lake Wobegon, Minnesota for a case where no children ever play
the uniform mixed strategy.
Don Stockbauer
Optimal Strategy for Scissors, Paper, Stone Game:
JOOTS, and go do something useful.
Tim Little
> Well, why wouldn't he? Why do you expect your opponent to be
> incredibly dumb?
If you read the previous posts in this thread, it concerned a
tournament in which players design computer programs to play against
other computer programs. Computer programs can be incredibly dumb.
Human players can also be sufficiently dumb that the locally optimal
strategy may not be globally optimal.
> When I play games like backgammon or chess against even the easiest
> opponents, I always plan for the worst case. Hope for the best, but
> plan for the worst.
Does "hope for the best" include departing from the optimal strategy
if you believe that your opponent is playing suboptimally in a way
that can be exploited? If so, then your criteria form part of a
locally suboptimal strategy. However, it may perform better in
practice.
- Tim
Ostap S. B. M. Bender Jr.
> On 2009-12-04, Ostap S. B. M. Bender Jr. <ostap_bender_1...@hotmail.com> wrote:
>
> > Well, why wouldn't he? Why do you expect your opponent to be
> > incredibly dumb?
>
> If you read the previous posts in this thread, it concerned a
> tournament in which players design computer programs to play against
> other computer programs. Computer programs can be incredibly dumb.
>
------------------
Tim Conrad and the "Elite 47" Dominant at the Dance, Yanis repeats as
Street RPS Champion!
Now how often have you played your best friend for a World
Championship in front of a record crowd with $7,000 on the line? That
was the unlikely finish to an amazing 2009 Yahoo! Rock Paper Scissors
World Championships as Tim Conrad took the championship in an head-to-
head showdown with his teammate and lifelong best friend Tom Butkin.
Conrad waded through the sold out crowd of 512 competitors in Toronto
to end up having to face his teammate and fellow Michigander in one
last duel. It was a dominant performance by Conrad who combined a
scissors-exclusionary strategy with a lethal Avalanche - Bureaucrat
combination to win a decisive victory in straight sets.
It speaks to the depth of this years competition that this amazing
story was just one of many surprises the night held, including the
repeat of Toronto Canada's Yanis as Street Champion. After the street
championship in 2007 and a top-16 finish in 2008 Yanis built a truly
epic stake of street winnings for one last match to take the $1,000
street prize, where he noted that he's posted almost all of his
strategies and theory on the society's own Bullboard.
It was a night of 1,000 stories and we hope the over 900 competitors
and spectators who joined us for this unforgettable night took home
one of their own.
To all pro RPS athletes in Toronto - and around the world - and to
2009 World Champion Tim Conrad we congratulate you on throws well
played. This dance truly brought down the house.
FINAL MATCH
2009 Yahoo! Rock Paper Scissors World Championships
Toronto, Canada
CONRAD BUTKIN
1st Set
R - R
R - P
R - S
P - R
2nd Set
R - S
P - P
P - P
P - R
-------------------------
>
> Human players can also be sufficiently dumb that the locally optimal
> strategy may not be globally optimal.
>
Well, yes. But do you really think that any of the "pro RPS athletes"
are dumb? How perverse it would be if a top professional would be dumb
in his own field of work?
>
> > When I play games like backgammon or chess against even the easiest
> > opponents, I always plan for the worst case. Hope for the best, but
> > plan for the worst.
>
> Does "hope for the best" include departing from the optimal strategy
> if you believe that your opponent is playing suboptimally in a way
> that can be exploited?
>
If I am playing against a simpleton - yes. But if I entered the World
RPS Championships - no, I will play the (1/3, 1/3, 1/3) strategy in
all my matches against pro players.
And you know what? If I were to play even these World Champs like
Conrad or Yanis, would have an even chance of beating them. What kind
of a sport is it if I, who has never played it, have an even chance
of beating the World Champ and other "athletes"?
Is Conrad **really** the best "athlete" in this game? If so, let's
look at this Butkin guy, whom Conrad beat in the final. Butkin knew
that Conrad had a great track record in these tournaments. So, did
Butkin use the simple (1/3, 1/3, 1/3) strategy?
If not - he is a fool and a sucker. And if a fool and a sucker can win
Silver, then it is a stupid game.
If yes - then it was a 50-50 chance, and Conrad just happened to be
lucky. Given that they played only 8 rounds, I bet that this was pure
luck anyway. The very fact that the Final consisted of only 8 rounds,
indicates that the organizers are aware that this is no more of a
"skill game" than coin tossing.
Were there 900 competitors? Well, next time i will take 900 people
from the street, tell them to employ the (1/3, 1/3, 1/3) strategy -
and with the 50% probability, one of us will win the next World
Championship. And if I bring 2700 people - we will have the 75%
chance.
>
> If so, then your criteria form part of a
> locally suboptimal strategy. However, it may perform better in
> practice.
>
Against Butkin, Yanis and Conrad?!
Ostap S. B. M. Bender Jr.
Even if I were "above-average", I would still use the uniform mixed
strategy against all players whom I consider to be "above me". And I
will have an even chance of beating them.
So, the losers (in the long term) in this game (if played on the
professional level) are those, who over-estimate their prowess, i.e.,
suckers.
In other words, if people were realistic about their skills, at least
one side would employ the uniform mixed strategy and all games would
be 50-50 affairs.
>
> Go to Lake Wobegon, Minnesota for a case where no children ever play
> the uniform mixed strategy.
>
Really? Children, who are above average, never play the uniform mixed
strategy? Never?! Not even against World RPS Champions like Conrad and
Yanis? And you call them "above average"? To me, they are pompous
idiots. You know, the kind that inundate sci.math with their "proofs"
of the Twin Prime Conjecture and the Fermat's Last Theorem.
Tim Little
> If I am playing against a simpleton - yes. But if I entered the
> World RPS Championships - no, I will play the (1/3, 1/3, 1/3)
> strategy in all my matches against pro players.
>
> And you know what? If I were to play even these World Champs like
> Conrad or Yanis, would have an even chance of beating them.
One-on-one, yes (assuming you are capable of producing truly random
numbers without external assistance). However, your chances of
winning an overall tournament would be lower. The reason is that the
tournament structure tends to pick out risky strategies that work
better against weaker opponents - "high variance" strategies.
So having been eliminated from regional tournaments, you wouldn't even
qualify for the World RPS Championships. Any statement of your
strategy predicated on that is moot.
>> If so, then your criteria form part of a locally suboptimal
>> strategy. However, it may perform better in practice.
>
> Against Butkin, Yanis and Conrad?!
You don't get to play against Butkin, Yanis, and Conrad unless you
employ a strategy that performs better against lower-tier competitors
first, even though any such strategy is theoreetically beatable.
- Tim
Ostap S. B. M. Bender Jr.
> On 2009-12-05, Ostap S. B. M. Bender Jr. <ostap_bender_1...@hotmail.com> wrote:
>
> > If I am playing against a simpleton - yes. But if I entered the
> > World RPS Championships - no, I will play the (1/3, 1/3, 1/3)
> > strategy in all my matches against pro players.
>
> > And you know what? If I were to play even these World Champs like
> > Conrad or Yanis, would have an even chance of beating them.
>
> One-on-one, yes (assuming you are capable of producing truly random
> numbers without external assistance).
>
Well, I sure can. I can use a 6-sided die or look at the number of
seconds on my watch and take it mod 3.
>
> However, your chances of
> winning an overall tournament would be lower.
>
Lower than whose? If everybody in this tournament is a professional
RPS player - I don't think my chances would be lower than anybody
else's.
I mean, these are brilliant men and pros at this game, so if they are
playing against higher-ranked players - they will surely use my
uniform strategy. And since in every game, one of the players is
ranked higher than the other - the other will use this strategy. Thus,
all games will have the exactly 50-50 chance.
Are you saying that many of these "professional RPS players" are so
dumb and/or so conceited that they will use a risky strategy against a
higher-ranked opponent? If so - that speaks volumes about this game,
if its professional players are so dumb and irrational.
>
> The reason is that the
> tournament structure tends to pick out risky strategies that work
> better against weaker opponents - "high variance" strategies.
>
Look, in serious games/sports like chess or poker or backgammon or
tennis, the term "strong" player refers to somebody with incredible
skills, and all professional players are strong. If many professional
RPS players are so unskilled that their performance against higher
ranked players is worse than my mindless uniform strategy - then this
is not a serious sport.
In what sport can a total beginner like myself have a 50-50 chance of
beating even the World Champ?
>
> So having been eliminated from regional tournaments, you wouldn't even
> qualify for the World RPS Championships. Any statement of your
> strategy predicated on that is moot.
>
It's all a matter of numbers. if enough of my friends enroll in these
tournaments - it will be very likely that one of us will win. The same
probability as the probability of one of us winning the World Coin
Tossing Championship.
Thus, RPS is as serious of a sport as coin-tossing.
>
> >> If so, then your criteria form part of a locally suboptimal
> >> strategy. However, it may perform better in practice.
>
> > Against Butkin, Yanis and Conrad?!
>
> You don't get to play against Butkin, Yanis, and Conrad unless you
> employ a strategy that performs better against lower-tier competitors
> first, even though any such strategy is theoreetically beatable.
>
Only if you know what it is. But if a match consists of only 8 rounds,
there is no time to learn your opponent's weaknesses even if he is
stupid enough to have them.
Look, no matter how you slice it, the classical mathematical game
theory makes much more sense for simple stylised games like RPS than
most people think. Sadly, it falls apart when applied to most real-
life situations, simply because math models cannot take into account
all real life variables.
Ostap S. B. M. Bender Jr.
Or, let's look at it from another angle. The original post in this
thread says:
------------------
From: Charlie-Boo <shymath...@gmail.com>
Newsgroups: sci.math,sci.logic
Subject: Optimal Strategy for Scissors, Paper, Stone Game
Date: Tue, 10 Nov 2009 09:00:03 -0800 (PST)
In honor of the Scissors, Paper, Stone tournament, I think it would be
nice if we developed an optimal / meaning as good as possible /
strategy for playing.
There are a lot of strategies. So many, in fact, that I would say
first list all of the possible strategies.
-----------------
Well, wouldn't your strategy be a function of your opponent's game
history?
Thus, there are at least as many good (not to mention "optimal")
strategies as there are opponents.
Moreover, such strategies will work only against opponents with long
history.
So, lets' start with listing all those guys who have played in these
tournaments? :-)
Don't you see how pointless and bizarre his statements like
>
>>>> I would say first list all of the possible strategies.
are, given that a good strategy must be based on each opponent's
personal history? Can you imagine how many different personal
histories can exist?
James Dow Allen
> In honor of the Scissors, Paper, Stone tournament, I think it would be
To restore this thread to interesting math content,
recall that Bill Taylor proved a theorem about games of
the S-P-R type, namely that interesting such games
(suitably restricted) must have an ODD number of plays.
Puzzle 1: Reconstruct Bill Taylor's exact theorem without
Googling.
Puzzle 2: Prove it.
James Dow Allen
Tim Little
>> One-on-one, yes (assuming you are capable of producing truly random
>> numbers without external assistance).
>
> Well, I sure can. I can use a 6-sided die or look at the number of
> seconds on my watch and take it mod 3.
Both involve external assistance, and the second is not at all random.
I very much doubt that the tournament organizers are going to let you
roll dice during the match. For one thing, it would be extremely
difficult to synchronize the outcome with the prime. Delivering your
throw later than your opponent (after the die stops rolling) is
obviously cheating, and if it stops rolling earlier it is an obvious
tell. Likewise looking at your watch before every throw would be
somewhat of a tell.
> Lower than whose? If everybody in this tournament is a professional
> RPS player - I don't think my chances would be lower than anybody
> else's.
Yes, it would. Bu using an exploiting (but exploitable) strategy,
their variance in win frequency is higher than yours. A very good
player is one who can detect and exploit many exploitable strategies
while using a strategy with weaknesses that are not easy to detect and
exploit.
If there are purely random players in the tournament, they will win
not much different from 1/2 of their matches regardless of the
(nonrandom) strength of their opponent. Strong nonrandom players will
beat weaker nonrandom players, with random players providing
essentially irrelevant white noise.
> I mean, these are brilliant men and pros at this game, so if they
> are playing against higher-ranked players - they will surely use my
> uniform strategy.
They do not necessarily know who is the higher ranked player on the
day. Even in cases where they do know, they are generally going to be
of similar rank themselves and competent to analyse their opponent's
play for potentially exploitable patterns or tells.
Even if you were correct, you have not demonstrated that you can
generate truly random synchronized plays in a tournament setting, so
your theoretical strategy may not be available to you in practice.
> Look, no matter how you slice it, the classical mathematical game
> theory makes much more sense for simple stylised games like RPS than
> most people think.
It is however incorrect to apply a game theoretic analysis predicated
on expected value of isolated games, to iterated plays and tournament
scoring structures.
- Tim
Ostap S. B. M. Bender Jr.
> On 2009-12-05, Ostap S. B. M. Bender Jr. <ostap_bender_1...@hotmail.com> wrote:
>
> >> One-on-one, yes (assuming you are capable of producing truly random
> >> numbers without external assistance).
>
> > Well, I sure can. I can use a 6-sided die or look at the number of
> > seconds on my watch and take it mod 3.
>
> Both involve external assistance, and the second is not at all random.
>
>
> I very much doubt that the tournament organizers are going to let you
> roll dice during the match. For one thing, it would be extremely
> difficult to synchronize the outcome with the prime. Delivering your
> throw later than your opponent (after the die stops rolling) is
> obviously cheating, and if it stops rolling earlier it is an obvious
> tell. Likewise looking at your watch before every throw would be
> somewhat of a tell.
>
Let me see... You wrote:
>
>>> If you read the previous posts in this thread, it concerned
>>> a tournament in which players design computer programs to
> play against other computer programs.
>
So, I can use a computer, and yet, you doubt if I can have a pseudo-
random number generator impervious to my opponent in an 8-round
match?!
>
> > Lower than whose? If everybody in this tournament is a professional
> > RPS player - I don't think my chances would be lower than anybody
> > else's.
>
> Yes, it would. Bu using an exploiting (but exploitable) strategy,
> their variance in win frequency is higher than yours.
>
OK, what exactly **is** their mean and variance? Give me your model.
>
> A very good
> player is one who can detect and exploit many exploitable strategies
> while using a strategy with weaknesses that are not easy to detect and
> exploit.
>
Give me an example of how a top-notch brilliant pro RPS athlete beat
another top-notch brilliant pro RPS athlete by "detecting and
exploiting many exploitable strategies while using a strategy with
weaknesses that are not easy to detect and exploit".
>
> If there are purely random players in the tournament, they will win
> not much different from 1/2 of their matches regardless of the
> (nonrandom) strength of their opponent. Strong nonrandom players will
> beat weaker nonrandom players, with random players providing
> essentially irrelevant white noise.
>
> > I mean, these are brilliant men and pros at this game, so if they
> > are playing against higher-ranked players - they will surely use my
> > uniform strategy.
>
> They do not necessarily know who is the higher ranked player on the
> day.
>
Ranking is not based "on the day". It is based on previous games. If
you have an inferior record to other players and you still refuse to
play the uniform strategy to them - you will likely lose again and
again.
>
> Even in cases where they do know, they are generally going to be
> of similar rank themselves and competent to analyse their opponent's
> play for potentially exploitable patterns or tells.
>
Do they still have the World Championships in the 3x3 tic-tac-toe?
>
> Even if you were correct, you have not demonstrated that you can
> generate truly random synchronized plays in a tournament setting, so
> your theoretical strategy may not be available to you in practice.
>
I don't have time to go into the details, but the question of pseudo-
random generators has been studied by quite a few brilliant
mathematicians, and I assure you that I have an ample supply of such
generators/sequences, impervious in any RPS tournament, that I can
download into my computer or watch.
master1729
its called " meta-strategy " ;)
Ostap S. B. M. Bender Jr.
> On Nov 10, 12:00 pm, Charlie-Boo <shymath...@gmail.com> wrote:
>
> > In honor of the Scissors, Paper, Stone tournament, I think it would be
> > strategy for playing.
>
> > There are a lot of strategies. So many, in fact, that I would say
> > first list all of the possible strategies.
>
>
> >http://www.worldrps.com/
>
> We can also add a slot machine strategy. Assume you have a set of
> tokens and the slot machines give out a single fixed coin or nothing,
> and you have 2 slot machines to choose from.
>
> C-B
>
Assuming that the two machines may have different returns
(probabilities of win), here is a simple but maybe optimal strategy:
at any give time, throw your coin into the machine that has given you
a larger percentage of wins so far. If tied - use the machine that you
have used less.
I am sure it is near-optimal, from the expected value point of view.
Tim Little
> at any give time, throw your coin into the machine that has given
> you a larger percentage of wins so far. If tied - use the machine
> that you have used less.
I.e. alternate between them until one wins, then always play that one.
- Tim
Ostap S. B. M. Bender Jr.
> On 2009-12-07, Ostap S. B. M. Bender Jr. <ostap_bender_1...@hotmail.com> wrote:
>
> > at any give time, throw your coin into the machine that has given
> > you a larger percentage of wins so far. If tied - use the machine
> > that you have used less.
>
> I.e. alternate between them until one wins, then always play that one.
>
Oops. Clearly, there must be some "learning" done first.
But it looks like this is a well-defined problem:
You have two such machines with different expected returns. For
starters, let's assume that they are known - mu_1 and mu_2 - but it is
not known which one is which. Find an optimal strategy.
Tim Little
> You have two such machines with different expected returns. For
> starters, let's assume that they are known - mu_1 and mu_2 - but it
> is not known which one is which. Find an optimal strategy.
Hmm, interesting problem. The main difficulty seems to be in finding
the strategy that converges fastest to the machine with greater
return. A simple strategy of "play a machine until its return drops
below (mu_1 + mu_2) / 2 then switch" should work long-term, but may
waste too many plays on the poorer-performing machine initially.
I'm not even sure how to evaluate the strategies for optimality.
Perhaps in terms of "least expected number of plays on the worse
machine"? This would be infinite for very suboptimal strategies such
as "play them alternately".
- Tim
Ilmari Karonen
On 2009-12-08, Tim Little <t...@little-possums.net> wrote:
> On 2009-12-08, Ostap S. B. M. Bender Jr. <ostap_be...@hotmail.com> wrote:
>> You have two such machines with different expected returns. For
>> starters, let's assume that they are known - mu_1 and mu_2 - but it
>> is not known which one is which. Find an optimal strategy.
>
> Hmm, interesting problem. The main difficulty seems to be in finding
> the strategy that converges fastest to the machine with greater
> return. A simple strategy of "play a machine until its return drops
> below (mu_1 + mu_2) / 2 then switch" should work long-term, but may
> waste too many plays on the poorer-performing machine initially.
An alternative would be to play the machine which, according to the
results so far, is more likely to be the higher-paying one. That is,
assuming that mu_1 > mu_2, and that you've obtained w_A wins and l_A
losses from machine A and w_B wins and l_B losses from machine B so
far, play machine A if
(mu_1/mu_2)^(w_A-w_B) > ((1-mu_2)/(1-mu_1))^(l_A-l_B)
and machine B otherwise. (If both sides are exactly equal, you may
choose any way you like.)
This strategy seems "locally optimal" in the sense that at any given
point during the game it should (if I didn't make a mistake somewhere)
maximize the expected payoff for the next round. For this specific
problem as posed, I suspect it _might_ also be "globally optimal" in
the sense of maximizing the expected payoff over any k rounds, but I
can't entirely convince myself of the just now.
Mind you, the assumption that mu_1 and mu_2 are known in advance
simplifies the problem considerably. In more realistic scenarios one
would usually also have to estimate those values during the game,
which makes things a lot more complicated. In particular, the optimal
strategy is then likely to depend on both the distribution of game
lengths and the distributions of mu_1 and mu_2 (and, in practice, on
one's guess of what those distributions might be).
Ps. I did some numerical tests, and it appears that my method is
indeed superior to yours for intermediate numbers of rounds, although
the difference is usually quite small and easily lost in the noise.
Both methods converge to the machine with the greater return in the
long term, and behave almost identically for the first few turns -- in
particular, both lead to switching after the first round if one lost
and staying if one won, which is the locally optimal strategy after
the first round -- so any difference tends to be most noticeable after
about a dozen or so rounds. The largest difference I could find was
after about 20 rounds, for mu_1 = 1/2 and mu_2 = 1/1000, where my
algorithm scores about 0.46 wins per round on average and yours only
about 0.44.
However, this seems to be mostly due the switching threshold in your
algorithm being very suboptimal for those odds. I'm not sure what the
optimal threshold would be, but replacing the arithmetic mean (mu_1 +
mu_2)/2 with, say, the harmonic mean 2/( 1/mu_1 + 1/mu_2 ) helps a
lot, getting your algorithm's performance to within 0.01 wins per
round of mine even in the worst case that I could find.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address.
Ostap S. B. M. Bender Jr.
Unfortunately, ENW - the expected number of plays on the worse machine
- will probably be infinite for ALL strategies. Here is why:
If you end up playing both machines an unbounded number of times, then
clearly ENW is infinite.
If not - then there will be a bounded from below probability that the
machine, that you chose to play finite times, was actually the better
one, and so you screwed up big time.
Something like that...
That's what's interesting about this problem: it makes you choose/
balance between the need to play the better machine and the need to
estimate what the better machine is.
A more promising definition of optimality could be:
Given a strategy S, let F(S,n) = expected number of plays on the worse
machine after n plays.
Strategy S is "better" than strategy T iff exists m, s.t., F(T,m) > F
(S,m) and F(T,k) >= F(S,k) for all k > m.
They are "equal" iff F(T,k) = F(S,k) for all k > 0.
A strategy is "optimal" iff it is better or equal than any other
strategy.
Ostap S. B. M. Bender Jr.
<ostap_bender_1...@hotmail.com> wrote:
> On Dec 7, 10:25 pm, Tim Little <t...@little-possums.net> wrote:
>
>
>
> > On 2009-12-08, Ostap S. B. M. Bender Jr. <ostap_bender_1...@hotmail.com> wrote:
>
> > > You have two such machines with different expected returns. For
> > > starters, let's assume that they are known - mu_1 and mu_2 - but it
> > > is not known which one is which. Find an optimal strategy.
>
> > Hmm, interesting problem. The main difficulty seems to be in finding
> > the strategy that converges fastest to the machine with greater
> > return. A simple strategy of "play a machine until its return drops
> > below (mu_1 + mu_2) / 2 then switch" should work long-term, but may
> > waste too many plays on the poorer-performing machine initially.
>
> > I'm not even sure how to evaluate the strategies for optimality.
> > Perhaps in terms of "least expected number of plays on the worse
> > machine"? This would be infinite for very suboptimal strategies such
> > as "play them alternately".
>
> Unfortunately, ENW - the expected number of plays on the worse machine
> - will probably be infinite for ALL strategies. Here is why:
>
> If you end up playing both machines an unbounded number of times, then
> clearly ENW is infinite.
>
> If not - then there will be a bounded from below probability that the
> machine, that you chose to play finite times, was actually the better
> one, and so you screwed up big time.
>
> Something like that...
>
The above is far from a rigorous proof, but I suspect it can be turned
into one. It all depends on how slow the sequence {F(S,n)} can grow.
(see below for definition)
>
> That's what's interesting about this problem: it makes you choose/
> balance between the need to play the better machine and the need to
> estimate what the better machine is.
>
> A more promising definition of optimality could be:
>
> Given a strategy S, let F(S,n) = expected number of plays on the worse
> machine after n plays.
>
> Strategy S is "better" than strategy T iff exists m, s.t., F(T,m) > F
> (S,m) and F(T,k) >= F(S,k) for all k > m.
>
> They are "equal" iff F(T,k) = F(S,k) for all k > 0.
>
> A strategy is "optimal" iff it is better or equal than any other
> strategy.
>
If there exist strategies with finite ENW, then your definition of
optimality is the same as mine, Tim. In other words, my definition is
more general.
Tim Little
> If you end up playing both machines an unbounded number of times, then
> clearly ENW is infinite.
Only if the probability of doing so is nonzero.
> If not - then there will be a bounded from below probability that
> the machine, that you chose to play finite times, was actually the
> better one, and so you screwed up big time.
For my example strategy, you only play the wrong machine an unbounded
number of times if the observed cumulative return on the correct
machine drops below (mu_1 + mu_2) / 2 an infinite number of times, or
the wrong machine stays above that threshold permanently. Both
outcomes have probability zero.
- Tim
Tim Little
> If there exist strategies with finite ENW, then your definition of
> optimality is the same as mine, Tim. In other words, my definition
> is more general.
Yes, I agree.
- Tim
Ostap S. B. M. Bender Jr.
That's correct. Random walks with positive drift tend to infinity. I
suspect that if you know mu_1 and mu_2 in advance, the expected number
of times play the wrong machine, under Ilmari's strategy, is finite.
It is probably expressible as the sum of a geometric progression of
common ratio below 1 (I am too lazy to set it up). I suspect his
strategy is close to optimal, but a proof would be great.
Also: what if we didn't know mu_1 and mu_2?
What if we only knew their difference? Or ratio?
What if we only knew that they are different, but nothing else? (That
seems like a very hard problem).
Ilmari Karonen
> On 2009-12-08, Tim Little <t...@little-possums.net> wrote:
>> On 2009-12-08, Ostap S. B. M. Bender Jr. <ostap_be...@hotmail.com> wrote:
>>> You have two such machines with different expected returns. For
>>> starters, let's assume that they are known - mu_1 and mu_2 - but it
>>> is not known which one is which. Find an optimal strategy.
>>
>> Hmm, interesting problem. The main difficulty seems to be in finding
>> the strategy that converges fastest to the machine with greater
>> return. A simple strategy of "play a machine until its return drops
>> below (mu_1 + mu_2) / 2 then switch" should work long-term, but may
>> waste too many plays on the poorer-performing machine initially.
>
> An alternative would be to play the machine which, according to the
> results so far, is more likely to be the higher-paying one. That is,
> assuming that mu_1 > mu_2, and that you've obtained w_A wins and l_A
> losses from machine A and w_B wins and l_B losses from machine B so
> far, play machine A if
>
> (mu_1/mu_2)^(w_A-w_B) > ((1-mu_2)/(1-mu_1))^(l_A-l_B)
>
> and machine B otherwise. (If both sides are exactly equal, you may
> choose any way you like.)
Expanding on this a little:
While the exponential form of the rule above is in some ways closer to
its derivation from the ratio of the likelihoods of the two possible
scenarios (A scores better v. B scores better), a much more convenient
way to express it is in terms of log-likelihoods:
(log mu_1-log mu_2) (w_A-w_B) > (log(1-mu_2)-log(1-mu_1)) (l_A-l_B).
As the first term on each side is always positive if mu_1 > mu_2 as we
assumed above and negative otherwise, we can also drop that assumption
and just take the absolute values:
|log mu_1-log mu_2| (w_A-w_B) > |log(1-mu_2)-log(1-mu_1)| (l_A-l_B).
The two differences of logarithms only depend on mu_1 and mu_2, and
can be precalculated before the game. Calling them k_W and k_L
respectively, the decision rule is then simply to play machine A if
k_W (w_A - w_B) > k_L (l_A - l_B)
and machine B otherwise. We don't even need to keep track of all the
four counts w_A, w_B, l_A and l_B: it suffices to keep track of the
differences w_A - w_B and l_A - l_B. Alternatively, we can rearrange
the condition to:
k_W w_A - k_L l_A > k_W w_B - k_L l_B
and just keep track of the total value of each side, adding k_W or
subtracting k_L from the appropriate side depending on the outcome.
These values can be thought of as weighted running scores for each of
the machines, and the rule then becomes simply to play whichever
machine currently has the highest score.
Also, if the winning odds of the two machines happen to be exactly
complementary, i.e. if mu_1 + mu_2 = 1, then k_W = k_L and we can
factor them both out to get the condition
w_A - l_A > w_B - l_B.
That is, if mu_1 + mu_2 = 1 (which is equivalent to the expected odds
of winning if playing at random being 1/2), then we should simply keep
playing whichever machine has given us a higher margin of wins over
losses so far. The weights k_W and k_L that come into play if this is
not the case can then be thought of, in some sense, as accounting for
the fact that rarer events carry more significance: if one is more
likely to lose than to win when playing at random, then the occasional
wins provide more information about the relative odds on the two
machines than the common and expected losses (and vice versa).
master1729
> On Dec 3, 10:26 am, David C. Ullrich
> <dullr...@sprynet.com> wrote:
> > > Since you cannot in fact know
> > >what strategies other people are playing, to
> factor that
> > >into your decision is sort of impossible in any
> case.
> >
> > It is? Huh. So there's no such thing as game
> theory.
>
> Damn, I had almost forgotten how destructive you can
> be
> when you truly put your mind to it.
>
> > Fascinating - I didn't know that.
>
> Liar.
>
> What you also don't know is a relevant definition of
> game theory.
>
> >
> > >Can you design a strategy that takes
> strategies-chosen-
> > >by-others into account?? That is a broader
> DEFINITION of
> > >"strategy" than is normally contemplated,
> >
> > It is? Huh.
>
> It is in any context where you do not know what
> strategies are
> available, YES.
>
> You know, you could just back your shit up instead of
> sniping
> and taking potshots.
not everybody agrees with ullrich.
Ostap S. B. M. Bender Jr.
<ostap_bender_1...@hotmail.com> wrote:
> On Dec 8, 5:06 pm, Tim Little <t...@little-possums.net> wrote:
>
> > On 2009-12-09, Ostap S. B. M. Bender Jr. <ostap_bender_1...@hotmail.com> wrote:
>
> > > If you end up playing both machines an unbounded number of times, then
> > > clearly ENW is infinite.
>
> > Only if the probability of doing so is nonzero.
>
> > > If not - then there will be a bounded from below probability that
> > > the machine, that you chose to play finite times, was actually the
> > > better one, and so you screwed up big time.
>
> > For my example strategy, you only play the wrong machine an unbounded
> > number of times if the observed cumulative return on the correct
> > machine drops below (mu_1 + mu_2) / 2 an infinite number of times, or
> > the wrong machine stays above that threshold permanently. Both
> > outcomes have probability zero.
>
> That's correct. Random walks with positive drift tend to infinity. I
> suspect that if you know mu_1 and mu_2 in advance, the expected number
> of times play the wrong machine, under Ilmari's strategy, is finite.
>
No, no, no! I was confused as to who said what. I am talking here not
about Ilmari's but your strayegy, Tim:
--------------
On Dec 7, 10:25 pm, Tim Little <t...@little-possums.net> wrote:
>
> Hmm, interesting problem. The main difficulty seems to be in finding
> the strategy that converges fastest to the machine with greater
> return. A simple strategy of "play a machine until its return drops
> below (mu_1 + mu_2) / 2 then switch" should work long-term, but may
> waste too many plays on the poorer-performing machine initially.
>
-----------------------------
But what do we do if both machines' returns keep on staying below
(mu_1 + mu_2) / 2? Play the one with a better return? Then if the
other machine has given us a return below mu_1 so far (or better yet,
0), it may never be played on, even though its true return is mu_2 and
thus it's the better machine.
Tim Little
> But what do we do if both machines' returns keep on staying below
> (mu_1 + mu_2) / 2?
According to my strategy? Keep playing both alternately. The
expected number of plays in this condition is finite. It's possible
(with probability 0) that both returns stay below (mu_1 + mu_2) / 2,
but then it's also possible with probability zero that both machines
never pay out anything at all.
- Tim
Ostap S. B. M. Bender Jr.
> On 2009-12-10, Ostap S. B. M. Bender Jr. <ostap_bender_1...@hotmail.com> wrote:
>
> > But what do we do if both machines' returns keep on staying below
> > (mu_1 + mu_2) / 2?
>
> According to my strategy? Keep playing both alternately.
>
But in what proportion? 1-to-1 regardless of their relative
performance so far? This is not going to be optimal, I bet.
Jim Ferry
> In honor of the Scissors, Paper, Stone tournament, I think it would be
> nice if we developed an optimal – meaning as good as possible –
> strategy for playing.
>
> There are a lot of strategies. So many, in fact, that I would say
> first list all of the possible strategies.
>
> C-B
>
> http://www.worldrps.com/
It gets complicated to define "strategy" as something that encompasses
play over an entire tournament, so let's limit the definition to a
single match. Suppose a match consists of n rounds. There is a
natural, general definition of a strategy for an n-round game. Let T
= {paper, scissors, rock}^2 be the set of 9 possible throws (one for
you, one for your opponent). Let W be the set {(x,y,z):x+y+z=1, x>=0,
y>=0, z>=0} of valid probability triples of playing paper, scissors,
and rock, respectively. Then a strategy S_k for the k^th round is
just a function S_k : T^(k-1) -> W, i.e., a triple of probabilities
for each possible history of throws in rounds 1 through k-1. A
strategy S for an n-round game is then a set {S_k : k = 1 to n} of
strategies for each round. Thus an n-round strategy is defined by
(9^n-1)/4 parameters.
For any two strategies S1 and S2, the probabilities pW, pT, and pL of
a win, tie, and loss, respectively for player 1 are well defined
(though perhaps difficult to compute). Thus we may define v(S1,S2) =
pW-pL. Given that the opponent is playing strategy S2, the optimal
strategies for player 1 are those S1 which maximize v(S1,S2).
An example of a strategy someone might try is the following: whenever
the previous throw was t (e.g., t = (scissors, rock)), consider all
previous occasions when the throw was t, assume the probability for
the opponent's next move will be distributed according to the
historical histogram (or (1/3,1/3,1/3) when there are no previous
throws), and select uniformly at random between moves that maximize Pr
(win) - Pr(loss).
Question: what is the set of n-round strategies which are optimal
when the opponent is playing the above strategy?
Tim Little
> But in what proportion? 1-to-1 regardless of their relative
> performance so far? This is not going to be optimal, I bet.
Yes, it was already shown to be suboptimal by another poster in this
subthread (Ilmari?). I never expected it to be optimal, just to have
finite expected loss from playing the wrong machine.
In practice, it actually performs better than I expected. If the
machines differ in performance enough to matter, it settles quite
rapidly on the better one with high probability. If they are very
close together in performance, no strategy can distinguish them
quickly (though it doesn't matter as much).
- Tim
Ostap S. B. M. Bender Jr.
> On 2009-12-10, Ostap S. B. M. Bender Jr. <ostap_bender_1...@hotmail.com> wrote:
>
> > But in what proportion? 1-to-1 regardless of their relative
> > performance so far? This is not going to be optimal, I bet.
>
> Yes, it was already shown to be suboptimal by another poster in this
> subthread (Ilmari?). I never expected it to be optimal, just to have
> finite expected loss from playing the wrong machine.
>
But you know what? If we applied ourselves, we could probably find THE
set of optimal strategies. I can feel in my bones that this is
solvable.
Tim Little
> It gets complicated to define "strategy" as something that
> encompasses play over an entire tournament, so let's limit the
> definition to a single match.
That's actually not very useful in illustrating how tournaments differ
from single games, as a match is still a 2-player zero-sum game having
a single optimal mixed strategy, and it is just the iterated
single-game strategy. With more than two players that no longer
holds.
Let's look at a very simplified type of play choice: where players may
choose the probabilities of each throw, which will remain fixed
throughout a tournament. Suppose there are 3 players, and the winner
is determined simply by each player playing the other two 10 times
with highest total score winning. The unbiased play choice is then
actually the worst-performing!
Although it is minimax optimal for two players, with three players it
loses to most of the pairs of choices of the other two players, and at
best draws.
Although a very simplistic example, this result does carry over to
more general in-tournament strategies. There is no strategy that the
unbiased random strategy beats, therefore its expected score is
clustered tightly around zero and it will most likely finish near the
middle of the pack. A strategy that beats some and loses to some will
have no greater mean, but will usually have greater variance over the
space of strategies it is likely to face.
> An example of a strategy someone might try is the following: whenever
> the previous throw was t (e.g., t = (scissors, rock)), consider all
> previous occasions when the throw was t, assume the probability for
> the opponent's next move will be distributed according to the
> historical histogram (or (1/3,1/3,1/3) when there are no previous
> throws), and select uniformly at random between moves that maximize Pr
> (win) - Pr(loss).
>
> Question: what is the set of n-round strategies which are optimal
> when the opponent is playing the above strategy?
Any strategy is optimal against it for n=1 or 2, since the opponent
always plays randomly in that case.
For n=3 the opponent only plays nonrandomly in the third round, and
only when the first two rounds are identical. You can maximise this
by making the same throw in both, and have a 1/3 chance that the
opponent will do so also. In that case you can certainly win the
third since they must assume that you will play the same again.
I'm not inclined to fully analyse n>=4, but expect that the optimal
strategy follows a similar pattern: either exploit a current
predictability in their strategy, or aim to maximise future
predictability. The only question is whether there can be a case
where the latter dominates the former.
- Tim
Ostap S. B. M. Bender Jr.
A better strategy: conduct the above reasoning for your opponent, to
figure out what your opponent will do next, if he is to use the above
strategy for himself. Then make your move that will make him regret
it.
An even better strategy: do the previous paragraph for your opponent,
to figure out what your opponent will do next, if he is to use the
above strategy for himself. Then make your move that will make him
regret it.
And so on.
>
> Question: what is the set of n-round strategies which are optimal
> when the opponent is playing the above strategy?
>
Don't forget that in RRS tournaments, the players play 8 rounds total.
Thus, all these "strategies" are about as effective as trying to
figure out presidential elections from a sample of 8 people.
Jim Ferry
Well yes, but this sequence isn't quite well defined. Let v(S',S) = pr
(S' wins vs. S) - pr(S' loses vs. S). This is a continuous function
on a compact set, so for any strategy S there exists strategies S'
which maximize v(S',S). Let m(S) be this maximum value, and O(S) =
{S': v(S',S) = m(S)} be the set of optimal strategies against S (which
is also a compact set). If we defined a function f(S) which selected
a member of O(S), we could take any strategy S0 and consider the
sequence S0, S1, S2, ..., where S(k+1) = f(Sk) for all k >= 0. One
would want such a function to be canonical, or at least natural
somehow, and to have some nice properties before making conjectures
about sequences S0, S1, S2, ..., however. For example, a nice
property which one might require of f is that it produces strategies
minimally susceptible to counter-play: i.e., for any strategy S, that
the minimal value of m(S') among all S' \in O(S) is achieved for S' = f
(S) (though possibly for other S' \in O(S) as well).
If Z is the trivial/random/minimax strategy, then v(Z,S) = v(S,Z) = 0
for all strategies S, of course, so m(S) >= 0 for all S. Furthermore,
m(Z) = 0, and for all S other than Z, m(S) > 0. This is because Z is
the (unique) minimax strategy, but to see this directly just look at
the first round for which S differs from Z, then pick a set of
previous throws for which S dictates probabilities (x,y,z) (of paper,
scissors, and rock, respectively) which are not all 1/3. Then let S'
be a strategy which is purely random except that for the given set of
previous throws (this arises with positive probability) it plays
"paper" if y-z > 0, "scissors" if z-x > 0, or "rock" if x-y > 0. S'
is not optimal w.r.t. S, of course, but v(S',S) > 0.
Optimizing play in the game-theoretic, minimax sense is trivial and
pointless. Optimizing against a single strategy hardly seems
relevant. So in what sense is one even trying to optimize play? I'd
argue that one is attempting to optimize in a *Bayesian* sense. I.e.,
all the head games that one reads about may be generalized into
formulating a prior distribution p0 for your opponent's strategy
(although to get even fancier, one does actually receive data during a
game, but let's think about the blind version for now). In principle,
then, one selects a strategy S' which maximizes the expected value
\sum_{S} v(S',S) p0(S). Of course, formulating this prior well is
horrendously difficult, particularly if you think you're up against an
opponent who is applying this same reasoning. "Let's see, if he
thinks my prior is p0, then he would select one of those optimizing
strategies S', so I'll give a lot of weight to those in my belief
about his priors, except he probably *knows* that I think that he
thinks my prior is p0 (well, actually a distribution of priors near
p0), so...." (It would be better to have spent years building up an
immunity to iocane powder....) Even without such a savvy opponent,
however, it seems quite daunting to incorporate all the knowledge of
human tendencies to create a prior for, say, a complete rube, and then
to perform the necessary computation of an optimal counter-strategy.
However, I believe that the actual strategies which win in practice
are, in some sense, versions of this (or would be versions of this for
blind games, but have the added dimension of reading an opponent in
actual play).
Ostap S. B. M. Bender Jr.
What strategy are you going to employ if your opponent has read the
above train of thought and is going to both use it AND take advantage
of **you** using it?
Jim Ferry
The strategy would be the one I outlined. Yes, if an opponent knows I
am using this broad class of strategy, that could help him in
principle. The way he could take advantage of it is to formulate a
prior distribution of the distributions over strategies that he
believes I think he would use. Therefore, if I knew he were doing
this, I could formulate a prior distribution over the prior
distributions (of the distributions over strategies that he believes I
think he would use) that I think he would use. Etc. If you had some
systematic way to model the prior distributions that you believe an
opponent would use at level k for all k, and then assigned a prior
probability to him using a level k strategy for each k, you'd have an
"omega" strategy, whereupon he could formula an "1+omega" strategy,
and on it goes forever, indexed by the ordinal numbers.
Of course, if you actually did this your strategy would differ only
infinitesimally from purely random play, because whenever your
strategy "thought it found a pattern to exploit" it would then "think"
"but wait! That's what he *wants* me to think!".
Indeed, if you have reason to believe your opponent's algorithm is
better, or has you sussed out, then you should just play randomly.
I imagine it would be quite difficult even to formulate a prior of
reasonable layman strategies and then computed an optimal strategy
based on that. The first exercise along these lines would be to
assume that an opponent's moves are i.i.d. samples with probabilities
(pP,pS,pR) (which are fixed, but unknown), and using some convenient
prior on (pP,pS,pR) (e.g., a Dirichlet distribution), compute one or
all of the set of optimal counter-strategies.
Ostap S. B. M. Bender Jr.
I think my points are falling on deaf ears. So, I wish you, gentlemen,
all the luck in devising "optimal" algorithms to play RPS in pro
tournaments.
Notice that after dozens and dozens of posts, nobody has come even
close to verbalising a coherent strategy to play the 8-round
championship game against a top professional RPS "athlete". Or against
me, for that matter.
Jim Ferry
<ostap_bender_1...@hotmail.com> wrote:
Each of us has then failed in proportion to our interest in such a
verbalization.
- I. M. Vorobianinov III
Ostap S. B. M. Bender Jr.
Kisa, if none of you has any interest in this, why do you guys write
posts? "Wovon man nicht sprechen will, darüber muss man schweigen." -
to paraphrase Ludwig Wittgenstein.
George Greene
> am using this broad class of strategy, that could help him in
> principle. The way he could take advantage of it is to formulate a
> prior distribution of the distributions over strategies that he
> believes I think he would use. Therefore, if I knew he were doing
> this, I could formulate a prior distribution over the prior
> distributions (of the distributions over strategies that he believes I
> think he would use) that I think he would use. Etc. If you had some
> systematic way to model the prior distributions that you believe an
> opponent would use at level k for all k, and then assigned a prior
> probability to him using a level k strategy for each k, you'd have an
> "omega" strategy, whereupon he could formula an "1+omega" strategy,
> and on it goes forever, indexed by the ordinal numbers.
Exactly. This way lies paradox.
It is just ridiculous. Why not acknowledge the far more
practical point from the outset? IT IS NOT POSSIBLE FOR
your opponent to know what strategy or class of stragies you
are using, nor for you to know what class of strategies he is
using. ALL you know, at any given point, is what moves he has
made so far.
VK
> IT IS NOT POSSIBLE FOR
> your opponent to know what strategy or class of stragies you
> are using, nor for you to know what class of strategies he is
> using. ALL you know, at any given point, is what moves he has
> made so far.
It is plenty enough to make the right guess in 99.(9) % of cases in
one situation and it means pretty much nothing in the other one. The
original question was not properly formulated to give a more precise
answer. The crucial question is - *who* is(are) your opponent(s).
If it's a program with a good randomness generating algorithm then the
only strategy what could be suggested is to use your own randomness
generating algorithm. If its as good as the opposing one then on the
long run you'll eventually get your 50% of wins. Any other
considerations are pointless. The "Scissors, Paper, Stone" game has
equal choice values so cannot be brought to the " Artilleryman VS.
Infantryman" form to be solved by Game theory tools. If OP meant that
then it was a mistake in the premises.
The situation is totally different if the opponent(s) is a fully
functional "higher order biological homeostasis" (or a "neural network
of the 1st order"). The most casual sample of such opponent would be
any normal human being of any reasonable age non being under influence
of specific drugs. One of main features of such homeostasis is its
complete inability to be random: any next decision depends on the set
of similar decisions made before. This way the task comes to a
variation to the Shannon's Clairvoyant algorithm. As the programmatic
reproduction of a neuron chain requires many initial in-out tests, no
results above random can be obtained for a single short game. With 100
plays or more with each opponent a steady result >50% is guaranteed.
With 1000 plays or more with each opponent the result should be above
80%.
I don't know of Shannon's Clairvoyant can be expressed in some math
formulas. At the same time it can be expressed in a rather short and
simple program in nearly any programming language (say JavaScript to
run it in the browser), so I guess it should be expressible
mathematically as well.
Ostap S. B. M. Bender Jr.
These players use computers, and their matches consist of 8 plays.
>
> I don't know of Shannon's Clairvoyant can be expressed in some math
> formulas. At the same time it can be expressed in a rather short and
> simple program in nearly any programming language (say JavaScript to
> run it in the browser), so I guess it should be expressible
> mathematically as well.
>
Let me see. You are going to use a computer to exploit the "human
nature" of your opponent's random number generator. But he is going to
use one of the best computer programs to generate random numbers. Can
you write a program that would defeat any (unknown to you) modern
pseudo-random number generator in 8 plays?
http://en.wikipedia.org/wiki/Pseudo-random_number_generator
Also tell me: is your own strategy going to be deterministic or
randomised? If randomised - what if your opponent writes his own
"rather short and simple program in nearly any programming language
(say JavaScript to run it in the browser)" to exploit the
imperfections of your own random number generator?
If your opponent can use the same tools as you can - why would you
have a greater than a 50% chance of defeating him?