Authors:
Frédéric Koriche, Sylvain Lagrue, Eric Piette, Sébastien Tabary

Venue:
Journées Francophones de Programmation par Contraintes (JFPC), 2015

Topics:
General Game Playing, stochastic constraints, Monte Carlo methods, decision making

Links: PDF

Cet article examine un fragment du problème de satisfaction de contraintes stochastiques représentant les jeux à information complète et incertaine.

Nous proposons un algorithme de résolution permettant de trouver des stratégies gagnantes pour cette classe de jeux. L’approche repose sur la décomposition du problème en une séquence de micro-SCSP, résolus successivement.

L’algorithme proposé, MAC-UCB, combine la méthode MAC (Maintaining Arc Consistency) pour la résolution de contraintes et l’algorithme UCB (Upper Confidence Bound) pour l’exploration stochastique. Cette combinaison permet d’estimer efficacement la valeur des stratégies et d’améliorer les performances par rapport à des approches classiques telles que UCT.

Koriche, F., Lagrue, S., Piette, E., Tabary, S. (2015). Résolution de SCSP avec borne de confiance pour les jeux de stratégie. In Actes des Journées Francophones de Programmation par Contraintes (JFPC).

@inproceedings{koriche2015jfpc,
  author    = {Koriche, Frédéric and Lagrue, Sylvain and Piette, Eric and Tabary, Sébastien},
  title     = {Résolution de SCSP avec borne de confiance pour les jeux de stratégie},
  booktitle = {Journées Francophones de Programmation par Contraintes (JFPC)},
  year      = {2015}
}