Newsgroups: rec.games.go,rec.games.abstract From: darse@cs.UAlberta.CA (Darse Billings) Subject: Go-Moku Solved (Summary and References) Summary: Go-Moku and a common variation solved by Allis Keywords: Go-Moku, computer game playing Organization: University of Alberta Date: Wed, 17 Nov 1993 20:53:12 GMT
In response to some questions raised in rec.games.go, here is a brief summary of the results in solving Go-Moku. Background: ----------- Go-Moku is played on a 15x15 Go board, with the objective being to make a line of five connected stones, horizontally, vertically, or diagonally. The game of Pente (TM) is the commercial version. The first player has a large advantage, and the game has long been considered by professionals to be a win for Black. But until now, there has not been a proof of this claim. There are several variations, designed to reduce the advantage for Black: (1) Playing on a full 19x19 Go board (but this actually *increases* Black's advantage [Sak81]). (2) A line of six connected stones does not win (for either player) -- it must be exactly five stones in a row. (3) Black must play the first stone on the center point and the second stone must be diagonally connected to this stone. (4) Black must play the first stone on the center point and the second stone cannot be placed in the 5x5 square centered around the first stone. (5) Renju, the Go-Moku version played by professionals. White may win with a line of six connected stones, and Black may not make the "three-three" nor "four-four" shape [Sak81]. Results: -------- Victor Allis et al. [AHH93] have demonstrated that Go-Moku is a win for Black (implying that variant (1) is also a win). Variation (2), above, is also a win for Black. Both Go-Moku and Variation (2) can be won by the first player in 18 moves (35 ply) against optimal defense. Their solution tree for Go-Moku contained 138,790 positions, while Variation (2) required 153,284 nodes. They employed a new search technique, called "threat space search", in which the branching factor for attacking sequences is greatly reduced by allowing the defensive side to play *all* direct responses to threats (typically two or three moves against each threat of three connected stones). This provides a very fast analysis of sufficient winning conditions, but may overlook certain possibilities. A secondary method is used to identify those (relatively uncommon) situations, and a proof number search is invoked for completeness. The computer program Victoria will always win with Black; playing from a database until White deviates, then using a threat space search to find the (shorter) forced win. In the Go-Moku competition at the 1992 Computer Olympiad (played under the rules of Variation (2)), Victoria won all of its games with Black, plus half of its games with White, which was sufficient to win the gold medal. As a result of solving Go-Moku, the game will be retired from competition. This is Allis' third scalp, having solved Connect Four (TM) in 1989, and (resolving) Qubic (TM) in 1991. References: ----------- [Sak81] G Sakata and W Ikawa, _Five-In-A-Row Renju_, The Ishi Press, Inc. (1981). [AHH93] L V Allis, H J van den Herik, and M P H Huntjens, "Go-Moku Solved by New Search Techniques", Working Notes of the AAAI Fall Symposium Series (Raleigh, NC, Oct 22-24, 1993). FS-93-02 AAAI Press. Cheers, - Darse. -- - Darse Billings, 2065 CFC, 7 kyu. Go is better than Chess. Poker is more lucrative. Sex is more fun.