Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> General Discussion >> How great an advantage is the first move?
        
(Message started by: Fritzlein on Sep 16^th, 2004, 11:42am)

Title: How great an advantage is the first move?
Post by Fritzlein on Sep 16^th, 2004, 11:42am

I've done a quick analysis of the game database which Omar has made available (Thanks, Omar!), to see how much of an advantage it is to play first. Gold has indeed won more often (across all 5047 rated games) than one would expect from the ratings alone. So I calculated the expected winnings by adding N points to the rating of Gold for various values of N, until the expected number of wins balances the actual number of wins. As it turns out, the value of N which compensates exactly is 3.

What? Is it possible that the first move is worth only 3 rating points? That isn't my experience at all. In fact, when I do the calculation over only the 59 rated games I have played, the value of N jumps to 113. Apparently for me, at least, going first is worth 113 rating points.

If I remember correctly, studies have shown that in chess the first move is worth about 40 rating points. I expected it would be approximately the same for Arimaa, but the data doesn't bear me out.

What do other people think? Is moving first a significant advantage in your experience? Maybe there is some anomaly created by people being allowed to choose their own color? Or maybe I am the anomaly and for everyone else moving first is irrelevant?

Just curious,
-Karl

Title: Re: How great an advantage is the first move?
Post by 99of9 on Sep 16^th, 2004, 3:19pm

Wow, this game database could allow some really interesting studies. Where is it? I haven't stumbled upon it yet. [EDIT: Ah, I found it in the download section... duh!]

I think the first move is pretty important. I'd say worth about 50 ratings points.

The ratings difference of 3 that you calculate is so small because many of the games were played dumbbot vs dumbbot ... and for weaker players, the colour matters much less.

Title: Re: How great an advantage is the first move?
Post by omar on Sep 21^st, 2004, 4:07pm

Would be interesting so see what the numbers are if you limit this to games where both players had a rating above some value like 1700.

Title: Re: How great an advantage is the first move?
Post by Fritzlein on Sep 24^th, 2004, 6:37pm

Limiting to the 958 rated games with both players over 1650, the advantage of moving first turns out to be 4 points. I still don't believe it, but that's what the data says.

Title: Re: How great an advantage is the first move?
Post by Fritzlein on Sep 24^th, 2004, 8:25pm

More data:

Over his last 86 rated games, 99of9's advantage from going first was 56 points.
Over his last 76 rated games, omar's advantage from going first was -58 points.
Over his last 200 rated games, Belbo's advantage from going first was 10 points.

No, that's not a typo: Omar has actually done worse with gold than silver. No wonder (when I asked by e-mail) he didn't think going first was a significant advantage! Meanwhile 99of9's subjective estimate of the value of the first move was extremely accurate, at least for his games.

Title: Re: How great an advantage is the first move?
Post by maker on Sep 25^th, 2004, 10:48pm

hehe, I'd bet that for me, I actually get a negative chance of winning, every time I play. Ah, being a newbie...

happy with his station,
maker

Title: Re: How great an advantage is the first move?
Post by omar on Sep 26^th, 2004, 3:30pm

So Im the one who is bring down the advantage stats for going first. ;D

Title: Re: How great an advantage is the first move?
Post by 99of9 on Nov 3^rd, 2004, 11:14am

on 09/26/04 at 15:30:15, omar wrote:

So Im the one who is bring down the advantage stats for going first. ;D

on 09/16/04 at 9:19pm, 99of9 wrote:

... and for weaker players, the colour matters much less.

:P QED :P

(just kidding of course)

Title: Re: How great an advantage is the first move?
Post by Fritzlein on Apr 11^th, 2005, 6:27pm

Recently I was thinking again about the advantage of moving first. It occurred to me that my previous statistics might have been skewed by a couple of factors: (1) Maybe humans start to play bots primarily with Silver once they start to master the bot and (2) Maybe in human vs. human matches, the stronger player offers to play Silver.

I therefore decided to generate a new statistic, in which I would not count multiple games between a pair of opponents unless they alternated colors. That is to say, if Naveed plays Fritzlein with Gold, then subsequent games between Naveed and Fritzlein don't count until Fritzlein plays Gold, and then their games don't count until Naveed plays Gold, etc. And of course I counted only rated games.

Under these rules, there were 6286 games I could count. Alas, Gold won only 3160 a.k.a. 50.27% a.k.a. an advantage of 2 ratings points. Sigh.

My intuition that Gold has a significant advantage is strong, but the data simply refuse to support my conviction.

Title: Re: How great an advantage is the first move?
Post by Fritzlein on Apr 12^th, 2005, 9:22am

on 04/12/05 at 01:10:06, Arimanator wrote:

Fourth, what ?! :o. You've only played 59 rated games ! That's incredible!
[...]
5th, I believe that you should limit your studies to human vs human players, that how it's done in chess and I am persuaded that the bot factor completely crooks the deal

I'm curious where you find that I've only played 59 rated games. When I click on my profile it shows me that I have played 371 games, but it doesn't show me how many were rated. The only way I can think of to check is to download the entire game database (which is updated weekly) and run a query. That method tells me I have played 330 rated games.

(Incidentally, you have already played 281 rated games, 7th most among humans over the life of the server. You have played 6917 moves in rated games which ranks 10th among humans over the life of the server, and gives you an average of 24.6 moves per rated game. Aren't databases fun?)

As to eliminating the bot factor, I re-ran my query for human vs. human games only, and this time Gold won only 177 of 398, i.e. 44.5%, which is a rating advantage of 39 points to Silver! I disbelieve this implication even more than the previous one. If Silver truly has an edge it must be due to psychology, or time zones, or numerology, or perturbations in the ether, or something other than the actual game mechanics, which slightly favor Gold. That's my story and I'm sticking to it. :-)

Title: Re: How great an advantage is the first move?
Post by jdb on Apr 12^th, 2005, 9:50am

I believe Silver has (at least) two helping factors.

First, the games are long. It is not unusual to see the momentum shift back and forth several times in a game. I haven't seen an opening system were Gold gets the advantage from the outset and directly converts the win. The Elephant/Horse attack has promise, but time will tell.

Second, Silver gets to place his pieces after he has seen Gold's placement. This can only help Silver.

My current opinion is that the advantage of the first move is negligible at best.

Title: Re: How great an advantage is the first move?
Post by Fritzlein on Apr 12^th, 2005, 11:51am

Ah, now I see. On September 16th, 2004, I did indeed write that I had played 59 rated games. Mystery solved.

At that time I also wrote that the first move was an advantage of 113 rating points for me. Out of curiosity I ran the same query over the 330 rated games I played up until April 9, 2005, and over that dataset the first move is an advantage of 55 rating points to me.

Title: Re: How great an advantage is the first move?
Post by Fritzlein on Apr 12^th, 2005, 1:59pm

Good thought. When I run the stats over the last 100 rated games I have played, it appears to be a rating advantage of 8 points to Silver! Just as you predicted.

In fact it was so stunning I rechecked my original query over all 330 rated games for me, and the advantage to Gold over the whole set was only 21 points, not 55 points.

I guess I must admit that the early data on myself was heavily skewed by one fact: I initially had trouble beating bot_Arimaanator with Silver but much less difficulty with Gold. Apart from that fluke, the color seems not to have made much difference to my winning percentages. It's amazing what a deep psychological impression an experience like that can leave behind, even when there is nothing afterwards to reinforce it.

Title: Re: How great an advantage is the first move?
Post by omar on Apr 13^th, 2005, 7:44pm

I guess what we want to know is if there is inherently an advantage for the first player and try to eliminate other factors such as psychology, speed of the game, readiness of the player, difference between the players abilities, etc.

I guess the best way to determine this would be to have the same program play many many games against itself and look the number of times it wins as gold vs silver. It should be done with a random bot at first to eliminate any skew due to the evaluation function.

Maybe Toby or Jeff could make a copy of their bot that plays randomly and run it locally to collect the results.
It would be interesting to see if they both independently come up with similar numbers.

We could then repeat the experiment with a bot that looks 1 ply deep and then one that looks 2 plys deep. Although we probably will not be able to collect as many games since they will run slower and slower with increasing depth.

We may also want to try it with two versions of the random bot. One that does the setup completely randomly and another that does the setup by randomly selecting a setup from a list of commonly used setups.

These results would not apply to human games or games between much stronger bots, but still it will give us some insight into some simple cases and maybe we can extrapolate at bit from it. It would be very interesting to see what the numbers are in these simple cases.

Title: Re: How great an advantage is the first move?
Post by Fritzlein on Apr 13^th, 2005, 9:48pm

on 04/13/05 at 19:44:41, omar wrote:

Maybe Toby or Jeff could make a copy of their bot that plays randomly and run it locally to collect the results.
It would be interesting to see if they both independently come up with similar numbers.

Clauchau already posted in the deflation thread that he ran random stepper against random stepper a million times and the results were

Gold won 50.3%, Silver won 49.7%

Interestingly that's almost exactly the percentage I got from the database with my alternating game methodology

Title: Re: How great an advantage is the first move?
Post by 99of9 on Apr 14^th, 2005, 5:30am

on 04/13/05 at 21:48:32, Fritzlein wrote:

Interestingly that's almost exactly the percentage I got from the database with my alternating game methodology

That just proves that we humans are basically playing randomly in the whole scheme of things :-).

I think the best way of eliminating psychology but preserving something interesting is not to use random bots, but to look at the better played games, although not in such great numbers, between reasonable bots and other reasonable bots. Since there have been quite a few versions of them over time, I don't think their style of play will be too significant a bias. [one problem could be excluding the multitude of testing games, eg gnobot playing firsttry]

But for me at least, the bias only really comes out when both players get good enough for tempo to be important. In my games I consider the initial 4 tempa advantage to last about 4-5 moves. By that time a structural advantage worth around 50 ratings points has often been attained.

So until we all get quite a bit better, I don't think any stats will show much.

Title: Re: How great an advantage is the first move?
Post by Fritzlein on Apr 14^th, 2005, 9:18am

If it turns out that the elephant/horse attack is, in general, sound, then that would be a way to demonstrate a tangible advantage for Gold. But if it turns out that the lone-elephant attack is the only sound opening, then Gold's advantage may well be as tiny as the stats are showing us.

I definitely agree that we just don't know enough about the game to pronounce a final opinion on the advantage of going first. It isn't too late for someone to invent an attacking strategy in which the initial four tempi are critical. It isn't too late for Arimaa to devolve into endless defensive manuevering in which the initial four tempi are utterly irrelevant. The elephant/horse attack really shook things up around here this past six months, and I'll bet that before the next challenge match something equally revolutionary surfaces.

Title: Re: How great an advantage is the first move?
Post by omar on Apr 14^th, 2005, 12:13pm

on 04/14/05 at 10:01:28, Arimanator wrote:

Fritzlein, if you don't mind giving me some examples of games where the elephant/horse attack has been particularly well executed , I'd be eager to study it myself as I am sure most of the budding players around here.

Pat, check out the games from this years human vs computer challenge match. Frank did a great job of using the EH attack in those games. We still don't know of a good defense against it, so until we find one and the bots incorporate it, they are totally vulnerable.

Title: Re: How great an advantage is the first move?
Post by omar on Apr 14^th, 2005, 12:26pm

I was about to post this under the 'Fixing Arimaa/Eliminating Draws' thread, but I think it is better to post it here. So this post might make more sense if you first check that thread to see 99of9 and Fritzlein's post to my comments about first player advantage in tic-tac-toe.

You guys are right. I am way off if we consider only the games that are not draws.

Here's the data again from the TTT experiment (it was posted in the 'Rating of a perfect chess player' thread). I am seperating it based on even and odd ply search depth since it produces very different results.

p0-p0
as X wins=577 draws=121 lost=302 games=1000
as O wins=288 draws=137 lost=575 games=1000

p2-p2
as X wins=302 draws=515 lost=183 games=1000
as O wins=191 draws=495 lost=314 games=1000

p4-p4
as X wins=318 draws=518 lost=164 games=1000
as O wins=149 draws=513 lost=338 games=1000

p6-p6
as X wins=0 draws=1000 lost=0 games=1000
as O wins=0 draws=1000 lost=0 games=1000

p0 66.1%
p2 62.2%
p4 67.7%
p6 undefined

p1-p1
as X wins=693 draws=40 lost=267 games=1000
as O wins=260 draws=51 lost=689 games=1000

p3-p3
as X wins=541 draws=264 lost=195 games=1000
as O wins=168 draws=296 lost=536 games=1000

p5-p5
as X wins=697 draws=254 lost=49 games=1000
as O wins=57 draws=266 lost=677 games=1000

p1 72.4%
p3 74.8%
p5 92.8%

The first player advantage might dips a little with quality of play above random, but not much; maybe not even enough to be statistically significant. However, it seems to shoot up a lot as we get close to perfect play. So I was totally off. Thanks for catching that.

It is quite intersting that the first move advantage starts to shoot up at near perfect play even though the game is a draw at perfect play.

I had generate some data for Connect4 once, but can't seem to find where I put. If I find it, I'll post it here so we can see how it compares.

But this suggests that the the results we find with the random bots may actually apply quite well to our level of higher quality, but far from perfect play. As Toby mentioned, in the big picture we are probably barely above random. So it tends to explain why Claude's results with random stepper are very close to Karl's results from the database.

Title: Re: How great an advantage is the first move?
Post by omar on Apr 14^th, 2005, 12:39pm

on 04/14/05 at 05:30:43, 99of9 wrote:

The nice thing about using random bots is that we can generate a lot more games with random bots than with bots that say take even 10 seconds per move. If we also assume that searching a few plys is not that far from random then the results from the random bots should be pretty close to what we find with the thinking bots.

Title: Re: How great an advantage is the first move?
Post by omar on Apr 14^th, 2005, 2:04pm

I found the data for the Connect4 games. I had setup a process to generate this last year and forgot about it. It finished and produced the data file, but I didn't look at it until now.

The Connect4 results tend to support that idea that first move advantage is higher at random play and gets lower with increasing search depth. But then shoots up again as play starts to approach near perfect.

Here is the self play data seperated by even and odd ply.

==> p0-p0 <==
as X wins=550 draws=2 lost=448 games=1000
as O wins=458 draws=2 lost=540 games=1000

==> p2-p2 <==
as X wins=488 draws=93 lost=419 games=1000
as O wins=424 draws=88 lost=488 games=1000

==> p4-p4 <==
as X wins=403 draws=183 lost=414 games=1000
as O wins=407 draws=159 lost=434 games=1000

==> p6-p6 <==
as X wins=395 draws=174 lost=431 games=1000
as O wins=374 draws=212 lost=414 games=1000

==> p8-p8 <==
as X wins=503 draws=142 lost=355 games=1000
as O wins=373 draws=159 lost=468 games=1000

First move advantage
p0 54.6%
p2 53.7%
p4 50.5%
p6 50.1%
p8 57.2%

==> p1-p1 <==
as X wins=617 draws=0 lost=383 games=1000
as O wins=379 draws=0 lost=621 games=1000

==> p3-p3 <==
as X wins=526 draws=19 lost=455 games=1000
as O wins=436 draws=24 lost=540 games=1000

==> p5-p5 <==
as X wins=522 draws=52 lost=426 games=1000
as O wins=462 draws=56 lost=482 games=1000

==> p7-p7 <==
as X wins=540 draws=64 lost=396 games=1000
as O wins=403 draws=68 lost=529 games=1000

First move advantage
p1 61.9%
p3 54.5%
p5 53.1%
p7 57.2%

I will try to see if I can generate some data for p9 and p10 so we can see if it continues to shoot up.

This data suggests that running self play experiments with random bots may help determine the worst case intrinsice first move advantage for non perfect play. But we have to check if the first move advantage also decreases if the bots have heuristics. These bots picked a random move unless the search showed and end node and had no heuristics.

Title: Re: How great an advantage is the first move?
Post by Fritzlein on Apr 14^th, 2005, 3:45pm

OK, Omar, I downloaded that database of chess games, and I used SCID and your methodology from your analysis of draws. The results show no decline in the advantage of moving first as the players get stronger.

Rating Wins Draws Losses Avg. Score
1600 63 35 40 0.583
1700 274 186 226 0.535
1800 440 317 352 0.540
1900 942 750 739 0.542
2000 1913 1694 1502 0.540
2100 5515 4576 4350 0.540
2200 18689 16553 14545 0.542
2300 37993 37469 28782 0.544
2400 43989 55673 30648 0.551
2500 34626 53263 22870 0.553
2600 12407 22860 8077 0.550
>2600 2063 4079 1323 0.550

I was a little suspicious of your method of setting the filters, because, for example, for the 1800 category you let white's rating run from 1700 to 1900, black's rating run from 1700 to 1900, and they had to be within 50 points of each other. But a game with white rated 1820 and black rated 1860 will be counted in both this and the 1900 category. If you count games in more than one category, you are probably unintentionally smoothing the data.

To count each game exactly once (if the players are within 50 rating points) I decided to filter only on white's rating and on the rating difference. Sure enough, the data looks somewhat choppier that way:

W Rating Wins Draws Losses Avg. Score
<1650 27 21 25 0.514
1650-1749 69 37 46 0.576
1750-1849 311 228 265 0.529
1850-1949 289 237 211 0.553
1950-2049 1086 934 895 0.533
2050-2149 1760 1615 1398 0.538
2150-2249 9413 8139 7743 0.533
2250-2349 21112 20435 16080 0.544
2350-2449 23875 30605 16958 0.548
2450-2549 20378 31589 12913 0.558
>2549 7923 14167 4820 0.558

But the conclusion is the same in my eyes: there is no discernable correlation between playing strength and the advantage of the first move.

Title: Re: How great an advantage is the first move?
Post by omar on Apr 16^th, 2005, 12:03pm

on 04/14/05 at 17:45:14, Arimanator wrote:

I believe Omar must be commended to have managed to create a game where the forces are so well balanced that no important advantage can be held onto without an impeccable technique and steadiness of game.

Thanks for the nice comments Pat. But really I just got very lucky. There was no way for me to know just how balanced the game would be in the long run. Even now we think it may be well balanced, but some strategy might come up that tips the scale to either too offensive or too defensive.

I did experiment with a lot of variations. So much so that my own relatives got tired of the rules changing and eventually stopped helping me test them :-) I've written a little summary about how Arimaa was created on the 'About' page.
http://arimaa.com/arimaa/about/

Title: Re: How great an advantage is the first move?
Post by omar on Apr 16^th, 2005, 12:37pm

on 04/14/05 at 15:45:23, Fritzlein wrote:

But the conclusion is the same in my eyes: there is no discernable correlation between playing strength and the advantage of the first move.

Thanks for trying this out Karl; that's interesting data. So it looks like there is about a 3 to 4 percent advantage for white in chess.

I have to agree with you that there does not seem to be any trend to suggest that the first move advantage decreases with increasing play streangth. But keep in mind that with this data we are only looking at a small piece in the middle of the curve. At the extream ends of the curve (near random play and perfect play) Im sure we would see the treand as we do in the simple games. Also Im not sure what effect heuristics have on this compared to random-or-perfect play. Im running some experiments with Connect4 to see if heuristics increases or decreases the first move advantage compared to random-or-perfect play.