Author |
Topic: Wikipedia Article Contains Arimaa Miscalculation? (Read 828 times) |
|
FireBorn
Forum Guru
Arimaa player #1832
Gender: 
Posts: 123
|
 |
Wikipedia Article Contains Arimaa Miscalculation?
« on: Mar 18th, 2010, 9:02am » |
 Quote  Modify
|
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. 
|
|
 IP Logged |
|
|
|
ChrisB
Forum Guru
Arimaa player #2339
Gender:
Posts: 147
|
|
Re: Wikipedia Article Contains Arimaa Miscalculati
« Reply #1 on: Mar 18th, 2010, 10:03am » |
Quote Modify
|
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.
|
| « Last Edit: Mar 18th, 2010, 10:57am by ChrisB » |
IP Logged |
|
|
|
docreason
Forum Senior Member
Arimaa player #5072
Gender:
Posts: 28
|
|
Re: Wikipedia Article Contains Arimaa Miscalculati
« Reply #2 on: Mar 20th, 2010, 10:49am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Wikipedia Article Contains Arimaa Miscalculati
« Reply #3 on: Mar 20th, 2010, 12:42pm » |
Quote Modify
|
From the sections he has added to the above article, the main 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
|
|
IP Logged |
|
|
|
knarl
Forum Guru
Arimaa player #1648
Gender:
Posts: 104
|
|
Re: Wikipedia Article Contains Arimaa Miscalculati
« Reply #4 on: Mar 23rd, 2010, 8:22pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Wikipedia Article Contains Arimaa Miscalculati
« Reply #5 on: Mar 23rd, 2010, 8:49pm » |
Quote Modify
|
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.
|
| « Last Edit: Mar 23rd, 2010, 10:26pm by Fritzlein » |
IP Logged |
|
|
|
knarl
Forum Guru
Arimaa player #1648
Gender:
Posts: 104
|
|
Re: Wikipedia Article Contains Arimaa Miscalculati
« Reply #6 on: Mar 23rd, 2010, 9:19pm » |
Quote Modify
|
Fritzlein, thanks for taking up the fight mate!
Cheers,
knarl.
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: Wikipedia Article Contains Arimaa Miscalculati
« Reply #7 on: Mar 23rd, 2010, 10:43pm » |
Quote Modify
|
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.
|
| « Last Edit: Mar 23rd, 2010, 10:49pm by lightvector » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Wikipedia Article Contains Arimaa Miscalculati
« Reply #8 on: Mar 27th, 2010, 5:45am » |
Quote Modify
|
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.
|
| « Last Edit: Mar 27th, 2010, 5:46am by omar » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print