2020-09-15
Opponent-Pruning Paranoid Search
Publication
Publication
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 finegrained 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 max^n and Paranoid search.We conclude that OPPS opens a promising research direction for search in multiplayer board and video games, and beyond.
| Additional Metadata | |
|---|---|
| , | |
| doi.org/10.1145/3402942.3402957 | |
| International conference on the Foundations of Digitial Games | |
| Organisation | Intelligent and autonomous systems |
|
Baier, H., & Kaisers, M. (2020). Opponent-Pruning Paranoid Search. In FDG '20: International Conference on the Foundations of Digital Games. doi:10.1145/3402942.3402957 |
|
