Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 1:01pm

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum « Measure stereotyped openings »


   Arimaa Forum
   Arimaa
   General Discussion
(Moderator: supersamu)
   Measure stereotyped openings
« Previous topic | Next topic »
Pages: 1 2 3  ...  5 Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Measure stereotyped openings  (Read 16066 times)
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Measure stereotyped openings
« on: Apr 8th, 2008, 2:24pm »
Quote Quote Modify Modify

In another thread, gatsby suggested a way to avoid stereotyped openings.  At the present, standardized play seems to be a total non-issue.  Can we quantify this somehow?
 
The metric I would like is to look at all rated games between humans in the entire database, and see how quickly they diverge into distinct positions.  There might be 5000 such games, and the statistic might look like this:
 
After 1w, there are 50 distinct positions, 4950 duplicates
After 1b, there are 1000 distinct positions, 4000 duplicates
After 2w, there are 4000 distinct positions, 1000 duplicates
After 2b, there are 4850 distinct positions, 150 duplicates
After 3w, there are 4980 distinct positions, 20 duplicates
After 3b, there are 4998 distinct positions, 2 duplicates
After 4w, there are 5000 distinct positions, 0 duplicates
 
I'm curious what the exact shape of this curve will be, and what is the longest that two games have coincided.  It would be great marketing to say that no two games have ever been identical after four moves.
 
Generating these numbers is beyond me, but would it be super-much trouble for someone who has already has a game database and a hashing function?  Janzert?  99of9?  Actually I have a vague recollection that 99of9 already did something like this to generate an opening book for Gnobot...
IP Logged

Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Measure stereotyped openings
« Reply #1 on: Apr 8th, 2008, 2:48pm »
Quote Quote Modify Modify

Actually, a much cooler measure of how stereotyped openings are would be Claude Shannon's measure of entropy.  If there are only ten setups that have ever been tried for Gold, there is less diversity (entropy) if the distribution is
 
4991, 1, 1, 1, 1, 1, 1, 1, 1, 1
 
and more diversity if the distribution is  
 
500, 500, 500, 500, 500, 500, 500, 500, 500, 500
 
even though the two distributions each have 10 distinct positions and 4990 duplicates.  By Shannon's measure the first distribution has entropy 0.025 and the second has entropy 3.32.  If we get up to five thousand distinct positions having occurred once each, the entropy is 12.29.
 
The second nice feature of using Shannon entropy is that one could compare it to a selection of 5000 random chess games from some database, and see the relative speed at which the two games break away from the grip of the opening and into something unique.
IP Logged

aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 768
Re: Measure stereotyped openings
« Reply #2 on: Apr 8th, 2008, 2:49pm »
Quote Quote Modify Modify

You're getting ahead of yourself there. Currently, only 3772 rated games have been played between humans so far. I frankly think that's too little to get any meaningful statistics about the diverging nature of Arimaa.
IP Logged
Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Measure stereotyped openings
« Reply #3 on: Apr 8th, 2008, 6:22pm »
Quote Quote Modify Modify

Yes, it is far too early to know if Arimaa will be prone to stereotyped openings once we know how to play it well.  Even if we fall into repeating openings some day, it may be positions that aren't even in the database yet.  I guess I just wanted to say how divergent openings are so far...
IP Logged

woh
Forum Guru
*****



Arimaa player #2128

   


Gender: male
Posts: 254
Re: Measure stereotyped openings
« Reply #4 on: Apr 10th, 2008, 6:15am »
Quote Quote Modify Modify

As of march 31 3745 rated HvH games have been played. Only 3719 lasted till turn 4b. 3701 board positions occured only in one those games and 9 board positions occured in two games each. So after 4b, there are 3710 distinct positions and 9 duplicates.
 
More results:

      total    distinct  duplicate
1w    3745     605      3140    
1b    3745     1977     1768
2w    3745     2547     1198
2b    3745     2993     752
3w    3745     3459     286
3b    3738     3641     97
4w    3726     3693     33
4b    3719     3710     9

IP Logged

woh
Forum Guru
*****



Arimaa player #2128

   


Gender: male
Posts: 254
Re: Measure stereotyped openings
« Reply #5 on: Apr 10th, 2008, 6:22am »
Quote Quote Modify Modify

The distribution of the positions after each move is:
 

1w    784 x1   778 x1   273 x1   140 x1    ...   4 x10   3 x31   2 x78   1 x420
1b    195 x1   188 x1   178 x1   143 x1    ...   4 x27   3 x47   2 x135  1 x1680
2w    103 x1    94 x1    57 x1    56 x1    ...   4 x26   3 x61   2 x148  1 x2155
2b     34 x1    29 x1    26 x1    24 x1    ...   4 x26   3 x47   2 x148  1 x2723
3w      9 x1     8 x3     7 x4     6 x1   5 x6   4 x9    3 x28   2 x121  1 x3283
3b                                        5 x2           3 x11   2 x67   1 x3561
4w                                                       3 x3    2 x27   1 x3663
4b                                                               2 x9    1 x3701
IP Logged

woh
Forum Guru
*****



Arimaa player #2128

   


Gender: male
Posts: 254
Re: Measure stereotyped openings
« Reply #6 on: Apr 10th, 2008, 6:30am »
Quote Quote Modify Modify

To clearify the data in the previous post:
 
After 3b 2 board positions occured in 5 games each, 11 positions in 3 games each, 67 positions occured in 2 games each and 3561 positions occured only in one game, for a total of 3738 games.
 
The entropy after each turn is:
1w     5.6121    (max 11.87)
1b     9.4795    (max 11.87)
2w    10.4058    (max 11.87)
2b    11.2211    (max 11.87)
3w    11.6808    (max 11.87)
3b    11.8120    (max 11.868 )
4w    11.8451    (max 11.8634)
4b    11.8559    (max 11.8607)
« Last Edit: Apr 10th, 2008, 12:00pm by woh » IP Logged

woh
Forum Guru
*****



Arimaa player #2128

   


Gender: male
Posts: 254
Re: Measure stereotyped openings
« Reply #7 on: Apr 10th, 2008, 11:49am »
Quote Quote Modify Modify

After Gold setup the most popular positions are:
 
1. 99of9 setup with cats behind the traps: 784 times
2. 99of9 setup with dogs behind the traps: 778 times
3. default setup: 273 times
4. omar setup: 140 times
IP Logged

Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Measure stereotyped openings
« Reply #8 on: Apr 10th, 2008, 12:03pm »
Quote Quote Modify Modify

Woh, thank you so much for running these numbers!  I didn't know you had implemented your own position hash function.  When can we expect your bot in the game room?
 
on Apr 10th, 2008, 6:15am, woh wrote:

      total    distinct  duplicate
1w    3745     605      3140    
1b    3745     1977     1768


I'm astonished that there have been 605 unique setups for Gold in HvH games.  Even with symmetry knocking out half of them (and one would expect that not all setups have been tried in reflection) that's hundreds of Gold setups we have collectively tried.  I almost can't believe it.  Are you sure that you counted it as a duplicate if the same setup was reached in a different order of steps?
 
on Apr 10th, 2008, 6:30am, woh wrote:
The entropy after each turn is:
1w     5.6121
1b     9.4795

I would like to measure the corresponding entropy for chess.  I suspect it is less than 2.0 after 1w and about 4.0 after 1b, but one would have to measure to be sure.  This is something it is probably within my skill to measure from a chess database, since one doesn't have to worry about transposed steps in the first two ply of chess.
 
But it is interesting to note that the theoretical most entropy possible on the first two ply of chess is lg(20^2), since each side has only twenty possible moves.  That works out to an entropy of 8.64.  That is to say, the players in Arimaa voluntarily provide more freshness in the opening than would be provided by the opening move of each player in chess being chosen entirely at random.  
 
Similarly the entropy provided by Fischerandom chess setup is only lg(960) = 9.9.  Players in Arimaa who are trying to win, trying to select the single best move, apparently provide as much variety in the setups as Fischer introduced with dice.
 
The Arimaa entropy approaches maximum too quickly to say much meaningful beyond the setup, but I see no reason that the huge branching factor won't continue to induce the players to provide their own variety throughout the game.  Even as we get better and better at Arimaa, there are just so many possible choices on each move that one can expect differences in taste and judgment to keep the game fresh from very early on.
« Last Edit: Apr 10th, 2008, 12:08pm by Fritzlein » IP Logged

Fritzlein
Forum Guru
*****



Arimaa player #706

   
Email

Gender: male
Posts: 5928
Re: Measure stereotyped openings
« Reply #9 on: Apr 10th, 2008, 12:15pm »
Quote Quote Modify Modify

on Apr 10th, 2008, 11:49am, woh wrote:
1. 99of9 setup with cats behind the traps: 784 times
2. 99of9 setup with dogs behind the traps: 778 times

I wonder if these two setups will eventually be like e4 and d4 in chess: dominant, equally popular, and entirely a matter of taste rather than quality.
« Last Edit: Apr 10th, 2008, 12:16pm by Fritzlein » IP Logged

aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 768
Re: Measure stereotyped openings
« Reply #10 on: Apr 10th, 2008, 12:52pm »
Quote Quote Modify Modify

on Apr 10th, 2008, 12:03pm, Fritzlein wrote:
But it is interesting to note that the theoretical most entropy possible on the first two ply of chess is lg(20^2), since each side has only twenty possible moves.  That works out to an entropy of 8.64.  That is to say, the players in Arimaa voluntarily provide more freshness in the opening than would be provided by the opening move of each player in chess being chosen entirely at random.

Which is exactly what makes me wonder whether it's fair to compare chess and Arimaa on a per half-move basis in the first place. I think what we should look for in a game is how little relative compression is possible of a typical database of games.
IP Logged
mistre
Forum Guru
*****





   


Gender: male
Posts: 553
Re: Measure stereotyped openings
« Reply #11 on: Apr 10th, 2008, 12:54pm »
Quote Quote Modify Modify

on Apr 10th, 2008, 11:49am, woh wrote:
After Gold setup the most popular positions are:
 
1. 99of9 setup with cats behind the traps: 784 times
2. 99of9 setup with dogs behind the traps: 778 times
3. default setup: 273 times
4. omar setup: 140 times

 
 
Can you continue this list down to at least the top 10?  I am curious.  Also, I wonder how many people would actually choose the default set-up if it wasn't the default. Any player that has any experience at all will begin to see that Horses on b2 and g2 are superior to dogs. Which is yet another reason to change the default set-up to the omar set-up.
 
IP Logged

aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 768
Re: Measure stereotyped openings
« Reply #12 on: Apr 10th, 2008, 1:00pm »
Quote Quote Modify Modify

on Apr 10th, 2008, 12:54pm, mistre wrote:
Can you continue this list down to at least the top 10?  I am curious.  Also, I wonder how many people would actually choose the default set-up if it wasn't the default. Any player that has any experience at all will begin to see that Horses on b2 and g2 are superior to dogs. Which is yet another reason to change the default set-up to the omar set-up.

 
Why not make it dynamically take the then currently most common opening (possibly only of rated human-vs-human games)?
 
Anyway, it shouldn't matter with the new client.
IP Logged
mistre
Forum Guru
*****





   


Gender: male
Posts: 553
Re: Measure stereotyped openings
« Reply #13 on: Apr 10th, 2008, 1:07pm »
Quote Quote Modify Modify

on Apr 10th, 2008, 1:00pm, aaaa wrote:

 
Anyway, it shouldn't matter with the new client.

 
What is this about a new client?
IP Logged

aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 768
Re: Measure stereotyped openings
« Reply #14 on: Apr 10th, 2008, 1:08pm »
Quote Quote Modify Modify

Go to Settings, Game Client and change the client to version 2.
IP Logged
Pages: 1 2 3  ...  5 Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB © 2000-2003. All Rights Reserved.