Le problème de satisfaction de contraintes quantifiées et les jeux à deux joueurs à horizon fini : le projet QuaCode

TitreLe problème de satisfaction de contraintes quantifiées et les jeux à deux joueurs à horizon fini : le projet QuaCode
Type de publicationArticle de revue
AuteurBarichard, Vincent , Stéphan, Igor
PaysFrance
EditeurLavoisier
TypeArticle scientifique dans une revue à comité de lecture
Année2017
LangueFrançais
Date2017
Numéro3
Pagination337-365
Volume31
Titre de la revueRevue d'Intelligence Artificielle
ISSN0992-499X
Mots-clésjeu à deux joueurs à horizon fini, problème de satisfaction de contraintes quantifiées, QCSP, quantified constraint satisfaction problem, finite two-players game
Résumé en anglais

Quantified Constraint Satisfaction Problems (QCSP) are a generalization of Constraint Satisfaction Problems (CSP) in which variables may be quantified existentially and universally. QCSP offers a natural framework to express PSPACE problems as finite two-player games with perfect information or planing under uncertainty. We present how QCSP may be used to model two-player games on three classical games : Nim game, MatrixGame and Connect Four. State-of-the-art QCSP solvers have an important drawback: they explore much larger combinatorial space than the natural search space of the original problem since they are unable to recognize that some sub-problems are necessarily true. We propose a very simple and elegant solution to use efficiently QCSP to design finite two-player games. Our QCSP solver built over GeCode, a CSP library, obtained very good results compared to state-of-the-art QCSP solvers.

Résumé en français

Le problème de satisfaction de contraintes quantifiées (QCSP) est une généralisation du problème de satisfaction de contraintes (CSP) pour lequel les variables peuvent être quantifiées aussi bien existentiellement qu’universellement. Le concept de QCSP offre un cadre naturel pour traiter des problèmes PSPACE comme par exemple les jeux à deux joueurs à horizon fini et information complète ou la planification sous incertitude. Nous présentons à travers trois exemples comment les QCSP peuvent être utilisés pour modéliser des jeux à deux joueurs : le Jeu de Nim, le MatrixGame et le Puissance Quatre. Les solveurs QCSP de l’état de l’art ont un défaut majeur : ils explorent un espace combinatoire plus important que l’espace de recherche naturel du problème original car ils sont inaptes à reconnaître que certains sous-problèmes sont nécessairement vrais. Nous proposons dans le cadre des jeux à deux joueurs à horizon fini une solution efficace pour utiliser les solveurs QCSP et une réponse aussi simple qu’élégante à ce parcours superflu. Nous proposons un solveur QCSP construit au-dessus de la librairie CSP GeCode que nous comparons aux solveurs de l’état de l’art.

URL de la noticehttp://okina.univ-angers.fr/publications/ua18400
DOI10.3166/ria.31.337-365
Lien vers le document

https://ria.revuesonline.com/article.jsp?articleId=38164