Go-Moku Solved by New Search Techniques

L. V. Allis, H. J. van den Herik, M. P. H. Huntjens

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.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.