Computer Go (version 142)

Table of contents Introduction References Philosophy List of Existing Go Playing Programs List of Existing Problem Solving Programs Robots Anti-Computer Strategy Competitions History of Go Programs vs Human Professional Matches History of Go Programs Articles in Magazines Links Maillist(-Archives)

Introduction

While many strategic games, such as chess and backgammon, have in the last few decades been conquered by machines, there is much yet to be done in the field of computer Go.

In 1995, professional player Janice Kim defeated the top program of the day despite of a whopping 25 stone handicap. Since then, rapid progress has been made. By the early 2000's, computer programs were at the footsteps of amateur 1 dan - quite a large improvement, but still lightyears away from the realm of top human professionals. However, in 2006 a new approach to Go AI began sweeping the Go scene: Monte Carlo. This method builds a tree of potential moves and responses, but evaluates each move in the tree by using a semi-random playouts. In a playout, the program plays the game to completion, using either random moves or very simple heuristics. When a playout results in a win, that improves the score of the moves it originated from, and the best performing move is chosen. As of 2012, several programs playing on KGS have reached 5 or 6 dan. Naive extrapolation would say that computers will reach professional strength sometime between 2015 and 2018. Unfortunately, no one knows any way to reliably estimate future progress. Strength improvements could slow at any time, or new ideas could make them come faster.

It has been argued that these ranks are a bit deceptive, however, because with sufficient practice playing against computers, a human can often adapt to the weaknesses of the programs and subsequently perform much better against them (see the Shodan Go Bet for one attempt to confirm this idea). Also, it is a common belief that on the go server people tend to take games against computer opponents less seriously. Today, the top programs have won against professionals with a 4 or 5 stone handicap.

Thus computer Go is a very exciting part of Artificial Intelligence (AI), and many new ideas and techniques are yet to be discovered. It's interesting to note that compared to the approach which proved so successful with Chess, brute force, appears to be not nearly as useful for solving Go problems because of the huge branching factor of the game tree.

In fact, Go endgames have been proven to be PSpace-hard, let alone other parts of the game. Also, many other aspects of Go, including life and death, are also known to be NP-hard. This means that it is very unlikely to be able to find a reasonably fast algorithm for playing perfect Go. So it looks like it's all about heuristics (surprise surprise).

Patrick Taylor: I'm not sure heuristics are all that bad. Humans don't know the perfect move sequence any more than computers do. Therefore, we basically play with heuristics as well. Proverbs are essentially heuristics used by human players to approximate good play.

In July 2011, KGS records accurately show computer program Zen19s achieving 4 dan. In June and July 2011, Zen19s played 700 games on the KGS Go server. Zen19s plays at 20 minutes main time and then 30 seconds per move. A player can download the games of Zen19s from the KGS server. The player can study the games to find the program's weakness and try to exploit it. After 700 games and almost 2 months, Zen19s is 4 dan on KGS. This shows that finding the weakness of computer players is just as hard as finding the weakness of human players. Computers have truly reached the 4 dan level. Successful chess programs do not use brute force, but are selective in finding a move. Chess programs that use brute force, play at a low level because of the huge branching factor. Chess programmers do not use fast algorithm for playing perfect Chess. Mark Schreiber, July 22, 2011

References

See the Computer Go Bibliography maintained by the Computer Go Group at the University of Alberta.

Philosophy

Before delving into computer Go, it would behoove the novice to consider some philosophical questions about computers and Go.

List of Existing Go Playing Programs

Please see Go Playing Programs for a discussion about the best programs currently available.

List of Existing Problem Solving Programs

• Go Tools -- enclosed life and death problems
• MadLab -- tesuji problems

Robots

Some online Go servers, such as KGS, provide software opponents or robots to clients. Robot is derived from the Czech word robota meaning drudgery or slave labour which certainly describes the work needed to pummel double digit kyu players like me. PatG

Anti-Computer Strategy

It might be entertaining and educational to consider strategies for beating computers? at Go.

Competitions

Below are competitions where Go playing programs can be tested.

• All competitions
• Monthly KGS internet tournaments
• Computer Go Server
• Computer Go Ladder
• Shodan Go Bet: 2010 can a computer beat a Shodan

International Competitions:

• Computer Olympiad (1988-present)
• UEC Cup? (2007-present)
• Gifu Challenge (2003-2006)
• 21st Century Cup (2001-2002)
• Ing World Championship (1985-2000)
  • Winners could make an attempt at the Ing Prize
• FOST (1995-1999)

Regional Competitions:

• European Championship (1987-2005,2008)
• US Championship (1988-2000,2008)
• USENIX (1984-1988)

Small Board Competitions:

• 2002 Computer-Go 13x13 Tournament -- Osnabrueck
• CGOS
• monthly KGS tournaments
• Computer Go Ladder

History of Go Programs vs Human Professional Matches

Program vs Professional

History of Go Programs

• [1989]: GNU Go 1.1 was posted to comp.sources.games March 13 1989
• [1968]: Albert L. Zobrist wrote the first ever program which played complete Go games.
• Ishi - old file format

Articles in Magazines

• To Test a Powerful Computer, Play an Ancient Game
• Go Computings Future Article
• Cracking Go by Feng-Hsiung Hsu published in the October 2007 issue of the IEEE magazine Spectrum Online.

Links

• Computer-go.info: http://www.computer-go.info/h-c/index.html contains a list with result of computer vs professionals.

• http://computergo.wikispaces.com/

• http://www.intelligentgo.org/

• http://www.citeulike.org/group/5884/library (Computer Go Bibliography)

• http://www.inventivity.com/OpenGo/Papers/EditedGoPapers.html

(Smaller Go Bibliography, with comments)

• http://www.mechner.com/david/compgo/

• http://gobase.org/go-7.html : Jan van der Steen's computer Go page has numerous links to famous programs and programmers as well as programming resources and articles.

• http://www.epp.infonomics.nl/FdAW/chen/go.htm : A nice compilation of the strategies and heuristics used by current Go playing programs. (LINK BROKEN)
  • Paper version: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.1567

• http://nis.acs.uci.edu/~strombrg/ml.html (Machine Learning) Including Neural Networks, Genetic Algorithms, Temporal Difference Learning. (LINK BROKEN)

• http://www.gnu.org/software/gnugo/gnugo.html (GNU Go)

• http://www.cgl.ucsf.edu/go/ladder.html (The Computer Go Ladder) still active ?

Maillist(-Archives)

• gnugo-list

• http://computer-go.org/pipermail/computer-go/ Active computer-go list archives.

• http://www.daogo.org/ Archive of Computer Go newsletter, issues 1 to 16. In PDF.

Authors: Gounter, Chestnut