A1 techniques used in Computer Go
Jay Burmeister, Janet Wiles · 1999
This paper surveys the most competitive Computer Go programs. It is targeted generally at the Cognitive Science community as an introduction to Computer-Go, given the growing importance of Go as a domain for Cognitive Science research, and specifically at Computer Go programmers (or prospective Go programmers). We survey the best current Computer Go programs, Handtalk, Go4++, Many Faces of Go, Go Intellect, and Explorer. We summarise the AI techniques used, key challenges that must be faced, and issues involved in game tree search, showing why Computer Chess techniques do not translate well to the Go domain. 1. Competitive Go Programs Go1 is one of the last formal game domains in which computer performance is not competitive against even moderately good human players. There are several annual Computer Go tournaments, notably the FOST Cup which promises JPY 2,000,000 (around AUD $23,000) for 1st place, as well as the unclaimed Ing Prize TWD $40M (around AUD $1.9M) for the first Go program to beat a professional player in a best-of-seven match without handicap. The earliest work in Computer Go using Go as a research domain was in 1962 although the first complete game played by a program was in 1968 (Zobrist, 1970). Computer Go became established as a field in the 1980's when Computer Go tournaments began and the first commercial programs were released, and has since flourished in the 1990s. The top programs currently active in Computer Go competitions include Explorer, Go Intellect, Go4++, HandTalk, and The Many Faces of Go, and are currently ranked in the range of approximately 4-8 kyu. 2. Game-Tree Search in Go The typical AI approach to playing 2 player perfect information games is to search the game-tree in order to decide what move to play. Standard game-tree search comprises four components: 1. representation of game states, 2. generation of possible moves, 3. determination and recognition of goal states, and 4. a static evaluation function to determine the relative merit of states. An effective means of pruning the game-tree (e.g., alphabeta) enhances the performance of programs. The game-tree approach can be very successful, as shown by chess programs which are based on full-width game-tree search typically using alpha-beta pruning, and challenge even the world champion2. In this section we examine the four components of game-tree search from a Computer Go perspective. 2.1 State Representation From a perfect information perspective, a Go board is a 19x193 grid with each intersection point being either empty or occupied by either a black or a white stone. The size of the state-space (i.e., the number of possible positions) can be estimated4 at 3361 (or 10172) compared to approximately 1050 for chess and 1030 for othello (Allis, 1994). The size of the game-tree (i.e., the number of possible games) is estimated5 to be between 10575 and 10620 compared with estimates of 10123 for chess and 1055 for othello (Allis, 1994). Solely representing the state space in terms of the 19x19 grid is too low-level for either humans or machines to use effectively, due to the combinatorial size of the space. The next level of description is to form orthogonally adjacent stones into strings (or chains). All programs collect strings into larger units, however, 1. Go is a very popular board game known as Igo in Japan, Wei-Ch’i in China and Taiwan, and Baduk in Korea. 2. Deep Blue beat the world champion Garry Kasparov in a best-of-six series in May 1997. 3. Go is also played on 9x9 and 13x13 boards. 4. Not all positions would be legal; also a history must be maintained for each board position to avoid illegal ko repetitions. 5. The estimate of 10575 is based on an average branching factor of 200 and average game length of 250 ply (i.e. 200250). The size of the game-tree may be as high as 10620 if the average game is considered to be 300 ply (Burmeister & Wiles, 1995). there is no generally accepted process even for expert human players for grouping strings into larger units. Depending on their theory of Go, programmers develop their own heuristics for assessing when strings are effectively linked together (called variously groups or blocks). In addition, the appropriate level of representation can vary depending on the sub-task being performed at the time, for example, tactical analysis, life-and-death analysis, or assessing territory.