Go-Moku Solved by New Search Techniques

Contents

Many decades ago, Japanese professional Go-Moku players stated that Go-Moku (Five-in-a-row on a horizontally placed 15x15 board) is a won game for the player to move first. So far, this claim has never been substantiated by (a tree of) variations or by a computer program. Meanwhile many variants of Go-Moku with slightly different rules have been developed. This paper shows that for two common variants the game-theoretical value has been established. Moreover, the Go-Moku program Victoria is described. It uses two new search techniques, threat-space search and proof-number search. One of the results is that Victoria is bound to win against any (optimal) counterplay if it moves first. Furthermore, it achieves good results as a defender against non-optimally playing opponents. In this contribution we focus on threat-space search and its advantages compared to conventional search algorithms.