Opponent-Pruning Paranoid Search
Hendrik Baier, Michael Kaisers · 2020
This paper proposes a new search algorithm for fully observable, deterministic multiplayer games: Opponent-Pruning Paranoid Search (OPPS). OPPS is a generalization of a state-of-the-art technique for this class of games, Best-Reply Search (BRS+). Just like BRS+, it allows for Alpha-Beta style pruning through the paranoid assumption, and both deepens the tree and reduces the pessimism of the paranoid assumption through pruning of opponent moves. However, it introduces three parameters that allow for more fine-grained control over the resulting search. Empirically, we show the effectiveness of OPPS in Chinese Checkers variants with three, four, and six players, where it outperforms its special case BRS+ as well as classic maxn and Paranoid search. We conclude that OPPS opens a promising research direction for search in multiplayer board and video games, and beyond.