Solving NoGo on Small Rectangular Boards

The game of NoGo is similar to Go in terms of rules, but requires very different strategies. While strong heuristic computer players have been created for NoGo, solving and optimal play have been less studied. We introduce Sorted Bucket Hash (SBH), a new approach to building transposition tables for game solvers, and apply it to solve NoGo on small boards. Using boolean negamax with standard heuristics and SBH, our program SBHSolver has now solved NoGo on 50 different rectangular boards including \(3\times 9\) , the largest solved NoGo game to date. It re-solved \(5\times 5\) NoGo much more efficiently than She’s work in 2013 and Cazenave’s work in 2020. The SBH data structure can also efficiently extract a proof tree for the game. We provide analyses of NoGo proof trees and games, and discuss human-understandable strategies from this perspective.