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.