From TheBestLinks.com
Arimaa is a two-player board game invented by Omar Syed, a computer engineer trained in artificial intelligence. Syed was inspired by Garry Kasparov's defeat at the hands of the chess computer Deep Blue to design a new game which would be difficult for computers to play well, but would have rules simple enough for his four-year-old son Aamir to understand. ("Arimaa" is "Aamir" spelled backwards plus an initial "a"). In 2002 Syed published the rules to Arimaa and announced a $10,000 prize, available through 2020, for the first computer program able to defeat a top-ranked human player in a match six games or longer. David Fotland, who is also the developer of Many Faces of Go (http://www.smart-games.com/manyfaces.html), fielded the strongest Arimaa program in early 2004, only to see it crushed by Syed himself in the challenge match, eight wins to zero with no draws.
Rules
Arimaa is played on a chessboard with four squares distinguished as trap squares, namely c3, f3, c6, and f6 in algebraic chess notation. The two players, Gold and Silver, each control sixteen pieces: these are, in order from strongest to weakest, one elephant, one camel, two horses, two dogs, two cats, and eight rabbits. The pieces may be represented by the chess king, queen, rooks, bishops, knights, and pawns respectively.
The objective of the game is to move a rabbit of one's own color onto the home rank of the opponent. Thus Gold wins by moving a gold rabbit to the eighth rank, and Silver wins by moving a silver rabbit to the first rank.
The game begins with an empty board. Gold places the sixteen gold pieces in any configuration on the first and second ranks. Silver then places the sixteen silver pieces in any configuration on seventh and eighth ranks. The diagram at right shows one possible initial placement.
After the pieces are placed on the board, the players alternate moves, starting with Gold. A move consists of one to four steps. With each step a friendly piece may be moved into an unoccupied square one space left, right, forward, or backward, except that rabbits may not step backward. The steps of a move may be made by a single piece or distributed between several pieces in any order. A move must make a net change to the position, thus one may not, for example, take one step forward and one step back with the same piece, effectively passing the turn.
The diagram at left helps illustrate the remaining rules of movement.
A player may use two steps of a move to dislodge an opposing piece with a stronger friendly piece which is adjacent. For example, a friendly dog may dislodge an opposing rabbit or cat, but not a dog, horse, camel, or elephant. The stronger piece may pull or push the weaker piece. When pulling, the stronger piece moves into an empty square, and the square it came from is occupied by the weaker piece. The silver elephant on d5 could move to d4 (or c5 or e5) and pull the gold horse from d6 to d5. When pushing, the weaker piece is moved to an adjacent empty square, and the square it came from is occupied by the stronger piece. The gold elephant on d3 could push the silver rabbit on d2 to e2 and then occupy d2. Note that the rabbit on d2 can't be pushed to d1, c2, or d3, as it must move into an empty square.
Friendly pieces may not be dislodged. Also, a piece may not push and pull simultaneously. For example the gold elephant on d3 could not simultaneously push the silver rabbit on d2 to e2 and pull the silver rabbit from c3 to d3.
A piece which is adjacent to a stonger opposing piece is frozen, unless it is also adjacent to a friendly piece. Frozen pieces may not move. The silver rabbit on a7 is frozen, but the one on d2 is able to move because it is adjacent to a silver piece. Similarly the gold rabbit on b7 is frozen, but the gold cat on c1 is not. The dogs on a6 and b6 do not freeze each other because they are of equal strength.
A piece which enters a trap square is captured and removed from the game unless there is a friendly piece adjacent. Also a piece on a trap square is captured if all adjacent friendly pieces move away. Thus if the silver rabbit on c4 and the silver horse on c2 move away, the silver rabbit on c3 will be captured.
In the early stages of the game, it is usually too crowded for a rabbit to reach the other side, so the focus is more on trapping opposing pieces by pushing and pulling. Silver to move could capture the gold horse on d6 by pushing it to c6 with the elephant on d5. Later in the game, however, rabbits may threaten to break through in many ways, sometimes allowing the materially weaker side to eke out a victory. If Silver does nothing to hinder it, Gold will win next move in three steps. The dog on a6 can push the rabbit on a7 to a8, and when the dog is on a7, it unfreezes the rabbit on b7, which can step to b8 for the victory.
There are several ways for the game to end apart from a rabbit reaching its goal, all of which are extremely rare:
- If all sixteen rabbits are captured, the game is a draw.
- If, at the beginning of a player's turn, no moves are possible because all friendly pieces are frozen or blockaded, the player whose move it is loses.
- If the same position occurs three times, the player whose move caused it to occur the third time loses. (Only positions at the end of each move are considered by this rule, not positions at the end of each step. Also, unlike chess, only the configuration of pieces matters, and not the player to move. For example, if a position occurs twice with Silver to move, and Silver later recreates the position with Gold to move, that counts as the third occurance, and Silver loses the game.)
Finally, if an opposing rabbit is dislodged onto its goal line and dislodged off within the same move, the game continues.
Computer Ineptitude
There are a number of facets of Arimaa which make it relatively difficult for computer programs to beat good human players. Because so much effort has gone into the development of strong chess-playing software, it is particularly relevant to understand why techniques effective for chess are ineffective or only partially effective for Arimaa.
The most important factor is that chess programs use brute-force searching coupled with static position evaluation that relies heavily on material considerations. Chess programs examine many, many possible moves, but they are not good (compared to humans) at determining who is winning at the end of a series of moves unless one side has more pieces than the other. The same is true for Arimaa programs, but their results are not as good in practice.
When brute-force searching is applied to Arimaa, the depth of the search is limited by the huge number of options each player has on each move. An Arimaa player has roughly as many legal choices for each step as a chess player has for each move. Thus a program which can search to depth of sixteen ply can look ahead eight moves for each player in chess, but only approximately two moves (eight steps) for each player in Arimaa.
In most Arimaa positions, particularly towards the beginning of the game when the board is still crowded, a competent player can avoid losing any pieces within the next two moves. Compared to chess, Arimaa has relatively few ways for either player to force captures or exchanges in the short term. Captures can often be pushed beyond the horizon of a brute-force search. The struggle is initially more positional, and revolves around making captures unavoidable at some point in the future. This sort of contest magnifies the importance of being able to judge who is gaining or losing ground in more subtle ways than by capturing or losing pieces. Thus the strength of computer programs (examining millions of positions) is not as significant as their weakness (judging the position apart from material considerations).
The weakness of Arimaa programs in the opening phases is further magnified by the setup phase. In chess every game starts from the same position. By compiling before the game a list of stock replies to all standard opening moves, chess programs may often make a dozen or more excellent moves before starting to "think". Humans do the same, but have a smaller and less reliable memory of openings, which puts them at a relative disadvantage. Arimaa, in contrast, has millions of possible ways to set up the pieces even before the first piece moves. This prevents programs from having any meaningful opening book.
As the game progresses, exchanges and the advancement of rabbits tend to make the position more open and tactical. Arimaa programs tend to play very well in this sort of position, as they see tactical shots which humans overlook. However, it is usually possible for humans to avoid wide-open positions by conservative play, and to angle for strategic positions where computers fare worse. Against a conservative opponent it is almost impossible to bust open the position in Arimaa, whereas in chess it is merely difficult. One must beat defensive play by the accumulation of small advantages, which programs do not do very well.
One additional technique from computer chess which does not apply to Arimaa is endgame tablebases. Master-level chess games sometimes trade down into unclear endgames with only a few pieces, for example a king and two knights vs. a king and a pawn. It is possible to build, by retrograde analysis, an exhaustive table of the correct move in all such positions. Programs have only to consult a pre-generated table in such positions, rather than "thinking" afresh, which gives them a relative advantage over humans. Arimaa, in contrast, seldom comes to an endgame of any sort, because it is almost always decided in the middlegame. Equal exchanges of pieces are less common than in chess, so it is rare for a game of Arimaa to "trade down" and still be unclear. Victory is usually attained with more than half of the pieces still on the board, and it is not uncommon for the victorious side to win without losing a single piece.
Omar Syed hopes that, because traditional computer game-playing techniques are only marginally effective for Arimaa, programmers will be forced to use artificial intelligence techniques to create a strong Arimaa-playing program. The successful quest to build a world-championship-caliber chess program has contributed essentially nothing to the field of artificial intelligence. Perhaps it will be otherwise for Arimaa.
Strategy and Tactics
For beginning insights into good play, see Arimaa Strategy and Tactics.
External links
ja:アリマア
Related links
Top visited
0 of
0 links
[no links posted yet]
>> place link >>
Discussion
Last posted
0 of
0 messages
[no messages posted yet]
>> post message >>
Watch
You can
add this article to your own "watchlist" and receive e-mail notification about all changes in this page.
