Ary et le General Game Playing

Je suis l'auteur principal d'un programme de General Game Playing nommé Ary (conçu en collaboration avec Tristan Cazenave, du Lamsade, université de Paris Dauphine).

Télécharger

On peut télécharger toute l'infrastructure d'Ary avec un programme subplayer, qui joue des parties aléatoires, utilisé dans un des modes de parallélisation d'Ary, dans le fichier subplayer-1.0.tar.gz.

Je comptais distribuer aussi les sources du programme principal, mais j'y ai découvert pendant la compétition 2011 une erreur de conception majeure que je souhaite corriger avant de les publier. J'espère achever ce travail cet automne.

Publications

Rapport sur la compétition de General Game Playing de 2013 Première partie : déroulement de la compétition, Jean Méhat, Rapport Technique, LIASD, Université de Paris 8, novembre 2013. post2013-part1.pdf

"Online Adjustment of Tree Search for GGP", Jean Méhat et Jean-Noël Vittaut. GIGA 2013, IJCAI 2013, Beijin, August 2013, mehat-adaptrave.pdf

"Tree Parallelization of Ary on a Cluster", Jean Méhat, Tristan Cazenave. GIGA 2011, IJCAI 2011, Barcelona, July 2011. treeParallelGIGA2011.pdf, slides.

"A Parallel General Game Player", Jean Méhat, Tristan Cazenave. KI journal, Vol. 25 (1), pp. 43-47, March 2011. rootparallelggp.pdf

"Combining UCT and Nested Monte-Carlo Search for Single-Player General Game Playing", Jean Méhat, Tristan Cazenave. IEEE Transactions on Computational Intelligence and AI in Games, Vol. 2 (4), pp. 271-277, 2010. ggp2009.pdf

"UCD : Upper Confidence bound for rooted Directed acyclic graphs", Abdallah Saffidine, Tristan Cazenave, Jean Méhat. TAAI IWCG, Taiwan, November 2010. taai2010-final.pdf

"An Account of a Participation to the 2007 General Game Playing Competition", J. Méhat, T. Cazenave. 2008. ggp2008-2.pdf

Le General Game Playing

L'idée est de faire jouer des programmes à des jeux dont ils viennent de découvrir la règle. Le principal intérêt est que cela oblige soit à trouver des méthodes de recherches qui fonctionnent bien dans tous les jeux, soit à reconnaître à partir des règles, quelles méthodes employer pour obtenir de bons résultats.

Une bonne source d'information sur le sujet est le serveur de Stanford, d'où provient la définition du langage employé pour décrire les règles du jeu et qui organise une compétition annuelle. On le trouve ici : http://games.stanford.edu

On peut aussi trouver de nombreuses définitions de jeux et voir des programmes jouer sur le serveur de Dresde http://euklid.inf.tu-dresden.de:8180/ggpserver/

Mon programme Ary

Mon programme Ary est écrit principalement en C ; il utilise (assez mal) un interprète Prolog pour interpréter les règles du jeu. Le source n'est pas complètement disponible, mais on peut trouver l'infrastructure dans le subplayer utilisé pour la parallélisation qu'on trouve ici subplayer-1.0.tar.gz.

Résultats en compétition

En 2005, le tournoi a été remporté par ClunePlayer, le programme de Jim Clune.

En 2006, il a été remporté par FluxPlayer, le programme de Stephan Schiffel et de Michael Thielcher, de l'université de Dresde.

En 2007, mon programme Ary a participé pour la première fois. Il est sorti troisième des qualifications qui se sont déroulées à travers Internet pendant tout le mois de juin. Je n'avais pas compris que la phase finale se jouerait pendant les journées qui précédaient la conférence plénière AAAI, et je suis arrivé à Vancouver alors que la compétition était terminée (il y avait au moins un autre compétiteur dans la même situation, mais il a réussi à participer à la finale à travers Internet).

Cette année là a marqué l'entrée des programmes fondés sur des méthodes de Monte-Carlo : le vainqueur de la compétition, CadiaPlayer de l'université de Reykjavik, était lui aussi construit autour de l'utilisation d'UCT.

En 2008, Ary a perdu en demie-finale contre ClunePlayer. À ceux qui s'intéressent aux excuses douteuses, je peux expliquer que ma gestion des débordements de la mémoire était défaillante : pour éviter l'utilisation du swap, qui conduisait à des timeouts, le programme cessait de créer des noeuds lorsque l'espace libre devenait trop petit. Dans une situation analysée comme gagnante par les deux programmes, Ary a cessé de créer des noeuds pour éviter de saturer la mémoire et a joué deux mauvais coups d'affilée qui ont été suffisant pour renverser la situation. La finale a été remportée de nouveau par CadiaPlayer, de l'université de Reykjavik.

En 2009, Ary a remporté la compétition et est devenu champion du monde de General Game Playing.

En 2010, Ary est de nouveau devenu champion du monde en remportant la finale face à MaLigne de l'université d'Alberta.

En 2011, Ary a perdu son titre après deux défaites face à TurboTurtle de Sam Schreiber, un chercheur indépendant, qui a remporté le tournoi face à CadiaPlayer en finale. L'une des défaites était due à un problème d'infrastructure sans intérêt. L'autre défaite a été concédée aux checkers en 60 coups, avec la partie adjugée à celui qui dispose du plus de matériel à ce moment. On peut trouver le log du match ici : ary-turbo-checkers.txt.