Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Posté par Redbran le Lundi 07/11/2016 à 12:00
Intelligence artificielle et jeux

Illustration: WoodStock
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 (L'intelligence artificielle ou informatique cognitive est la « recherche de moyens susceptibles de doter les systèmes informatiques de capacités intellectuelles comparables à celles des êtres...) dédiée, contre Lee Sedol, le champion du jeu de Go. Pour gagner, AlphaGo combine apprentissage (L’apprentissage est l'acquisition de savoir-faire, c'est-à-dire le processus d’acquisition de pratiques, de connaissances, compétences, d'attitudes ou de valeurs...) par réseaux de neurones profonds et recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par extension...) 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 (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le traitement automatique de l'information par des machines telles que...) 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 (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) un panel (Le panel est un groupe de personnes interrogées régulièrement sur leurs opinions ou leurs attitudes. Les personnes peuvent participer aux...) de jeux dont les règles ne sont pas connues à l’avance. Ces règles sont décrites dans un formalisme logique (La logique (du grec logikê, dérivé de logos (λόγος), terme inventé par Xénocrate signifiant à la...), 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 (En géométrie euclidienne, un cube est un prisme dont toutes les faces sont carrées. Les cubes figurent parmi les solides les plus remarquables de l'espace. C'est un des cinq solides de Platon, le seul ayant exactement 6...), Échecs, Dames, Puissance (Le mot puissance est employé dans plusieurs domaines avec une signification particulière :) 4… Récemment une seconde ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est...) 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 (Dans le langage ordinaire, le mot hasard est utilisé pour exprimer un manque efficient, sinon de causes, au moins d'une reconnaissance de cause à effet d'un événement.) (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 (La programmation logique est une forme de programmation qui définit les applications à l'aide d'un ensemble de faits élémentaires les concernant et de règles de logique leur associant des...), un type de programmation (La programmation dans le domaine informatique est l'ensemble des activités qui permettent l'écriture des programmes informatiques. C'est une...) 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 (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout »,...) 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 (En botanique, le fruit est l'organe végétal protégeant la graine. Caractéristique des Angiospermes, il succède à la fleur par...) 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 (L'automatique fait partie des sciences de l'ingénieur. Cette discipline traite de la modélisation, de l'analyse, de la commande et, de la régulation des systèmes dynamiques. Elle a pour fondements théoriques...) au travers d’échantillonnage par bandit stochastique (UCB). À la différence des intelligences artificielles dédiées, ce logiciel (En informatique, un logiciel est un ensemble d'informations relatives à des traitements effectués automatiquement par un appareil informatique. Y sont inclus les...) ne possède aucune simulation ou heuristique (L'heuristique (du grec heuriskêin, « trouver ») est l'utilisation de règles empiriques :) 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 (Le jour ou la journée est l'intervalle qui sépare le lever du coucher du Soleil ; c'est la période entre deux nuits, pendant laquelle les rayons...) opposant 10 programmes joueurs conçus tout autour (Autour est le nom que la nomenclature aviaire en langue française (mise à jour) donne à 31 espèces d'oiseaux qui, soit appartiennent au genre Accipiter, soit constituent les 5 genres Erythrotriorchis, Kaupifalco, Megatriorchis,...) 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 (L’observation est l’action de suivi attentif des phénomènes, sans volonté de les modifier, à l’aide de moyens...) partielle de l’état du jeu que possède l’ensemble des joueurs.

Source:
CNRS-INS2I
Commentez et débattez de cette actualité sur notre forum Techno-Science.net. Vous pouvez également partager cette actualité sur Facebook, Twitter et les autres réseaux sociaux.
Icone partage sur Facebook Icone partage sur Twitter Partager sur Messenger Icone partage sur Delicious Icone partage sur Myspace Flux RSS