Morpion minimax : la machine qui refuse de perdre
Joue au morpion contre une machine qui lit tous les futurs possibles et ne perd jamais. Regarde-la noter chaque coup, victoire, nul ou défaite, avant de jouer.
Cette semaine, l’IA arrête de deviner et se met à calculer. Le perceptron a appris, le babilleur de Markov a compté ; l’invité du jour ne fait ni l’un ni l’autre. Il cherche.
Le gadget ci-dessous joue au morpion avec une stratégie parfaite appelée minimax. Avant chaque coup, il examine toute la partie, chaque coup qu’il pourrait jouer, chaque réponse que tu pourrais donner, jusqu’à la dernière case libre, puis choisit un coup qui ne peut pas perdre. Vas-y, essaie de le battre. Tu n’y arriveras pas. Au mieux, tu obtiendras un match nul.
Comment jouer :
- Choisis de jouer X (tu commences) ou O (la machine commence).
- Touche une case. La machine répond aussitôt.
- Regarde le panneau à côté du plateau : il liste chaque case que la machine a pesée à ce tour avec le résultat garanti en jeu parfait, la machine gagne, nul ou la machine perd, et met en évidence celle qu’elle a choisie.
Chercher, pas apprendre
Minimax est magnifiquement bête. Il n’a ni expérience, ni entraînement, ni données. Il suppose simplement que les deux joueurs sont parfaits, déroule chaque branche de l’arbre de jeu et note chaque fin : +1 si la machine gagne, −1 si elle perd, 0 en cas de nul. Puis il prend la branche au meilleur score garanti. Voilà toute l’astuce.
C’est l’autre grande famille de l’IA des débuts, celle qui n’avait rien à voir avec les neurones. Elle va de l’esquisse de Claude Shannon en 1950 d’une machine jouant aux échecs jusqu’à Deep Blue, l’ordinateur d’IBM qui a battu le champion du monde Garry Kasparov en 1997 en fouillant des millions de positions avec des règles réglées à la main, de l’anticipation en force brute, pas de l’apprentissage.
Pourquoi il s’arrête au morpion
Le morpion ne compte que 255 168 parties possibles, un ordinateur portable les lit toutes en un clin d’œil. Les échecs comptent plus de positions qu’il n’y a d’atomes dans l’univers observable, si bien que Deep Blue ne pouvait regarder que quelques dizaines de coups à l’avance en s’appuyant sur une fonction d’évaluation astucieuse. Le go est plus vaste encore, et c’est pourquoi le vaincre a exigé une tout autre idée : le mélange de recherche et d’apprentissage derrière AlphaGo en 2016.
Alors savoure ta partie impossible à gagner. C’est le plus petit et le plus pur exemple de l’IA symbolique à l’ancienne : une machine qui paraît brillante simplement parce qu’elle est minutieuse.
Tu as manqué les éditions précédentes ? Entraîne un perceptron dans le navigateur ou regarde une chaîne de Markov babiller.