Author |
Topic: Arimaa is deeper than chess? (Read 4796 times) |
|
Fritzlein
Forum Guru
Arimaa player #706
Gender: 
Posts: 5928
|
 |
Arimaa is deeper than chess?
« on: Nov 22nd, 2005, 4:02pm » |
 Quote  Modify
|
One way to measure how much strategic depth exists in a game is to rate it according to Elo and see how much the ratings of the players spread out. If there isn't much depth to a game, then the good players will all learn everything there is to know about it, and their ratings will bunch up. Conversely, if the ratings spread way out, it shows that there is a lot to learn about the game, and it is dificult for any one person to know it all.
Looking at the "Established Players" page right now, Arimaa ratings cover a range of about 1100 points. If we call 200 rating points a skill level, then Arimaa has 5.5 levels of skill.
Chess ratings, meanwhile, go as high as 2800. On the low end, I know that there are 5-year-olds in the U.S. who legitimately earn chess ratings of zero, but let's take 400 as a more reasonable minimum rating. That means chess ratings range over about 2400 points, or equivalently there are about 12 levels of skill in chess.
Now these numbers are far from the final word on the relative depth of Arimaa and chess. First, chess has a vastly larger pool of players than Arimaa, so by random variation we expect to find a larger spread in chess. Suppose Arimaa has 100 players while chess has 100,000. In a normal distribution there are 4.6 standard deviations between 0.01 and 0.99, whereas there are 8.5 standard deviations between 0.00001 and 0.99999. Most of the difference is explained right there.
But second, and perhaps more importantly, Arimaa has not been around long enough for humanity to discover everything that is "in there", so to speak. We are still re-writing the book year to year on optimal play. It could well be that five years from now, even if the playing pool for Arimaa is the same size (not likely!) there will be a greater spread in ratings due to a greater body of Arimaa theory.
I'm going to go out on a limb to predict that Arimaa is actually deeper than chess. That is to say, if it is studied for as many years as chess and it is played by as many people as chess, then more than 12 levels of skill will be found in Arimaa. Is that a reasonable projection?
|
| « Last Edit: Nov 22nd, 2005, 4:05pm by Fritzlein » |
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Arimaa is deeper than chess?
« Reply #1 on: Nov 22nd, 2005, 5:23pm » |
Quote Modify
|
I have done some research on Little Golem, a play-by-e-mail site for abstract strategy games. They maintain Elo ratings for all of their games. Here is the spread of ratings according to game:
| Game | Players | Levels | | Chess | 737 | 7.0 | | Twixt | 336 | 6.3 | | Amazons | 295 | 5.4 | | Hex(19) | 297 | 5.0 | | Reversi(8) | 404 | 4.9 | | Hex(13) | 385 | 4.8 | | Dots and Boxes | 350 | 4.8 | | DVONN | 299 | 4.4 | | Reversi(10) | 209 | 3.6 |
I didn't include the numbers from go, because they don't specify the conversion from dan-kyu ranks to Elo points, but it is well-known that if go were ranked on the Elo scale it would have about 40 levels as compared to 12 for chess.
Clearly the size of the playing pool matters, as shown by Reversi on a larger board having fewer levels. Nevertheless, it isn't all-important, as shown by Twixt having more levels than Reversi(8) despite the smaller playing pool.
|
|
IP Logged |
|
|
|
Adanac
Forum Guru
Arimaa player #892
Gender:
Posts: 635
|
|
Re: Arimaa is deeper than chess?
« Reply #2 on: Nov 22nd, 2005, 5:45pm » |
Quote Modify
|
There are some other reasons why the number of Arimaa skill levels would be low. Unlike chess, we don't have any 40 year-old players with 35 years of experience playing the game (for obvious reasons) and we don't have many young children playing. If our players all tend to be adult males with 2 or less years of experience, we shouldn't expect nearly as many skill levels as chess. A more diverse demographic and more time to allow "Master level" players to develop would definitely increase the number of levels of skill. As an aside: Ratings tended to be a bit higher in Arimaa than in Chess, so I would guess that we'll have our first AM-Arimaa Master player when Fritzlein attains a 2450 rating. 
In general, I find that abstract/positional-type games have more levels of skill than purely tactical games and so I expect Arimaa will prove to be a very difficult game with a great many levels of skill indeed. And it's very encouraging that Arimaa is becoming more and more complex as we learn more about the strategy.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Arimaa is deeper than chess?
« Reply #3 on: Nov 22nd, 2005, 9:42pm » |
Quote Modify
|
Another way of looking at how deep a game is, is by estimating its state space and game tree size. The wikipedia has an article about this and I was suprised to find that someone already included Arimaa in the list.
http://en.wikipedia.org/wiki/Game-tree_complexity
I don't know who did these calculations, but Arimaa is listed as having the largest game tree; even surpassing Go. Assuming an average of about 20,000 choices per move and a typical game lasting about 50 moves (or 100 plys), the log of 20,000^100 is about 10^430; close to the number listed there. For placing the 32 Chess pieces on a 64 space board I get a value of about 10^42. A bit less than what they list for chess. I don't know how they got 10^54 for Arimaa. The number of actual legal positions for Chess and Arimaa are much less. But I would say that the chances of any random position being legal for Arimaa is much higher than for Chess. So the state space of Arimaa is probably much bigger than that of Chess.
Chapter 6 of Victor Allis's thesis also discusses the complexity of various games. It used to be online, but is not anymore. However, it can still be viewed from the Archive at:
http://web.archive.org/web/20040607185428/www.cs.vu.nl/~victor/thesis.ht ml
|
|
IP Logged |
|
|
|
Adanac
Forum Guru
Arimaa player #892
Gender:
Posts: 635
|
|
Re: Arimaa is deeper than chess?
« Reply #4 on: Nov 23rd, 2005, 9:48am » |
Quote Modify
|
on Nov 22nd, 2005, 9:42pm, omar wrote:
For placing the 32 Chess pieces on a 64 space board I get a value of about 10^42. A bit less than what they list for chess. I don't know how they got 10^54 for Arimaa. The number of actual legal positions for Chess and Arimaa are much less. But I would say that the chances of any random position being legal for Arimaa is much higher than for Chess. So the state space of Arimaa is probably much bigger than that of Chess.
|
|
I also believe that the 10^54 is incorrect and I also calculated a number close to Omar's. It's possible that someone simply calculated 64!/32! and took that as a rough estimate, forgetting to divide out the repeated positions from identical pieces.
Without eliminating illegal positions, I calculated roughly 4.9 * 10^41 positions with 32 pieces on the board (except that I did exclude rabbits from the 8th rank). With a very, very rough approximation of board positions with 4 to 31 pieces, the number doesn't increase much: 3.3 * 10^42. The only remaining step would be to exclude board positions with pieces on c3, f3, c6, f6 without supporting pieces of the same colour. I estimated that roughly 56% of positions would be illegal for this reason, so Arimaa should be in the 10^42 ballpark. I'm not sure if I overlooked anything or miscalculated, but it's a good sign that I matched Omar's answer
|
|
IP Logged |
|
|
|
acheron
Forum Full Member
Arimaa player #1613
Gender:
Posts: 11
|
|
Re: Arimaa is deeper than chess?
« Reply #5 on: Nov 23rd, 2005, 1:33pm » |
Quote Modify
|
32 pieces, each of which can be in one of 65 positions (64 board locations or removed).
From this you can exclude positions with an unsupported pieces in a trap (relatively few), and rabbits in the opposing back row (reducing the potential locations for 16 of those pieces from 65 to 57).
64^16*57^16 - unsupported trap positions.
|
| « Last Edit: Nov 23rd, 2005, 1:34pm by acheron » |
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Arimaa is deeper than chess?
« Reply #6 on: Nov 23rd, 2005, 2:59pm » |
Quote Modify
|
Quote:So the state space of Arimaa is probably much bigger than that of Chess.
|
|
Chess allows promotions, where Arimaa does not. I would guess (without proof!) that this makes the state space larger for chess.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Arimaa is deeper than chess?
« Reply #7 on: Nov 23rd, 2005, 3:05pm » |
Quote Modify
|
Acheron your calculation leaves a couple of things out. One is that two pieces cannot be on the same position (except off-the-board), so although the first piece has 65 possibilities, the second only has 64, etc. Also, some pieces are indistinguishable from one another, so if you switch two rabbits around, you have not created a new position, and cannot count it again. Adanac has accounted for this, and I think his estimates are close to correct.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Arimaa is deeper than chess?
« Reply #8 on: Nov 23rd, 2005, 7:13pm » |
Quote Modify
|
The size of the game tree and state space are interesting mathematical questions, but how well do we expect them to correspond to strategic depth? I'm guessing that if one or two moves are dominant in most positions, then the presence of lots of other possible moves doesn't add much strategy. Furthermore, if one or two moves are dominant in most positions, much less of the state space will ever be visited. So, chess could have a larger state space than Arimaa (my intuition agrees with JDB's) and Arimaa could still be deeper.
Of course, the levels of strategy I'm mumbling about exist only relative to human understanding. It would be nice to have some mathematical, human-independent way to measure "amount of strategy", but I'm not sure what it would be.
Incidentally (and this belongs in this thread only because it is another unsubstantiated intuition of mine that I feel strongly about) I have always been skeptical of the claim that shogi is hard for computers because of the huge game-tree (10^226 according to Wikipedia). I don't know much about shogi, but I do know that any enemy pieces you capture can come back into the game as part of your army. It seems intuitively obvious that having a handful of pieces that can "fall out of the sky" onto the opponent's king would give computers an advantage over humans, and not the reverse, even though the branching factor is huge. I assumed that developers just hadn't tried as hard for shogi as for chess. And wouldn't you know it, nowadays shogi computers are starting to get near championship level, or so I read.
To bring it back to Arimaa, I'm just not convinced that the large branching factor is what makes Arimaa hard for computers or deep for humans. I believe that there is something more subtle, something beyond raw numbers, going on here. I guess we'll have some evidence one way or another in the coming years: we live in interesting times.
|
|
IP Logged |
|
|
|
BlackKnight
Forum Guru
Arimaa player #695
Gender:
Posts: 98
|
|
Re: Arimaa is deeper than chess?
« Reply #9 on: Nov 24th, 2005, 6:42am » |
Quote Modify
|
on Nov 23rd, 2005, 7:13pm, Fritzlein wrote:
To bring it back to Arimaa, I'm just not convinced that the large branching factor is what makes Arimaa hard for computers or deep for humans. I believe that there is something more subtle, something beyond raw numbers, going on here. I guess we'll have some evidence one way or another in the coming years: we live in interesting times. |
|
Ja, I also thought so.
For example while attacking the castled King in Chess you might want to exchange a Bishop for a Knight on f6 to get rid of one of the defenders. So at least two pieces will leave the board and maybe you can destroy the pawn wall. So there are quite some tactics involved and major positional changes.
On the other hand in Arimaa I thought while you are trying to get control over trap f6, you might want to push away a defender from g6. But where should you push it to? If there is no other piece holding hand, then quite obiously into the trap. But otherwise? Is it better to push it onto the trap square, or backwards to g7 so that it is quite out of the game for the moment, or to pin (in case no piece is on h7) it on the rim? That might give a chance to further push it down towards the own trap f3.
I don't even know whether humans find it easy to decide on that. Maybe the stronger players have a clear concept how to handle this?!
|
|
IP Logged |
|
|
|
grey_0x2A
Forum Full Member
Arimaa player #1358
Gender:
Posts: 14
|
|
Re: Arimaa is deeper than chess?
« Reply #10 on: Nov 24th, 2005, 12:18pm » |
Quote Modify
|
I suspect that Arimaa is hard because of two classic AI reasons:
- Horizon effect-- thing take a lot of time in Arimaa this makes it hard to
search far enough ahead. Take the game http://arimaa.com/arimaa/gameroom/replayFlash.cgi?gid=21695&s=b& client=1 I suspected that Omar though of doing the HM switch to conduct HE attack as far back as turn 12 but it took until turn 35 to do is This is very fair in the future for was is really a strategic game. The large number of minor changes an the slow change make for "stragic depth".
- Subgames there in Arimma there are often subgames that require balancing, each may be a game losing/winning aspect. This means That relavence of any given peice is fairly hard to determin and one must balance the worth of each subgame, race situations, etc. make the techniques for chess harder to apply. (I do not know hear I have not implement a bot for ether game yet.)
Both these things also make it hard for humans too.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Arimaa is deeper than chess?
« Reply #11 on: Nov 24th, 2005, 1:43pm » |
Quote Modify
|
BlackKnight, I quite like your comparison of the attack on the castled king to the attack on an opposing trap. An exchange of pieces in chess is a sudden, permanent change to the position, but if you push a piece away from a trap in Arimaa, it is still on the board and may come back to life at a later date. Where you push a defender may determine whether or not you can get control of the trap, but more often than not the opposing player has some way to share control no matter which way you push. In those cases, you really have to look far ahead to see what you can threaten as compared to what your opponent can threaten.
For example, when there is a race going on, it may be important for me to make as big a threat as possible immediately. Then I may push a defending piece onto a trap just to have a large threat that buys me time. In another situation I might not be threatened myself, and might push the piece sideways just so that I can get at a rabbit behind it. Or maybe I will push the piece backwards purely to insure that the only defense is for the other player to come home with the elephant.
In other words, much of the time in Arimaa the maneuevers aren't making permanent changes to the position, they are merely temporarily increasing or decreasing one's initiative. This is shown by how often there are twenty moves or more before the first capture. It is as if you are forced to accumulate a great number of small, temporary advantages before you can convert them into any permanent advantage. Of course, this happens in chess too, but chess has so many large abrupt changes available that they seem to dominate the small, slow changes in a lot of positions.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Arimaa is deeper than chess?
« Reply #12 on: Nov 24th, 2005, 2:47pm » |
Quote Modify
|
I like both of your reasonas, Grey. (1) The longer a position goes without anything obvious happening, the more there is room for subtle maneuvering. That makes it hard for computers, and deep for humans. (2) The way Arimaa breaks into subgames around different traps magnifies the importance of good positional judgement. I want to dwell on (2), because it isn't obvious why this is so important.
There is a big distinction between being able to find the best move in a given situation, and being able to tell who is winning a given fight. When the first strong neural net backgammon programs came out, everyone was amazed at how well they played. However, there was an error of judgement, as opposed to an error of play, that experts still exploited for big gains. The bots tended to think they were winning in certain "back game" situations where the human had some anchors in the bot's home board and a lot of checkers on the bar. Then the bot was happy to double, re-double, and re-redouble in a game it was losing. This allowed humans to accept losing a few 2-point games in exchange for being able to pump the stakes up to 128 points in games where they were 60% favorites to win.
Just to be perfectly clear, it wasn't that the bot was playing bad moves on the board so much as that it couldn't tell whether it was winning or losing. The doubling cube was the mechanism for exploiting this error of judgement.
Now Arimaa doesn't have a doubling cube, so you might think that it doesn't matter if the bot knows whether it is winning or losing at any given time, as long as it keeps making good moves. However, when Arimaa breaks into subgames, for example a race, then judgement is critical. A perfect illustration comes from game 21410, Adanac vs. Paul, which JDB helped me analyze and understand. http://arimaa.com/arimaa/gameroom/replayFlash.cgi?gid=21410&s=w
Look at the position after Adanac launches a race on move 19w. Paul has taken over c3, while Adanac has taken over f6. Neither player can stop the other without bringing home his own elephant. But if they both decide to keep racing, then one player is going to win the game very soon. Whoever is going to lose the race needs to break it off and defend before it becomes catastrophic.
JDB and I analyzed it out with a reasonably convincing thoroughness that Paul could have played 19b eb3e ec3e ed3e ee3n, which is enough to stop Adanac's goal threat with an even game. If anything, I think Paul has a slight edge in the resulting position. But Paul didn't defend: instead he captured the cat in c3. This is the Arimaa equivalent of doubling in backgammon. In effect Paul said, "I will happily race you with the game on the line, because I will win."
Paul didn't start to bring the elephant home until move 22b. It isn't clear whether that was too late to stop goal, but it was clearly so late that Adanac would have had a dominating position. Paul should have cut his losses while they were still small.
Nevertheless, capturing a cat in c3 on move 19b was locally the best move. On that front, there wasn't a better move available. It was just a question of which front was the right one to play on, or whether to reallocate forces between fronts. Thus in Arimaa the decision of which quadrant to play in acts like the doubling cube in backgammon: it magnifies the importance of judgement relative to mere move-finding.
Moreover, racing to a goal is not the only situation in Arimaa in which this type of judgement is important. On the contrary, any time the elephants are apart there is a question of which has the bigger threat, even if that threat isn't goal. Moreover, any time the elephants are together, deadlocked around one trap, each player has to be able to judge ahead of time how much they will lose locally if they leave with their elephant, versus the amount they can gain elsewhere in the mean time. Someone can locally fight like a tiger and still lose because of not making the right global decision of when to cut and run.
In this sense, Arimaa is somewhere between chess and go. Chess usually has only one fight, but sometimes has two. Arimaa almost always has two fights, can sometimes have three, and very rarely has four. Go almost always has four local fights, and routinely has six. Therefore go, even more than Arimaa, magnifies the judgement call of where it is most important to play next.
The way a game breaks into subgames that must be correctly evaluated independently before being stitched back into a whole is, to my understanding, a more important reason than the branching factor in making a game hard for computers and deep for humans. Thanks for bringing up this point, Grey.
|
|
IP Logged |
|
|
|
Adanac
Forum Guru
Arimaa player #892
Gender:
Posts: 635
|
|
Re: Arimaa is deeper than chess?
« Reply #13 on: Nov 29th, 2005, 6:52pm » |
Quote Modify
|
The fact that many strategic considerations reverse themselves in the endgame also makes it more difficult for bot-programmers. It’s something that I really like about Arimaa as opposed to Chess, for example.
1. In the opening it can advantageous to pull the enemy rabbits but in the endgame it’s often disadvantageous to do so.
2. In the opening, dogs are worth more than rabbits, but not necessarily so in the endgame. This applies to all rabbits, not just the advanced ones.
3. It’s sometimes beneficial to frame an enemy horse in the opening but virtually never in the middlegame.
4. Camel hostages are far more valuable in the opening than in the endgame.
5. Blockades lose their value as both sides exchange pieces.
6. etc.
Admittedly, it’s difficult for a human to know the exact moment that a rabbit is worth more than a dog, but evaluating the permanent strategic shifts caused by material exchanges seems to be much easier for a human to grasp than a bot. I can’t imagine that it would be very much fun programming the value every possible strategic concept with all combinations of exchanged pieces!
|
|
IP Logged |
|
|
|
Ryan_Cable
Forum Guru
Arimaa player #951
Gender:
Posts: 138
|
|
Re: Arimaa is deeper than chess?
« Reply #14 on: Dec 2nd, 2005, 2:49am » |
Quote Modify
|
I think a good measure of the strategic depth of a game is how many extra ply are necessary for tactical evaluation to overwhelm strategic evaluation. Hydra searches to 18 ply (at full width), and it has never lost a game at match time controls (except against human-computer teams). It is questionable whether hydra’s evaluation should be called strictly tactical, but the fact that it can be quickly calculated on a FPGA indicates it isn’t very deeply strategic. I believe grandmasters can search to 12 to 14 ply, but certainly not at full width. Thus, I think tactics overwhelm strategy at ~8 ply for chess.
My guess is that Arimaa is about the same. If you took Bomb, fixed the obvious bugs (blockading/smothering, reversible moves, M cowardice, etc.), and gave it enough computing power to calculate 8 ply at match time controls, I think that after ~6 months of evaluation optimization, it would be able to beat all of the sub-titans more often than not. 2 more ply and another year or two of optimization and I expect it would dominate all humans to at least the extent that the titans do today. Of course, this wouldn’t get you Omar’s money, but I think it would show that Arimaa is not truly a "Game of Real Intelligence."
However, I doubt that tactical evaluation can overwhelm strategic evaluation for go at any depth that classical computers can hope to calculate. Personally, I don’t have much faith in neural networks or genetic algorithms for a game as precise and unforgiving as go. I think that conquering go will require finding a way to impart a real strategic understanding of go to computers. Still, my guess is that go will be conquered before computers get close to human level intelligence.
Ultimately, precise, discrete calculation is a computer specialty. It is when computers start getting good at games like multiplayer poker and diplomacy that you should think about investing in a bomb shelter.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print