Intelligence artificielle et jeux

Une intelligence artificielle dirigée par les contraintes championne de General Game Playing.

Ces derniers mois, l'intelligence artificielle a été mise en avant, notamment par la victoire d'AlphaGo, une intelligence artificielle dédiée, contre Lee Sedol, le champion du jeu de Go. Pour gagner, AlphaGo combine apprentissage par réseaux de neurones profonds et recherche arborescente Monte Carlo. Mais d'autres pistes sont explorées en intelligence artificielle, notamment l'intelligence artificielle généraliste. Un des tests de cette méthode est un concours de General Game Playing, qui vient d'être remporté par un programme-joueur du Centre de Recherche en Informatique de Lens (CRIL -CNRS/Université de l'Artois), appelé WoodStock.

Depuis 2005, l'Université de Stanford a initié le General Game Playing (GGP), avec pour objectif de créer des intelligences artificielles capables de jouer efficacement à tout un panel de jeux dont les règles ne sont pas connues à l'avance. Ces règles sont décrites dans un formalisme logique, appelé Game Description Language (GDL). Les jeux à informations parfaites, où l'on connaît sa position, celles des autres joueurs, et toutes les actions du jeu, peuvent être pour la plupart représentés: Sudoku, Rubik's Cube, Échecs, Dames, Puissance 4... Récemment une seconde version, dénommée GDLII, permet d'englober les jeux à informations incomplètes, où les joueurs ne connaissent pas totalement l'état du jeu et les actions jouées par leurs adversaires (comme dans les jeux de cartes), et ceux faisant intervenir le hasard (représenté par des dés ou des pièces).

Au fil des années, ce cadre a permis la naissance de nombreuses techniques de résolutions généralistes. Une des pistes est la programmation logique, un type de programmation qui établit des règles logiques qui se basent sur des faits. Il est également possible d'employer des constructions automatiques de fonctions d'évaluations, appelées heuristiques, ou encore ce qui fait aujourd'hui référence: les méthodes de type Monte Carlo. Il s'agit ici d'un ensemble de fonctions d'échantillonnage et de simulation qui permettent de fournir une valeur pour chaque état du jeu, afin d'estimer si cet état est favorable ou non pour la poursuite du jeu. Chacune de ces méthodes a donné naissance à un ou plusieurs programmes-joueurs génériques se confrontant les uns aux autres au travers de compétitions internationales organisées par Stanford. Chaque année, les programmes-joueurs s'affrontent sur des jeux différents de plus en plus complexes, afin de déterminer les meilleures techniques de résolutions. Pour la première fois cette année, WoodStock, le programme du CRIL basé sur la programmation par contraintes, était parmi les participants et a remporté la compétition.

WoodStock est le fruit du travail de thèse d'Éric Piette, supervisé par Frédéric Koriche, Sylvain Lagrue et Sébastien Tabary. Sa particularité est qu'il propose une approche utilisant le problème générique de satisfaction de contraintes stochastiques (SCSP). Dans ce cadre, un jeu est représenté par un problème composé de contraintes représentatives des règles et de l'évolution de l'état du jeu. L'aspect stochastique permet de représenter le hasard et l'incertitude présents dans certains jeux au fil de la résolution du problème.

En pratique, dès la réception des règles du nouveau jeu, WoodStock commence par le traduire pour satisfaire des contraintes stochastiques équivalentes, décomposables en sous-réseaux, chacune représentative d'un état du jeu. Une fois généré, il met en pratique MACUCB, un algorithme utilisant un raisonnement par propagation (MAC), permettant de “résoudre” chaque sous-réseau (en supprimant très rapidement les solutions inutiles) combiné à une technique d'apprentissage automatique au travers d'échantillonnage par bandit stochastique (UCB). À la différence des intelligences artificielles dédiées, ce logiciel ne possède aucune simulation ou heuristique spécialisée lui permettant de s'orienter vers une stratégie caractéristique d'un jeu en particulier.

La compétition 2016 s'est déroulée sur deux jours opposant 10 programmes joueurs conçus tout autour de la planète. Woodstock s'est distingué dès le début des parties par la qualité de ses réponses lui permettant d'être le seul à déterminer une solution pour l'ensemble des puzzles et d'être très compétitif face aux autres programmes-joueurs. Il a surpassé le champion précédent, et a même été victorieux contre un joueur humain de l'Université de Stanford sur un jeu dénommé Breakthrough.

Mais le General Game Playing ne se limite pas uniquement au cadre ludique. Il permet également la résolution de problèmes de décisions séquentielles, pour définir une succession de tâches à réaliser dans un certain ordre, ou pour les problèmes multiagents. Dans ce cas où plusieurs "agents" sont nécessaires pour la résolution d'un problème, chaque agent va être représenté par un joueur, et la stratégie commune entre les agents peut ainsi être définie. Un exemple d'application envisagée est la robotique où l'intelligence collective peut être représentée par un jeu et leurs comportements par des programmes-joueurs.

Pour la suite, des premières expérimentations ont été menées et semblent encourageantes pour ouvrir WoodStock à la résolution de jeux à informations imparfaites, quand la grande majorité de la recherche en intelligence artificielle dédiée ou généraliste se restreint aujourd'hui aux jeux à informations parfaites, moins complexes à gérer. En effet, WoodStock est réalisé au travers d'une représentation stochastique (basée sur des méthodes aléatoires) lui permettant également de jouer à de nombreux jeux à informations imparfaites. La représentation des connaissances utilisée permet également de modéliser l'action du hasard et l'observation partielle de l'état du jeu que possède l'ensemble des joueurs.

Source: CNRS-INS2I