|
||
Title: Game informational complexity Post by NIC1138 on Apr 4th, 2006, 11:25pm Hello folks... This topic is more directed to the Intelligent Systems community! 8) 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? |
||
Title: Re: Game informational complexity Post by Swynndla on Apr 5th, 2006, 2:30am You might be able to start with: http://arimaa.com/arimaa/forum/cgi/YaBB.cgi?board=talk;action=display;num=1143707386 ... I don't know if any of the graphs on the wiki are really to do with what you are asking, but here it is anyway: http://arimaa.com/arimaa/twiki/bin/view/Arimaa/GraphicalStats In chess, as more and more pieces are swapped off, the more stable and certain the game becomes. But in arimaa, it seems to get more unstable. The more experienced arimaa players will be able to explain this better. |
||
Title: Re: Game informational complexity Post by Fritzlein on Apr 5th, 2006, 4:42pm on 04/04/06 at 23:25:31, NIC1138 wrote:
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. |
||
Title: Re: Game informational complexity Post by omar on Apr 6th, 2006, 12:05am 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 |
||
Title: Re: Game informational complexity Post by omar on Nov 7th, 2007, 12:42am 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/ |
||
Title: Re: Game informational complexity Post by Janzert on Nov 7th, 2007, 11:40pm on 11/07/07 at 00:42:50, 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 |
||
Title: Re: Game informational complexity Post by Fritzlein on Nov 8th, 2007, 8:08am 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. |
||
Title: Re: Game informational complexity Post by RonWeasley on Nov 8th, 2007, 11:08am 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. |
||
Title: Re: Game informational complexity Post by omar on Nov 9th, 2007, 12:09am 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. |
||
Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1! YaBB © 2000-2003. All Rights Reserved. |