Résolution de SCSP avec borne de confiance pour les jeux de stratégie

Cet article examine un fragment du problème de satisfaction de contraintes stochastiques, représentant les jeux à informations complètes et incertaines. Nous proposons un algorithme de résolution permettant de trouver des stratégies gagnantes pour cette classe de jeux. L'intérêt de ce travail est de permettre la résolution efficace d'un SCSP initial par la résolution successive d'une séquence de « micro-SCSP » à chaque étape du jeu. L'algorithme MAC, proposé pour résoudre les premiers micro-SCSP de la séquence, est couplé à une heuristique de type UCB utilisée pour estimer les valeurs des stratégies sur toute la séquence. Notre approche, MAC-UCB, est validée par une série d'expérimentations sur un ensemble de jeux très divers, décrits en GDL (Game Description Language), et comparée à l'algorithme UCT, qui est la référence actuelle pour cette classe de jeux.