Author |
Topic: Measure stereotyped openings (Read 16514 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Measure stereotyped openings
« on: Apr 8th, 2008, 2:24pm » |
 Quote  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
Gender:
Posts: 5928
|
|
Re: Measure stereotyped openings
« Reply #1 on: Apr 8th, 2008, 2:48pm » |
Quote 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 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
Gender:
Posts: 5928
|
|
Re: Measure stereotyped openings
« Reply #3 on: Apr 8th, 2008, 6:22pm » |
Quote 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:
Posts: 254
|
|
Re: Measure stereotyped openings
« Reply #4 on: Apr 10th, 2008, 6:15am » |
Quote 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:
Posts: 254
|
|
Re: Measure stereotyped openings
« Reply #5 on: Apr 10th, 2008, 6:22am » |
Quote 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:
Posts: 254
|
|
Re: Measure stereotyped openings
« Reply #6 on: Apr 10th, 2008, 6:30am » |
Quote 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 |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Measure stereotyped openings
« Reply #8 on: Apr 10th, 2008, 12:03pm » |
Quote 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
Gender:
Posts: 5928
|
|
Re: Measure stereotyped openings
« Reply #9 on: Apr 10th, 2008, 12:15pm » |
Quote Modify
|
on Apr 10th, 2008, 11:49am, woh wrote:
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 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:
Posts: 553
|
|
Re: Measure stereotyped openings
« Reply #11 on: Apr 10th, 2008, 12:54pm » |
Quote Modify
|
on Apr 10th, 2008, 11:49am, woh 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.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Measure stereotyped openings
« Reply #12 on: Apr 10th, 2008, 1:00pm » |
Quote 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:
Posts: 553
|
|
Re: Measure stereotyped openings
« Reply #13 on: Apr 10th, 2008, 1:07pm » |
Quote 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 Modify
|
Go to Settings, Game Client and change the client to version 2.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print