Opponent-Pruning Paranoid Search

Hendrik Baier; Michael Kaisers

doi:10.1145/3402942.3402957

Opponent-Pruning Paranoid Search

Hendrik Baier
, Michael Kaisers

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Samenvatting

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.

Originele taal-2	Engels
Titel	FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games
Redacteuren	Georgios N. Yannakakis, Antonios Liapis, Kyburz Penny, Vanessa Volz, Foaad Khosmood, Phil Lopes
Uitgeverij	Association for Computing Machinery, Inc.
Aantal pagina's	7
ISBN van elektronische versie	9781450388078
ISBN van geprinte versie	978-1-4503-8807-8
DOI's	https://doi.org/10.1145/3402942.3402957
Status	Gepubliceerd - 15 sep. 2020
Evenement	15th International Conference on the Foundations of Digital Games - , Malta Duur: 15 sep. 2020 → 18 sep. 2020 Congresnummer: 15

Publicatie series

Naam	ACM International Conference Proceeding Series

Congres

Congres	15th International Conference on the Foundations of Digital Games
Verkorte titel	FDG 2020
Land/Regio	Malta
Periode	15/09/20 → 18/09/20

Toegang tot document

10.1145/3402942.3402957

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

Baier, H., & Kaisers, M. (2020). Opponent-Pruning Paranoid Search. In G. N. Yannakakis, A. Liapis, K. Penny, V. Volz, F. Khosmood, & P. Lopes (editors), FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital Games Artikel 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. redacteur / 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 (reds.), 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. reds. / 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).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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

Samenvatting

Publicatie series

Congres

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit