💻 computer science

An ASP-based approach to Solving General Stochastic Two-Player Games

Cet article présente la Programmation par Ensembles de Réponses Stochastiques (SQASP) comme la première approche fondée sur la Programmation par Ensembles de Réponses (ASP) pour résoudre des jeux à deux joueurs à tours alternés en Langage de Description de Jeux Généraux (GDL) avec incertitude, démontrant sa compétitivité par rapport à la recherche avant sur les petits jeux stochastiques et son potentiel pour l'évaluation des fins de partie.

Auteurs originaux : Yifan He, Michael Thielscher

Publié 2026-05-25

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yifan He, Michael Thielscher

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez d'enseigner à un ordinateur comment jouer à un jeu de plateau. Habituellement, ces jeux sont comme les échecs : vous faites un coup, votre adversaire fait un coup, et le plateau change de manière prévisible. Mais que se passerait-il si le jeu impliquait aussi une « carte joker » ? Que se passerait-il si, après votre coup, un lancer de dé magique décidait si votre coup fonctionne, ou si un troisième joueur invisible (appelons-le « Hasard ») jetait un dé dans les engrenages ?

Ce papier porte sur l'enseignement aux ordinateurs de la résolution de ces jeux complexes et imprévisibles. Les auteurs, Yifan He et Michael Thielscher, ont construit une nouvelle boîte à outils mathématique pour déterminer la meilleure stratégie possible lorsque la chance est en jeu.

Voici la décomposition de leur approche en utilisant des analogies simples :

1. Le Problème : Le Joueur « Hasard »

Dans la théorie des jeux classique, les ordinateurs sont excellents pour calculer le coup parfait contre un adversaire intelligent. Mais lorsque vous ajoutez de l'aléatoire (comme lancer des dés ou tirer des cartes), les mathématiques deviennent désordonnées.

L'Ancienne Méthode : Les anciens programmes informatiques pouvaient gérer des jeux avec deux joueurs intelligents (comme les échecs) ou des jeux avec un joueur et un élément aléatoire (comme le Solitaire). Ils ne pouvaient pas gérer un jeu avec deux joueurs intelligents ET un élément aléatoire simultanément.
L'Objectif : Les auteurs voulaient résoudre les « Jeux Stochastiques Généraux à Deux Joueurs ». Imaginez-le comme un jeu de Morpion où, chaque fois que vous essayez de placer un X, il y a 30 % de chances que la case se transforme en O, ou 50 % de chances que le coup soit totalement bloqué.

2. Le Nouvel Outil : SQASP (Le « Plan Magique »)

Les auteurs ont inventé un nouveau langage appelé Programmation par Réponse d'Ensemble Stochastique (SQASP).

L'Analogie : Imaginez que vous êtes un architecte concevant une maison. Vous avez un plan (les règles du jeu). Dans le passé, vous ne pouviez concevoir des maisons que pour deux types spécifiques de constructeurs : l'un étant un stratège génial (l'adversaire) et l'autre un robot suivant des règles strictes.
L'Innovation : SQASP est comme un nouveau type de plan capable de décrire un chantier où vous avez un Stratège Génial, un Robot et un Joueur de Hasard travaillant tous ensemble.
- Le Génie (Joueur X) veut gagner.
- L'Adversaire (Joueur O) veut empêcher le Joueur X de gagner.
- Le Joueur de Hasard (Hasard) lance une pièce pour décider de ce qui se passe ensuite.
SQASP permet à l'ordinateur de demander : « Quelle est la plus haute probabilité possible que j'aie de gagner, en supposant que mon adversaire joue parfaitement pour m'arrêter, et que le Joueur de Hasard fasse ce qu'il veut ? »

3. Le Traducteur : Transformer les Plans en Énigme

Les ordinateurs ne parlent pas « Plan ». Ils parlent « Énigmes Logiques ».

Le Processus : Les auteurs ont construit un traducteur (un outil appelé sqasp2xssat). Il prend leur plan SQASP sophistiqué et le convertit en une immense énigme logique appelée Satisfiabilité Stochastique Étendue (XSSAT).
La Métaphore : Imaginez que SQASP est une recette complexe pour un gâteau. Le traducteur est une machine qui transforme cette recette en un immense Sudoku à plusieurs couches. Une fois l'énigme résolue, la réponse vous indique la probabilité exacte de gagner le jeu.
Le Résolveur : Ils ont utilisé un résolveur existant (SharpSSAT) pour résoudre ce Sudoku. Si le résolveur dit « Oui, cette énigme peut être résolue », cela signifie que le joueur a une stratégie gagnante. S'il calcule une chance de 67 %, c'est le meilleur résultat possible.

4. L'Astuce du « Déplacement de Quantificateurs »

Le papier a également testé une technique d'optimisation spécifique appelée Déplacement de Quantificateurs.

L'Analogie : Imaginez que vous organisez un tournoi.
- Méthode A (Référence) : Vous listez chaque coup de chaque joueur, puis vérifiez si les coups sont légaux, puis vérifiez si la partie est terminée.
- Méthode B (Déplacement) : Vous vérifiez si les coups sont légaux avant même de lister les coups. Cela semble plus rapide car vous ne perdez pas de temps à planifier des coups illégaux.
Le Résultat : Dans les jeux à deux joueurs intelligents (jeux déterministes), cette astuce de « Déplacement » offre un énorme boost de vitesse. Cependant, les auteurs ont constaté que dans les jeux avec le « Joueur de Hasard » (jeux stochastiques), cette astuce ne faisait pas beaucoup de différence.
Pourquoi ? Le résolveur qu'ils ont utilisé (SharpSSAT) est très intelligent. Il possède un « détective » intégré (appelé propagation d'unités) qui détermine les coups illégaux par lui-même, indépendamment de l'ordre dans lequel vous avez donné les instructions. Ainsi, le réordonnancement sophistiqué n'était pas nécessaire pour ce résolveur spécifique.

5. Les Résultats : Comment s'est-il comporté ?

L'équipe a testé son système sur des variantes de jeux classiques comme le Morpion, le Connect-4 et le Nim, mais avec l'ajout du joueur « Hasard ».

Performance : Leur nouvelle méthode était compétitive par rapport aux méthodes standards de « recherche avant » (qui sont comme un ordinateur jouant le jeu des millions de fois dans sa tête pour voir ce qui se passe).
La Contrainte : Cela fonctionnait très bien sur de petits plateaux (comme 3x3 ou 4x4). Cependant, lorsque le jeu devenait trop grand (comme une pile de 100 pièces dans le Nim), l'énigme logique devenait trop énorme pour que l'ordinateur puisse la résoudre dans un délai raisonnable.
La Conclusion : La méthode est excellente pour l'évaluation de la fin de partie. Si une partie est presque terminée, ce système peut dire à une IA de jeu généraliste : « Hé, si tu fais ce coup, tu as 99 % de chances de gagner », l'aidant à prendre la décision finale.

Résumé

Les auteurs ont créé une nouvelle façon de décrire mathématiquement des jeux où la chance et la stratégie entrent en collision. Ils ont transformé ces descriptions en énigmes logiques qu'un ordinateur peut résoudre pour trouver les « meilleures chances possibles » de gagner. Bien que ce ne soit pas une solution miracle pour toutes les tailles de jeux, cela prouve que nous pouvons utiliser la programmation logique pour résoudre des jeux complexes et incertains, offrant aux ordinateurs une meilleure façon de penser au futur dans un monde chaotique.

Ce qu'ils n'ont PAS affirmé :

Ils n'ont pas affirmé que cela fonctionne pour des jeux où vous ne pouvez pas voir tout le plateau (comme le Poker ou le Krieg-Morpion). Ils déclarent explicitement que leur méthode est pour des jeux où tout le monde voit tout le plateau (information parfaite).
Ils n'ont pas affirmé que cela remplacera immédiatement toutes les autres méthodes d'IA ; ils ont noté qu'il s'agit d'une alternative pour des scénarios spécifiques, en particulier les fins de partie.

Résumé technique : Une approche basée sur l'ASP pour résoudre les jeux stochastiques généraux à deux joueurs

Énoncé du problème

Les systèmes de jeu général (General Game Playing, GGP) visent à jouer à des jeux stratégiques à partir de descriptions exécutées sans connaissance préalable des règles. Le langage de description de jeux (Game Description Language, GDL) et son extension GDL-II sont les formalismes standards pour spécifier de tels jeux, GDL-II prenant en charge l'aléatoire (stochastique) et l'observabilité partielle. Bien que la programmation par ensembles de réponses (Answer Set Programming, ASP) ait été appliquée avec succès à la résolution de jeux GDL déterministes à un et deux joueurs, les cadres ASP existants ne possèdent pas la capacité d'exprimer simultanément les comportements adversariaux (minimax) et stochastiques. Par conséquent, il existe un vide dans l'utilisation de méthodes basées sur l'ASP pour résoudre des jeux GDL à deux joueurs à tours successifs impliquant de l'incertitude.

Méthodologie

Les auteurs proposent une approche novatrice pour résoudre des jeux GDL stochastiques à deux joueurs en introduisant un nouveau langage et un solveur basé sur la traduction.

1. Programmation par ensembles de réponses quantifiés stochastiques (SQASP)

Pour combler le fossé entre l'ASP et la résolution de jeux stochastiques, l'article introduit le SQASP, un langage qui étend le QASP (Quantified ASP) avec des quantificateurs de hasard.

Syntaxe : Un programme SQASP prend la forme $Q_1.x_1 \dots Q_n.x_n \ P$ , où $P$ est un programme logique normal et les quantificateurs $Q_i$ peuvent être existentiels ( $\exists$ ), universels ( $\forall$ ) ou de hasard ( $\mathcal{R}_{p}$ ).
Sémantique : La probabilité maximale de satisfaction d'un programme SQASP est définie de manière récursive. Le quantificateur de hasard $\mathcal{R}_{p}$ attribue une probabilité $p$ à ce qu'une variable soit vraie, en calculant la valeur attendue basée sur les probabilités des sous-formules.
Traduction : Les auteurs implémentent un outil, sqasp2xssat, qui traduit les programmes SQASP en formules de Satisfiabilité Stochastique Étendue (XSSAT). XSSAT étend les formules booléennes quantifiées (QBF) avec des quantificateurs de hasard. La traduction exploite des outils existants (comme lp2sat) pour convertir le programme logique $P$ en une formule CNF $\psi$ dont les modèles correspondent aux modèles stables de $P$ .

2. Encodage des jeux GDL en SQASP

La contribution centrale est la construction d'un programme SQASP $\Psi$ tel que sa probabilité maximale de satisfaction soit égale à la probabilité maximale de victoire d'un joueur $x$ en $n$ étapes ( $P_x^w(S_0, n)$ ). L'encodage se déroule en deux phases principales :

Référence coopérative : Tout d'abord, un programme logique $P_c$ est construit en supposant que tous les joueurs (y compris l'adversaire $o$ et le joueur aléatoire $r$ ) coopèrent pour atteindre un état terminal où $x$ gagne. Cela garantit une progression valide du jeu, une terminaison en $n$ étapes et la réalisation de l'état objectif.
Modélisation adversariale et stochastique : Le programme est ensuite étendu pour capturer les comportements spécifiques de l'adversaire et de l'environnement :
- Joueur adversaire ( $o$ ) : Modélisé à l'aide d'une quantification universelle ( $\forall$ ) sur les variables de décision (dec_o). Cela force le solveur à considérer le scénario le pire où l'adversaire minimise la probabilité de victoire de $x$ . L'encodage utilise une représentation logarithmique des actions pour réduire le nombre de règles.
- Joueur stochastique ( $r$ ) : Modélisé à l'aide de quantificateurs de hasard ( $\mathcal{R}_{1/i}$ ). L'encodage garantit que si le jeu n'est pas terminé, le joueur aléatoire sélectionne exactement une action légale de manière uniforme parmi les coups légaux disponibles. Cela est réalisé en comptant les actions légales et en appliquant des contraintes de probabilité aux variables de décision (dec_r).

3. Stratégies de quantification

L'article examine deux stratégies de quantification pour la formule XSSAT résultante :

Méthode de référence ( $Q_b$ ) : Tous les atomes non-choix (par exemple legal, terminal) sont placés dans le bloc existentiel le plus interne, suivant un ordre temporel strict des atomes de choix.
Méthode basée sur les dépendances ( $Q_d$ ) : Inspirée des techniques pour les jeux déterministes, cette méthode déplace les atomes non-choix pour qu'ils apparaissent le plus tôt possible dans le préfixe de quantification, immédiatement après les atomes de choix dont ils dépendent. Cela vise à réduire l'espace de recherche en fixant des valeurs comme legal avant de brancher sur does.

Contributions clés

Premier solveur basé sur l'ASP pour GDL stochastique : L'article présente la première approche pour résoudre des jeux GDL à deux joueurs, stochastiques et à tours successifs en utilisant l'ASP.
Langage SQASP : L'introduction de la Programmation par ensembles de réponses quantifiés stochastiques, qui unifie le raisonnement adversarial et stochastique au sein d'un cadre de programmation logique.
Solveur basé sur la traduction : Le développement de sqasp2xssat, qui convertit les programmes SQASP en formules XSSAT, permettant l'utilisation de solveurs XSSAT existants (notamment SharpSSAT) pour la résolution de jeux.
Correction théorique : Les auteurs fournissent des preuves formelles (Théorèmes 2 et 3) établissant l'équivalence entre la probabilité maximale de victoire dans le jeu GDL et la probabilité maximale de satisfaction de la formule SQASP/XSSAT générée.

Résultats expérimentaux

Les auteurs ont évalué leur approche sur des variations stochastiques de Morpion, Connect-4 et Nim, comparant la méthode basée sur SQASP (utilisant les deux quantifications $Q_b$ et $Q_d$ ) à un solveur Minimax Espéré (EMM) par recherche avant.

Performance : L'approche basée sur l'ASP est compétitive avec la recherche avant sur de petits jeux stochastiques. Dans de nombreux cas (par exemple, Morpion, Connect-3), le solveur ASP calcule des probabilités de victoire comparables à l'EMM, souvent dans des délais similaires.
Déplacement de quantificateurs : De manière surprenante, la quantification basée sur les dépendances ( $Q_d$ ) n'a pas produit d'améliorations de performance significatives par rapport à la référence ( $Q_b$ ) lors de l'utilisation du solveur SharpSSAT. Les auteurs attribuent cela au mécanisme interne de propagation d'unités de SharpSSAT, qui peut déduire les valeurs des atomes (comme legal) indépendamment de l'ordre des quantificateurs, atténuant efficacement le besoin d'un déplacement explicite.
Limites de l'évolutivité : L'approche peine avec des espaces d'états plus grands, tels que le Nim stochastique avec de grandes tailles de tas. Les formules XSSAT résultantes deviennent trop volumineuses (plus d'un million de clauses) pour être traitées efficacement par les solveurs actuels, alors que l'EMM s'adapte bien grâce à la programmation dynamique et aux tables de transposition.

Importance et affirmations

L'article affirme que l'approche basée sur l'ASP proposée offre une alternative viable pour l'évaluation de fins de partie dans les systèmes de jeu général. En étendant l'application réussie de l'ASP aux jeux déterministes vers le domaine stochastique, ce travail démontre que la programmation logique peut gérer efficacement l'incertitude et le raisonnement adversarial.

Les auteurs notent modestement que, bien que l'approche ne domine pas la recherche avant dans tous les cas (particulièrement pour les jeux avec des espaces d'états très grands ou des structures spécifiques comme Nim), elle généralise avec succès les résultats précédents pour les jeux déterministes vers les jeux stochastiques. Ils identifient l'extension à l'observabilité partielle (par exemple, Poker, Krieg-Morpion) comme une direction critique pour les travaux futurs, reconnaissant que la méthode actuelle est limitée aux jeux à information parfaite.