JultikaUniversity of Oulu repository

In 1988, Connect-4 became the second non-trivial board game to be solved. PopOut is a variant of Connect-4 that was released in 2009. PopOut allows both players to "pop" disks from the bottom row in addition to dropping new disks from above. Connect-4 is a divergent game where the maximum depth of the game tree is 42. Because of the pop moves, PopOut is not divergent but unchangeable and this causes the maximum depth to be much larger. Furthermore, PopOut allows positions to be repeated making the Graph History Interaction (GHI) problem possible. It is not fully understood why some games have been solved while others remain unsolved. Connect-4 and PopOut are similar games but they have slight changes in some game characteristics. The biggest of these is the change in convergence type. There has not been a previous reported attempt to solve PopOut. By analyzing the game, more light is shed on the relationship between game characteristics and solvability. We studied whether the search techniques that have been used in solving Connect-4 are also applicable to PopOut and how they should be modified or augmented to be effective. Proof-number search was able to weakly solve PopOut with no modifications. Alpha-beta with its standard enhancements needed heavier modifications to counteract the depth of the game tree and to circumvent the GHI problem. The game-tree depth was successfully limited by “handicapping” the first player. The first player was prohibited from making non-winning pop moves and any game exceeding a chosen number of moves was declared a loss for the first player. Alpha-beta was able to show that the first player still wins under these handicapping rules. The handicapping technique was essential in solving the game with Alpha-beta. The technique has not been used previously but it might also be applicable to other board games and search algorithms. PopOut is a first-player win on the standard board size 7x6. Smaller board sizes are either first-player wins or draws by repetition. Some of the smaller boards were strongly solved by retrograde analysis which performed a total enumeration of the state space. No contradictions were found between the three different solving approaches suggesting that the results are reliable.