Arimaa Forum - Print Page


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

        Arimaa >> General Discussion >> First move advantage in CR vs CR
        
(Message started by: jdb on Aug 5^th, 2008, 10:22am)

Title: First move advantage in CR vs CR
Post by jdb on Aug 5^th, 2008, 10:22am

There was some discussion about whether the first move is an advantage in arimaa. If the pieces are reduced to CR vs CR, the following happens.

If the players can only set their pieces up only on the first rank:
Gold has 4*7 different setups and 3 of them win.
Rb1 Cd1
Rc1 Ce1
Rc1 Cf1

If the players can set their pieces up anywhere on the first two ranks:
Gold has 8*15 different setups and 6 of them win.

Setup Wins in
Ra1 Cd2 8
Rb1 Cc2 8
Rb1 Cd2 9
Rc1 Cd2 8
Rd1 Cd2 9
Rd1 Ce2 9

Title: Re: First move advantage in CR vs CR
Post by Janzert on Aug 5^th, 2008, 10:28am

On my initial read I thought you were saying 10% and 5% win rates respectively, but after a second look I see it's 75% win rate for both. Am I reading it correctly now?

Janzert

Title: Re: First move advantage in CR vs CR
Post by Fritzlein on Aug 5^th, 2008, 11:56am

Actually, it sounds like a forced win for Gold, because he can choose a setup that wins no matter what Silver does. Only if Gold is forced to make a random setup does Silver have a 90% (95%) chance of being able to force a win by playing optimally. Is that right?

Title: Re: First move advantage in CR vs CR
Post by jdb on Aug 5^th, 2008, 1:06pm

on 08/05/08 at 11:56:31, Fritzlein wrote:

Yes, in both cases gold has a forced win, but needs to choose the opening setup with care.

Title: Re: First move advantage in CR vs CR
Post by Fritzlein on Aug 5^th, 2008, 1:56pm

Thanks, JDB.

The winning setups are fascinating in both cases. When only the first rank is available, the gold rabbit can't go in the middle or on the corner. When both ranks are available, the gold rabbit can go anywhere on the back rank, but nowhere on the second rank. I wouldn't have anticipated either of these results. I would have thought Gold would want the rabbit a step closer to goal in the latter case. In the former case I would have expected either centralization or decentralization to be correct, but both are wrong.

As if I needed any more proof that I don't understand the endgame! At least it is good to centralize the cat, as I would have expected, but it blows my mind that Cd2 Ra1 wins for Gold while Cd2 Ra2 loses.

What is the length of Gold's shortest forced win against best Silver defense?

Title: Re: First move advantage in CR vs CR
Post by omar on Aug 7^th, 2008, 2:40pm

Very interesting. Thanks for posting this Jeff.

In the 1 row case 3 out 28 setups lead to a forced win by gold. So that means there are 25 setups which can be considered a blunder for gold because they don't lead to forced wins. So about 89% of the moves are blunders. For each of these 25 "gold blunders" there are 28 setups for silver with some of them leading to a forced win by silver. Thus out of the 25*28 positions I wonder how many lead to a forced win by silver. I wonder if the percentages for silver are about the same as for gold.

Title: Re: First move advantage in CR vs CR
Post by Fritzlein on Aug 8^th, 2008, 10:50am

It is interesting how we try to translate first-move advantage as calculated by a computer into human terms. On the one hand, it's pretty clear that even in this simplified CR vs CR game, Gold will not have a 100% chance to win in a game between two humans, because humans are prone to make mistakes. We don't want to accept JDB's absolute answer that it's a first player win, we want an answer that applies to us.

On the other hand, it is also clearly wrong to introduce error by considering random playouts. We know from Janzert that, from the starting position, having an extra rabbit is worth more to a random player than having an extra elephant. The randomized computer result applies to us even less than the infallible computer result.

It's somehow a question of how fast we approach the ideal. If we practiced the CR vs. CR endgame, how long would it take us to get 90% wins for Gold, and 90% wins for Silver if Gold chooses a non-winning setup? How hard is it to understand? Would we be able to play it perfectly after a day of study, or a week, or a month?

On the Internet Chess Club, there is (or at least used to be) a variant of king and three pawns versus king and three pawns, with the pawn masses of the two players on opposite sides. After a while people figured out how to achieve in practice what it was obvious to expect, namely that it is a forced win for white. Still, it was (is?) amusing and instructive to play that simplified endgame for a while.

Although JDB can tell us some theoretical things from his tablebase, he can't tell us how dramatic the CR vs CR endgame is. We would have to play it lots of times to know whether we can quickly squeeze the blunders out of our game, and quickly approach the theoretical perfection. Any kind of appeal to hypothesized randomness won't capture the real percentage chance of human misjudgment.

The game of Arimaa as a whole, since it is finite and drawless, is either a first-player win or a second-player win, unlike chess, which is probably a draw. We can expect that, the better we get at Arimaa, the more our actual win percentages will tilt in favor of the player with the theoretical win. One way to interpret the fact that actual winning percentages are about 50-50 is that we still stink at Arimaa!

All the fuss about trying to "balance" the game so that it is exactly equal was missing the point. It doesn't matter who has the theoretical advantage as long as the game is so complex and so far beyond our understanding that comebacks are common. If the winning percentage were 52-48, that wouldn't be a problem either. What _would_ be a problem is if, as our understanding improved, comebacks became rarer and rarer. It will kill Arimaa if it turns out that when one player gets an advantage, there is nothing the other player can do about it (nothing in human terms; obviously there can be no comebacks with theoretically perfect play). If Arimaa suffers from the "no comeback" flaw, then fiddling with the opening procedure to get the winning percentage back to 50-50 isn't going to save the game. What do I care if my winning chance at a broken game is 50% or 60%? The drama (as J. Mark Thompson calls it) will have gone out of Arimaa, an ill that can't be cured without radical rule changes.

Fortunately, we are are laughably far from Arimaa being undramatic. We still have great come-from-behind victories that can't be pinned on blunders. We can play mistake-free (to the best of our current knowledge) and still see games see-saw and hang fire for many moves. Here's hoping things stay that way for many years to come!

Title: Re: First move advantage in CR vs CR
Post by jdb on Aug 8^th, 2008, 5:00pm

on 08/07/08 at 14:40:04, omar wrote:

I tabulated this for the two row case.
There are 8*15 setups for gold and 16*15 setups for silver.
The second column is the number of gold wins out of the 240 possible silver setups.

Gold Setup Number of gold wins
Ra1 Cb1 200
Ra1 Cc1 210
Ra1 Cd1 223
Ra1 Ca2 200
Ra1 Cb2 213
Ra1 Cc2 228
Ra1 Cd2 240
Ra1 Ce1 223
Ra1 Cf1 217
Ra1 Cg1 194
Ra1 Ch1 172
Ra1 Ce2 235
Ra1 Cf2 223
Ra1 Cg2 219
Ra1 Ch2 194
Rb1 Ca1 176
Rb1 Cc1 207
Rb1 Cd1 239
Rb1 Ca2 204
Rb1 Cb2 218
Rb1 Cc2 240
Rb1 Cd2 240
Rb1 Ce1 231
Rb1 Cf1 213
Rb1 Cg1 195
Rb1 Ch1 170
Rb1 Ce2 239
Rb1 Cf2 231
Rb1 Cg2 213
Rb1 Ch2 195
Rc1 Ca1 179
Rc1 Cb1 193
Rc1 Cd1 237
Rc1 Ca2 193
Rc1 Cb2 219
Rc1 Cc2 238
Rc1 Cd2 240
Rc1 Ce1 238
Rc1 Cf1 210
Rc1 Cg1 187
Rc1 Ch1 173
Rc1 Ce2 239
Rc1 Cf2 238
Rc1 Cg2 213
Rc1 Ch2 187
Rd1 Ca1 161
Rd1 Cb1 194
Rd1 Cc1 215
Rd1 Ca2 194
Rd1 Cb2 216
Rd1 Cc2 234
Rd1 Cd2 240
Rd1 Ce1 236
Rd1 Cf1 216
Rd1 Cg1 195
Rd1 Ch1 162
Rd1 Ce2 240
Rd1 Cf2 237
Rd1 Cg2 218
Rd1 Ch2 195
Ra2 Ca1 117
Ra2 Cb1 148
Ra2 Cc1 133
Ra2 Cd1 174
Ra2 Cb2 161
Ra2 Cc2 181
Ra2 Cd2 205
Ra2 Ce1 167
Ra2 Cf1 161
Ra2 Cg1 140
Ra2 Ch1 113
Ra2 Ce2 203
Ra2 Cf2 181
Ra2 Cg2 176
Ra2 Ch2 141
Rb2 Ca1 135
Rb2 Cb1 140
Rb2 Cc1 139
Rb2 Cd1 193
Rb2 Ca2 157
Rb2 Cc2 199
Rb2 Cd2 204
Rb2 Ce1 173
Rb2 Cf1 145
Rb2 Cg1 148
Rb2 Ch1 125
Rb2 Ce2 208
Rb2 Cf2 182
Rb2 Cg2 175
Rb2 Ch2 151
Rc2 Ca1 120
Rc2 Cb1 141
Rc2 Cc1 148
Rc2 Cd1 173
Rc2 Ca2 151
Rc2 Cb2 182
Rc2 Cd2 230
Rc2 Ce1 186
Rc2 Cf1 144
Rc2 Cg1 147
Rc2 Ch1 128
Rc2 Ce2 204
Rc2 Cf2 192
Rc2 Cg2 178
Rc2 Ch2 153
Rd2 Ca1 104
Rd2 Cb1 144
Rd2 Cc1 139
Rd2 Cd1 163
Rd2 Ca2 145
Rd2 Cb2 165
Rd2 Cc2 177
Rd2 Ce1 173
Rd2 Cf1 149
Rd2 Cg1 137
Rd2 Ch1 99
Rd2 Ce2 231
Rd2 Cf2 187
Rd2 Cg2 167
Rd2 Ch2 141

Title: Re: First move advantage in CR vs CR
Post by omar on Aug 10^th, 2008, 5:57am

Thanks for posting this Jeff. It seems that if gold makes a blunder on 1g (95% chances) then silver has only a 76.65% chance of blundering on 1s. I got this by taking the sum of the numbers you posted not including the 6 lines that are 240 to get 20972. Dividing this by (120-6)*240 gives 0.76652.

I was expecting this number to be higher. Or maybe I am not calculating it right.

Title: Re: First move advantage in CR vs CR
Post by omar on Aug 10^th, 2008, 6:11am

Quote:

The game of Arimaa as a whole, since it is finite and drawless, is either a first-player win or a second-player win, unlike chess, which is probably a draw. We can expect that, the better we get at Arimaa, the more our actual win percentages will tilt in favor of the player with the theoretical win.

If Go on a odd size board is a win for the first player, I wonder if there seems to be an increase in the percentage of first player wins in Go as the rank of the players increases.

Title: Re: First move advantage in CR vs CR
Post by Fritzlein on Aug 10^th, 2008, 4:03pm

on 08/10/08 at 06:11:16, omar wrote:

If Go on a odd size board is a win for the first player, I wonder if there seems to be an increase in the percentage of first player wins in Go as the rank of the players increases.

Oh, yes. If Go is played on a 19x19 board with no komi, then beginners will win about 50% as black or white, and the better the players are, the more likely black is to win. Go with no komi is so lopsided as to be unsuitable for top tournament play.

To compensate for this the second player gets a komi of 5.5 free points. This doesn't change the fact that Go must be a theoretical win for one player or the other, but it is pretty close to 50-50 even at top levels. However, I have heard that the win percentages are deviating enough that some top players feel the first player still has an advantage, and the komi should be 6.5.

If I am not mistaken, there must be some integer komi (maybe 6?) at which 19x19 Go is a theoretical draw. If Go players got so good that 5.5 komi is won 60-40 for black while 6.5 komi is won 60-40 for white, what would they do? Accept an imbalanced game, or accept a game with draws? Fortunately Go players are still too far from perfect to have this dilemma.

Title: Re: First move advantage in CR vs CR
Post by Fritzlein on Aug 10^th, 2008, 4:10pm

on 08/10/08 at 05:57:21, omar wrote:

I was expecting this number to be higher.

Yes, I would expect that in a very sharp endgame, if the player on move has a forced win, then about 90% of random moves are blunders that convert the forced win into a forced loss. But why should our intuitions be at all accurate? We have never studied this stuff until now when JDB came along with his tablebases.

Title: Re: First move advantage in CR vs CR
Post by omar on Aug 11^th, 2008, 6:31pm

on 08/10/08 at 16:03:49, Fritzlein wrote:

Thanks, I didn't know that. So in tournament games where the players are not that strong are lower komi values used? Or is the same komi value used regardless of the strength of the players.

Title: Re: First move advantage in CR vs CR
Post by Fritzlein on Aug 11^th, 2008, 7:53pm

on 08/11/08 at 18:31:31, omar wrote:

Thanks, I didn't know that. So in tournament games where the players are not that strong are lower komi values used? Or is the same komi value used regardless of the strength of the players.

The same komi is used regardless, but what's 5.5 points in a game you might win by 75 points due to a massive blunder?

Title: Re: First move advantage in CR vs CR
Post by aaaa on Aug 11^th, 2008, 8:36pm

on 08/10/08 at 16:03:49, Fritzlein wrote:

To compensate for this the second player gets a komi of 5.5 free points. This doesn't change the fact that Go must be a theoretical win for one player or the other, but it is pretty close to 50-50 even at top levels. However, I have heard that the win percentages are deviating enough that some top players feel the first player still has an advantage, and the komi should be 6.5.

Standard komi in Japan has already been increased to 6.5 in 2002.

Title: Re: First move advantage in CR vs CR
Post by Fritzlein on Aug 11^th, 2008, 8:59pm

on 08/11/08 at 20:36:15, aaaa wrote:

Standard komi in Japan has already been increased to 6.5 in 2002.

I'm behind the times! I think when I first learned, komi was only 4.5 points.

Title: Re: First move advantage in CR vs CR
Post by Fritzlein on Jan 8^th, 2012, 2:44pm

on 08/05/08 at 10:22:06, jdb wrote:

There was some discussion about whether the first move is an advantage in arimaa. If the pieces are reduced to CR vs CR, the following happens.

I am struck again at how non-obvious the winning setups are. It would have taken me a long time to start a rabbit behind the trap (in the back row case) and an even longer time to start a rabbit on the back row (in the case where both home ranks are available).

Anyway, JDB, did you repeat this analysis for DCR vs DCR after you completed the six-piece tablebase? Clyring renewed my interest in this question in this thread (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=other;action=display;num=1319440780;start=15#22). Of course, with clueless entered in the World Computer Championship, I don't expect you to have time at the moment for any other hobby coding, but I thought it couldn't hurt to raise the question. :)

Title: Re: First move advantage in CR vs CR
Post by 99of9 on Jan 9^th, 2012, 3:53am

on 08/08/08 at 10:50:12, Fritzlein wrote:

The theoretical win has many many more moves than the games we play. So by this theory, the better we get, the longer the games will get. Which also means that all you aggressive players are making us all play worse :). Not only do we stink at Arimaa... but we're getting worse! :)