Arimaa
Arimaa is a two-player
abstract strategy board game that can be played using the same equipment as
chess. Arimaa has so far proven to be more computer-resistant than chess.
Arimaa was 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 yearly through 2020, for the first computer program (running on inexpensive, off-the-shelf hardware) able to defeat a top-ranked human player in a match six games or longer. Syed has applied for a patent on the Arimaa rules, and the name "Arimaa" is trademarked;
see below for more.
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.{{arimaa diagram|=
tright | 1 | =8 |rs|rs|rs|rs|rs|rs|rs|rs|=7 |hs|ds|cs|es|ms|ds|cs|hs|=6 | | | | | | | | |=5 | | | | | | | | |=4 | | | | | | | | |=3 | | | | | | | | |=2 |hg|dg|cg|mg|eg|rg|rg|rg|=1 |cg|dg|hg|rg|rg|rg|rg|rg|= | {{chess diagram>= | tright | 2 | =8 |pd|pd|pd|pd|pd|pd|pd|pd|=7 |rd|bd|nd|kd|qd|bd|nd|rd|=6 | | |xx| | |xx| | |=5 | | | | | | | | |=4 | | | | | | | | |=3 | | |xx| | |xx| | |=2 |rl|bl|nl|ql|kl|pl|pl|pl|=1 |nl|bl|rl|pl|pl|pl|pl|pl|= a b c d e f g h|The same position in chess pieces. The trap squares are marked with an x.{{arimaa diagram|= | tright | 3 | =8 | | | | | | | |rs|=7 |rs|rg|cs| | |ds|rs| |=6 |dg|ds| |hg| | | | |=5 | | | |es| | | | |=4 | | |rs| | |rs| | |=3 | |dg|rs|eg|rg| |rg| |=2 | | |hs|rs| |hs| | |=1 | | |cg|cg|rg|rg|rg|rg|=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. However, because it is difficult to usher a rabbit to the goal line while the board is full of pieces, an intermediate objective is to capture opposing pieces by pushing or pulling them into the trap squares.
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 turns, starting with Gold. A turn consists of making one to four steps. With each step a friendly piece may move into an unoccupied square one space left, right, forward, or backward, except that rabbits may not step backward. The steps of a turn may be made by a single piece or distributed between several pieces in any order. A turn 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 third diagram, from the same game as the initial position above, helps illustrate the remaining rules of movement.
A player may use two steps of a turn 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 adjacent weaker piece. When pulling, the stronger piece steps into an empty square, and the square it came from is occupied by the weaker piece. The silver elephant on d5 could step 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, because those squares are not empty.
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. An elephant can never be dislodged, since there is nothing stronger.
A piece which is adjacent to a stronger opposing piece is frozen, unless it is also adjacent to a friendly piece. Frozen pieces may not be moved by the owner, but may be dislodged by the opponent. A frozen piece can freeze another still weaker piece. 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. An elephant cannot be frozen, since there is nothing stronger, but an elephant can be blockaded.
A piece which enters a trap square is captured and removed from the game unless there is a friendly piece adjacent. Silver to move could capture the gold horse on d6 by pushing it to c6 with the elephant on d5. 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, voluntarily or by being dislodged, the silver rabbit on c3 will be captured.
Note that a piece may voluntarily step into a trap square, even if it is captured thereby. Also, the second step of a pulling maneuver may be completed, even if the piece doing the pulling is captured on the first step. For example, Silver to move could step the silver rabbit from f4 to g4, step the silver horse from f2 to f3, which captures the horse, and still pull the gold rabbit from f1 to f2 as part of the horse's move.
In the diagrammed position, if it were Gold's turn to move, Gold could win 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. (The frequency of each in the first thousand rated human vs. human games on the Arimaa server is shown in parentheses.)
* (1.3%) If, at the beginning of a player's turn, no steps are possible because all friendly pieces are frozen or blockaded, the player whose turn it is loses.
* (0.2%) If the same position occurs three times with the same player to move, the player whose turn caused it to occur the third time loses. Only positions at the end of each turn are considered by this rule, not positions at the end of each step. (This rule originally did not consider side to move, but Syed changed it to be more like the chess repetition rule on May 28, 2005.)
* (0.0%) If all sixteen rabbits are captured, the game is a draw. (In elimination tournaments where a draw would be inconvenient, Syed has ruled that a player who captures all eight opposing rabbits wins the game, although as of June, 2006, it has been a moot point.)
Finally, if an opposing rabbit is dislodged onto its goal line and dislodged off within the same turn, the game continues.For beginning insights into good play, see the Arimaa Wikibook articles on tactics and strategy.Several aspects of Arimaa make it 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 applicable to chess are less effective for Arimaa.
Top chess programs use brute-force searching coupled with static position evaluation dominated by 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 turn. An Arimaa player has nearly as many legal choices for each step as a chess player has for each turn. Thus a program which can search to depth of sixteen ply can look ahead eight turns for each player in chess, but only approximately two turns (eight steps) for each player in Arimaa.
Brute force search depth, for chess software, is nearly doubled by alpha-beta pruning, which allows the software to conclude that one move is better than another without examining every possible continuation of the weaker move. If the opponent can crush a certain move with one reply, it isn't necessary to examine other replies, which dramatically increases search speed. In Arimaa, however, the side to move switches only every four steps, which reduces the number of available cutoffs in a step-based search.
Furthermore, the usefulness of alpha-beta pruning is heavily dependent on the order in which movesare considered. Good moves must be considered before bad ones in order for the bad ones to be neglected. In particular, checking and capturing moves are key for pruning, because they are often much better than other moves. In Arimaa software the speedup provided by alpha-beta pruning is less, because captures are more rare. In rated games played on arimaa.com, only 3% of steps result in capture, compared to about 19% of chess moves that result in capture.
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 turns. Compared to chess, Arimaa allows either player to delay captures for longer. Indeed, the average move number of the first capture in chess is turn 6, whereas in Arimaa it is turn 12. The struggle is initially more positional in Arimaa, 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 non-material ways. Thus the strength of computer programs (examining millions of positions) is not as significant as their weakness (judging the position apart from who has more pieces).
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 humans at a relative disadvantage in chess. 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 typically play better in this sort of position, because 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 in which 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, long-term 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 king and knight vs. king and rook. 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. 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. An average game of Arimaa has only eight captures (compared to seventeen for chess), and top humans can often defeat top programs in Arimaa without losing a single piece, for example the second game of the 2006 challenge match.
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 produced many techniques to successfully play games, but has contributed essentially nothing to more general reasoning; in fact, the techniques of chess playing programs have been excluded from some definitions of artificial intelligence; a goal for Arimaa is that the techniques involved in playing it will help the larger goals of artificial intelligence.
The structure of Omar Syed's man against machine challenge, however, is at odds with his professed confidence in the difficulty of creating a strong program. In the annual challenge, programs are run on machines chosen and provided by Omar Syed himself, under the criterion that it be a typical, inexpensive, off-the-shelf home computer. The challenge would not be open to anyone requiring expensive multi-processor machines such as those used to challenge top-level chess players, much less something like the custom-built supercomputer Deep Blue, even though it was the success of this hardware-intensive approach which inspired Arimaa's invention.The huge number of options per turn in Arimaa is sometimes presented as a completeexplanation of human dominance over computers. While a high branching factor clearly stunts brute-force searching, it is unclear why human players are not equally confused by the sea of possibilities. Why doesn't a human presented with about 15,000 choices per turn (400,000 counting different step-orderings) inevitably overlook the best move or the best response? Computers can unfailingly consider every single move and every single response to each move, so why aren't they continually capitalizing on human oversights and blunders? What channels human thoughts in the right direction?
The longer the challenge prize is unclaimed, the more it appears that Arimaa has strategic aspects which the human mind can grasp more easily than they can be encoded into software. As David Fotland said, "For a while my program was as strong as or stronger than any person, but the human players improved rapidly and developed some new strategic concepts that were very difficult to capture in a computer program." A different game with tens of thousands of possibilities per turn might not givethe same advantage to humans. It is unclear which features of Arimaa, if any, will continue to elude computers as new programming techniques are applied. Perhaps the evolution of the challenge will provide insight into human intelligence as much as machine intelligence.| Year | Prize | Challenger | Developer | Human Defender | Human Rank!Result | | 2004 | $10,000 | Bomb | David Fotland | Omar Syed | #1 | 0-8 | | 2005 | $10,000 | Bomb | David Fotland | Frank Heinemann | #4 | 1-7 | | 2006 | $17,500 | Bomb | David Fotland | Karl Juhnke
Greg Magne
Paul Mertens | #1
#2
#6 | 0-3
0-3
1-2 | |
The Arimaa Challenge has happened three times so far. Prior to the third match, Syed changed the format to require the software to win two out of three games against each of three players, to reduce the psychological pressure on individual volunteer defenders. Also Syed launched a program to encourage sponsorship of the Arimaa Challenge, and hopefully build a bigger prize fund.
In each of the three challenge cycles David Fotland, who is also the developer of Many Faces of Go, won the Arimaa Computer Championship and the right to play for the prize money, only to see his program beaten decisively each year. In 2006 the human players won eight of the nine games, and six of those without losing a piece. The only victory for the computer was the final game, in which it was given material handicap of a camel, roughly comparable to queen odds in chess.United States Patent number 6,981,700 was filed on the 3rd of October 2003, and granted on the 3rd of January 2006. Omar Syed also holds a trademark on the name "Arimaa".
Syed has stated that he does not intend to restrict noncommercial use, though the meaning of noncommercial is not clear at this time. He has released a license called "The Arimaa Public License" with the declared intent to "make Arimaa as much of a public domain game as possible while still protecting its commercial usage". Items covered by the license are the pending patent and the trademark.*Game complexity
*Go (board game)
*Chess*Official Arimaa Website
*David Fotland's Arimaa Program - warning! the free version is turn limited
*The Arimaa Public License
|
