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.