Opponent-Pruning Paranoid Search

Hendrik Baier; Michael Kaisers

doi:10.1145/3402942.3402957

Opponent-Pruning Paranoid Search

Hendrik Baier
, Michael Kaisers

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

This paper proposes a new search algorithm for fully observable, de-
terministic 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 as-
sumption, 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.

Original language	English
Title of host publication	FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games
Editors	Georgios N. Yannakakis, Antonios Liapis, Kyburz Penny, Vanessa Volz, Foaad Khosmood, Phil Lopes
Publisher	Association for Computing Machinery, Inc.
Number of pages	7
ISBN (Electronic)	9781450388078
ISBN (Print)	978-1-4503-8807-8
DOIs	https://doi.org/10.1145/3402942.3402957
Publication status	Published - 15 Sept 2020
Event	15th International Conference on the Foundations of Digital Games - , Malta Duration: 15 Sept 2020 → 18 Sept 2020 Conference number: 15

Publication series

Name	ACM International Conference Proceeding Series

Conference

Conference	15th International Conference on the Foundations of Digital Games
Abbreviated title	FDG 2020
Country/Territory	Malta
Period	15/09/20 → 18/09/20

Keywords

game tree search
multiplayer games

Access to Document

10.1145/3402942.3402957

Cite this

Baier, H., & Kaisers, M. (2020). Opponent-Pruning Paranoid Search. In G. N. Yannakakis, A. Liapis, K. Penny, V. Volz, F. Khosmood, & P. Lopes (Eds.), FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games Article 10 (ACM International Conference Proceeding Series). Association for Computing Machinery, Inc.. https://doi.org/10.1145/3402942.3402957

Baier, Hendrik ; Kaisers, Michael. / Opponent-Pruning Paranoid Search. FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games. editor / Georgios N. Yannakakis ; Antonios Liapis ; Kyburz Penny ; Vanessa Volz ; Foaad Khosmood ; Phil Lopes. Association for Computing Machinery, Inc., 2020. (ACM International Conference Proceeding Series).

@inproceedings{2d6d103533a84f08b757f524817e034b,

title = "Opponent-Pruning Paranoid Search",

abstract = "This paper proposes a new search algorithm for fully observable, de- terministic 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 as- sumption, 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.",

keywords = "game tree search, multiplayer games",

author = "Hendrik Baier and Michael Kaisers",

year = "2020",

month = sep,

day = "15",

doi = "10.1145/3402942.3402957",

language = "English",

isbn = "978-1-4503-8807-8",

series = "ACM International Conference Proceeding Series",

publisher = "Association for Computing Machinery, Inc.",

editor = "Yannakakis, \{Georgios N.\} and Antonios Liapis and Kyburz Penny and Vanessa Volz and Foaad Khosmood and Phil Lopes",

booktitle = "FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games",

address = "United States",

note = "15th International Conference on the Foundations of Digital Games, FDG 2020 ; Conference date: 15-09-2020 Through 18-09-2020",

}

Baier, H & Kaisers, M 2020, Opponent-Pruning Paranoid Search. in GN Yannakakis, A Liapis, K Penny, V Volz, F Khosmood & P Lopes (eds), FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games., 10, ACM International Conference Proceeding Series, Association for Computing Machinery, Inc., 15th International Conference on the Foundations of Digital Games, Malta, 15/09/20. https://doi.org/10.1145/3402942.3402957

Opponent-Pruning Paranoid Search. / Baier, Hendrik; Kaisers, Michael.
FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games. ed. / Georgios N. Yannakakis; Antonios Liapis; Kyburz Penny; Vanessa Volz; Foaad Khosmood; Phil Lopes. Association for Computing Machinery, Inc., 2020. 10 (ACM International Conference Proceeding Series).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Opponent-Pruning Paranoid Search

AU - Baier, Hendrik

AU - Kaisers, Michael

N1 - Conference code: 15

PY - 2020/9/15

Y1 - 2020/9/15

N2 - This paper proposes a new search algorithm for fully observable, de- terministic 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 as- sumption, 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.

AB - This paper proposes a new search algorithm for fully observable, de- terministic 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 as- sumption, 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.

KW - game tree search

KW - multiplayer games

UR - https://www.scopus.com/pages/publications/85092328252

U2 - 10.1145/3402942.3402957

DO - 10.1145/3402942.3402957

M3 - Conference contribution

SN - 978-1-4503-8807-8

T3 - ACM International Conference Proceeding Series

BT - FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games

A2 - Yannakakis, Georgios N.

A2 - Liapis, Antonios

A2 - Penny, Kyburz

A2 - Volz, Vanessa

A2 - Khosmood, Foaad

A2 - Lopes, Phil

PB - Association for Computing Machinery, Inc.

T2 - 15th International Conference on the Foundations of Digital Games

Y2 - 15 September 2020 through 18 September 2020

ER -

Opponent-Pruning Paranoid Search

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this