Jouer au jeu des allumettes contre une machine !
I-Présentation
Objectif
Le jeu des allumettes ou jeu de NIM. Ce jeu se joue à deux joueurs. Ici, on dispose 8 bâtonnets sur la table, chaque joueur à son tour ramasse 1 ou 2 bâtonnets. Celui qui prend le dernier a gagné.
Il existe une stratégie gagnante, une méthode, un « algorithme » qui permet de gagner à tous les coups, si l’on est le joueur qui commence. Cette stratégie n’est pas difficile a deviner. En expérimentant un peu on comprend vite qu’il y a des « positions perdantes » si au moment de jouer, on se retrouve avec 3 ou 6 bâtonnets, c’est perdu … sauf si l’adversaire joue mal. La stratégie consiste donc à laisser à l’adversaire 3 ou 6 bâtonnets.
Comment jouer contre la machine? Avant de commencer, on met dans chaque urne, le même nombre de boules rouges et de boules bleus, généralement deux de chaque. On est fairplay, on laisse la machine commencer, pour lui laisser toutes ses chances face à un joueur averti (qui connait la stratégie).
Lorsque c’est au tour de la machine de jouer, on compte le nombre de bâtonnets restants et on pioche une boule dans l’urne correspondant à ce nombre:
- si la boule est rouge, on retire deux bâtonnets
- si la boule est bleue, on en retire un seul
Attention, on ne remet pas la boule dans l’urne, on la pose devant. À la fin de la partie,
- si la machine a perdu, on enlève toutes les boules qui ont été tirées
- si la machine a gagné, dans chaque urne ou une boule rouge a été tirée, on remet deux boules rouges. Pareil pour les bleus.
Lorsqu’une urne se vide, on la recharge avec deux boules de chaque couleur comme au début.
Au fil des parties, la machine va gagner de plus en plus souvent.
En augmentant la probabilité de tirer une ou l’autre boule, on « apprend » à la machine à jouer de mieux en mieux.
Avec cette activité, nous proposons de soulever le capot pour mieux comprendre les bases d’une technique classique d’apprentissage, dite apprentissage par renforcement.
Histoire
Les jeux ont joué un rôle important dans le développement des méthodes d’apprentissage, un domaine de l’intelligence artificielle en plein essor. Dès les années 50, Alan Turing (1912-1954) explore la question de l’intelligence artificielle et conçoit une expérience connue sous le nom de le test de Turing. Avec Donald Michie, il sont les premiers à s’intéresser à la création d’un programme capable de rivaliser avec les humains pour un jeu de stratégie, dans leur cas les échecs. Ils mettent au point des programmes alors qu’il n’existe pas encore de machines pour les exécuter! Ces réflexions sur la possibilité de créer des machines « qui apprennent » amènent Donald Michie à développer en 1961 une machine destinée à jouer, et surtout à apprendre à jouer, au morpion. Depuis, ce défi a passionné les chercheurs et les victoires se sont multipliées. On se souvient de celle du programme Deep Blue d’IBM sur le champion d’échec Garry Kasparov et de celle du programme AlphaGo sur le champion de go, Ke Lie.
Liens
- une vidéo sur le jeu de Nim
- une variante avec des gobelets
- la page du Liris qui décrit cette activité en détail et dont on s’est inspirés pour créer notre machine
- une machine qui apprend à jouer au morpion
- la video de David Louape: Une intelligence artificielle peut-elle être créative ? Le cas des jeux
II-Construction
Plan de l’objet
Matériaux
- 1 planche de contreplaqué 9mm 1380x 190 mm (bas)
- 1 planche de contreplaqué 9mm 1380x 180 mm (haut)
- 1 planche de contreplaqué 9mm 1380x 200 mm (fond)
- 7 planches de contreplaqué 9mm 200x150mm (séparation)
- 2 planches de contreplaqué 9mm 190x200mm (cotés)
- 1 planche de contreplaqué 9mm 30×30 (pour le support des batonnets)
- 1 planche de plexi transparente 5mm 1200x200mm
- 1 tasseau 5x5mm 2m40
- 1 tourillon 10mm de diamètre 2.4m de longeur
- 1 cornière en bois 45x45mm , 1380mm
- 1 sachet de petits clous
- colle à bois
- 1 morceau de tissus de 1m20x30cm et 8 morceaux de 11cmx35m qui serviront de manches
- papier blanc
- imprimante
- Outils : Perceuse , mèche à bois de 10 , scie cloche 100mm de diamètre , agrafeuse murale, marteau, scie, mètre, colle à tissus, colle à bois, imprimante, découpeuse laser (on en trouve dans les Fablab).
Montage
-Boite machine IA
- Faire 8 trous grâce à la scie cloche avec 7.5cm d’écart entre les bords et chacun des ronds puis mettre de côté 2 cercles qui nous serviront pour la manivelle par la suite.
- Coller à l’aide de la colle tissus les 8 morceaux de 11cmx35m afin d’en faire des petites manches .
- Agrafer sur la planche du haut chacune des petites manches à un trou.
- Assembler le bas , le fond et les côtés grâce aux clous et à la colle à bois.
- Coller les 7 séparations avec un espace de 14.4cm puis le haut et renforcer avec des clous.
- Couper le tasseau de 5mm en : 4 morceaux de 19cm et 1 morceau de 120cm.
- Coller les tasseaux de façon à caler la plaque de plexi contre les séparations.
- Couper le tourillon : 1 morceau de 123cm (pour la manivelle) et 8 morceaux de 10cm (batonnets).
- Faire 1 trou à l’aide de la mèche de 10 sur chacun des côtés afin d’y insérer la manivelle (morceau de tourillon de 123cm).
- Prendre les 2 cercles préalablement mis de côté puis les coller sur chacune des extrémités de la manivelle.
- Enrouler le tissu à la manivelle en collant une extrémité du tissu pour ne pas qu’il glisse entièrement lorsque l’on déroule.
- Coller et clouter la cornière en bois sur la devanture de la machine comme sur l’image.
- Imprimer les chiffres de 1 à 8 puis les coller sur la cornière.
-Support batonnets
- Découper à la découpeuse laser le
fichier svg - Assembler les pièces puis coller
III-Animation
- une vidéo d’un programme qui permet de simuler le comportement de la machine à apprendre pour un grand nombre de parties et d’observer l’évolution des urnes.
- l’arbre des possibilités, un schéma qui explicite tous les choix possibles à chaque étape du jeu et qui permet de comprendre la stratégie gagnante.
