Donald Michie (1923–2007) était un chercheur anglais en intelligence artificielle. Il a travaillé pendant la Seconde Guerre mondiale avec Alan Turing pour casser les codes utilisés par l’armée allemande. Au début des années 1960, il fabrique une machine… en carton, capable d’apprendre à jouer au jeu de morpion (ou tic-tac-toe, ou encore noughts and crosses en anglais) sur une grille 3 × 3 et d’améliorer son jeu jusqu’à devenir expert. Il appelle cette machine MENACE (pour Machine educable noughts and crosses engine).
Un jeu qui démange
À tour de rôle, les deux joueurs placent une croix (joueur 1) et un rond (joueur 2) sur une case vide de la grille. Le premier joueur ayant réalisé un alignement de trois de ses symboles en ligne, en colonne ou en diagonale gagne la partie. La partie est nulle si aucun alignement n’est obtenu. Le morpion apparaît dans le film d’anticipation Wargames (John Badham, 1983), où il est utilisé pour apprendre à un ordinateur devenu fou qu’il existe des jeux auxquels il n’est pas toujours possible de gagner.
Le joueur 2 a gagné.
Donald Michie a dénombré les configurations du jeu ne comportant pas d’alignements de trois symboles identiques, depuis la grille vide (début du jeu) jusqu’aux grilles contenant six symboles. En éliminant les grilles identiques par rotation et symétrie, il a obtenu 304 configurations. Il s’est muni d’autant de boîtes d’allumettes sur lesquelles il a dessiné ces configurations. Il a ensuite placé dans ces boîtes des billes de neuf couleurs différentes, chacune correspondant à une case de la grille, à raison d’une seule bille par couleur pour les configurations contenant six symboles, de deux billes par couleur pour celles contenant quatre symboles, de trois billes par couleur pour celles contenant deux symboles et de quatre billes par couleur pour la grille vide (mais trois couleurs suffisent pour cette grille particulière en raison des rotations et symétries).
Sans tenir compte des rotations et des symétries, combien existe-t-il de configurations de la grille de morpion 3 × 3 après un coup, deux coups, trois coups, quatre coups, cinq coups, six coups ?
Le jeu se déroule ainsi. MENACE joue en premier (et joue donc les coups impairs 1, 3, 5, 7, le coup 9 ne laissant plus aucun choix). Le joueur 2 joue les coups pairs. On ouvre la boîte correspondant à la grille vide et on tire une bille de couleur au hasard, qui détermine le premier coup de la machine (trois coups sont possibles compte tenu des rotations et symétries).
L’adversaire humain choisit ensuite un coup. Pour jouer le troisième coup, on ouvre la boîte correspondant à la configuration de deux symboles déjà joués et on tire une bille de couleur, qui donne le coup joué par la machine. On continue ainsi jusqu’au gain de l’un des joueurs ou jusqu’à une partie nulle.
L’idée de génie de Donald Michie a été de mettre en place un système de « punitions et récompenses » permettant à la machine d’apprendre et de progresser en tenant compte de ses échecs et de ses réussites.
Lorsqu’une partie est nulle, on remet toutes les billes tirées dans les boîtes. Lorsque le joueur humain gagne, on « punit » la machine en lui retirant toutes les billes qu’elle a tirées au cours de la partie. Lorsqu’elle gagne, on la « récompense » en remettant les billes tirées dans les boîtes et en les doublant par un ajout de billes des mêmes couleurs. Ainsi, l’ajout des billes de couleurs « gagnantes » augmente la probabilité de choix de ces billes dans les parties suivantes, et donc de gain ; lorsqu’elle perd, le retrait des billes « perdantes » diminue la probabilité de perdre à nouveau lors de parties suivantes…