Computer cracks Go game

[Tormod]

A computer program that can solve the Go game for a 5x5 playing board. Dutch researcher Erik van der Werf achieved a world first with this program. A complete Go playing board has 19x19 rows. Van der Werf investigated new computing techniques to improve the Go programs with the ultimate aim of beating the best human players.

 

Not only has Van der Werf solved the Go game on a playing board of 5x5 rows, but also Battle Go (a simplified version of Go) for boards of up to 6x6 rows. With their last program MAGOG, Van der Werf and his colleagues won the bronze medal at the 9x9 Go tournament, held at the ninth Computer Olympiad in Israel last summer.

 

Technique

 

Van der Werf's research focused on searching and learning techniques for games programs. Searching techniques are used in chess programs to think several moves ahead. This allows the tactical complications in positions to be better assessed. A search program that is efficient enough to think so far ahead that it achieves end positions can, in principle, play perfectly. The MIGOS program used to solve the Go game on a 5x5 playing board, is based on searching techniques.

 

However, searching techniques alone are not enough to play Go well on larger playing boards. Then the program cannot always search deep enough to achieve end positions. 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.

 

Tactics

 

Go is a board game from Eastern Asia for two players. Each tries to surround a territory with stones of their colour. 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. 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.

 

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.

 

The research was funded by the Netherlands Organisation for Scientific Research.

[zadojla]

Factors that make difficult for Go progams to be strong include:

• Branching factor - simply put, there are 20 choices for the first half-move of a chess game, followed by 20 choices for the second half-move. For Go, these numbers are 361 and 360 respectively.
  
• Length of game - a typical chess game lasts 60 to 100 half moves; a typical go game can last for over 300.
  

This makes devising effective pruning strategies for Go very challenging.

Certain simpler games, like Othello/Reversi, with more limited move trees have programs that are almost impossible for a human to beat, picking the optimum play for a look-ahead of 24 half-moves, and perfect play for the last 40 half-moves.

[pgrmdave]

I've never played Go, though I've wanted to learn how. I've never known anybody who knew how to play, and reading the rules doesn't teach strategy, or typical game-play very well. It always seemed like it was deceivingly simple.

[zadojla]

I've never played Go, though I've wanted to learn how. I've never known anybody who knew how to play, and reading the rules doesn't teach strategy, or typical game-play very well. It always seemed like it was deceivingly simple.

Me, too. But I have two go sets and 17 elementary books on Go. At least you could look at the diagrams to see what a real game looks like. There are also internet Go servers where one can play. I'll try to find one for you that doesn't mind beginners.

[TINNY]

over here, a modified type of Go game is very popular at school. they call it 'kepung' or literally translated as 'siege' or 'empire'. Real fun. You have the checked exercise books to play on. so all my maths exercise books at the back pages are full of it.

[zadojla]

So, don't tease me! What are the rules?

[TINNY]

i did a computer game of it with VB a few years back. see if I can find it when I get home next month...