Ivars Peterson's MathTrek
September 9, 2002
The game of awari has entranced players for thousands of years. Originating in Africa, it remains a popular pastime in many parts of the world. Awari and its numerous variants are instances of "count-and-capture" strategy games, and they are known generically as mancala games.
In its traditional form, the awari game "board" consists of two parallel rows of six hollows, with four markers (beans) in each hollow, or cup. Two players sit opposite each other, with six cups belonging to one player and six to the other. The game's goal is to capture the most beans.
The first player takes all the beans from any one of the six cups on his or her side and, moving anticlockwise, adds one bean to each succeeding cup, until all the beans are used up. The second player then takes the beans from one of the six cups on his or her side and does the same.
When a player drops his or her last bean into a cup on the opponent's side containing only one or two beans (making a total of two or three beans), that player removes all the beans from this cup, taking them out of the game. The same player also takes any beans in cups immediately before the emptied cup if they now also total two or three.
Players take beans only from their opponent's side. As the game progresses, a given cup can contain any number of beans, but the total number remains 48. The game ends when one player has no beans left in the cups on his or her side and, hence, cannot move any beans. The winner is the player who has captured the majority of the beans.
Technically, awari is a two-person game of perfect information. Like chess, checkers, and other games in which chance is not involved, it has been of particular interest to researchers in the field of artificial intelligence. Over the years, programmers have also created software to play the game. A number of these computer programs faced off against each other in a computer awari tournament, held in 1999 at the University of Alberta. At that time, no program could guarantee a win or even a draw.
To figure out what happens in the game, computer scientists John W. Romein and Henri E. Bal of the Free University in Amsterdam wrote a computer program that calculates the best move and eventual outcome for all 889,063,398,406 positions that can possibly occur in the game.
Their result? As in tic-tac-toe, when you and your opponent play perfectly, the game always ends in a draw.
A computational tour de force, the calculations required about 51 hours on a large computer cluster with 144 processors, orchestrated by a novel divide-and-conquer algorithm for distributing the computations. The results were stored in a 778-gigabyte database.
Romein and Bal are now developing what they describe as an "invincible" awari program, which uses the database to play perfectly. In the meantime, visitors to their Web site at http://awari.cs.vu.nl/ can play an online version of the game, which is programmed to play at a less-than-optimal level so that a good human player can actually still beat the computer.
Copyright 2002 by Ivars Peterson
Davis, J.E., and G. Kendall. Preprint. An investigation, using co-evolution, to evolve an awari player. Available at http://www.cs.nott.ac.uk/~gxk/papers/cec2002gxk.pdf.
The complete rules of awari can be found at http://www.awari.com/ or or http://www.cs.ualberta.ca/~awari/rules.html.
You can play awari online at http://awari.cs.vu.nl/. See http://www.myriad-online.com/awalink.htm for links to additional Web sites where you can play the game or download software for playing it on your computer or even cell phone.
The University of Alberta computer awari group has a Web page at http://www.cs.ualberta.ca/~awari/.
Comments are welcome. Please send messages to Ivars Peterson at email@example.com.
A collection of Ivars Peterson's early MathTrek articles, updated and illustrated, is now available as the MAA book Mathematical Treks: From Surreal Numbers to Magic Circles. See http://www.maa.org/pubs/books/mtr.html.