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.
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 > 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.
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.
"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.)
>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.
On Nov 12, 3:36 am, Virgil <Vir...@home.esc> wrote:
> 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.
> >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)
<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
>> >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
"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.)
> 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
> >> >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).
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.
<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
>> >> >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).
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?
>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
"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.)
> 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
> >> >> >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).
> 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.
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?
<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
>> >> >> >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).
>> 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.
>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?
>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
"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.)
> 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
> >> >> >> >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).
> >> 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.
> >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?
> Hmm. I guess I just don't understand this at all.
> I'm used to that.
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.
On Nov 10, 11:00 am, 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 – 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.
William Hughes <wpihug...@hotmail.com> writes: > 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
<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
>> >> >> >> >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).
>> >> 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.
>> >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?
>> Hmm. I guess I just don't understand this at all.
>> I'm used to that.
>The trick is that in a tournament, suboptimal >play may be needed to win.
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.
>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
"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.)
> 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
> >> >> >> >> >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).
> >> >> 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.
> >> >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?
> >> Hmm. I guess I just don't understand this at all.
> >> I'm used to that.
> >The trick is that in a tournament, suboptimal > >play may be needed to win.
> 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.
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.
William Hughes 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 >>>> <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"? >>>>>>>>>>> – 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). >>>>>> 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. >>>>> 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 >>>> Hmm. I guess I just don't understand this at all. >>>> I'm used to that. >>> The trick is that in a tournament, suboptimal >>> play may be needed to win. >> 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.
> 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.
[...]
This is interesting. Also, a mixed strategy could include Random and two or more non-random strategies.
<wpihug...@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...)
>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 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.)
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.
