Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> General Discussion >> Wikipedia Article Contains Arimaa Miscalculation?
        
(Message started by: FireBorn on Mar 18^th, 2010, 9:02am)

Title: Wikipedia Article Contains Arimaa Miscalculation?
Post by FireBorn on Mar 18^th, 2010, 9:02am

http://en.wikipedia.org/wiki/Deep_Blue_%28chess_computer%29#Aftermath

Somehow, I think the calculation that Arimaa has a state-space complexity of 10^43 compared to Chess's 10^50 is incorrect. This revision was made recently. Perhaps someone more knowledgeable about this would like to update the calculations. :)

Title: Re: Wikipedia Article Contains Arimaa Miscalculati
Post by ChrisB on Mar 18^th, 2010, 10:03am

The calculation may be good, but it provides very little support to the statement in the paragraph that "chess is harder than Arimaa for the computer." More important is the game tree complexity -- which is much higher for arimaa and grows much more quickly -- as well as other features of arimaa, such as the difficulty to achieve captures.

Comparing the state-space complexity of the two games seems difficult, but I'm guessing that chess is higher because of pawn promotion and the different movements for each type of piece. For example, with pawn promotion, positions could occur with 2 or more queens of the same color or 3 or more rooks, bishops or knights of the same color. And in arimaa the four endgames KQP vs. KQP, KRP vs. KRP, KBP vs. KBP, and KNP vs. KNP are all the same. Also, in arimaa, any active position requires at least one pawn of each color. Factors in favor of arimaa being higher, though, are that positions with one or both kings off the board could occur and that pawns could be on the back rank.

Title: Re: Wikipedia Article Contains Arimaa Miscalculati
Post by docreason on Mar 20^th, 2010, 10:49am

The Wikipedia entry has myself scratching my head a bit. Is it possible for a computer to have an easier time with a game, but do poorer with it? Are the decision tree size smaller with Arimaa than chess?

Title: Re: Wikipedia Article Contains Arimaa Miscalculati
Post by Janzert on Mar 20^th, 2010, 12:42pm

From the sections he has added to the above article, the main Arimaa (http://en.wikipedia.org/wiki/Arimaa) article and the comments made on the Arimaa talk page, it seems to me that this is someone who believes that Chess is the harder game and wants to prove it.

Certainly state-space complexity is a horrible measure of how hard the game is for computers. Decision tree size would be much better*, alas I think the decision tree size is pretty much uncalculable for either Chess or Arimaa. About the best we can do is the game tree complexity, which can be estimated at around 10^123 for Chess and 10^296 for Arimaa. So certainly from a complexity standpoint Arimaa is pretty certainly much, much harder than Chess.

For the sake of Arimaa someone really needs to argue against his changes but at this point I've used up my will to push back against bad wikipedia edits for the foreseeable future.

Janzert

* personally I believe even decision tree size is only a very, very rough measure of difficulty

Title: Re: Wikipedia Article Contains Arimaa Miscalculati
Post by knarl on Mar 23^rd, 2010, 8:22pm

I tried to put a strike through that entire paragraph in wikipedia yesterday, but apparently I can't edit wikipedia through my employers firewall.

Someone with a wikipedia account should just go and delete it ;-)

Cheers,
knarl.

Title: Re: Wikipedia Article Contains Arimaa Miscalculati
Post by Fritzlein on Mar 23^rd, 2010, 8:49pm

We are in a ticklish situation. According to Wikipedia norms, it would be justified to rebut the nonsense of the recent edits. However, a single, determined editor can cause an edit war and force an article into arbitration. If the Arimaa article is put under a microscope, the powers that be will demand that the "original research" and "unverified claims" that are positive to Arimaa should be removed along with the most recent fluff. We have been permitted to fly under the radar only because the article was not controversial (until now?).

Unfortunately, we have to risk an edit war. :( We can't let someone claim, on such silly justification, that chess is harder for computers than Arimaa. People who don't know any better will be misled unless the article is made truer.

I will start by engaging the editor on the Arimaa:talk page, on the hope that he can be persuaded.

Title: Re: Wikipedia Article Contains Arimaa Miscalculati
Post by knarl on Mar 23^rd, 2010, 9:19pm

Fritzlein, thanks for taking up the fight mate!

Cheers,
knarl.

Title: Re: Wikipedia Article Contains Arimaa Miscalculati
Post by lightvector on Mar 23^rd, 2010, 10:43pm

I'd agree that state-space complexity is a terrible measure of a game's "difficulty" and in fact, I'd argue that game tree complexity is just as terrible. These are really only relevant if you want to perfectly solve the game, and tend to be absurdly weak upper bounds if all you want is champion-level play. Certainly they have little to do with the relative strength of humans vs. computers - this depends greatly on how well humans play, which has much more to do with how well a game allows strategic comprehension, rather than some abstract counting of possible game states.

I do think some of the criticisms merit consideration though. It *is* true that the developer base for Arimaa is relatively small. For comparison, I'd imagine that it would take a great deal of expertise to produce a chess program capable of top-level play on desktop hardware. Such programs exist, of course, but I hardly think they'd be easy to write for most amateur programmers, and one could try to make the argument that the case for Arimaa is not too different, that the lack of a strong program is partly just the result of a lack of attention.

That said, I actually do believe that Arimaa is "harder", given that the player base is very small as well, and people have not actually yet had time to delve much of the potential strategy available. And, the basic approach of optimized alpha-beta + hand-coded evaluation + pruning heuristics indeed does not seem in practice to get nearly as far as it does in Chess.

Title: Re: Wikipedia Article Contains Arimaa Miscalculati
Post by omar on Mar 27^th, 2010, 5:45am

Clearly the wiki page about the Deep Blue-Kasparov match should only have a small mention of Arimaa and not dwell into the additional details trying to compare chess and Arimaa. I've deleted the additional details.

I've updated the 'Comparing Arimaa challenge to chess challenges' section of the Arimaa wiki page to provide the Arimaa communities view on this topic.