Un robot imbattable à Puissance 4 ?

Qui pourrait croire que jouer avec des Legos^TM peut faire partie d'un projet de master en sciences mathématiques ? Il semble cependant que ce soit le cas pour plusieurs étudiants ! Sabrina Dassonville, Vinciane De Waele, Florine Frist et David Sbabo ont partagé cette expérience. Demandons quelques informations à ces quatre étudiants...

Q : Dans quel contexte vous a-t-on proposé de « jouer » avec des Legos à l'université ?

R : Dans le cadre de notre première Master en Sciences Mathématiques, finalité Informatique, nous devions réaliser un projet. Celui-ci pouvait s'effectuer dans la discipline de notre choix, pour autant que celle-ci ait un rapport avec les mathématiques et/ou l'informatique.

Nous voulions réaliser ce projet en groupe. Un projet de robotique avait été conçu par d'autres étudiants deux années auparavant : un robot capable de sortir seul d'un labyrinthe et un autre capable de résoudre un Rubik's cube. L'idée de réaliser un projet similaire nous motivait. Nous avons brièvement discuté avec ces étudiants, ce qui nous a confortés dans l'idée de construire un nouveau robot malgré leur mise en garde sur la quantité de travail à fournir.

Nous avons donc demandé à Monsieur Troestler, le professeur ayant dirigé ce projet, d'en réaliser un à notre tour. Il nous a alors proposé de créer un robot jouant à Puissance 4 contre un joueur humain.

Q : Le travail était-il conséquent ?

R : Oui, nous devions réaliser à la fois la construction du robot, le code pilotant les servomoteurs, et l'implémentation de l'intelligence artificielle. Nous avons commencé le projet dans le courant du mois d'octobre. Nous avons travaillé progressivement : avant décembre nous y consacrions une dizaine d'heures par semaine pour en arriver à occuper toutes nos journées (voire nos nuits... ;-)).

Q : Pouvez-vous nous parler de cette construction ?

R : Nous avions à notre disposition des boîtes de Lego Mindstorm et un jeu de Puissance 4 standard. À partir de cela, nous devions tout imaginer : trouver un moyen d'ajouter une pièce dans la grille et détecter les pièces insérées par l'adversaire. Afin d'ajouter une nouvelle pièce, nous avons créé une pince se déplaçant au-dessus du jeu dont le but est de déposer cette dernière dans la colonne voulue. Pour connaître le coup de l'adversaire, nous déplaçons un capteur de couleur en face des cases de la grille jusqu'à ce qu'une nouvelle pièce soit trouvée.

La version finale ne s'est pas faite du premier coup mais après de multiples modifications. Nous avons en effet rencontré de nombreuses difficultés lors de la construction, notamment dues à la précision des moteurs Lego, ce ne sont quand même que des jouets !

Q : Pouvez-vous nous parler de la programmation du robot ?

R : Les déplacements du robot sont programmés de manière événementielle dans le langage OCaml. Ceci signifie qu'une action est lancée lorsqu'un événement s'est produit. Par exemple, la pince se déplace latéralement jusqu'à arriver au-dessus de la colonne voulue et c'est seulement à ce moment là que la pince doit s'ouvrir pour laisser tomber la pièce, etc.

Au niveau de la programmation de l'intelligence artificielle, une première approche est d'explorer tous les coups possibles que chacun des deux joueurs peut réaliser alternativement. Cependant nous avons vite remarqué que le temps nécessaire à cette exploration serait beaucoup trop élevé. Ce n'était donc pas réalisable. Après quelques recherches, nous avons trouvé le mémoire de Victor Allis qui décrit l'algorithme utilisé par notre robot. Celui-ci comporte plusieurs ingrédients.

Le premier consiste à regarder, à l'aide de règles simples, si nous pouvons gagner ou éviter à l'adversaire de le faire. Par exemple, si ce dernier possède trois pions alignés, nous devons l'empêcher d'y ajouter un quatrième. Cependant ces règles, trop simples, ne permettent pas d'avoir une vision à long terme du jeu.

Pour développer une stratégie sur le long terme, on utilise, entre autres, une variante de l'algorithme de minmax. Afin que le robot joue endéans une seconde, cet algorithme s'appuie sur une heuristique qui donne un score évaluant la force ou la faiblesse d'une position du jeu.

Q : Votre robot est-il imbattable ?

R : Oui, si vous le laissez commencer ! Cependant si vous choisissez de commencer le jeu, vous pouvez éventuellement gagner… du moins si vous ne commettez aucune erreur.

En fait, Victor Allis a prouvé grâce à son algorithme que le joueur débutant la partie a une stratégie gagnante, c'est-à-dire que ce dernier possède une série de règles qui, s'il les applique, lui assurent la victoire quelle que soit la manière dont joue l'adversaire. Par exemple, une de ces règles est de jouer le premier coup au milieu. Néanmoins, vu le nombre très important de configurations du jeu (de l'ordre de 7×10¹³), il est impossible de stocker en mémoire les meilleurs coups pour chaque position. Cette situation explique l'utilisation des algorithmes décrits au point précédent. De plus ceux-ci permettent au robot de profiter de toute erreur commise par son adversaire, même si ce dernier a commencé la partie.

Q : Où et quand avez-vous présenté votre projet ?

R : Lors de la « Journée Math Sciences » organisée à l'UMONS, le 25 mars, nous avons présenté notre projet à des classes du secondaire. Les élèves se sont tout de suite pris au jeu et essayaient à tout prix de battre notre robot, sans succès la plupart du temps ! Nous l'avons également présenté le week-end suivant à l'hôtel de ville. Notre robot a eu beaucoup de succès auprès des enfants mais aussi des adultes qui ne voulaient pas accepter de perdre contre une « machine ». Ils étaient impressionnés par notre travail, mais très déçus de ne pas pouvoir gagner ! (rires)

Q : Comment avez-vous vécu cette expérience ?

R : Cela n'a pas toujours été facile mais nous sommes fiers du résultat final et contents de l'avoir fait. Ce projet est différent des autres que nous avions l'habitude de réaliser. En effet, celui-ci était concret, ludique et imaginatif.