Computer Arimaa

Uses your system voice; voice and rate in settings.

Snapshot

≈ 8 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Computer Arimaa refers to the playing of the board game Arimaa by computer programs. In 2002, Indian-American computer engineer Omar Syed published the rules to Arimaa and announced a $10,000 prize, available annually until 20201, for the first computer program (running on standard, off-the-shelf hardware) able to defeat each of three top-ranked human players in a three-game series. The prize was claimed in 2015, when a computer program played 7:2 against three human players. The game has been the subject of several research papers.

Computer Arimaa refers to the playing of the board game Arimaa by computer programs. In 2002, Indian-American computer engineer Omar Syed published the rules to Arimaa and announced a $10,000 prize, available annually until 2020, for the first computer program (running on standard, off-the-shelf hardware) able to defeat each of three top-ranked human players in a three-game series. The prize was claimed in 2015, when a computer program played 7:2 against three human players. The game has been the subject of several research papers.

State space of Arimaa

Opening

The number of different ways that each player can set up their pieces at the beginning of the game is: \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: 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."

Artificial intelligence techniques

Material evaluation

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.

Techniques used in Arimaa bots

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

Techniques rarely used In Arimaa bots

Opening book Endgame tablebase

Computer performance

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. 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.

Resources for software developers

The Arimaa Engine Interface, developed by Brian Haskin, defines a protocol that allows an Arimaa engine to communicate with a controller. According to the documentation: "An engine is a program capable of taking the state of an Arimaa game and selecting a legal move to make. A controller is anything that wants to communicate with and control an engine. This could be anything from a simple script to have the engine analyse a single position to a GUI program that allows games to be played with humans or other engines." The Arimaa Engine Interface includes an implementation of an engine and controller, documentation, and various scripts to control the engine and play games on any website which supports the protocol, including the official Arimaa website.

Research papers

Arimaa challenge - comparission study of MCTS versus alpha-beta methods thesis by Thomas Jakl (Charles University, Prague) Oct 2011 Move Ranking and Evaluation in the Game of Arimaa thesis by David Jian Wu (Harvard College, Cambridge, Massachusetts, USA) May 2011 Arimaa, a New Challenge for Artificial Intelligence thesis by Stefano Carlini (University of Modena and Reggio Emilia, Italy) Apr 2010 Methods of MCTS and the game Arimaa thesis by Tomas Kozelek (Charles University of Prague, Czech Republic) Dec 2009 Modeling the game of Arimaa with linguistic geometry paper by Joséoberto Mercado Vega and Zvi Retchkiman Kösberg (from Instituto Politéico Nacional, presented at Proceedings of the 5th international conference on Computational Intelligence and Games, Milano, Italy) Sep 2009 Researching and Implementing a Computer Agent to Play Arimaa thesis by Sam Miller (University of Southampton, UK) May 2009 Plans, Patterns and Move Categories Guiding a Highly Selective Search paper by Gerhard Trippen (presented at the 2009 Advances in Computer Games 12 conference, Pamplona, Spain) May 2009 Arimaa, the Game of Real Intelligence? presentation by Nicolas A.

Barriga (University Tecnica Federico Santa Maria, Chile) Aug 2006 Analysis and Implementation of the Game Arimaa and Appendix B thesis by Christ-Jan Cox (Universiteit Maastricht, Institute for Knowledge and Agent Technology), Mar 2006 Building a Strong Arimaa-playing Program thesis by Haizhi Zhong (University of Alberta, Dept. of Computing Science) Sep 2005 Building a World Champion Arimaa Program paper by David Fotland (www.Smart-Games.com) 2004 Arimaa - A New Game Designed to be Difficult for Computers paper by Omar Syed and Aamir Syed; Journal of the International Computer Games Association; Jun 2003

Footnotes

Text derived from https://en.wikipedia.org/w/index.php?oldid=1312025888 under CC BY-SA 4.0; modifications have been made.

References

  1. ↩Wikipedia “Computer Arimaa” revision 1312025888 · retrieved 2026-10-20 publication date (×1) · confidence 0.95 revision URL