Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

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

Résumé :

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.

Type de document :
Article dans une revue
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-02715049
Contributeur : Okina Université d'Angers <>
Soumis le : lundi 1 juin 2020 - 19:56:19
Dernière modification le : mardi 2 juin 2020 - 04:03:49

Identifiants

Collections

Citation

Vincent Barichard, Igor Stephan. Le problème de satisfaction de contraintes quantifiées et les jeux à deux joueurs à horizon fini : le projet QuaCode. Revue des Sciences et Technologies de l'Information - Série RIA : Revue d'Intelligence Artificielle, Lavoisier, 2017, 31 (3), pp.337-365. ⟨10.3166/ria.31.337-365⟩. ⟨hal-02715049⟩

Partager

Métriques