Computer Cracks Go Game
Dutch researcher Erik van der Werf has achieved a world first with a computer program that can solve the Go game for a playing board of 5×5 rows, as well as Battle Go (a simplified version of Go) for boards of up to 6×6 rows. The research was funded by the Netherlands Organisation for Scientific Research.
In playing Go, an Eastern Asian board game, two players each try to surround a territory with stones of their color. A player can strike the stones of his opponent by surrounding these with his own stones. The player with the most territory wins the game. A complete Go playing board has 19×19 rows. According to legend, the game was first played in 2300 BC by a Chinese emperor who wanted to teach his son tactics, strategy and concentration.
Van der Werf investigated new computing techniques to improve Go programs with the ultimate aim of beating the best human players. With their last program MAGOG, Van der Werf and his colleagues won the bronze medal at the 9×9 Go tournament, held at the ninth Computer Olympiad in Israel last summer.
Van der Werf’s research is modeled on searching and learning techniques for games programs. Searching techniques are used in chess programs to think several moves ahead, allowing the tactical complications in positions to be better assessed. A search program efficient enough to think so far ahead that it achieves end positions can, in principle, play perfectly. The MIGOS program used to solve the 5×5 board game is based on searching techniques.
However, the program cannot always search deep enough to achieve end positions on larger playing boards. Therefore, Van der Werf also investigated learning techniques, which are used in games such as backgammon or other complex applications such as image recognition. The computer uses learning techniques to learn from human demonstration games which the Go program analyses. Van der Werf used learning techniques to predict strong positions, predict life and death and to estimate potential territory.
In 1997, the chess computer Deep Blue beat the world chess champion Kasparov. Yet, almost eight years later, a Go program that can beat a good amateur has yet to be developed. In the mid-1980s the Taiwanese industrial mogul Mr Ing put up $1 million for the maker of the first Go program capable of beating a professional player. The prize money expired in 2000 with the death of Mr Ing, but the challenge has yet to be met.
