MENACE : Le dispositif qui apprend à jouer au morpion
La présentation originale de Matthew Scroggs est disponible à cette page : https://www.mscroggs.co.uk/blog/19
MENACE : acronyme anglais de « Machine Educable Noughts And Crosses Engine » (dispositif qui apprend à jouer au morpion).
En 1961, Donald Michie a élaboré MENACE, un dispositif capable d’apprendre à mieux jouer au morpion. Comme les ordinateurs étaient bien moins disponibles à cette époque, MENACE a été conçue avec 304 boîtes d’allumettes.
Comment jouer contre MENACE
Chaque configuration de jeu à laquelle MENACE peut être confrontée est dessinée sur une boîte d'allumettes. Des perles de couleur sont placées dans chaque boîte. Chaque couleur correspond à un coup possible que MENACE peut effectuer dans la configuration donnée.
Pour réduire le nombre de boîtes d'allumettes nécessaires, MENACE joue toujours en premier.
Pour faire jouer MENACE, l’opérateur doit trouver la boîte correspondant à la configuration en cours. Il secoue la boîte puis l'ouvre. MENACE joue alors le coup correspondant à la couleur de la perle qui apparaît à l'avant de la boîte.
Par exemple, dans la partie ci-dessus, la première boîte d'allumettes est ouverte et révèle une perle rouge. Cela signifie que MENACE (O) joue dans le coin. Le joueur humain (X) joue ensuite au centre. Pour effectuer le coup suivant, l'opérateur de MENACE repère la boîte d'allumettes correspondant à la nouvelle situation, secoue la boîte, puis l'ouvre. Cette fois, la perle est bleue. Cela indique que MENACE joue en bas, au milieu.
Le joueur humain joue en bas, à droite. De nouveau l’opérateur sélectionne la boîte où figure la situation correspondante. Il en tire une perle orange, MENACE joue au milieu, à gauche. Finalement le joueur humain l’emporte en jouant en haut, à gauche.
MENACE a perdu la partie mais n’a pas tout perdu. MENACE peut, à présent, apprendre de ses erreurs afin que cela ne se reproduise pas.
Comment MENACE apprend
MENACE a perdu la partie ci-dessus, dans ce cas les perles tirées au sort sont extraites des boîtes. MENACE sera donc moins susceptible de choisir à nouveau ces mêmes couleurs et a donc appris. Si MENACE avait gagné, trois perles de la couleur tirée au sort auraient été ajoutées à chaque boîte, encourageant MENACE à reproduire ces coups dans une même configuration. Si la partie est nulle, une perle est ajoutée à chaque boîte.
Initialement, on dispose quatre perles de chaque couleur dans la boîte correspondant au premier coup, trois perles de chaque couleur dans les boîtes correspondant au troisième coup, deux dans les boîtes correspondant au cinquième coup et une dans les suivantes. Enlever une perle de plus de chaque boîte en cas de défaite signifie que de tels coups sont, par la suite, moins fortement encouragés. Cela aide MENACE à apprendre plus rapidement, ces coups étant davantage susceptibles de conduire à une défaite.
Après quelques parties, il est possible que certaines boîtes soient vides. Si l'une de ces boîtes doit être utilisée, alors MENACE abandonne. Lorsque MENACE joue contre des joueurs qualifiés, il est possible que la première boîte se vide rapidement. Dans ce cas, MENACE doit être réinitialisé avec plus de perles dans les premières boîtes pour lui octroyer plus de temps d'apprentissage avant qu'elle ne soit contrainte à l’abandon.
Comment MENACE se perfectionne
Lors du premier essai de Donald Michie contre MENACE, 220 parties durant 16 heures ont été jouées. MENACE a régulièrement fait des parties nulles après les 20 premières parties.
Insérez une légende ici...
Après un certain temps, Michie a essayé de jouer des coups plus inhabituels. Pendant un certain temps, il a pu vaincre MENACE, mais MENACE a rapidement appris à ne plus perdre. Vous pouvez en savoir plus sur la MENACE d’origine dans « A matchbox game learning-machine » de Martin Gardner [1] et « Trial and error » de Donald Michie [2].
Jouer contre MENACE
Vous aimerez peut-être expérimenter vous-même différentes tactiques contre MENACE.
J'ai réalisé une implémentation de MENACE en JavaScript pour que vous puissiez la défier. Le code source de cette implémentation est disponible sur GitHub.
Lorsque vous jouez avec cette version de MENACE, le contenu des boîtes d'allumettes est affiché sur le côté droit de la page. Les chiffres indiqués sur les boîtes indiquent combien de perles correspondant à ces coups restent dans la boîte. Les chiffres rouges montrent quelles perles ont été choisies dans la partie en cours.
Le nombre initial de perles dans les boîtes et les incitations peuvent être ajustés en cliquant sur Ajuster les paramètres de MENACE au-dessus des boîtes d'allumettes. Ma version de MENACE commence par plus de perles dans chaque boîte que la MENACE d’origine afin d’éviter que les premières boîtes ne soient à court de perles, et limiter les abandons de MENACE. De plus, à côté du tableau, vous pouvez choisir l’option : jouer contre MENACE ou MENACE contre elle-même.
Note : Après avoir assisté à une de mes conférences éclairs sur MENACE à la CCC, Oliver Child a conçu un exemplaire de MENACE. Voici quelques photos qu'il m'a envoyées :
[1] : A matchbox game learning-machine par Martin Gardner. Scientific American, March 1962. [lien]
[2] : Trial and error par Donald Michie. Penguin Science Survey, 1961.