Generalisation of alpha-beta search for AND-OR graphs with partially ordered values
Li, Junkang; Cazenave, Tristan; Zanuttini, Bruno; Ventos, Veronique (2022), Generalisation of alpha-beta search for AND-OR graphs with partially ordered values, 16es Journées d'Intelligence Artificielle Fondamentale (JIAF 2022), Association française pour l'Intelligence Artificielle (AFIA), p. 101-111
View/ Open
Type
Communication / ConférenceDate
2022Conference title
Journées d’Intelligence Artificielle Fondamentale (JIAF)Conference date
2022-06Conference city
Saint-EtienneConference country
FranceBook title
16es Journées d'Intelligence Artificielle Fondamentale (JIAF 2022)Publisher
Association française pour l'Intelligence Artificielle (AFIA)
Number of pages
147Pages
101-111
Metadata
Show full item recordAuthor(s)
Li, JunkangGroupe 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]
Zanuttini, Bruno
Groupe de Recherche en Informatique, Image et Instrumentation de Caen [GREYC]
Ventos, Veronique
Abstract (FR)
Nous proposons un cadre pour l'évaluation de graphes ET-OU (orientés, acycliques) portant des valeurs partiellement ordonnées. De tels graphes apparaissent naturellement dans la résolution de jeux à information incomplète (par exemple, la plupart des jeux de cartes, comme le bridge) ou multicritères. En particulier, notre cadre généralise l'évaluation standard de graphes ET-OU et le calcul de stratégies optimales pour les jeux à information complète. Dans ce cadre, nous proposons un nouvel algorithme, qui utilise l'élagage alpha-beta et un cache des valeurs déjà calculées. Cet article présente l'algorithme, démontre sa correction, et fournit des résultats expérimentaux sur des jeux aléatoires et sur un jeu de cartes à information incomplète.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 random games and on a card game with incomplete information.Subjects / Keywords
Intelligence artificielleRelated items
Showing items related by title and author.
-
Méhat, Jean; Cazenave, Tristan (2010) Article accepté pour publication ou publié
-
Saffidine, Abdallah; Cazenave, Tristan (2012) Communication / Conférence
-
Arib, Souhila; Aknine, Souhila; Cazenave, Tristan (2015) Communication / Conférence
-
Cazenave, Tristan; Jouandeau, Nicolas; Saffidine, Abdallah (2012) Communication / Conférence
-
Zanuttini, Bruno; Lang, Jérôme; Saffidine, Abdallah; Schwarzentruber, François (2019) Article accepté pour publication ou publié