Go-Moku and Threat-Space Search
L.V. Allis, H.J. van den Herik, M. P. H. Huntjens · 1993
Many decades ago, Japanese professional Go-Moku players stated that Go-Moku (Five-in-a-row on a horizontally placed 15×15 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. 1.