Computer Arimaa

The number of different ways that each player can set up their pieces at the beginning of the game is:

${\displaystyle {\dbinom {16}{8}}\cdot {\dbinom {8}{2}}\cdot {\dbinom {6}{2}}\cdot {\dbinom {4}{2}}\cdot {\dbinom {2}{1}}\cdot {\dbinom {1}{1}}=64,864,800}$

The player can put 8 rabbits on 16 possible squares, followed by 2 cats on the 8 remaining squares, 2 dogs on the 6 remaining squares, 2 horses on the four remaining squares, one camel on one of the two remaining squares, and the elephant on the final unused square.

Because each player can start the game with one of 64,864,800 opening setups, the total state space for the opening is:

${\displaystyle 64,864,800^{2}\approx 4.2\cdot 10^{15}}$

As Christ-Jan Cox said in his Master's thesis, because the number of possible initial states is so large, "[i]t follows that it is very difficult to develop complete databases of opening moves."[3][4]

It is important for the computer to be able to evaluate the value of the pieces on the board so it can assess whether or not a capture or exchange would be desirable. Assessing the relative value of pieces is an area of ongoing Arimaa research. Some currently used systems are DAPE and FAME.

The following techniques are used by some or all of the artificial intelligence programs that play Arimaa:

• Bitboards
• Transposition tables
• Zobrist hashing
• Minimax and Alpha beta pruning
• Killer moves and refutation tables
• Static evaluation function
• Quiescence search
• Monte-Carlo Tree Search
• UCT

• Opening book
• Endgame tablebase

The simplest chess programs use brute-force searching coupled with static position evaluation dominated by material considerations. They 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. Computationally, the number of options a player has available to them governs the number of different paths play can go down. This is known as the branching factor. The average branching factor in a game of Chess is about 35,[5] whereas in Arimaa it is about 17,000.[6]

These differing branching factors imply that a computer which can search to a depth of eight turns for each player in chess, can only search about three turns deep for each player in Arimaa:

${\displaystyle 35^{8}\approxeq 17000^{3}}$

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 moves are 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 rarer. 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 toward 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 median 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 magnifies the importance of correctly judging who is gaining 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 2014 Challenge match. Another example of low capture density is this semifinal game of the 2012 World Championship, featuring only a single capture, a goal-forcing elephant sacrifice.

Omar Syed hopes that, because traditional artificial intelligence techniques are only moderately effective for Arimaa, programmers will be forced to use new 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 Syed's man-against-machine challenge is focused on rewarding advances in AI software and not advances in hardware. In the annual challenge, programs are run on machines chosen and provided by 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. Syed believes that even the computer used in the 2004 challenge match (a Pentium 4 2.4 GHz system with 512 MB of RAM) had sufficient hardware to win the challenge prize if only it was running the proper software. Supercomputers might already have the power to conquer Arimaa by brute force using conventional AI software, and eventually personal computers will too, if hardware continues to advance at the current rate. This is why the Arimaa challenge prize was originally offered only until the year 2020.