# Solving an Ancient African Game

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.

 Player 2 4 4 4 4 4 4 Player 1 4 4 4 4 4 4

Awari: initial configuration.

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.

 Player 2 4 4 4 4 4 5 Player 1 4 4 0 5 5 5

Above: Configuration after player 1 takes a turn.

 Player 2 5 0 4 4 4 5 Player 1 5 5 1 5 5 5

Above: Configuration after player 2 takes a turn.

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.

Player 2
Cup 12 Cup 11 Cup 10 Cup 9 Cup 8 Cup 7
2 0 2 1 2 4
Cup 1 Cup 2 Cup 3 Cup 4 Cup 5 Cup 6
1 1 2 0 5 0
Player 1

If player 1 plays the five beans in the fifth cup, beans are deposited in cups 6, 7, 8, 9, and 10. The player captures the beans in cups 10, 9, and 8 (a total of eight beans). If player 2 then plays the two beans in cup 12, beans go into cups 1 and 2. The player captures the beans in cups 1 and 2 (a total of four beans).

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 (including captured beans) 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.