Author |
Topic: Game informational complexity (Read 3125 times) |
|
NIC1138
Forum Guru
Arimaa player #65536
Gender: 
Posts: 149
|
 |
Game informational complexity
« on: Apr 4th, 2006, 11:25pm » |
 Quote  Modify
|
Hello folks... This topic is more directed to the Intelligent Systems community! 
As I believe many of you, I`ve heard of arimaa from wikipedia, because of it's mention on the page about the match between Garry Kasparov and Deep Think, and I was immediately attracted to the concept of the game!...
Now I sedimented (do you say that in english?  ) my toughts, and I am curious: are there any articles already comparing arimaa's computational/informational complexity to chess and go? Do the rules effectively increase the combinatory possibilities/entropy of the game? How is a chess match compared to arimaa in terms of number of plys and of moves?...
I was wondering if arimaa's rules don't end up making games shorter altough more complex, for example...
I`m sure there are lots of references already, where can I find them?
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Game informational complexity
« Reply #2 on: Apr 5th, 2006, 4:42pm » |
Quote Modify
|
on Apr 4th, 2006, 11:25pm, NIC1138 wrote:| I was wondering if arimaa's rules don't end up making games shorter altough more complex, for example... |
|
Arimaa games don't appear to be much shorter than chess games. In fact, top-level Arimaa games may turn out to be longer on average than top-level chess games. It is hard to compare, though, because in chess it is standard practice to resign a losing position, whereas Omar tries to discourage any resignations on arimaa.com. Also chess has many agreed draws while Arimaa has none.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Game informational complexity
« Reply #3 on: Apr 6th, 2006, 12:05am » |
Quote Modify
|
Good question, but very hard to answer. There is an article in the Wikipedia that compares the complexity of various games:
http://en.wikipedia.org/wiki/Game_complexity
Other than that there aren't many references on this topic.
Both the game-space complexity and game-tree complexity are estimated values.
Recently Brian Haskin (username Janzert) has done a study of the branching factor in Arimaa. See:
http://arimaa.janzert.com/bf_study/
I've never seen anything similar to this kind of study done for any other game.
The results of this study provide a more accurate way of measuring the game-tree complexity.
GTC = N1^F1 * N2^F2 * ... * Nx^Fx
where:
GTC means game-tree complexity
N1 is the average number of moves at ply 1
F1 is the fraction of games that reach ply 1
x is the ply number at which Fx is almost zero
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Game informational complexity
« Reply #4 on: Nov 7th, 2007, 12:42am » |
Quote Modify
|
I rediscovered this Thesis by Christ-Jan Cox.
http://www.cs.unimaas.nl/~uiterwijk/Theses/MSc/Cox_thesis1.pdf
It gives estimates for the state space and game tree complexity. Very interesting thesis.
I've updated the wikipedia game complexity page to use the numbers from this Thesis and referenced the Thesis.
I've made a local copy of the Thesis and some other papers and linked them on this page:
http://arimaa.com/arimaa/papers/
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Game informational complexity
« Reply #5 on: Nov 7th, 2007, 11:40pm » |
Quote Modify
|
on Nov 7th, 2007, 12:42am, omar wrote:
Interesting, I don't believe I've seen this before.
His numbers for branching factor were not making any sense to me though; I was actually writing this post before it clicked. I finally realised it appears that he is using every possible move for the branching factor not just distinct resulting positions, i.e. 2w Md2n, Ee2n is counted seperately from 2w Ee2n, Md2n. This leads to his branching factor being 10-15x higher than counting distinct resulting positions.
Is this actually the correct way to define the branching factor?
Janzert
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Game informational complexity
« Reply #6 on: Nov 8th, 2007, 8:08am » |
Quote Modify
|
I don't think it can be correct to count reaching the same position via different steps as two different moves. The branching factor is the number of different states you can transition into from the current state. Janzert, your study of branching factor defined it the right way, according to my understanding of the essence of branching.
It may seem flattering to Arimaa to use the higher branching factor (including transpositions), but I don't think it does us any favors. Once I read a posting in some forum that said essentially, "The Arimaa people are morons who don't understand computer science. Transposition of steps can be weeded out instantly by checking the hash table. Those idiots say Arimaa is hard, but it isn't really."
Well, actually Arimaa is hard. A branching factor of 15,000 per move is still very significant, and still makes brute force search ineffective. So why should we give the outside world the impression that we don't know how transposition tables work? Why should we claim the branching factor is higher than the number of child nodes that must be created in the tree for each parent node?
I think that in the long run, inflating claims of game-tree complexity don't make Arimaa look good, they make Arimaa look bad.
|
| « Last Edit: Nov 8th, 2007, 8:10am by Fritzlein » |
IP Logged |
|
|
|
RonWeasley
Forum Guru
Harry's friend (Arimaa player #441)
Gender:
Posts: 882
|
|
Re: Game informational complexity
« Reply #7 on: Nov 8th, 2007, 11:08am » |
Quote Modify
|
To my knowledge, our current set of bots all use transposition tables. Actually, bomb's advantage comes from Fotland's efficiency techniques. So I don't think Lockhart has found the key to winning the Arimaa Challenge. Hey, at least somebody's talking about it.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Game informational complexity
« Reply #8 on: Nov 9th, 2007, 12:09am » |
Quote Modify
|
Humm.... that's probably why his GTC number came out larger. I've changed the Arimaa GTC value in the wikipedia
to what it was before.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print