Boffins crack ancient board game with 36 server cluster

Boffins have harnessed advanced computer techniques to devise how to play a perfect game of Awari, an ancient board game originating in Africa that is more than 3,500 years old, for the first time.

Awari is a two-player game where both players own six pits, in which stones are kept. These 48 stones are sown around over the pits, and can be captured according to the rules of the game. The objective of the game is to capture more than 24 stones.

Although the rules are simple, the game requires deep strategic insight to be played well.

Dutch computer scientists from the Vrije Universiteit, Amsterdam solved the game by developing a program that computes the best move and eventual outcome for all 889,063,398,406 positions that can possibly occur in a game. If played perfectly by both players, Awari results in a draw.

To analyse the game, scientists used a large computer cluster of 36 IBM dual processor servers, featuring 1GHz Pentium III chips (72 processors in all).

This cluster ran a newly developed fast, parallel algorithm which successfully generated a 778 GB database on the game in only 51 hours.

Dr. John Romein and Professor Henri Bal, who led the work, had to overcome several obstacles in order to complete their task.

One complication was that the available main memory, 72 GB, was far too small to hold the entire database. Another problem was the heavy communication between the processors, which strained the network used in the project.

Having successfully completed this task, the researchers developed an invincible Awari program, which uses the database to play a perfect game. The game can be played online, with its default settings turned down so that humans stand a chance of winning.

Although the research resulted in a faster parallel processing algorithm, Dr. Romein said it wasn't directed towards any particularly commercial application. The researchers took on their task out of a spirit of intellectual curiosity and the fun involved in developing a Web-based version of the venerable game.

Romein told us, however, that the Dutch researchers intend to quit while they're ahead.

It seems unlikely that games like chess and go will prove solvable in the foreseeable future, no matter how much computing power is thrown at the effort. Solving draughts (checkers) does seems feasible, but is not something the Dutch researchers have any plans to take on. ®

Related Stories

Greek govt bans all computer games
Uni chess course aims to spawn smarter supercomputers