RoShamBo Programming Competition
Darse Billings
Q: Can you tell me what kind of hardware/OS the competition will be run on?
A: That has not yet been decided. It may be a Sun Ultra-5 Workstation
running Unix (Solaris), or it could be a fast PC running Linux.
If the code compiles cleanly with gcc, it shouldn't matter too much.
Q: Can I enter Random (Optimal)?
A: No. You shouldn't want to anyway, because it is guaranteed to
finish in the middle of the pack. It definitely will not finish
in first place, because it cannot exploit the weaker programs.
Q: Are we allowed to have other functions, or must everything be
done in a single function?
A: You may have auxiliary functions, provided they can all be placed
together in the tournament program. There must, of course, be only
one player that is called for each move.
Q: Can I produce my own random numbers, or must I use random and/or
the provided flip_biased_coin and biased_roshambo?
A: You may use your own random number generator, but it must use a
fixed seed, so that the tournament results are reproducible, given
a fixed seed to srandom().
Q: Can I use the defined trials constant to know how many trials
will be played (for defining array sizes, for example)?
A: Yup, that's what constants for. :)
For up to date information, check www.cs.ualberta.ca/~darse/rsbpc.html
- Darse.
--
"There's no sense in searching for perfection
when you're making successful mistakes" -The Tragically Hip.
Doug
Darse Billings <da...@cs.UAlberta.CA> wrote:
>Here are some questions and answers about the RSB contest:
>
Darse,
Where can we go to find some deep thought on Roshambo strategy. Searches
of the web seem to be crowded out by noise. It seems that some people
think that Roshambo is simply random. Any game theoretic links or
scholarly analysis that you would like to share with us?
Doug Hershberger
http://umn.edu/~hersh006/
hers...@tc.umn.edu
Jim Geary
Jim Geary
jaygee at primenet dot com
http://www.primenet.com/~jaygee
Kevin Lacquement
Jason Hutchens
>Q: Can I use the defined trials constant to know how many trials
> will be played (for defining array sizes, for example)?
>
>A: Yup, that's what constants for. :)
D'oh! I've been programming my entry under the misapprehension that
the only external information we're allowed to use is the history
arrays.
What would be *really* useful is the ability to find out who your
opponent is, so, if you're meeting it for the second time, you can
use what you've learned about it previously. Is there any scope
for doing this, or are we limited to the two history arrays and the
trials define?
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -569- http://ciips.ee.uwa.edu.au/~hutch-+
| Unsolicited email advertising is treated with the contempt it deserves |
+=-== === --= -====- =-- =--- - - =- -=-- -- ==- ---- = - =- - =-- --==--+
Jason Hutchens
>D'oh! I've been programming my entry under the misapprehension that
>the only external information we're allowed to use is the history
>arrays.
My entry is finished and submitted. I've named it MegaHAL, after
another of my programs. It achieves a score that is, on average,
17.5 times higher than the score achieved by the second best algorithm,
which is "Beat Last Move". I will be interested to see what methods
other people come up with to play. Should be fun!
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -573- http://ciips.ee.uwa.edu.au/~hutch-+
Darse Billings
sample program, called freqbot2().
This is the same algorithm as freqbot(), but uses static variables
to avoid re-scanning the entire history array each turn. This
technique may save you vast amounts of execution time, so please
consider it.
There are more than 10 entries already, from all around the world.
BTW, if you think dealing with my programming style is awkward, I
can assure you that my problems are far greater. :)
Also, I'm not ignoring follow-up messages, but I do not read news
regularly. You will generally get much better response by sending
me e-mail, and checking the webpage for updates to the FAQ.
For up to date information, check www.cs.ualberta.ca/~darse/rsbpc.html
- Darse.
int freqbot2 ()
{
/* maintain stats with static variables to avoid re-scanning the
history array */
static int rcount, pcount, scount;
int opp_last;
if( opp_history[0] == 0 ) {
rcount = 0; pcount = 0; scount = 0; }
else {
opp_last = opp_history[opp_history[0]];
if ( opp_last == rock) { rcount++; }
else if ( opp_last == paper) { pcount++; }
else /* opp_last == scissors */ { scount++; }
}
if ( (rcount > pcount) && (rcount > scount) ) { return(paper); }
else if ( pcount > scount ) { return(scissors); }
else { return(rock); }
Darse Billings
> D'oh! I've been programming my entry under the misapprehension that
> the only external information we're allowed to use is the history
> arrays.
Sorry, I should have made that clearer.
A number of people are viewing this contest as much more complicated
than it really is. The intention is to write a program that can
predict what the opponent will do next, even while they're trying to
do the same to you. A tournament program similar to the one posted
will be used for the official competition. Just make your function
fit the program, and everything will be fine.
Trying to alter the results by other means, such as manipulating the
tournament program, trying to crack random(), or fiddling with the
arrays used by others, is "not in the spirit of the competition".
> What would be *really* useful is the ability to find out who your
> opponent is, so, if you're meeting it for the second time, you can
> use what you've learned about it previously. Is there any scope
> for doing this, or are we limited to the two history arrays and the
> trials define?
Opponents are anonymous. The basic model is that you will be facing
each opponent once during the round-robin tournament, but the number
of tourneys is defined in any case. I may run multiple tournaments
to achieve statistical significance, but each meeting should be with
no memory of previous encounters.
- Darse.
Darse Billings
> to alter the results by other means, such as ... trying to
> crack random(), ... is "not in the spirit of the competition".
I would like to announce that the winner of the unofficial
"supermodified" class of programs is Tim Dierks, for his
submission of Nostradamus, which reverse-engineers random(),
scoring 100% against Random (Optimal). Congratulations Tim!
With his obvious technical skill, and his "cheat early and often"
attitude, Tim could have a promising career as an AI programmer
in the computer games industry. :)
Obviously, his function will not be competing in the official
event. Furthermore, the random() function may be replaced with
a different RNG (but this will not affect any entries).
Darse Billings
information is available on the webpage, at:
www.cs.ualberta.ca/~darse/rsbpc.html
There have been 18 entries to date, coming from Canada, the US,
Mexico, Great Britain, Germany, the Netherlands, Finland, and
Australia.
FAQ (frequently asked questions)
Q: Can you tell me what kind of hardware/OS the competition will be
run on?
A: That has not yet been decided. It may be a Sun Ultra-5 Workstation
running Unix (Solaris), or it could be a fast PC running Linux. If
the code compiles cleanly with gcc, it shouldn't matter too much.
Q: Can I enter Random (Optimal)?
A: No. You shouldn't want to anyway, because it is guaranteed to
finish in the middle of the pack. It definitely will not finish
in first place, because it cannot exploit the weaker programs.
Q: Are we allowed to have other functions, or must everything be
done in a single function?
A: You may have auxiliary functions, provided they can all be placed
together in the tournament program. There must, of course, be
only one player that is called for each move.
Q: Can I produce my own random numbers, or must I use random
and/or the provided flip_biased_coin and biased_roshambo?
A: You may use your own random number generator, but it must use
a fixed seed, so that the tournament results are reproducible,
given a fixed seed to srandom().
Q: Can I use the defined trials constant to know how many trials
will be played (for defining array sizes, for example)?
A: Yup, that's what constants are for. :)
Q: RoShamBo? I thought that was the game where you and Cartman
take turns kicking each other in the nuts as hard as you can.
A: No, that's Roshambeau. Notice that alternating turns (rather
than simultaneous) affects the strategy. Going first tends to
be somewhat advantageous in Roshambeau.
Q: Can I enter more than one program?
A: You may, provided they are completely independent (ie. one does
not lose to the other by a large margin, in order to stack the
results). If I have any doubts, I will take only the last entry,
or I will assign a zero (ie. break-even) result to that match-up.
Q: Do you want C source that compiles to an object file, or do
you want code you can cut and paste?
A: Cut and paste. You should be able to just plug it into the
sample tournament program.
Q: Do you plan to use the same scoring system for the competition
that your example program has?
A: Yes and no. There will effectively be two divisions, and all
programs will participate in both. In the round-robin format
used in the sample program, the magnitude of each match counts.
The winner of this competition will be the program that is most
efficient at detecting and exploiting weaker programs.
The second format is "evolutionary", where the lowest finishers
are systematically eliminated, until only the strongest of the
strong algorithms are playing each other. The winner of this
event will be the program that beats all other opponents, even
if only by a small margin.
Oliver Roese
Darse Billings <da...@cs.UAlberta.CA> schrieb in im Newsbeitrag:
7rrno7$ssm$1...@scapa.cs.ualberta.ca...
> Q: Can I enter Random (Optimal)?
>
> A: No. You shouldn't want to anyway, because it is guaranteed to
> finish in the middle of the pack. It definitely will not finish
> in first place, because it cannot exploit the weaker programs.
>
I could think of the following strategy: Try to exploit the weaker programs
and fall back to the "sane" strategy, if something went wrong. Would this be
"in the spirit of competition"?
Oliver Roese
Angela Hu
1. USB LL3 Cable for @USD30.00
2. Home PNA card for @USD85.00 (ALL include worldwide carrier charge by EMS)
----------------------------------------------------------------------------
An innovative USB LL3 cable (bridge cable) now direct selling from manufacturer
/ exporter to your door.
Feature: 1. Transit/Delete files between 2 computers.
2. No file name length limitation. Working under windows
operation.
3. Max. Transit Speed about 4M bps.
4. Package by white box
include USB bridge cable, driver and user manual.
We also have USB Hub, Modem, ADSL Modem (G.Lite and Full rate), USB To USB
Networking Bridge Cable (Super Cable), USB To Ethernet Adapter UE45 and PC Net
Speeder(2 Ethernet Adapter to be a network) ready for your request.
Serious buyer please contact us as below:
Name: Ms. Cheryl Cheng
Company: Univex Microtechnology Corporation.
Address: 2, Tze-Chiang 3rd Road, Chung-Li Industrial Park Taoyuan
Hsien, 320, Taiwan, R.O.C.
Tel: 886-3-4512100 ext. 503
Fax: 886-3-4512800
e-mail: che...@univex-group.com.tw
http://www.univex-group.com (telecom product)
Payment: By credit card or cash in advanced
Delivery: Within 14 days after received your payment.
Warranty: 12 months.
Jason Hutchens
>I could think of the following strategy: Try to exploit the weaker programs
>and fall back to the "sane" strategy, if something went wrong. Would this be
>"in the spirit of competition"?
I don't see why not! One of the things that I'm enjoying so much about
this competition is that on the surface it appears to be a pretty lame
waste of time (after all, we know what the optimal strategy is), but
when you look more closely, it reveals itself as the perfect test-bed
for predictive algorithms. The program which performs the best will be
the one which can predict what its opponent's strategy is, and turn it
against them, while, at the same time, preventing its opponent from
doing the same to it! A good predictive algorithm will always "fall-back"
when it fails to learn the opponent's model.
Should be fun fun fun! Can't wait to see the results, and the details
of the other algorithms entered!
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -683- http://ciips.ee.uwa.edu.au/~hutch-+
Sunir Shah
comp.ai.games, I don't read it very often. That could explain
the last changed date on the FAQ being April, '96.. it could
also explain why I handed it off. Speaking of which, where
is David anyway?
I digress.
> I don't see why not! One of the things that I'm enjoying so much about
> this competition is that on the surface it appears to be a pretty lame
> waste of time (after all, we know what the optimal strategy is),
That depends on what you mean by optimal. What is optimal?
From a game theoretic point of view, it means the highest guaranteed
strategy, which is random. Because RoShamBo is zero-sum, you can't
be guaranteed to do any better than averaging zero because the other
person can use the same strategy to guarantee himself to "win." You
can't both win! It's zero sum!
However, this is hardly going to get you to Vegas. The optimal
strategy in RoShamBo has got to be to predict the other agent's
strategy and use that against them.
After all, as soon as they go non-random, they become at least
moderately deterministic. [Well, both my bots are at least random
if everything goes against them]. If they are deterministic, they are
simulatable on another Turing Machine (e.g. your own bot)/another
similar Kantian thingy (e.g. you) and thus predictable.
> when you look more closely, it reveals itself as the perfect test-bed
> for predictive algorithms. The program which performs the best will be
> the one which can predict what its opponent's strategy is, and turn it
> against them, while, at the same time, preventing its opponent from
> doing the same to it!
I'm going rock.
Speaking of which, this game is really missing the funnest part of
RoShamBo.. the psyche out. :)
Seriously, you're right. I'd like to see which bots suffer from analysis
paralysis.
> A good predictive algorithm will always "fall-back" when it fails
> to learn the opponent's model.
Really?
Why must it be so schizophrenic? Why can't it just naturally adapt
as part of its behaviour?
Neither of my bots "fall-back," if they fail to learn the opponent's
model; they just get pretty random while trying to figure it out.
SS
Jason Hutchens
>That depends on what you mean by optimal. What is optimal?
Achieving the highest possible score, on average.
>> A good predictive algorithm will always "fall-back" when it fails
>> to learn the opponent's model.
>
>Really?
Of course!
>Why must it be so schizophrenic? Why can't it just naturally adapt
>as part of its behaviour?
>
>Neither of my bots "fall-back," if they fail to learn the opponent's
>model; they just get pretty random while trying to figure it out.
Oh, I see you probably don't know what "fall-back" means.
What I meant by that is that a predictive model will attempt to use
as much information about the opponent that it can in order to predict
what the opponent's next move is going to be.
If it is not able to make a prediction, however, some of this information
must be discarded. The constraints applied to the predictive model
need to be relaxed.
If all of the information is discarded, the predictor behaves exactly
like the random one. This is when it has fallen all the way back!
This is also the a priori state of the predictor (i.e. before any
predictions are made).
It will be fun putting our bots head-to-head in the contest, and
analysing our algorithms afterwards. Good luck!
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -707- http://ciips.ee.uwa.edu.au/~hutch-+
Bjorn Reese
>
> You know for (until a month ago) "maintaining" the FAQ for
> comp.ai.games, I don't read it very often. That could explain
> the last changed date on the FAQ being April, '96.. it could
> also explain why I handed it off. Speaking of which, where
> is David anyway?
David who?
Gaspard Petit
"slow" can it be? 1000 trials takes about 3 seconds on my poor 75mHz,
is that too slow? I could certainly optimize it, but I don't want to
waste time for nothing...
It has 6 layers of pattern finding and it modifies itself depending
whether it believes it has found a pattern or not and it switches to a
defence mode (not random) if something goes wrong... It's going to
crunch anything previously done ;) Even I, can't win against it...
Gaspard Petit
David J Burbage
I have taken ownership of the FAQ from Sunir, and am halfway through
revamping it for re-publication here. I've removed a lot of dead wood,
references to old pages and quirky Sunir comments :-)
Please feel free to pass comments when I've re-posted it here, and
we can try to make it a real picture of the FAQ in Game AI.
cheers
David J Burbage
Blue Legend Software
email: da...@blueleg.co.uk
web: www.blueleg.co.uk
Darse Billings
> That depends on what you mean by optimal. What is optimal?
> However, this is hardly going to get you to Vegas. The optimal
> strategy in RoShamBo has got to be to predict the other agent's
> strategy and use that against them.
There is an important distinction between "optimal" and "maximal".
You want to write a maximal algorithm -- one which exploits an
opponent's weaknesses. To do this, you must always take a risk,
playing sub-optimally to gain a positive expectation. If someone
out-thinks you, you'll lose.
In this competition, if you play optimally, you'll still lose, because
you are told there will be sub-optimal players in the tournament.
Drawing every match isn't going to cut it.
> I'm going rock.
> Speaking of which, this game is really missing the funnest part of
> RoShamBo.. the psyche out. :)
I thought of having an "I'm going rock" flag. Maybe next time. :)
Mark Zwicker
Some of us are missing a big point of the tournament... winning. I have no
interest in entering as almost all predictave models can be cracked. <why I
don't bother trying to code one>. Almost all predictave models will fall into
this very trap.
Start playing the game with a predefined set of starting routines. "Give"
the predictave model a very easy prediction and then exploit it. If I always
answer Rock after I just played paper for the first 50 turns and always answer
Paper after I just played rock the predictave algorythim will very quickly
"learn" your routine, thus weighting it's own responce as a condition of your
answers. thus after 50 plays of always loosing I can then go on a 100+ run of
winning. <as your program will be conditioned and weighed to answers.
No program can account for the "impluse" of any situation. This competition
is a good BASE-LINE starter for prediction but nothing will "in the end" beat
the random effect of the mind. There is no way any of these programs should be
able to beat a human. "Or even a really good randomizer."
My 2 cents worth.
Perry Friedman
http://www.sportsrocket.com/roshambo/
or for one which you can register for and play over a longer period of time
(1 week) and keep a running record, try:
http://contest1.pickem.com/roshambo/
You may want to register for the "Pro" version so you can have your session
saved and resumed.
Both of these beat most humans, and the more the person plays, the better it
does. In fact, if you "try to be random", you will fail miserably. Most
people are quite POOR randomizers. Most people will, for example, not
go rock 10 times in a row because they think "that is not random". That alone
makes them have some predictability. I believe you will be quite surprised
by the success of the bots above. Try playing, say, 500 games against the
second bot. Let me know how you do.
Perry
aka
Roshamboy
In article <37E80525...@ns.sympatico.ca>,
John A. D. Cervanyk
>
> frie...@Xenon.Stanford.EDU (Perry Friedman) writes:
>
> >Try playing the bot at
> >http://www.sportsrocket.com/roshambo/
> >or for one which you can register for and play over a longer period of time
> >(1 week) and keep a running record, try:
> >http://contest1.pickem.com/roshambo/
> >You may want to register for the "Pro" version so you can have your session
> >saved and resumed.
>
> >Both of these beat most humans, and the more the person plays, the better it
> >does. In fact, if you "try to be random", you will fail miserably. Most
> >people are quite POOR randomizers. Most people will, for example, not
> >go rock 10 times in a row because they think "that is not random". That alone
> >makes them have some predictability. I believe you will be quite surprised
> >by the success of the bots above. Try playing, say, 500 games against the
> >second bot. Let me know how you do.
>
> >Perry
> >aka
> >Roshamboy
>
>
> gj
I was thinking of a single die.
--
Take care,
John A. D. Cervanyk --- ja...@dnvr.uswest.net
gj bart
Perry Friedman
will likely be predictable. You could use a digitial stopwatch that goes
hundreds (or thousands) of a second, and use the last digit... that might be
more random, but still not completely random.
Perry
In article <7s9gm0$8...@dfw-ixnews19.ix.netcom.com>,
Sunir Shah
> I have taken ownership of the FAQ from Sunir, and am halfway through
>revamping it for re-publication here. I've removed a lot of dead wood,
>references to old pages and quirky Sunir comments :-)
I went through my website today. I have to burn a lot of it.
I wrote most of that in my "salad days." Ugh.
By the way, in the meantime, people can read the existing FAQ,
quirky Sunir comments and all, at
http://www.intranet.ca/~sshah/cagfaq.html
SS
Sunir Shah
Darse Billings wrote in message <7s8na2$o9f$1...@scapa.cs.ualberta.ca>...
>There is an important distinction between "optimal" and "maximal".
Good point.
> > I'm going rock.
>
> > Speaking of which, this game is really missing the funnest part of
> > RoShamBo.. the psyche out. :)
>
>I thought of having an "I'm going rock" flag. Maybe next time. :)
Well, you still couldn't do it justice. RoShamBo is better
in person.
As mentioned somewhere else, how do you
"psyche" out a bot? The bot has to have some sort
of emotions built into it in some form or the other;
that's easy. But trying to figure out a completely alien
persona, with no a priori knowledge of the player (well,
not after Darse told me to stop remembering) is a bit
much to offer.
I suppose you could attempt to think about how other
people may have constructed their bots and make psyche
out strategies reflecting your best guesses.
Hmm...
Or you could just cheat. I'm going dynamite. :)
SS
gj bart
>And do what? Use the seconds? That's no good. Your interval between picks
>will likely be predictable. You could use a digitial stopwatch that goes
>hundreds (or thousands) of a second, and use the last digit... that might be
>more random, but still not completely random.
>Perry
What is this we're dealing with, HAL 9000? Sheesh. Use *two*
digital watches. Use a modulo of the fresh-deck ordinal value of your
2nd down card. Use shifting criteria. Use your imagination.
gj
Perry Friedman
to "go random" without using outside sources for that randomness, they
will not do very well. And of course, even a die is not truly "random",
just chaotic.
Perry
In article <37E8496F...@dnvr.uswest.net>,
John A. D. Cervanyk <ja...@dnvr.uswest.net> wrote:
>gj bart wrote:
>>
>> frie...@Xenon.Stanford.EDU (Perry Friedman) writes:
>>
>> >Try playing the bot at
>> >http://www.sportsrocket.com/roshambo/
>> >or for one which you can register for and play over a longer period of time
>> >(1 week) and keep a running record, try:
>> >http://contest1.pickem.com/roshambo/
>> >You may want to register for the "Pro" version so you can have your session
>> >saved and resumed.
>>
>> >Both of these beat most humans, and the more the person plays, the better it
>> >does. In fact, if you "try to be random", you will fail miserably. Most
>> >people are quite POOR randomizers. Most people will, for example, not
>> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>> >go rock 10 times in a row because they think "that is not random". That alone
>> >makes them have some predictability. I believe you will be quite surprised
>> >by the success of the bots above. Try playing, say, 500 games against the
>> >second bot. Let me know how you do.
>>
>> >Perry
>> >aka
>> >Roshamboy
>>
>> Use your (digital) watch.
>>
>> gj
>
John A. D. Cervanyk
>
> Look at what you highlighted. A die is not a person. If a person tries
> to "go random" without using outside sources for that randomness, they
> will not do very well. And of course, even a die is not truly "random",
> just chaotic.
>
> Perry
>
I understand that a human does not do well trying to be random. But
I don't understand your distinction of a die being chaotic and not truly
random. If you have a fair die and roll before every turn why isn't it
random?
Perry Friedman
chaotic. Coin tosses, dice rolling, roullette, etc. are chaotic. It's been
a while, so I am not certain of exact definitions, but chaotic means a small
perturbation causes a large end effect. Random means truly un-predictable
except via probabilities. Some quantum events are random and truly cannot
be determined with certainty, and only have probabilistic outcomes. Chaotic
events can be determined exactly, if all parameters are known exactly.
You can flip a coin, or roll a die, or drop a roullette ball onto a rotating
table, and if you actually knew all the parameters, you should be able to
guess the correct outcome. If you rolled a fair die exactly the same
way every time (starting with the same orientation, etc.), you should get
the same outcome every time. It's just that very small inaccuracies in
measurement, or very small variations in how the die is rolled, will lead
to incorrect guesses of outcome.
Perry
In article <37E932BE...@dnvr.uswest.net>,
John A. D. Cervanyk <ja...@dnvr.uswest.net> wrote:
Daryl Sterling
On Wed, 22 Sep 1999, John A. D. Cervanyk wrote:
> > will not do very well. And of course, even a die is not truly "random",
> > just chaotic.
> >
> > Perry
>
> I understand that a human does not do well trying to be random. But
> I don't understand your distinction of a die being chaotic and not truly
> random. If you have a fair die and roll before every turn why isn't it
> random?
>
> John A. D. Cervanyk --- ja...@dnvr.uswest.net
Well,
I guess if you REALLY want to be nasty, you could say the only way a die
can be TRULY random it if a perfectly uniform die is thrown in a vacuum
onto a perfectly flat surface at random angular velocities (for all axes
of rotation). And the result
But if that's not what he meant, then I don't understand him either. :)
Daryl
dste...@ucsd.edu
Randolph M. Jones
>
> >
> > Look at what you highlighted. A die is not a person. If a person tries
> > to "go random" without using outside sources for that randomness, they
> > just chaotic.
> >
> > Perry
> >
>
> I understand that a human does not do well trying to be random. But
> I don't understand your distinction of a die being chaotic and not truly
> random. If you have a fair die and roll before every turn why isn't it
> random?
I'm guessing that Perry is making a distinction between "things that we
couldn't predict 100% of the time even if we had *all* the available
information" (random) and "things that we could predict 100% of the time
if we had all the available information, but getting all the information
is 'really hard'" (chaotic).
I'm not sure why the distinction is important in the present context,
however, so perhaps my guess is wrong.
Randy Jones
Philip Wilson
> I guess if you REALLY want to be nasty, you could say the only way a die
> can be TRULY random it if a perfectly uniform die is thrown in a vacuum
> onto a perfectly flat surface at random angular velocities (for all axes
> of rotation).
In this case the die is not random. You have imposed an external source of
randomness i.e. the random angular velocities. If this source of randomness
is excluded then the exercise is chaotic but not random - unless of course
we move down to the level of quantum mechanics and the possibility of
quantum probabilities making some difference at the macro level - but that
sort of discussion would be completely unwarranted for the topic of "how a
human can play RoShamBo".
Philip
David J Burbage
The point is, if you can generate random numbers, the payoff will tend towards
1:1:1 win:tie:lose.
If you can apply any AI at all, you should diverge from this result. The
direction
of the divergence is dependent on the power of the AI and what it is playing.
Innit?
David J Burbage
Daryl Sterling wrote:
> On Wed, 22 Sep 1999, John A. D. Cervanyk wrote:
>
> > > will not do very well. And of course, even a die is not truly "random",
> > > just chaotic.
> > >
> > > Perry
> >
> > I understand that a human does not do well trying to be random. But
> > I don't understand your distinction of a die being chaotic and not truly
> > random. If you have a fair die and roll before every turn why isn't it
> > random?
> >
> > John A. D. Cervanyk --- ja...@dnvr.uswest.net
>
> Well,
>
> I guess if you REALLY want to be nasty, you could say the only way a die
> can be TRULY random it if a perfectly uniform die is thrown in a vacuum
> onto a perfectly flat surface at random angular velocities (for all axes
Peter James
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
Randolph M. Jones
>
> Aren't we getting a little off-thread here :-)
>
> The point is, if you can generate random numbers, the payoff will tend towards
> 1:1:1 win:tie:lose.
>
> If you can apply any AI at all, you should diverge from this result. The
> direction
> of the divergence is dependent on the power of the AI and what it is playing.
>
> Innit?
I believe part of the issue is that there is no such thing as a
"powerful" AI in this game. Because of the nature of the game, any AI
that is non-random is also going to be theoretically predictable. Thus
any AI that displays advantages over some opponents will display
disadvantages to other opponents. So this becomes not a contest of who
can build the "best" AI for this game, rather a crap-shoot determining
who is luckiest in choosing a strategy that is effective against the
other AIs that happen to get entered into this particular contest.
David J Burbage
I disagree. Sorry :-)
There has to be an element of AI because the computer is actively trying to find
patterns and strategies which will enable it to succeed. The success may well
be dependent on the type of opponent it meets, on the other hand, it may not.
A truly fantastic piece of AI might detect opponents who
1) use historical analysis of successful patterns to choose the next item
eg I chose rock,rock,rock,scissors and won 4/4. If I chose rock,rock and
won 2/2 then will I chose rock again? Or will the opponent now chose paper
because it has predicted I will chose rock because it worked last time?
2) use random guesses : the AI would work out the proportion of random
guesses. By some mathematical means (least squares?) you could work out
the deviation from a truly random norm. From this you could possibly work
out the frequency that random choices have been made. I wouldn't underestimate
the simplicity of this task.
3) use sequences of moves in response to my own AI's moves.
Just because there's a large element of apparent randomness in the game doesn't mean
you can't apply AI successfully.
If as you suggest an AI will 'pick a strategy' it therefore follows that a better AI
might be able to dynamically choose between multiple strategies and measure
the results.
I could go on about Prisoner's Dilemma but I won't.....
David J Burbage
Daryl Sterling
On Thu, 23 Sep 1999, David J Burbage wrote:
> Aren't we getting a little off-thread here :-)
> The point is, if you can generate random numbers, the payoff will tend towards
^^^^^^^^^^^^^^
Isn't this what we're talking about ?
The problem of generating TRULY random numbers ? Wait, or is it
RoShamBo? Ah crap. I dunno. :)
To get back on track. If RoShamBo is Rock-Paper-Scis, what is KaiKaiBo ?
I thought KaiKaiBo was R-P-S and RoShamBo was the ball kicking game from
South Park :)
Daryl
Jason Hutchens
>I believe part of the issue is that there is no such thing as a
>"powerful" AI in this game. Because of the nature of the game, any AI
>that is non-random is also going to be theoretically predictable. Thus
>any AI that displays advantages over some opponents will display
>disadvantages to other opponents. So this becomes not a contest of who
>can build the "best" AI for this game, rather a crap-shoot determining
>who is luckiest in choosing a strategy that is effective against the
>other AIs that happen to get entered into this particular contest.
You're right in one respect; this contest isn't about the game, it's
about the algorithms. But I disagree with you that the contest is
measuring "luck". Rather, I believe it is an ideal way of testing the
effectiveness of different approaches to the prediction/inference
problems.
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -733- http://ciips.ee.uwa.edu.au/~hutch-+
rjo...@colby.edu
<Pine.LNX.4.10.990924...@nuit.ee.uwa.edu.au>,
Jason Hutchens <hu...@ee.uwa.edu.au> wrote:
> On Thu, 23 Sep 1999, Randolph M. Jones wrote:
>
> >I believe part of the issue is that there is no such thing as a
> >"powerful" AI in this game. Because of the nature of the game, any
AI
> >that is non-random is also going to be theoretically predictable.
Thus
> >any AI that displays advantages over some opponents will display
> >disadvantages to other opponents. So this becomes not a contest of
who
> >can build the "best" AI for this game, rather a crap-shoot
determining
> >who is luckiest in choosing a strategy that is effective against the
> >other AIs that happen to get entered into this particular contest.
>
> You're right in one respect; this contest isn't about the game, it's
> about the algorithms. But I disagree with you that the contest is
> measuring "luck". Rather, I believe it is an ideal way of testing the
> effectiveness of different approaches to the prediction/inference
> problems.
But what are we going to learn when a program that uses a purely random
(pardon me, chaotic) approach ties for the championship?
Sent via Deja.com http://www.deja.com/
Before you buy.
Will Dwinnell
"It's been a while, so I am not certain of exact definitions, but
chaotic means a small
perturbation causes a large end effect."
That is one typical quality of chaotic systems, but it is also true of
divergent systems, including purely random ones.
"Random means truly un-predictable except via probabilities."
More or less: the probabilities do not predict, they summarize.
"Some quantum events are random and truly cannot be determined with
certainty, and only have probabilistic outcomes."
This gets into what is essentially philosophy and what one is calling
'inside' or 'outside' the system in question. Presumably, anything
outside of the system might be considered random if its behavior is
sufficiently complex as to defy analysis.
"Chaotic events can be determined exactly, if all parameters are known
exactly."
Only in theory. Of course, sensitive dependence on initial conditions
(which you mentioned earlier) will quickly wreck such predictions and
real-world systems tend not be purely chaotic, but include an element of
randomness as well.
Will Dwinnell
Will Dwinnell
"You can flip a coin, or roll a die, or drop a roullette ball onto a
rotating table, and if you actually knew all the parameters, you should
be able to guess the correct outcome. If you rolled a fair die exactly
the same way every time (starting with the same orientation, etc.), you
should get the same outcome every time. It's just that very small
inaccuracies in measurement, or very small variations in how the die is
rolled, will lead to incorrect guesses of outcome."
Yes, but this amounts to saying that inaccuracies in measurement wreck
attempts at prediction, and would be true for stable, chaotic and
divergent systems. This feature of coin flipping behavior does not
imply that it is chaotic.
Will Dwinnell
Will Dwinnell
"There is an actual definitional difference in physics between random
and chaotic."
Yes, and the definition has to do with correlation over time. Chaotic
processes may appear random, but are in fact correlated over time.
"Coin tosses, dice rolling, roullette, etc. are chaotic."
Successive flips of a coin are not correlated, therefore they cannot be
chaotic. Chaotic systems adhere (at least statistically) to some
dynamic with finite degrees of freedom. Coin tosses and so forth are
not restricted to any such phase space.
Will Dwinnell
David desJardins
> A strong RoShamBo program will be capable of defeating a large field
> of weaker programs, and the exact composition of the field will have
> little bearing on the outcome of the tournament. If you don't believe
> it, wait for the results of the competition. - Darse. --
I don't believe it, and I don't feel that I need to wait to see the
results before forming an opinion.
If it really doesn't matter, why seed the competition with stupid
programs to pick on?
And who came up with the stupid name?
David desJardins
Darse Billings
> I believe part of the issue is that there is no such thing as a
> "powerful" AI in this game. Because of the nature of the game, any
> AI that is non-random is also going to be theoretically predictable.
> Thus any AI that displays advantages over some opponents will display
> disadvantages to other opponents.
This is true. Nevertheless, there is a heirarchy of strong programs.
> So this becomes not a contest of who
> can build the "best" AI for this game, rather a crap-shoot determining
> who is luckiest in choosing a strategy that is effective against the
> other AIs that happen to get entered into this particular contest.
This is false. The strongest programs are objectively stronger than the
rest, just as the best chess programs beat weaker ones, despite the fact
that "chess is a draw". A strong RoShamBo program will be capable of
defeating a large field of weaker programs, and the exact composition of
the field will have little bearing on the outcome of the tournament.
If you don't believe it, wait for the results of the competition.
- Darse.
--
"There's no sense in searching for perfection
when you're making successful mistakes" -The Tragically Hip.
Jason Hutchens
>Darse Billings <da...@cs.UAlberta.CA> writes:
>> A strong RoShamBo program will be capable of defeating a large field
>> of weaker programs, and the exact composition of the field will have
>> little bearing on the outcome of the tournament. If you don't believe
>> it, wait for the results of the competition. - Darse. --
>
>I don't believe it, and I don't feel that I need to wait to see the
>results before forming an opinion.
Hahaha! This is perfect irony! The whole business of inference is about
using as much information as possible to form an opinion. Your statement
above is equivalent to the RoShamBo entry which plays "rock" every time,
regardless of the evidence ;^)
I will be interested in your comments after Darse posts the results of the
contest to this newsgroup. I hope you will have the decency to respond
to his post saying that the opinion has changed.
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -744- http://ciips.ee.uwa.edu.au/~hutch-+
Jason Hutchens
Firstly, it won't tie. Sure, it will break even on average against all
the entries. But some of the entries will win on average.
But what we'll actually learn is something about predictors. That's what
is so interesting about the game. In order to win, you need to be able
to infer the algorithm your opponent is using, and turn it against them
Of course, your opponent may be doing the same thing, but perhaps in a
different way. Therefore, this game is a good testbed for such programs.
The program which can infer its opponent's strategy most effectively will
score the highest, on average.
The game itself has little to do with it. The fact that the game embodies
a process of "mutual prediction", if you like, is what I find interesting.
There are many, many applications of a good inference engine, such as data
compression, speech recognition, natural language acquisition, syntactic
pattern recognition, stock market analysis, human genome modelling, weather
forecasting, text generation, email classification, data mining, speech
segmentation, input methods for disabled users, author identification
and RoShamBo! Playing the game of RoShamBo is actually a very good way of
comparing these algorithms with one another.
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -743- http://ciips.ee.uwa.edu.au/~hutch-+
Beldin the Sorcerer
> > So this becomes not a contest of who
> > can build the "best" AI for this game, rather a crap-shoot determining
> > who is luckiest in choosing a strategy that is effective against the
> > other AIs that happen to get entered into this particular contest.
>
> This is false. The strongest programs are objectively stronger than the
> rest, just as the best chess programs beat weaker ones, despite the fact
> that "chess is a draw".
When has chess been shown to be a draw?
Often, the best programs draw weaker ones, because the weaker ones still use
standard defenses.
A strong RoShamBo program will be capable of
> defeating a large field of weaker programs, and the exact composition of
> the field will have little bearing on the outcome of the tournament.
> If you don't believe it, wait for the results of the competition.
> - Darse.
I would wager a human would do better at this than a program.
Unknown
>And do what? Use the seconds? That's no good. Your interval between picks
>will likely be predictable. You could use a digitial stopwatch that goes
>hundreds (or thousands) of a second, and use the last digit... that might be
>more random, but still not completely random.
Really? How so?
I really doubt that you are going to find a much better
random number generator than the last digit of a stopwatch
which counts in the thousandths of seconds. Especially if
the one who stops the watch doesn't look at the watch when
he stops it.
I know from that the human ability to resolve time is at
this bound, so doing things at this "rhythm" would seem
pretty darn improbable.
- Andrew
Perry Friedman
outside sources of randomness/pseuorandomness. Just try yourself against the
bot and see how you do.
Perry
In article <7slj68$obp$1...@nntp2.atl.mindspring.net>,
Beldin the Sorcerer <bel...@sprynet.com> wrote:
>
>Perry Friedman <frie...@Xenon.Stanford.EDU> wrote in message
>news:7skrmt$g7m$1...@nntp.Stanford.EDU...
>> I accept your wager. I have empirical evidence that a computer can defeat
>> most humans at roshambo. The various bots I have programmed and put on
>the
>> web have shown time and again that they beat most humans. Even the bots
>> out there that I have that only keep people's BEST performance (you can
>> keep playing it, and it saves your all time best 100,250, and 500 game
>> records) shows an overall positive score for all levels, getting better
>> at each level. The more you play, the better it gets.
>We'll see.
>
>
>>
>> Some people can beat the bot, especially over the short term, but only 16
>> out of 43 people to play 500 games show a positive score on the one bot,
>and
>> again, this takes their best ever 500 game score.
>Lots of people are lazy.
>Let me get Kasparov on the phone.
>
>>
>> If you are serious about your wager, I will be more than happy to wager
>with
>> you, given the right parameters (a reasonable time limit, no outside
>source
>> of randomness, etc.).
>Define "Outside source of randomness". I'm a human, I don't have a program.
>The correct strategy is to play randomly.
>
>I have a simple algorythym.... How about I post the first 50 calls, and see
>how well your bot does predicting the second 50?
>
>
Beldin the Sorcerer
> Like I said, humans are notoriously bad at trying to be random, without
> outside sources of randomness/pseuorandomness. Just try yourself against
the
> bot and see how you do.
>
> Perry
>
>
Still waiting.
David J Burbage
for the competition, is that a random player will perform less well against
some of the deliberately weaker opposition, and therefore the program
which is best able to exploit them without becoming predictable itself
will be the winner.
Darse, do I have this about right?
David J Burbage
Jason Hutchens
>Perry Friedman <frie...@Xenon.Stanford.EDU> wrote in message
>news:7sman0$r0d$1...@nntp.Stanford.EDU...
>> Like I said, humans are notoriously bad at trying to be random, without
>> outside sources of randomness/pseuorandomness. Just try yourself against
>the
>> bot and see how you do.
>>
>> Perry
>>
>>
>I requested a formal definition of "outside source of randomness"
>
>Still waiting.
Okay, I'll give it to you, since it's so bloody obvious anyway.
When the human being plays the bot, the human being is only allowed to
decide what their next move is using their knowledge of the history of
the game so far, and their brain. They are not allowed to use any
external devices, such as calculators, digital watches, coins, dice,
computer programs which generate pseudo-random numbers or whatever.
Why don't you just play his damn bot instead of filibustering? Afraid
it's going to beat you or something?
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -760- http://ciips.ee.uwa.edu.au/~hutch-+
Andrew Prock
>Randolph M. Jones wrote:
>
>I disagree. Sorry :-)
While you may disagree, the point is still valid.
It becomes a game of "I think he thinks I think..."
ad infinitum. Esentially it becomes a variant of
the thought process that very good poker players
go through.
A very good AI will stay one step ahead of the
opposition. The ideal strategy against any
*superior* AI is randomness. Once you figure
out that you are inferior, then you simply apply
the random algorithm and the game will converge
to 1:1:1 (win:tie:loss).
As for what your AI algorithm of choice is, well
there are a lot of options, some more interesting
than others, but it doesn't change the fact that
the optimal strategy falls within the form:
if (winning)
keepUsingMyAI
else
useRandom
If *all* the submissions follow this meta-algorithm,
then the results will be pretty dull.
- Andrew
Andrew Prock
>On Mon, 27 Sep 1999, Beldin the Sorcerer wrote:
>
>>Perry Friedman <frie...@Xenon.Stanford.EDU> wrote in message
>>news:7sman0$r0d$1...@nntp.Stanford.EDU...
>>> Like I said, humans are notoriously bad at trying to be random, without
>>> outside sources of randomness/pseuorandomness. Just try yourself against
>>the
>>> bot and see how you do.
>>>
>>> Perry
>>>
>>>
>>I requested a formal definition of "outside source of randomness"
>>
>>Still waiting.
>
>Okay, I'll give it to you, since it's so bloody obvious anyway.
>
>When the human being plays the bot, the human being is only allowed to
>decide what their next move is using their knowledge of the history of
>the game so far, and their brain. They are not allowed to use any
>external devices, such as calculators, digital watches, coins, dice,
>computer programs which generate pseudo-random numbers or whatever.
>
>Why don't you just play his damn bot instead of filibustering? Afraid
>it's going to beat you or something?
Somehow I doubt this is a fair contest. If the "bot" has access
to a random number generator, then I want one too. If this sounds
a bit unreasonable, then I suggest that the bot really isn't
outsmarting the opponents as much as out randomizing the opponent.
If I am to compete with a computer then I sure as heck would like the
same tools that it is using. Heck, is it fair to hand compute my
"random" number with pen and paper? What about using my own
"algorithm"?
If your argument is that "people" aren't better than the bot, I
really resent that. The bot is just the computational embodiment
of a particular human created strategy. Maybe your argument is that
computers are faster at computation than people, well...
... you got me there.
- Andrew
Perry Friedman
than the first move.
The other is probabilistic.
Try your hand on the deterministic one.
http://contest1.pickem.com/roshambo/
Perry
In article <7splqc$j...@spool.cs.wisc.edu>,
Jason Hutchens
>Somehow I doubt this is a fair contest. If the "bot" has access
>to a random number generator, then I want one too.
But if you use a random number generator, then you'll just play that all
the time, and you and the bot will draw on average. This doesn't measure
how good a human being is at predicting what the bot's next move will
be, so the game wouldn't have any interest. There would be no sense of
competition.
The whole point is to try to beat the bot, not draw with it, so you
shouldn't even need a random number generator in the first place.
>If your argument is that "people" aren't better than the bot, I
>really resent that.
No, I believe the whole argument is that a good predictive algorithm
will be able to consistently beat a human being because the moves the
human being makes are predictible. This is because a human being
cannot generate pseudo-random numbers without some sort of assistance.
Someone who posted to this thread did not agree with this claim.
Instead of actually going ahead and playing the algorithm, they
started filibustering by asking for definitions of this and that,
which suggests to me they know deep down that the bot would win, but
that they would find this humiliating ;^)
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -761- http://ciips.ee.uwa.edu.au/~hutch-+
Perry Friedman
Andrew Prock <jeffy...@yahoo.com> wrote:
>According to Jason Hutchens <hu...@ee.uwa.edu.au>:
>>On Mon, 27 Sep 1999, Beldin the Sorcerer wrote:
>>
>>>Perry Friedman <frie...@Xenon.Stanford.EDU> wrote in message
>>>news:7sman0$r0d$1...@nntp.Stanford.EDU...
>>>> Like I said, humans are notoriously bad at trying to be random, without
>>>> outside sources of randomness/pseuorandomness. Just try yourself against
>>>the
>>>> bot and see how you do.
>>>>
>>>> Perry
>>>>
>>>>
>>>I requested a formal definition of "outside source of randomness"
>>>
>>>Still waiting.
>>
>>Okay, I'll give it to you, since it's so bloody obvious anyway.
>>
>>When the human being plays the bot, the human being is only allowed to
>>decide what their next move is using their knowledge of the history of
>>the game so far, and their brain. They are not allowed to use any
>>external devices, such as calculators, digital watches, coins, dice,
>>computer programs which generate pseudo-random numbers or whatever.
>>
>>Why don't you just play his damn bot instead of filibustering? Afraid
>>it's going to beat you or something?
>
>a bit unreasonable, then I suggest that the bot really isn't
>outsmarting the opponents as much as out randomizing the opponent.
You can't really outrandomize your opponent. While randomizing is a
non-dominatable strategy, it is also non-dominating. I suppose you could
sit on a lead, but you won't dominate an opponent by going random.
>
>If I am to compete with a computer then I sure as heck would like the
>same tools that it is using. Heck, is it fair to hand compute my
>"random" number with pen and paper? What about using my own
>"algorithm"?
>
>If your argument is that "people" aren't better than the bot, I
>really resent that. The bot is just the computational embodiment
>of a particular human created strategy. Maybe your argument is that
>computers are faster at computation than people, well...
>
>... you got me there.
I grant you this one. Clearly, I can beat the bot, because I know it's
strategy. And clearly, if I played the same strategy as the bot against
people, I'd do just as well. All I am saying is that you can write
algorithms that can beat most people, and not only am I stating it
theoretically, I am stating it as a fact, as the bot's record shows.
Perry
smacleod
B,I went 43-23-34 and was waiting for the bot to make a play at me,it never
happened.Of course,maybe I got "lucky".
Steve "show me a bot that can beat me " Macleod
Beldin the Sorcerer
Jason Hutchens <hu...@ee.uwa.edu.au> wrote in message
news:Pine.LNX.4.10.99092...@nuit.ee.uwa.edu.au...
> On Mon, 27 Sep 1999, Beldin the Sorcerer wrote:
>
> >Perry Friedman <frie...@Xenon.Stanford.EDU> wrote in message
> >news:7sman0$r0d$1...@nntp.Stanford.EDU...
> >> Like I said, humans are notoriously bad at trying to be random, without
> >> outside sources of randomness/pseuorandomness. Just try yourself
against
> >the
> >> bot and see how you do.
> >>
> >> Perry
> >>
> >>
> >I requested a formal definition of "outside source of randomness"
> >
> >Still waiting.
>
> Okay, I'll give it to you, since it's so bloody obvious anyway.
>
> When the human being plays the bot, the human being is only allowed to
> decide what their next move is using their knowledge of the history of
> the game so far, and their brain. They are not allowed to use any
> external devices, such as calculators, digital watches, coins, dice,
> computer programs which generate pseudo-random numbers or whatever.
Unlike anyone in an actual game with a person, who could look at their watch
any damn time they wanted.
Why not saY I have to submit all my moves first too?
As long as you aren't modelling reality anyway
>
> Why don't you just play his damn bot instead of filibustering?
Because the correct strategy is to be random and look for a pattern in your
opponent.
Seeing as how I know the strategy, I'd like to be clear on the rules first.
Afraid
> it's going to beat you or something?
It might, in a statistically insignificant way.
Not the point of the exercise.
Beldin the Sorcerer
Jason Hutchens <hu...@ee.uwa.edu.au> wrote in message
news:Pine.LNX.4.10.99092...@nuit.ee.uwa.edu.au...
>
> >to a random number generator, then I want one too.
>
> the time, and you and the bot will draw on average. This doesn't measure
> how good a human being is at predicting what the bot's next move will
> be, so the game wouldn't have any interest. There would be no sense of
> competition.
>
The strategey is to play random unless an obvious pattern is played against
you.
It's a dumb game. Remember most of us said that at the beginning of this
discussion?
You could do the same thing with tic-tac-toe, but it'd be pointless.
> The whole point is to try to beat the bot, not draw with it, so you
> shouldn't even need a random number generator in the first place.
If you're predictable, you'll lose.
You need a source of randomness to be random until and unless your opponent
becomes predictable.
>
> >If your argument is that "people" aren't better than the bot, I
> >really resent that.
>
> No, I believe the whole argument is that a good predictive algorithm
> will be able to consistently beat a human being because the moves the
> human being makes are predictible. This is because a human being
> cannot generate pseudo-random numbers without some sort of assistance.
>
Neither can a computer.
> Someone who posted to this thread did not agree with this claim.
> Instead of actually going ahead and playing the algorithm, they
> started filibustering by asking for definitions of this and that,
> which suggests to me they know deep down that the bot would win, but
> that they would find this humiliating ;^)
No, you idiot, I asked for a definition of an outside source of randomness,
which you still haven't provided.
For instance, a watch... a coin, a die, etc.... all things I would use
playing another person.
John A. D. Cervanyk
>
> On Tue, 28 Sep 1999, smacleod wrote:
>
> >What is all the hype about guys? Using my A plan,without switching to plan
> >B,I went 43-23-34 and was waiting for the bot to make a play at me,it never
> >happened.Of course,maybe I got "lucky".
>
> experiment for themselves!
> +=-== === --= -====- =-- =--- - - =- -=-- -- ==- ---- = - =- - =-- --==--+
heH, I did too. I played until I had a score of +1 and quit.
--
Take care,
John A. D. Cervanyk --- ja...@dnvr.uswest.net
Perry Friedman
>
>Because the correct strategy is to be random and look for a pattern in your
>opponent.
>Seeing as how I know the strategy, I'd like to be clear on the rules first.
How can the correct strategy be "to be random and look for a pattern in
your opponent"? Are you proposing you LOOK but don't act on it? As soon
as you act on it, you are not being random.
> Afraid
>> it's going to beat you or something?
>It might, in a statistically insignificant way.
>Not the point of the exercise.
Anyhow, like I said, the bot I mentioned is completely deterministic, other
than the first move. Certainly, you could try to beat it, and once you
had a lead, then "lock in" the lead by going random. What I am saying is
that if you play it to try to beat it in any statistically significant way,
you will not WANT to go random. I am also saying that trying to go random
without using an outside source of randomness, will likely lead to you
getting thomped.
Perry
Perry Friedman
smacleod <smac...@home.com> wrote:
>What is all the hype about guys? Using my A plan,without switching to plan
>B,I went 43-23-34 and was waiting for the bot to make a play at me,it never
>happened.Of course,maybe I got "lucky".
>
>
>
>
>
Keep playing. See how you do at the 250 and 500 levels. Ah, I see you
did hit the 250 level. Looks like the bot regained a lot of ground on you:
86-82-82
Actually I see when you left off you were at:
105-105-102
I think the fact that the bot came back from it's 20 point deficit says
something (although I am not sure what).
If you manage to play all the way to the 500 level, we'll see where you
stand then.
Like I said, the more you play, the better it gets and the better it is
able to exploit patterns in your play.
Perry
Andrew Prock
>Beldin the Sorcerer <bel...@sprynet.com> wrote:
>>> Why don't you just play his damn bot instead of filibustering?
>>Because the correct strategy is to be random and look for a pattern in your
>>opponent.
>>Seeing as how I know the strategy, I'd like to be clear on the rules first.
>How can the correct strategy be "to be random and look for a pattern in
>your opponent"? Are you proposing you LOOK but don't act on it? As soon
>as you act on it, you are not being random.
I think this is what he was suggesting, you just have to be careful
that when you *do* act, you still seem random.
>>> Afraid it's going to beat you or something?
>>It might, in a statistically insignificant way.
>>Not the point of the exercise.
>Anyhow, like I said, the bot I mentioned is completely deterministic, other
>than the first move. Certainly, you could try to beat it, and once you
>had a lead, then "lock in" the lead by going random. What I am saying is
>that if you play it to try to beat it in any statistically significant way,
>you will not WANT to go random. I am also saying that trying to go random
>without using an outside source of randomness, will likely lead to you
>getting thomped.
Sure you do. This is what I meant by "out-randomizing" you want an
algorithm which *appears* random, but which still beats any thinking
opponent. Keeping your actions random looking keeps your opponent
from getting one step ahead of you.
I'll leave it as an exercise as to how one actually produces "random"
looking selections while still using winning strategies. Of course,
as I mentioned before, the *actual* correct strategy is to keep pounding
away with your AI till it's clear you are beat, THEN revert to a random
algorithm to lock out further losses. This *is* different from what
BTS suggests above, but not significantly.
- Andrew
Jason Hutchens
>What is all the hype about guys? Using my A plan,without switching to plan
>B,I went 43-23-34 and was waiting for the bot to make a play at me,it never
>happened.Of course,maybe I got "lucky".
Yay! Somebody has decided to get their hands dirty and perform the
experiment for themselves!
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -771- http://ciips.ee.uwa.edu.au/~hutch-+
| Unsolicited email advertising is treated with the contempt it deserves |
Jason Hutchens
>The bot is using a random number generator.
>The strategey is to play random unless an obvious pattern is played against
>you.
So? A chess program may look ahead 100 moves. Does that mean you'd want
to do the same if you played against one? My point is that if your opponent
is playing random moves, it doesn't matter what moves you play, because you'll
draw on average. And, if your opponent isn't playing random moves, then the
game will test how capable a human being is of prediction, provided that the
human being doesn't play random moves.
>It's a dumb game. Remember most of us said that at the beginning of this
>discussion?
Yes, it's dumb if you're only looking at the surface of the game. But
underneath you'll find a very good mechanism for measuring the effectiveness
of various predictive strategies. And there's nothing dumb about that.
>If you're predictable, you'll lose.
Wrong. If you're predictible, you'll lose to bots which can out-predict
you. That's the whole point. The bot that wins will be the one that is best
at predicting what it's opponent's strategy is, on average.
Wouldn't it be interesting to find out where a human being would come in this
game? Would they come first? Or would some of the better bots beat them?
You shouldn't underestimate the importance of a good predictive algorithm.
Applications abound.
>No, you idiot,
Oh, thanks very much. This is where I leave; I don't continue to debate
issues when they devolve into personal insults. It's a pity you couldn't
state your case more clearly. Goodbye.
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -780- http://ciips.ee.uwa.edu.au/~hutch-+
Andrew Prock
>
>>The bot is using a random number generator.
>>The strategey is to play random unless an obvious pattern is played against
>>you.
>
>So? A chess program may look ahead 100 moves. Does that mean you'd want
>to do the same if you played against one?
As I understand it Deep Blue looked forward 8 or 9 moves. Expert players
are around this depth, however they prune the search tree more agressivly.
And YES, Kasparov wanted to have a computer with him to help him explore
the space more fully.
>My point is that if your opponent
>is playing random moves, it doesn't matter what moves you play, because you'll
>draw on average. And, if your opponent isn't playing random moves, then the
>game will test how capable a human being is of prediction, provided that the
>human being doesn't play random moves.
>
>>It's a dumb game. Remember most of us said that at the beginning of this
>>discussion?
>
>Yes, it's dumb if you're only looking at the surface of the game. But
>underneath you'll find a very good mechanism for measuring the effectiveness
>of various predictive strategies. And there's nothing dumb about that.
Well, yes. Sort of. If it was required that the program be offensive
only, it might be more interesting. But defensive play involves using
randomness so that it is hard for your opponents to figure YOU out.
>>If you're predictable, you'll lose.
>Wrong. If you're predictible, you'll lose to bots which can out-predict
>you. That's the whole point. The bot that wins will be the one that is best
>at predicting what it's opponent's strategy is, on average.
Yes, but again, if you are losing, you just lock yourself into random
mode so that the game converges to a draw.
>Wouldn't it be interesting to find out where a human being would come in this
>game? Would they come first? Or would some of the better bots beat them?
Again, it's humans who coded the algorithms. I assume that many are
simple enough for a person to implement is a reasonable amount of time.
>You shouldn't underestimate the importance of a good predictive algorithm.
>Applications abound.
Well, this is actually an interesting topic, what are some of the
applications? In particular, what are some applications which exhibit
the same property as RoShamBo?
- Andrew
Jason Hutchens
>>You shouldn't underestimate the importance of a good predictive algorithm.
>>Applications abound.
>
>Well, this is actually an interesting topic, what are some of the
>applications? In particular, what are some applications which exhibit
>the same property as RoShamBo?
A predictive algorithm is an algorithm which is able to make a prediction
about the next value in a sequence of values. The best predictive
algorithms work by inferring a model of the sequence. A good predictive
algorithm will be able to play RoShamBo very well, without being explicitly
programmed to solve that task. A few applications of such algorithms are
data compression, grammatical inference, speech recognition, data mining,
natural language understanding, syntactic pattern recognition, speech
segmentation, machine translation, text generation, spelling correction,
author identification, email classification, image recognition, stock market
analysis, finding structure in data, analysis of DNA sequences, analysis of
music, input methods for disabled users, and playing RoShamBo!
The only requirements of an algorithm is that it be capable of making
a prediction about the next symbol in a symbolic time series using only
information about the history of the series, and that the prediction be
made in the form of a probability distribution over the alphabet of
symbols. Once you've got an algorithm that can do that, you can apply
it to all of the problems above. To compare two different algorithms
that have the required properties, you can just get them to play RoShamBo
against each other.
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -782- http://ciips.ee.uwa.edu.au/~hutch-+
Beldin the Sorcerer
Jason Hutchens <hu...@ee.uwa.edu.au> wrote in message
news:Pine.LNX.4.10.99092...@nuit.ee.uwa.edu.au...
>
> >The bot is using a random number generator.
> >The strategey is to play random unless an obvious pattern is played
against
> >you.
>
> So? A chess program may look ahead 100 moves. Does that mean you'd want
> to do the same if you played against one?
I'd sure as hell want to be able to look as deep as they do.
I'd rather have the blinding insight of Fisher.
My point is that if your opponent
> is playing random moves, it doesn't matter what moves you play, because
you'll
> draw on average.
Read it again.
The play is to begin playing random moves and only vary if your opponent
seems predictable.
And, if your opponent isn't playing random moves, then the
> game will test how capable a human being is of prediction, provided that
the
> human being doesn't play random moves.
No, that's wrong. The game is to play randomly until and unless you can
predict your opponent, at which time you switch to predicting... and go back
to random should you find yourself being wrong.
>
> >It's a dumb game. Remember most of us said that at the beginning of this
> >discussion?
>
> Yes, it's dumb if you're only looking at the surface of the game. But
> underneath you'll find a very good mechanism for measuring the
effectiveness
> of various predictive strategies. And there's nothing dumb about that.
In a game where the only rational play is NOT to be predictive?
Seems fairly dumb to me.
>
> >If you're predictable, you'll lose.
>
> Wrong. If you're predictible, you'll lose to bots which can out-predict
> you.
If you're predictable, you'll lose.
Over time.
If you're playing randomly, the results won't skew.
That's the whole point. The bot that wins will be the one that is best
> at predicting what it's opponent's strategy is, on average.
Or, and this is far more likely, the one with the greatest variance.
>
> Wouldn't it be interesting to find out where a human being would come in
this
> game? Would they come first? Or would some of the better bots beat them?
The bots are all going to start off playing randomly.
If they don't, they'll lose.
If the human plays randomly, variance is the winner.
>
> You shouldn't underestimate the importance of a good predictive algorithm.
> Applications abound.
predictive of the random? That only shows possible flaws in the randomizer.
>
> >No, you idiot,
>
> Oh, thanks very much. This is where I leave; I don't continue to debate
> issues when they devolve into personal insults.
You mindlessly accused me of filibustering.
Sounds like a personal insult to me.
So you slapped first and complain about a shot back.
It's a pity you couldn't
> state your case more clearly. Goodbye.
Ah, so you being rude is fine then.
Fascinating.
>
> +=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-=
+
> | Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire
|
> | TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More
|
> +-mailto:hu...@ciips.ee.uwa.edu.au -780-
Beldin the Sorcerer
> In article <7sr3ds$205$1...@nntp2.atl.mindspring.net>,
> Beldin the Sorcerer <bel...@sprynet.com> wrote:
> >>
> >> Why don't you just play his damn bot instead of filibustering?
> >
> >Because the correct strategy is to be random and look for a pattern in
your
> >opponent.
> >Seeing as how I know the strategy, I'd like to be clear on the rules
first.
>
> How can the correct strategy be "to be random and look for a pattern in
> your opponent"? Are you proposing you LOOK but don't act on it? As soon
> as you act on it, you are not being random.
Sigh.
Let me try this in simple words.
Step 1 : Be random
Step 2 : Discover a pattern in your opponent, if possible
Step 3 : Assuming step 2 is successful, apply said pattern to your picks
until you do NOT score a hit at which point revert at once to step 1.
Any other play is inferior.
>
> > Afraid
> >> it's going to beat you or something?
> >It might, in a statistically insignificant way.
> >Not the point of the exercise.
>
> Anyhow, like I said, the bot I mentioned is completely deterministic,
other
> than the first move. Certainly, you could try to beat it, and once you
> had a lead, then "lock in" the lead by going random. What I am saying is
> that if you play it to try to beat it in any statistically significant
way,
> you will not WANT to go random. I am also saying that trying to go random
> without using an outside source of randomness, will likely lead to you
> getting thomped.
Since the BOT has an outside source of randomness, how is it fair to
preclude a human?
Andrew Prock
>
>>>Applications abound.
>>
>>applications? In particular, what are some applications which exhibit
>>the same property as RoShamBo?
>
>A predictive algorithm is an algorithm which is able to make a prediction
>about the next value in a sequence of values. The best predictive
>algorithms work by inferring a model of the sequence. A good predictive
>algorithm will be able to play RoShamBo very well, without being explicitly
>programmed to solve that task. A few applications of such algorithms are
>data compression, grammatical inference, speech recognition, data mining,
>natural language understanding, syntactic pattern recognition, speech
>segmentation, machine translation, text generation, spelling correction,
>author identification, email classification, image recognition, stock market
>analysis, finding structure in data, analysis of DNA sequences, analysis of
>music, input methods for disabled users, and playing RoShamBo!
This list of applications is nice and long. Unfortunatly only
*two* of the applications are anything like roshambo; stock market analysis,
and ...
roshambo.
All the others do not have opponents who are trying to foil you. And
most people approach stock market analysis as if there were no opponents,
just a market which behaves independently of any particular buy or sell.
It is this incorrect assumption which makes traditional stock market analysis
unstable.
If the point of looking at roshambo is to find patterns, there are a myriad
of tools for this including PCA, neural networks, Bayesian networks,
vector support machines, etc.
However, I don't think the point is to excercise our pattern recognition
algorithms, rather it is to do some opponent modelling, which is a much
different problem. Unfortunately roshambo is not the most interesting
arena to do this work in. As I pointed out before there is a very simple
meta-algorithm which ensures that in the limit, any bot using is will
score better than or equal to a draw. If all bots use this meta-algorithm,
then the entire tournament will converge to a draw.
>The only requirements of an algorithm is that it be capable of making
>a prediction about the next symbol in a symbolic time series using only
>information about the history of the series, and that the prediction be
>made in the form of a probability distribution over the alphabet of
>symbols. Once you've got an algorithm that can do that, you can apply
>it to all of the problems above. To compare two different algorithms
>that have the required properties, you can just get them to play RoShamBo
>against each other.
Yes, but roshambo is a "deeper" game. It has arbitrary levels of
"he thinks I think...", so doing pattern analysis on the series is
not going to serve you well in the long run against any sophistocated
opponent.
- Andrew
Jason Hutchens
>> >No, you idiot,
>>
>> Oh, thanks very much. This is where I leave; I don't continue to debate
>> issues when they devolve into personal insults.
>
>
>You mindlessly accused me of filibustering.
>Sounds like a personal insult to me.
>So you slapped first and complain about a shot back.
I humbly and unreservedly apologise for my statement about you filibustering.
I wasn't aware that you took umbrage at that, and I'm obviously too dumb to
realise that your statement above, where you called me an idiot, was a
shot back. Sorry.
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -790- http://ciips.ee.uwa.edu.au/~hutch-+
Jason Hutchens
>Since the BOT has an outside source of randomness, how is it fair to
>preclude a human?
Our problem is, I believe, that you're interested in the game, whereas
I'm interested in how the game may be used to measure the effectiveness
of different predictive strategies.
I would be far more interested in the results of a game between a human
being and a 'bot if the human being made his or her choices based on
intuition, because that would reveal a lot more about what's going on
inside the human brain than if the human opponent rolled die, flipped
coins and scribbled on paper before making each move.
Based on the couple of reports from people who have played bots, it seems
that even when a human being is making choices based on intuition, the
bots still have a hard time winning. Obviously, more rigorous experiments
would need to be performed to show if this is indeed the case, but it
would be of considerable interest if it was.
The game of RoShamBo in itself holds no interest for me otherwise.
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -791- http://ciips.ee.uwa.edu.au/~hutch-+
Tero Markus Ronkko
>According to Jason Hutchens <hu...@ee.uwa.edu.au>:
>>On 29 Sep 1999, Andrew Prock wrote:
>>
>>>>You shouldn't underestimate the importance of a good predictive algorithm.
>>>>Applications abound.
>>>
>>>Well, this is actually an interesting topic, what are some of the
>>>applications? In particular, what are some applications which exhibit
>>>the same property as RoShamBo?
>>
>>A predictive algorithm is an algorithm which is able to make a prediction
>>about the next value in a sequence of values. The best predictive
>>algorithms work by inferring a model of the sequence. A good predictive
>>algorithm will be able to play RoShamBo very well, without being explicitly
>>programmed to solve that task. A few applications of such algorithms are
>>data compression, grammatical inference, speech recognition, data mining,
>>natural language understanding, syntactic pattern recognition, speech
>>segmentation, machine translation, text generation, spelling correction,
>>author identification, email classification, image recognition, stock market
>>analysis, finding structure in data, analysis of DNA sequences, analysis of
>>music, input methods for disabled users, and playing RoShamBo!
>
>This list of applications is nice and long. Unfortunatly only
>*two* of the applications are anything like roshambo; stock market analysis,
>and ...
>
>roshambo.
Just have been following this thread here and developed one of bots (helped, but did not donate mine, cuz anyway, it always scored zero
for everyone, even for random, gee. Why? Because it forgot to answer sometimes.). I cannot stop wondering how in the hell computer
science student/doctor/master/guru/whatever can be so ---------- (guess) that they dont understand roshambo contest?
I mean, why, what, what use are they etc? Are you like 1st year student writing VB programs? Or just coming from some engineer school
where you are not supposed to understand datamining for example? Geez.
It was not personal insult towards anyone, atleast it should not have been. I like this thread but wanted to say that roshambo contest
rocks (paper wins).
Just waiting how my friends do.
More this kinds of competitions plz. It was clever and simple enough in first place to interest much people, i guess.
codemo...@my-deja.com
> No shit.
> Sigh.
> Let me try this in simple words.
> Step 1 : Be random
> Step 2 : Discover a pattern in your opponent, if possible
> Step 3 : Assuming step 2 is successful, apply said pattern to your
> picks until you do NOT score a hit at which point revert at once
> to step 1.
>
> Any other play is inferior.
>
Okay, you've stated your *opinion* and backed it up with *theory* as
has Jason. We all know your both your opinions on the subject. Jason
is backing his up with a bot. Are you?
If not why not?
Will you ignore the results of the contest?
Theory and opinion are nothing unless backed up by experimental or
observational evidence .
Thad
Sent via Deja.com http://www.deja.com/
Before you buy.
Andrew Prock
>In article <7su1n3$d...@spool.cs.wisc.edu>, Andrew Prock wrote:
>>
>>This list of applications is nice and long. Unfortunatly only
>>*two* of the applications are anything like roshambo; stock market analysis,
>>and ...
>>
>>roshambo.
>
>
>Just have been following this thread here and developed one of bots (helped, but did not donate mine, cuz anyway, it always scored zero
>for everyone, even for random, gee. Why? Because it forgot to answer sometimes.). I cannot stop wondering how in the hell computer
>science student/doctor/master/guru/whatever can be so ---------- (guess) that they dont understand roshambo contest?
Uh, I understand it. I understand it very well. Do you?
Do you understand how roshambo is unlike speech recognition?
Pity you didn't enter, I'm sure you would have trounced my
3 hour/3am bot.
>I mean, why, what, what use are they etc? Are you like 1st year student writing VB programs? Or just coming from some engineer school
>where you are not supposed to understand datamining for example? Geez.
Heh, this is hilarious.
I have no desire to get into a CS qualification pissing contest.
- Andrew
Rafael Morales Gamboa
> Let me try this in simple words.
> Step 1 : Be random
> Step 2 : Discover a pattern in your opponent, if possible
> Step 3 : Assuming step 2 is successful, apply said pattern to your picks
> until you do NOT score a hit at which point revert at once to step 1.
>
> Any other play is inferior.
Please consider this one:
Step 1 : Show enough hints for a pattern.
Step 2 : Assume your opponent has discovered the pattern an issue a
wining move (out of the pattern).
Step 3 : Revert to pretending a pattern (Step 1).
Will it be inferior to your algorithm?
Of course, the problem (of opponent modelling nature) is to discover the
time your bot takes to believe you are "really" following a pattern.
Rafael
Beldin the Sorcerer
<codemo...@my-deja.com> wrote in message
news:7sv872$k0q$1...@nnrp1.deja.com...
> > Step 1 : Be random
> > Step 2 : Discover a pattern in your opponent, if possible
> > Step 3 : Assuming step 2 is successful, apply said pattern to your
> > picks until you do NOT score a hit at which point revert at once
> > to step 1.
> >
> > Any other play is inferior.
> >
>
> has Jason. We all know your both your opinions on the subject. Jason
> is backing his up with a bot. Are you?
>
> If not why not?
I'm not an excellent programmer.
I am merely adequate in old languages.
> Will you ignore the results of the contest?
As i would the results of a tic-tac-toe contest.
>
> Theory and opinion are nothing unless backed up by experimental or
> observational evidence .
This is well established fact.
Play : Be unpredictable.
You can only score one point at a time, you cannot therefore do a "setup" of
leading someone on to think you're an idiot.
It ISN'T Poker, it's flipping coins.
Jason Hutchens
>> Will you ignore the results of the contest?
>As i would the results of a tic-tac-toe contest.
Which means that you must apparently think that "Discover a pattern in
your opponent, if possible" is a trivial business, and not worth
investigating? That was step 2 of your "algorithm". I contend that
even if you were the world's most brilliant programmer, you wouldn't
have entered the contest, because you would have no idea how to implement
step 2. Am I right?
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -801- http://ciips.ee.uwa.edu.au/~hutch-+
Beldin the Sorcerer
> On Wed, 29 Sep 1999, Beldin the Sorcerer wrote:
>
> >> >No, you idiot,
> >>
> >> Oh, thanks very much. This is where I leave; I don't continue to
debate
> >> issues when they devolve into personal insults.
> >
> >
> >You mindlessly accused me of filibustering.
> >Sounds like a personal insult to me.
> >So you slapped first and complain about a shot back.
>
> I humbly and unreservedly apologise for my statement about you
filibustering.
> I wasn't aware that you took umbrage at that, and I'm obviously too dumb
to
> realise that your statement above, where you called me an idiot, was a
> shot back. Sorry.
>
We all often miss our own precursers, myself included.
codemo...@my-deja.com
> > If not why not?
> I'm not an excellent programmer.
> I am merely adequate in old languages.
>
You've stated that this isn't a 'hard' programming challenge, and
therfore irrelevent. Random is in the contest, but your alegedly
perfect algorythm was more that that, stage 2 is a hard problem, as is
true algorythmic random behavior. If you really think this is no
contest, and that you know how to solve it then do it, if you can't
then don't insult those that try.
An analogy - Tight rope walking? Easy just walk along the rope.
Anyone can do it. Just don't fall off. Duh.
> > Will you ignore the results of the contest?
> As i would the results of a tic-tac-toe contest.
>
You wouldn't need to ignore the results, tic-tac-toe has been proved,
both in theory and in practice. The results would back up your claim.
As it stands you cannot back up you claim with evendence.
<SNIPED REPEATED OPININS>
> You can only score one point at a time, you cannot therefore do
> a "setup" of leading someone on to think you're an idiot.
True, but it doesn't make it any less worthwhile.
The same applies to chess, go, whatever.
> It ISN'T Poker, it's flipping coins.
Your right, it isn't poker, but so what?
(I agree that this thread shouldn't be on r.g.p, but it is, and thats
life.)
But it isn't flipping coins, in any way.
Anyway, it doesn't matter what you think, the contest isn't hurting
you, so why insult those that enter it by bilitiling it. You have to
look beond the superficial simplicity, and examine the deeper
complexity.
I thought it was trival at first, and only entered for a bit of fun, it
wasn't till I started trying to write my bot that I realised how
complex/deep it actually is.
So, to be blunt, put up or shut up.
(Personally I think the contest would have been more interesting if the
global random had been removed, and people who wanted to create an
apparently random behavior would have had to do it themselves.)
Randolph M. Jones
> It ISN'T Poker, it's flipping coins.
I think this sums up well my feeling about rock, scissors, paper. I
admit it will be (is) very interesting to see what kinds of pattern
predictors people might develop, even for this game. My main concern is
that sophisticated algorithms don't really have a chance to "show off",
precisely because the forms of expression allowed in this game are so
enormously constrained. This is why I suggest that luck may play a
large factor in a tournament of this type.
Another way to put it:
It doesn't pay to be smart if there are only 3 things you can do.
Tero Markus Ronkko
>Uh, I understand it. I understand it very well. Do you?
Good, so what is wrong then?
>Do you understand how roshambo is unlike speech recognition?
Well, yes, parts of it. Elseway, it also is something like that. Both sr programs and roshambo bots try to find patterns on data. Game
is irrelevant. Saying roshambo is useless cuz you can anyway win with random, is like friend said that martial arts are useless, anyway
there is someone with gun and much stronger than you. Well. Hes right, so are you.
>Pity you didn't enter, I'm sure you would have trounced my
>3 hour/3am bot.
Ah, i think not.
>Heh, this is hilarious.
>I have no desire to get into a CS qualification pissing contest.
Well, it was not ment to sound like one, i just remembered why i should not have written that anyways. Over and out.
Beldin the Sorcerer
<codemo...@my-deja.com> wrote in message
news:7t04cr$90r$1...@nnrp1.deja.com...
>
> > > If not why not?
> > I'm not an excellent programmer.
> > I am merely adequate in old languages.
> >
>
> You've stated that this isn't a 'hard' programming challenge, and
> therfore irrelevent.
I never said boo about the program.
Random is in the contest, but your alegedly
> perfect algorythm was more that that, stage 2 is a hard problem, as is
> true algorythmic random behavior.
I said I had an algorythm that a human could use to beat, or at least
defeat, a computer.
I didn't say it would be easily duplicated BY a computer.
If you really think this is no
> contest, and that you know how to solve it then do it, if you can't
> then don't insult those that try.
I'm not insulting the programmers.
I'm pointing out that the results aren't meaningful, other than as a check
of randomizing routines,
>
> An analogy - Tight rope walking? Easy just walk along the rope.
> Anyone can do it. Just don't fall off. Duh.
>
> > > Will you ignore the results of the contest?
> > As i would the results of a tic-tac-toe contest.
> >
>
> You wouldn't need to ignore the results, tic-tac-toe has been proved,
> both in theory and in practice. The results would back up your claim.
If someone managed to win several games, against an idiot, it wouldn't show
him as superior.
Just lucky enough to get an idiot for an opponent.
>
> As it stands you cannot back up you claim with evendence.
>
> <SNIPED REPEATED OPININS>
>
> > You can only score one point at a time, you cannot therefore do
> > a "setup" of leading someone on to think you're an idiot.
>
> True, but it doesn't make it any less worthwhile.
> The same applies to chess, go, whatever.
No, it doesn't apply to chess.
Chess is an ideal trap game, laying bait to gain a huge tactical advantage.
>
> > It ISN'T Poker, it's flipping coins.
>
> Your right, it isn't poker, but so what?
> (I agree that this thread shouldn't be on r.g.p, but it is, and thats
> life.)
> But it isn't flipping coins, in any way.
It's random.
And it isn't even particularly good random.
>
> Anyway, it doesn't matter what you think, the contest isn't hurting
> you, so why insult those that enter it by bilitiling it.
I'm not belittling the contest, I'm belittling the game.
You have to
> look beond the superficial simplicity, and examine the deeper
> complexity.
>
There isn't much, as a human against a bot.
> I thought it was trival at first, and only entered for a bit of fun, it
> wasn't till I started trying to write my bot that I realised how
> complex/deep it actually is.
>
> So, to be blunt, put up or shut up.
I believe you have totally misinterpreted what I've said about this...
I shall await your reading before continuing.
buy.
Beldin the Sorcerer
Randolph M. Jones <rjo...@colby.edu> wrote in message
news:37F386AE...@colby.edu...
> Beldin the Sorcerer wrote:
> > It ISN'T Poker, it's flipping coins.
>
> admit it will be (is) very interesting to see what kinds of pattern
> predictors people might develop, even for this game. My main concern is
> that sophisticated algorithms don't really have a chance to "show off",
> precisely because the forms of expression allowed in this game are so
> enormously constrained. This is why I suggest that luck may play a
> large factor in a tournament of this type.
>
> Another way to put it:
> It doesn't pay to be smart if there are only 3 things you can do.
Though if the amount of points changes, and you could lay traps for big
payoffs, it might be different.
Beldin the Sorcerer
Jason Hutchens <hu...@ee.uwa.edu.au> wrote in message
news:Pine.LNX.4.10.990930...@nuit.ee.uwa.edu.au...
>
> >> Will you ignore the results of the contest?
> >As i would the results of a tic-tac-toe contest.
>
> your opponent, if possible" is a trivial business, and not worth
> investigating? That was step 2 of your "algorithm".
The algorythm is a simple randomizer.
I contend that
> even if you were the world's most brilliant programmer, you wouldn't
> have entered the contest, because you would have no idea how to implement
> step 2. Am I right?
wrong.
Observable patterns (repeated patterns over time)
Frequency checks.
Omissions (Never plays rock, for instance)
Insufficient varience (at 298, there are 100 R, 99 P, 99 S... this is too
tight a distribution to be chance, so a rock most likely won't be thrown.
Thus, S is the next optimal play. If he plays S, play S again. If he plays
P, Play R the next round)
Etc.
Any good random routine will not fall victim to these.
>
Lee Daniel Crocker
> Step 2 : Discover a pattern in your opponent, if possible
> Step 3 : Assuming step 2 is successful, apply said
> pattern to your picks until you do NOT score a hit at
> which point revert at once to step 1.
> Any other play is inferior.
Not necessarily. If the pattern you find is merely a
statistical imablance and not a fixed 100% predictable
sequence, switching back to random on the first miss is
a big mistake; a program that sticks to its strategy as
long as it has evidence for its statistical superiority
will be more explotive.
But then that's just what the contest is supposed to
find out, isn't it?
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
Lee Daniel Crocker
> therefore do a "setup" of leading someone on to think
Then you /have/ misunderstood the contest, because
this isn't true at all. The contest between each two
bots is 1000 consecutive trials, with the history of
each known to both, so you /can/ set up your opponent
with false expectations.
In fact, this is exactly what my 'bot does: it plays
predictably for several turns, on the assumption that
the opposing bot will learn to predict the pattern
and play to beat it, and then it switches to playing
whatever would defeat the move its opponent would make
if it was exploiting my earlier pattern. I called it
"bait and switch".
David desJardins
> Although this seems like a good strategy, I believe that there will be
> some sort of entropic law at play here, meaning that the points you
> sacrifice while baiting a good opponent will always exceed the points
> you gain when you switch.
This is obviously wrong. Any given "good opponent" is either random, in
which case nothing you do can cost you, or is not random, in which case
there exist strategies against it that gain more than they lose. The
strategy that gains more than it loses does so specifically by making
plays that induce a certain nonrandom behavior, and then taking
advantage of that behavior for as long as it persists.
David desJardins
Jason Hutchens
>Another way to put it:
> It doesn't pay to be smart if there are only 3 things you can do.
That's one more thing than a computer can do ;^)
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -804- http://ciips.ee.uwa.edu.au/~hutch-+
Jason Hutchens
>I'm pointing out that the results aren't meaningful, other than as a check
>of randomizing routines,
This is amazingly incorrect. My bot generates less than 5 random numbers
every 100 moves, on average (against the seven default opponents), and it
uses the standard random number generator to do so. If I replaced all of
the random number calls with a choice of "ROCK", it still kicks mega-ass,
beating the second best algorithm by 20:1. And, incredibly, it continues
to "look random" to an unpredictable opponent (simply because that
opponent becomes a random number generator)!
Furthermore, my bot is the exact same algorithm used in a data compression
program. The algorithm was NOT designed with the game of RoShamBo in mind.
>It's random.
>And it isn't even particularly good random.
Unfortunately you do not seemed to have grasped the deeper aspects of
the game. You're just looking at the surface of the game, and it seems
no amount of reasoned argument will turn you around. Oh, well.
>I'm not belittling the contest, I'm belittling the game.
Yes, exactly. And I *agree* that on the surface the game is a monumental
waste of time, and it must be hard to imagine why researchers would be
interested in something so trivial. Rather like a small child who can't
comprehend why anyone would want to spend hours staring at pages and
pages of boring little symbols when they could be looking at books with
magnificent pictures in them. But when you grow up, you begin to realise
that the surface appearance of a book has little to do with how interested
one is in it!
>There isn't much, as a human against a bot.
No-one's performed proper experiments into this yet, but, if a bot
could reliably beat a human being at RoShamBo, it would tell us a lot
about the limits of the human brain as far as inference and prediction
goes. And vice-versa: if a human being reliably beats the best bot,
it would humble us into realising that the human brain is an amazing
information processing device, capable of detecting patterns in data
with ease, and applying what it learns to arbitrary problems. Of
course, these results would depend on the human being not being able
to use any sort of external random number generator.
>I believe you have totally misinterpreted what I've said about this...
>I shall await your reading before continuing.
I think a lot of us have misinterpreted you. Would you care to
succinctly re-state your beliefs about this game so we can all be
certain of what your position is?
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -805- http://ciips.ee.uwa.edu.au/~hutch-+
Jason Hutchens
>Observable patterns (repeated patterns over time)
>Frequency checks.
>Omissions (Never plays rock, for instance)
>Insufficient varience (at 298, there are 100 R, 99 P, 99 S... this is too
>tight a distribution to be chance, so a rock most likely won't be thrown.
>Thus, S is the next optimal play. If he plays S, play S again. If he plays
>P, Play R the next round)
Can you please explicitly list each of your strategies for pattern
detection, as you have begun to above, and I will implement the
program for you, and submit it to Darse as an eleventh-hour entry,
in an attempt to show you how wrong you are.
>Any good random routine will not fall victim to these.
Of course not! But that's not the point!
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -806- http://ciips.ee.uwa.edu.au/~hutch-+
Jason Hutchens
>In fact, this is exactly what my 'bot does: it plays
>predictably for several turns, on the assumption that
>the opposing bot will learn to predict the pattern
>and play to beat it, and then it switches to playing
>whatever would defeat the move its opponent would make
>if it was exploiting my earlier pattern. I called it
>"bait and switch".
Although this seems like a good strategy, I believe that there will be
some sort of entropic law at play here, meaning that the points you
sacrifice while baiting a good opponent will always exceed the points
you gain when you switch.
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -808- http://ciips.ee.uwa.edu.au/~hutch-+
Jason Hutchens
>Jason Hutchens <hu...@ee.uwa.edu.au> writes:
>> Although this seems like a good strategy, I believe that there will be
>> some sort of entropic law at play here, meaning that the points you
>> sacrifice while baiting a good opponent will always exceed the points
>> you gain when you switch.
>
>This is obviously wrong. Any given "good opponent" is either random, in
>which case nothing you do can cost you, or is not random, in which case
>there exist strategies against it that gain more than they lose. The
>strategy that gains more than it loses does so specifically by making
>plays that induce a certain nonrandom behavior, and then taking
>advantage of that behavior for as long as it persists.
Precisely. Which is why the statement I made is *not* obviously wrong,
because what you've just said applies equally well to the "Bait-n-Switch"
algorithm. A good predictive algorithm will quickly take advantage of
the "Bait" mode of play, and will quickly defend itself when the "Switch"
occurs.
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -809- http://ciips.ee.uwa.edu.au/~hutch-+
Perry Friedman
Jason Hutchens <hu...@ee.uwa.edu.au> wrote:
>On Thu, 30 Sep 1999, Lee Daniel Crocker wrote:
>
>>In fact, this is exactly what my 'bot does: it plays
>>predictably for several turns, on the assumption that
>>the opposing bot will learn to predict the pattern
>>and play to beat it, and then it switches to playing
>>whatever would defeat the move its opponent would make
>>if it was exploiting my earlier pattern. I called it
>>"bait and switch".
>
>some sort of entropic law at play here, meaning that the points you
>sacrifice while baiting a good opponent will always exceed the points
>you gain when you switch.
>
Unless you are a master baiter.
Perry
Jason Hutchens
True; in that case you'd win single-handedly.
+=-- -- =-- =-== === --= ---- === =- - --- = -=-- =-== = ---- -- =- =-= +
| Mr Jason Lloyd Hutchens, PhD Student and Procrastinator Extraordinaire |
| TMBG/IF/MAME/MB/BEOS/PSX/AMIGA/MIDI Me/Research/Spy/MegaHAL/Humour/More |
+-mailto:hu...@ciips.ee.uwa.edu.au -814- http://ciips.ee.uwa.edu.au/~hutch-+
Perry Friedman
Jason Hutchens <hu...@ee.uwa.edu.au> wrote:
>On 1 Oct 1999, Perry Friedman wrote:
>
>>In article <Pine.LNX.4.10.991001...@nuit.ee.uwa.edu.au>,
>>Jason Hutchens <hu...@ee.uwa.edu.au> wrote:
>>>On Thu, 30 Sep 1999, Lee Daniel Crocker wrote:
>>>
>>>>In fact, this is exactly what my 'bot does: it plays
>>>>predictably for several turns, on the assumption that
>>>>the opposing bot will learn to predict the pattern
>>>>and play to beat it, and then it switches to playing
>>>>whatever would defeat the move its opponent would make
>>>>if it was exploiting my earlier pattern. I called it
>>>>"bait and switch".
>>>
>>>Although this seems like a good strategy, I believe that there will be
>>>some sort of entropic law at play here, meaning that the points you
>>>sacrifice while baiting a good opponent will always exceed the points
>>>you gain when you switch.
>>>
>>
>>Unless you are a master baiter.
>
>True; in that case you'd win single-handedly.
>
Just be careful not to go scissors.
Perry
Beldin the Sorcerer
Lee Daniel Crocker <leeNO...@piclab.com.invalid> wrote in message
news:06284168...@usw-ex0102-015.remarq.com...
> > Step 1 : Be random
> > Step 2 : Discover a pattern in your opponent, if possible
> > Step 3 : Assuming step 2 is successful, apply said
> > pattern to your picks until you do NOT score a hit at
> > which point revert at once to step 1.
> > Any other play is inferior.
>
> Not necessarily. If the pattern you find is merely a
> statistical imablance and not a fixed 100% predictable
> sequence, switching back to random on the first miss is
> a big mistake; a program that sticks to its strategy as
> long as it has evidence for its statistical superiority
> will be more explotive.
>
being predictable yourself is a death sentence.
Beldin the Sorcerer
> On Thu, 30 Sep 1999, Lee Daniel Crocker wrote:
>
> >In fact, this is exactly what my 'bot does: it plays
> >predictably for several turns, on the assumption that
> >the opposing bot will learn to predict the pattern
> >and play to beat it, and then it switches to playing
> >whatever would defeat the move its opponent would make
> >if it was exploiting my earlier pattern. I called it
> >"bait and switch".
>
> Although this seems like a good strategy, I believe that there will be
> some sort of entropic law at play here, meaning that the points you
> sacrifice while baiting a good opponent will always exceed the points
> you gain when you switch.
>
Good to see we agree on something in this discussion