Thumbnail - No thumbnail

Generalisation of Alpha-Beta Search for AND-OR Graphs With Partially Ordered Values

Li, Junkang; Zanuttini, Bruno; Cazenave, Tristan; Ventos, Véronique (2022), Generalisation of Alpha-Beta Search for AND-OR Graphs With Partially Ordered Values, in Luc De Raedt, Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI), AAAI Press / IJCAI : Palo Alto (USA), p. 4769-4775. 10.24963/ijcai.2022/661

Type
Communication / Conférence
External document link
https://hal.science/hal-03656224
Date
2022
Conference title
IJCAI-ECAI 2022, the 31st International Joint Conference on Artificial Intelligence
Conference date
2022-07
Conference city
Vienne
Conference country
Austria
Book title
Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI)
Book author
Luc De Raedt
Publisher
AAAI Press / IJCAI
Published in
Palo Alto (USA)
ISBN
978-1-956792-00-3
Number of pages
5959
Pages
4769-4775
Publication identifier
Metadata
Show full item record
Author(s)
Li, Junkang
Groupe de Recherche en Informatique, Image et Instrumentation de Caen [GREYC]
Zanuttini, Bruno
Groupe de Recherche en Informatique, Image et Instrumentation de Caen [GREYC]
Cazenave, Tristan
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Ventos, Véronique
NukkAI [Paris]
Abstract (EN)
We define a new setting related to the evaluation of AND-OR directed acyclic graphs with partially ordered values. Such graphs arise naturally when solving games with incomplete information (e.g. most card games such as Bridge) or games with multiple criteria. In particular, this setting generalises standard AND-OR graph evaluation and computation of optimal strategies in games with complete information. Under this setting, we propose a new algorithm which uses both alpha-beta pruning and cached values. In this paper, we present our algorithm, prove its correctness, and give experimental results on a card game with incomplete information.
Subjects / Keywords
Computer games; Game playing