Author |
Topic: Reddit.com (Read 2412 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
According to Alexa, reddit.com is about three times as popular as metafilter.com. However, it looks like the surge of new players might be of a similar scale to what happened when we were mentioned on Metafilter, rather than three times as large.
|
|
 IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
 |
Re: Reddit.com
« Reply #2 on: Aug 4th, 2007, 1:22pm » |
 Quote  Modify
|
There is a discussion of the game complexity there and gives a link to a wikipedia article. The article says:
It's hard even to estimate the game-tree complexity, but for some games a reasonable lower bound can be given by raising the game's average branching factor to the power of the number of plies in an average game.
If I use the branching factor of about 17,000 that Janzert calculated here:
http://arimaa.janzert.com/bf_study/
and raise it to the 70 power, I get: 1.3x10^296 which is much higher than the 190 listed in the Wikipedia. I've updated the wikipedia page and added Janzert's page as a reference.
|
|
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: Reddit.com
« Reply #3 on: Aug 4th, 2007, 3:54pm » |
Quote Modify
|
Perhaps you can clarify for me. Is the 17000 branching factor the average number of choices for one player, or is it the average number of choices for a twofold move?
If an average game of Arimaa lasts 45 moves, then:
Half-move: 17000^90 = 10^380.74
Move: 17000^45 = 10^190.37 (and the Wiki is already right)
Of course, if you think an average game is 70 moves, then yes, it's a severe underestimation.
If two players play very passively, the gametree complexity could get almost infinitely larger as the game could go on almost endlessly, there being no 50-move rule as there is in chess. Do you only count meaningful games? Or do I misunderstand something?
|
| « Last Edit: Aug 4th, 2007, 3:58pm by The_Jeh » |
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Reddit.com
« Reply #4 on: Aug 4th, 2007, 5:08pm » |
Quote Modify
|
It's per half-move. 17000 for a play and a response would leave about 130 possibilities per player. That's even less than the number of ways to choose up to 4 out of 8 free pieces to move.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Reddit.com
« Reply #5 on: Aug 4th, 2007, 7:14pm » |
Quote Modify
|
Yes, 17,000 is the average number of unique new positions that can arise from a typical Arimaa position. This was computed from thousands of real games. It must have taken Janzert quite some time to run through all those, and I'm very thankful to him for having done this study; it answered a lot of questions.
I ran some queries on the games database to see what the total number of plies in rated games is really like. I think Fritzlein had ran some stats on this before, but I can't seem to find it at the moment.
For all rated games: average number of plies is 64.5 (44,856 games). Average number of moves would be half of this: 32.25.
When the rating of both players is greater than 1500 the average number of plies is 81.6 with 18747 games in the set. This is for rated games only. As the rating of both players increases the game length seems to increase but then levels off.
1500 81.6 (18747 games)
1600 85.6 (12865 games)
1700 88.7 (7784 games)
1800 91.1 (3688 games)
1900 96.0 (1313 games)
2000 91.1 (457 games)
2100 93.7 (128 games)
2200 89.8 (24 games)
From this it seems I was too conservative in using 70 as the ply count. A more realistic value for well played real games seems more like 90.
So 17000^90 gives: 5.5x10^380. Whoa, that's more than Go (10^360). OK I'll be more conservative and use 86; that gives: 6.5x10^363.
Humm, am I doing this right. Can others double check.
|
| « Last Edit: Aug 4th, 2007, 7:46pm by omar » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Reddit.com
« Reply #6 on: Aug 4th, 2007, 7:54pm » |
Quote Modify
|
on Aug 4th, 2007, 3:54pm, The_Jeh wrote:
If an average game of Arimaa lasts 45 moves, then:
Half-move: 17000^90 = 10^380.74
Move: 17000^45 = 10^190.37 (and the Wiki is already right)
|
|
Well the description of how to compute the game-tree complexity says to raise it to the number of plies. The definition of a ply is one turn taken by one player:
http://en.wikipedia.org/wiki/Ply_%28game_theory%29
So I think raising it to 90 is right.
|
| « Last Edit: Aug 4th, 2007, 7:56pm by omar » |
IP Logged |
|
|
|
aaaa
Forum Guru
Arimaa player #958
Posts: 768
|
|
Re: Reddit.com
« Reply #7 on: Aug 4th, 2007, 8:01pm » |
Quote Modify
|
The big problem here is that it looks like the number 17000 is an arithmetic mean and not a geometric one. Since the branch factor is clearly not constant judging from the same study, one can't just raise this number to the number of plies.
Additionally, I consider it a liability that such a large part of the games analyzed involves bots.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Reddit.com
« Reply #8 on: Aug 4th, 2007, 8:20pm » |
Quote Modify
|
Im noticing some errors in the Wikipedia Game complexity page. For Go it says the game length is 200 plies (actually the heading of the column says 'moves' and should be changed to say 'plies') but the game-tree complexity says: 10^360. If I assume 200 as the branching factor then the game-tree complexity should be: 200^200 = 10^460. So I looked up what Victor Allis said in his Thesis (I can't find it online anymore, but I had a saved copy). He used a branching factor of 250 and a ply count of 150, thus 250^150 = 4.9x10^359. So the game-tree complexity was right, but the ply count was wrong. I wonder how many more errors there are on that wiki page.
|
| « Last Edit: Aug 4th, 2007, 8:23pm by omar » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Reddit.com
« Reply #9 on: Aug 4th, 2007, 8:46pm » |
Quote Modify
|
on Aug 4th, 2007, 8:01pm, aaaa wrote:| The big problem here is that it looks like the number 17000 is an arithmetic mean and not a geometric one. Since the branch factor is clearly not constant judging from the same study, one can't just raise this number to the number of plies. |
|
I agree with you that the branching factor is not constant throughout the game, but the description for computing game-tree complexity says to use "the game's average branching factor". In Go also the branching factor starts at 361 and decreases as the game progresses, but Victor uses an average of 250.
Perhaps a more accurate way to estimate the game-tree complexity based on real game data would be to use the data from Janzert's frist graph and take the product of:
(average branching factor at ply count N) * (fraction of games that reached ply count N)
and then take the product of all these numbers for all ply counts where the fraction of games that reached that ply count is greater than some small number like 0.01.
Quote:
Additionally, I consider it a liability that such a large part of the games analyzed involves bots. |
|
Janzert also looked at human vs human games and got an average branching factor of 16,844.
|
| « Last Edit: Aug 4th, 2007, 8:59pm by omar » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Reddit.com
« Reply #10 on: Aug 4th, 2007, 8:47pm » |
Quote Modify
|
Just to confirm, the 17000'ish number is an arithmetic mean.
I thought somewhere I had figured a geometric mean but I'm not finding it now.
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Reddit.com
« Reply #11 on: Aug 4th, 2007, 10:14pm » |
Quote Modify
|
Janzert, if you stored all your calculated data about the number of possible moves in each position, you should be able to make a more direct calculation of game tree complexity. For each game calculate the the product of the branching factors for each of its moves; that's the estimated tree size for that game. Then take the geometric mean of tree sizes across all the games.
|
|
IP Logged |
|
|
|
The_Jeh
Forum Guru
Arimaa player #634
Gender:
Posts: 460
|
|
Re: Reddit.com
« Reply #12 on: Aug 4th, 2007, 11:45pm » |
Quote Modify
|
Why isn't Go's gametree complexity more like:
(361!)/((361-n)!) , where n is the average number of plies?
Using 300 as n, this would be 10^684.45
Using 200 as n, this would be 10^481.28
Using 150 as n, this would be 10^367.81
My reasoning is that the branching factor decreases by about 1 with each ply. A move that captures stones generally does not increase options in an intelligent way, so I assume it is negligible.
I realized a little after I posted that the square root of 17000 is only 130.38. Please forgive my poor math skills. I just graduated from high school, and the most advanced math I have is elementary statistics and calculus I. I plan on majoring in mathematics at college, though, so please take every opportunity to teach me.
|
| « Last Edit: Aug 4th, 2007, 11:59pm by The_Jeh » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Reddit.com
« Reply #13 on: Aug 5th, 2007, 10:20am » |
Quote Modify
|
on Aug 4th, 2007, 11:45pm, The_Jeh wrote:Why isn't Go's gametree complexity more like:
(361!)/((361-n)!) , where n is the average number of plies?
|
|
That seems like an excellent estimate. It is somewhat too high, since suicides and ko moves are illegal, but somewhat too low because captures re-open spaces. Your estimate makes more sense to me than (average branching factor)^(average game length).
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Reddit.com
« Reply #14 on: Aug 5th, 2007, 2:28pm » |
Quote Modify
|
Here are a few geometric means I got calculated, at least I hope I did it right. 
| Type of games | Number of games | Number of moves | Arithmetic mean | Geometric mean | | All | 55249 | 3209440 | 16411 | 11411 | | HvH | 3401 | 214321 | 19690 | 13451 | | BvB | 5668 | 403696 | 15122 | 10560 |
One other thing to remember about all of the means I've given is that they do not include the initial setup moves. If they were included it would increase all the numbers a bit.
Janzert
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print