Author |
Topic: A look at Arimaa branching factor. (Read 5385 times) |
|
Janzert
Forum Guru
Arimaa player #247
Gender: 
Posts: 1016
|
 |
A look at Arimaa branching factor.
« on: Mar 6th, 2006, 1:04am » |
 Quote  Modify
|
As some of you know I've been taking a small look at the arimaa branching factor as shown in the database of past games. This "small" look has stretched into 2+ months but finally there are some actual results in a decent form for people to look at.
I've put it online at http://arimaa.janzert.com/bf_study/. Have a look and post your thoughts.
Janzert
[Edit 2-18-2010: update link]
|
| « Last Edit: Feb 17th, 2010, 10:37pm by Janzert » |
 IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: A look at Arimaa branching factor.
« Reply #1 on: Mar 7th, 2006, 10:29am » |
Quote Modify
|
Wow, this is really amazing Brian. I had often tried to picuture what a graph of move number vs unique moves would look like. Thanks to your efforts, I've finally seen one.
The graph comparing win vs lose is quite surprising. I didn't expect there to be such big difference. For bot developers this may suggest taking mobility into consideration when evaluating positions. Also does this suggest that by looking at the rate of change of mobility we may be able to predict which side will win quite early in the game.
Your report suggests that my estimate of 20,000 possible moves as mentioned on the arimaa.com front page was a bit optimistic. I'll have to revise that page now  But I'll archive the original version.
You now the data needed to calculate the "Practical Game Tree Complexity" of Arimaa. For each move number weight the unique number of moves by the percentage of games which reach that move and then sum up the results. This number will be much more accurate than the estimated calculations which make an assumtion about the average number of moves and average game length. I think this may be the first time someone has ever computed such a number for any game. I've never seen this done for chess or any other game.
Thanks so much for all the effort you've put into producing this report.
|
| « Last Edit: Mar 7th, 2006, 10:31am by omar » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: A look at Arimaa branching factor.
« Reply #2 on: Mar 7th, 2006, 3:02pm » |
Quote Modify
|
on Mar 7th, 2006, 10:29am, omar wrote:| The graph comparing win vs lose is quite surprising. I didn't expect there to be such big difference. For bot developers this may suggest taking mobility into consideration when evaluating positions. Also does this suggest that by looking at the rate of change of mobility we may be able to predict which side will win quite early in the game. |
|
This is mostly because the side that loses more pieces automatically has less possible moves.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: A look at Arimaa branching factor.
« Reply #3 on: Mar 7th, 2006, 3:03pm » |
Quote Modify
|
This is amazingly cool analysis, Janzert. Thanks for putting in all the time to compile it. A few comments:
* Thanks for changing the spikes to bars in the second graph.
* For all the calculations of mean number of moves, wouldn't it be better to calculate geometric mean rather than arithmetic mean? If I have 4 choices on one move and 16 choices the next, it will produce as many leaves on my search tree as having 8 choices each move, i.e. less than arithmetic mean of 10 choices each move.
* I'm astonished that the average number of available moves peaks as early as move 8. In a defensive game, that's barely long enough to complete a rabbit pull, never mind mixing it up with additional pieces once a piece gets framed. I wonder how the decline in number of available moves correlates with the number of pieces remaining, i.e. if the reason for the decline is that usually a piece or two has been captured by that point, particularly in beginner games. I have trouble believing an alternative hypothesis, i.e. that positions have a tendency to get knotted up with both elephants deadlocked around the same trap.
* It seems that captures must be to blame for a decreasing branching factor. An interesting way to check this would be to throw out all positions before move ten, and then compare number of available moves, not correlated with move number, but correlated with the size of one's army. Alternatively, if one controlled for army size, the number of available moves might be monotonically increasing throughout the game.
* It is in line with my intuition that the maximum number of available moves on a given move number doesn't decline rapidly, and in fact the maximum maximum was as late as move 58. Games which are knotted up can often explode quite late and create wild middlegames and wild endgames, although I guess that is the exception rather than the rule.
* Megamau and I apparently played our "fastest immobilization" game after the cutoff for your database, because otherwise the minimum number of moves would have hit zero on move 6 already.
* It is interesting that the number of moves for the eventual loser peaks above that of the number for the eventual winner. Probably this is due to tons of ShallowBlue and Arimaazilla games in which the bot advances recklessly in the opening moves. I don't think it can be a reliable commentary on the effectiveness of aggressive play otherwise.
* It would be interesting to reverse the time axis based on the number of moves before goal, particularly for the losing side. For example, does the eventual loser generally have a lot fewer moves available one move before losing than he had two moves before losing? Probably so given that the second-last move may well be a capture.
* I wouldn't have guessed that hvh games would have a lower average branching factor than hvb games, but it isn't hard to imagine an explanation. Perhaps humans have a natural tendency to seek simplicity, whereas bots don't care whether the position is more complicated or less.
All in all, a fascinating read. Thanks again, Janzert.
|
| « Last Edit: Mar 7th, 2006, 3:08pm by Fritzlein » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: A look at Arimaa branching factor.
« Reply #4 on: Mar 8th, 2006, 12:53pm » |
Quote Modify
|
Brian, I would be very interested to see how the first graph would look if you limited the games to ones where both players have a rating above 1700.
Also if you could provide a comma delimited file with: game id, plycount, unique moves; perhaps other could also try their own analysis.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: A look at Arimaa branching factor.
« Reply #5 on: Mar 10th, 2006, 11:01pm » |
Quote Modify
|
on Mar 7th, 2006, 10:29am, omar wrote:| You now the data needed to calculate the "Practical Game Tree Complexity" of Arimaa. For each move number weight the unique number of moves by the percentage of games which reach that move and then sum up the results. |
|
That would be interesting.
What should be done when reaching later turns for which there aren't enough games to be statistically significant? Also, if I understand the definition of Game Tree Complexity correctly, won't the result be larger than it should be since it doesn't take into account different moves reaching the same position?
on Mar 7th, 2006, 3:03pm, Fritzlein wrote:| * Thanks for changing the spikes to bars in the second graph. |
|
A little time in a graphics manipulation program can change lots of results. 
Quote:| * For all the calculations of mean number of moves, wouldn't it be better to calculate geometric mean rather than arithmetic mean? If I have 4 choices on one move and 16 choices the next, it will produce as many leaves on my search tree as having 8 choices each move, i.e. less than arithmetic mean of 10 choices each move. |
|
Hmm. Yes, you're right the geometric mean would seem best when combining multiple turns together to come up with an overall game mean. When looking at, or thinking of it as, a simple collection of moves, or maybe better positions, I think the arithmetic mean might still be best.
So for instance the last two graphs in the report show a mean that is essentially the arithmetic mean of the arithmetic mean of each game. Whereas it would be better to have the arithmetic mean of the geometric mean of each game, correct?
Quote:* I'm astonished that the average number of available moves peaks as early as move 8. In a defensive game, that's barely long enough to complete a rabbit pull, never mind mixing it up with additional pieces once a piece gets framed. I wonder how the decline in number of available moves correlates with the number of pieces remaining, i.e. if the reason for the decline is that usually a piece or two has been captured by that point, particularly in beginner games. I have trouble believing an alternative hypothesis, i.e. that positions have a tendency to get knotted up with both elephants deadlocked around the same trap.
* It seems that captures must be to blame for a decreasing branching factor. An interesting way to check this would be to throw out all positions before move ten, and then compare number of available moves, not correlated with move number, but correlated with the size of one's army. Alternatively, if one controlled for army size, the number of available moves might be monotonically increasing throughout the game. |
|
Yeah, Ryan already mentioned looking at the correlation between piece count and available moves. Unfortunately it'll take a little work to set this up.
Quote:| * It is in line with my intuition that the maximum number of available moves on a given move number doesn't decline rapidly, and in fact the maximum maximum was as late as move 58. Games which are knotted up can often explode quite late and create wild middlegames and wild endgames, although I guess that is the exception rather than the rule. |
|
I had been thinking about posting some graphs of the available moves throughout some individual games. Anyone have some specific games they'd like to see?
Quote:| * Megamau and I apparently played our "fastest immobilization" game after the cutoff for your database, because otherwise the minimum number of moves would have hit zero on move 6 already. |
|
Yep, looks like it took place on January 13. You should have been 2 weeks quicker.
Quote:| * It is interesting that the number of moves for the eventual loser peaks above that of the number for the eventual winner. Probably this is due to tons of ShallowBlue and Arimaazilla games in which the bot advances recklessly in the opening moves. I don't think it can be a reliable commentary on the effectiveness of aggressive play otherwise. |
|
Unfortunately I'm afraid alot of the graphs may be "tainted" by bad bot behaviour. The total number of games looked at was 23022, but there are only 1447 hvh games. The majority are hvb with 18883 games.
Quote:| * It would be interesting to reverse the time axis based on the number of moves before goal, particularly for the losing side. For example, does the eventual loser generally have a lot fewer moves available one move before losing than he had two moves before losing? Probably so given that the second-last move may well be a capture. |
|
This is another thing that I've thought would be interesting to look at in the future. Like the piece correlation above it will take a little setup to make it happen.
on Mar 8th, 2006, 12:53pm, omar wrote:| Brian, I would be very interested to see how the first graph would look if you limited the games to ones where both players have a rating above 1700. |
|
Here it is, HvH 1700+ per move using all games up to the beginning of this week (March 5).
The one problem with trying to look at hvh 1700+ is the relatively small number of games that have been played. After updating with all the games that have been played so far this year, there are still only 607 hvh1700+ games. I cut the above graph off at move 68 after which the number of turns played drops below 50 or around 25 games.
The peak mean is at turn 15 with 20407 unique moves. This is a little later, a little lower and seemingly somewhat broader with a slower fall off than the overall results.
Also here is a clip showing the histograms for the first 50 moves.
It's probably too few games to draw much of a conclusion from the later turns. But it does give at least a rough idea of the differences.
Quote:| Also if you could provide a comma delimited file with: game id, plycount, unique moves; perhaps other could also try their own analysis. |
|
Sure, I also added a few fields to make it a little easier to double check that it's getting applied to the right move and a short form of the board (similiar to what the move generator outputs with the 'p' option).
One gotcha to remember if trying to use this. The board is the resulting board after that move is taken and the replies are the number of unique replies possible to the move. Don't use them as the possible moves on that move. So the replies are the following turn's possible moves. You'll also notice there is a field marking moves that result in goal with the possible replies set to 0 when true.
Anyway the file containing all moves up to the beginning of this week is here, it's just under 18MB.
Omar, if you this available permanently would you mind hosting it somewhere? I'll probably be taking it down after a few weeks.
Janzert
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: A look at Arimaa branching factor.
« Reply #6 on: Mar 15th, 2006, 4:49pm » |
Quote Modify
|
Thanks for the graph Brian. It confirms what I suspected; mainly that the peak should be more to the right in well played games.
Also thanks for making the data available. I have placed it in the download section of the Arimaa site.
Quote:
What should be done when reaching later turns for which there aren't enough games to be statistically significant?
|
|
Well we could wait till there are more games, but I don't think it will change the result much since less weight will be given to those turns due to smaller and smaller percentage of games reaching higher turns.
Quote:
Also, if I understand the definition of Game Tree Complexity correctly, won't the result be larger than it should be since it doesn't take into account different moves reaching the same position?
|
|
Yes, but that's just how game tree complexity is defined.
GTC = (average moves per turn) * (2*average game length)
For example for Arimaa it might be:
GTC_Arimaa = 17,000^(2*30)
assuming average of 17,000 movers per turn and a game length of 30 moves.
Using the data you have this can be done as:
GTC_Arimaa = (average moves on 1w)*(fraction of games that reach 1w) * (average moves on 1b)*(fraction of games that reach 1b) * (average moves on 2w)*(fraction of games that reach 2w) * so on.
This number will be less than the 10^440 mentioned in the Wikipedia. I think that was calculated as 20,000^(2*50).
|
|
IP Logged |
|
|
|
frostlad
Forum Senior Member
Arimaa player #1704
Gender:
Posts: 46
|
|
Re: A look at Arimaa branching factor.
« Reply #7 on: Mar 16th, 2006, 3:41am » |
Quote Modify
|
on Mar 7th, 2006, 3:03pm, Fritzlein wrote:
* It seems that captures must be to blame for a decreasing branching factor. An interesting way to check this would be to throw out all positions before move ten, and then compare number of available moves, not correlated with move number, but correlated with the size of one's army. Alternatively, if one controlled for army size, the number of available moves might be monotonically increasing throughout the game.
|
|
It also would make sense that one or two advanced noble pieces would decrease the branching factor in that if a piece is frozen it is as almost worse than being captured in that it can't move, and it could be blocking other friendly pieces from moving if enough of them are bunched up near the back line.
This is an amazing analysis of the branching factor. Very interesting to read through even for someone beginning to play. It gives me an idea of what I'm getting myself into.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: A look at Arimaa branching factor.
« Reply #8 on: Mar 16th, 2006, 4:18pm » |
Quote Modify
|
on Mar 10th, 2006, 11:01pm, Janzert wrote:Hmm. Yes, you're right the geometric mean would seem best when combining multiple turns together to come up with an overall game mean. When looking at, or thinking of it as, a simple collection of moves, or maybe better positions, I think the arithmetic mean might still be best.
So for instance the last two graphs in the report show a mean that is essentially the arithmetic mean of the arithmetic mean of each game. Whereas it would be better to have the arithmetic mean of the geometric mean of each game, correct? |
|
Hmmm... What are we trying to get at with the "average" branching factor? Why do we care about that number? In my mind we want to provide a guesstimate of feasible brute force computer search depth, if we were to plunk a computer down into a random position.
I don't quite warm up to the definition of "random position" that works like this: first choose a game, giving all games equal probability, then choose a position within that game giving all positions equal probability. Why give all games equal weight rather than all positions? If you consider the total set of positions a computer will have to face in its lifetime, long games contribute proportionally more to that set than short games.
My instinct is therefore to take the whole mass of positions, and take the geometric mean of the number of possible moves. Indeed, I think this is also the number you want to raise to the power of (2 * average game length) to get a reasonable definition of game tree complexity.
I would, however, spend some energy limiting which games are allowed in the set, perhaps by looking at only games with both players (bot and human) rated 1700+.
Quote:| I had been thinking about posting some graphs of the available moves throughout some individual games. Anyone have some specific games they'd like to see? |
|
If you would provide numbers of unique moves for each position in game 15552, my postal game against Omar which I commented on in the local Wiki, I would love to include them in the article. Maybe that would help us build up our intuition as to how various changes in the position affect the move count.
Quote:
Here it is, HvH 1700+ per move using all games up to the beginning of this week (March 5). |
|
Thanks for this. It is interesting that it peaks later than the general graph. This raise another question, though: does it have the same shape as the other graph, but stretched out horizontally? If it is the same shape, then one of these games will have the same average branching factor as another. If, however, it is more "humped" (i.e. staying high until the game abruptly ends) then these games may have a higher average branching factor.
Again, thanks for this great analysis. It is cool to have some hard numbers for comparison against other games.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: A look at Arimaa branching factor.
« Reply #9 on: Mar 16th, 2006, 10:14pm » |
Quote Modify
|
on Mar 16th, 2006, 4:18pm, Fritzlein wrote:| If you would provide numbers of unique moves for each position in game 15552, my postal game against Omar which I commented on in the local Wiki, I would love to include them in the article. Maybe that would help us build up our intuition as to how various changes in the position affect the move count. |
|
Here it is:
The highest number of possible moves occurs at move 20w with 51818.
Also here are the details for the game:
The columns are, move number, possible moves for gold, possible moves for silver.
Code:# Game #15552 between omar and Fritzlein. Fritzlein wins
2 3331 2161
3 6120 7833
4 19357 12431
5 15515 11202
6 21108 8777
7 18317 9440
8 27234 10135
9 18263 8145
10 32002 6728
11 39496 4830
12 45180 9150
13 32446 8854
14 34262 5838
15 34275 9722
16 32465 10193
17 38799 15243
18 37052 27138
19 51499 12752
20 51818 7122
21 38432 9184
22 33052 12207
23 28561 8208
24 32500 23978
25 37332 19048
26 23602 33494
27 31083 27690
28 29465 19103
29 19888 29228
30 11146 27614
31 10967 27218
32 15369 35497
33 31601 28829
34 36500 28930
35 23887 26090
36 13666 23976
37 13598 23045
38 21189 32473
39 18066 15444
40 13500 14927
41 13385 13884
42 14836 9923
43 16328 8464
44 23329 16318
45 23984 18023
46 24558 17462
47 9403 17535
48 11753 6652
49 19420 10996
50 15740 8614
51 6996 5128
52 7748 3691
53 7271 4918
54 7575 5734
55 8188 2459
56 8125 5067
57 6385 7466
58 6199 7721
59 4984 6347
60 1410 10288
61 2836 6793
62 2646 6325
63 4225 7453
64 2147 6734
65 1140 4959
66 1074 4710
67 524 2677
68 760 1812
|
|
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: A look at Arimaa branching factor.
« Reply #10 on: Mar 17th, 2006, 10:10am » |
Quote Modify
|
Thanks, Janzert. I'll put it in the commentary when Omar sends me the TWiki password. Some interesting points:
* At first glance, the number of available moves has no relationship to who is winning.
* On moves 23w and 24w, when I say in my commentary that Omar had only one playable move in each case, his actual number of choices was 28,561 and 32,500 respectively.
* My mobility peaked from moves 25 to 40, much later than the average curve. Coincidentally (?) moves 30 to 40 was the time that I was strategically losing my grip on the position and squandering my advantage.
*Omar had more pieces than I did from move 43 onward, but for half of the rest of the game I had more move choices.
* There were no captures from move 54 forward, but there were significant changes in mobility. In the waning moves of the game, as I got closer and closer to a forced win, not only did Omar's mobility decline, mine did as well, to its lowest point in the game. Perhaps this was because I wasn't just trying to make my own goal, I was also trying to shut down his counterplay.
* Maybe graphing the number of moves on a logarithmic scale makes more sense. For example, it would better display out the dramatic changes in mobility toward the end, which were proportionally at least as great as the midgame changes, which are graphed as huge jags.
Thanks again, Janzert.
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: A look at Arimaa branching factor.
« Reply #11 on: Mar 17th, 2006, 10:52am » |
Quote Modify
|
I actually had taken a look at it with a log scale and thought it flatten the middle out too much, but maybe it is better.
Janzert
|
|
IP Logged |
|
|
|
msyed
Forum Newbie
Arimaa player #5015
Gender:
Posts: 1
|
|
Re: A look at Arimaa branching factor.
« Reply #12 on: Feb 17th, 2010, 7:43pm » |
Quote Modify
|
The link to the article isn't working.
Thanks.
|
|
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: A look at Arimaa branching factor.
« Reply #13 on: Feb 17th, 2010, 7:56pm » |
Quote Modify
|
Try this one instead.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print