IA et 2048 : comment un programme atteint la tuile 32 768
Les programmes qui jouent le mieux au 2048 associent deux choses : une recherche qui explore les prochains coups (l'expectimax) et une évaluation des positions, écrite à la main ou apprise en jouant. Un article de recherche de 2021 annonce ainsi un score moyen de 625 377 points et la tuile 32 768 dans 72 % des parties.
Pourquoi le 2048 intéresse-t-il les informaticiens ?
Le jeu a des règles minuscules et pourtant il résiste. Il n'y a pas d'adversaire : après chaque coup, une tuile apparaît dans une case vide tirée au sort, un 2 neuf fois sur dix, un 4 une fois sur dix. Un programme ne peut donc pas calculer la suite de la partie. Il doit choisir le coup qui donne le meilleur résultat en moyenne, sur toutes les tuiles qui peuvent tomber.
Autre avantage pour qui veut faire apprendre une machine : chaque fusion rapporte des points, si bien que le programme reçoit un retour à presque chaque coup, sans attendre la fin de la partie. C'est ce qui fait du 2048 un banc d'essai courant pour l'apprentissage par renforcement.
Comment fonctionne l'expectimax ?
L'expectimax construit un arbre. À chaque étage où le programme joue, il garde le meilleur des quatre coups possibles. À chaque étage où le jeu pose une tuile, il fait la moyenne de toutes les cases et des deux valeurs possibles, pondérée par leurs probabilités. Arrivé au bout de la profondeur fixée, il faut bien donner une note à la position atteinte : c'est le rôle de la fonction d'évaluation.
Le programme le plus connu de cette famille est celui de Robert Xiao, publié sur GitHub sous le pseudonyme nneonneo en mars 2014, le mois même de la sortie du jeu. Son auteur indique qu'il code la grille de façon assez compacte pour examiner plus de dix millions de coups par seconde, et qu'il regarde en général de 4 à 8 coups devant lui.
Sa fonction d'évaluation est écrite à la main. Elle récompense les cases vides, les grosses tuiles placées au bord et les fusions possibles entre voisines, et elle pénalise les lignes et les colonnes dont les valeurs ne sont pas rangées dans l'ordre. Les poids de ces critères ont été réglés automatiquement par Petr Morávek, avec un algorithme d'optimisation appelé CMA-ES.
Sur 100 parties rapportées par Robert Xiao, le programme a atteint les tuiles 2048, 4096 et 8192 à chaque fois, la tuile 16 384 dans 94 % des parties et la tuile 32 768 dans 36 %. Le score médian est de 387 222 points, le plus faible de 124 024 et le plus élevé de 794 076.
Un programme peut-il apprendre seul à jouer ?
Oui. En 2014, Marcin Szubert et Wojciech Jaśkowski, de l'université de technologie de Poznań, ont entraîné un programme sans lui donner aucun conseil humain et sans recherche dans l'arbre des coups : il se contente de jouer le coup qui mène à la position qu'il estime la meilleure.
Deux idées se combinent :
- L'apprentissage par différences temporelles. Le programme joue un très grand nombre de parties. Après chaque coup, il corrige la note qu'il donnait à la position précédente à partir des points gagnés et de la note de la position suivante. Les estimations s'affinent de proche en proche.
- Les réseaux n-tuple. Malgré leur nom, ce sont de grandes tables. Chacune surveille un petit groupe de cases et garde un poids pour chaque contenu possible de ce groupe. La note d'une grille est la somme des poids lus dans toutes les tables. Le programme juge donc des relations entre tuiles voisines, pas des tuiles prises une à une.
Résultat : la tuile 2048 atteinte dans plus de 97 % des parties. Wojciech Jaśkowski précise dans un article de 2016 que la meilleure fonction de ce premier travail comptait près de 23 millions de paramètres et marquait 100 178 points en moyenne.
Quels résultats donnent les deux méthodes réunies ?
Rien n'oblige à choisir. Une évaluation apprise peut servir à noter les positions au bout d'une recherche expectimax, et c'est ce que font les programmes les plus forts.
En 2021, Hung Guei, Lung-Pin Chen et I-Chen Wu ont publié une méthode dite d'initialisation optimiste : les poids démarrent à des valeurs très élevées, ce qui pousse le programme à essayer des positions qu'il a peu rencontrées avant de se fier à ses habitudes. Associée à une recherche expectimax et à un apprentissage en plusieurs étapes, elle atteint un score moyen de 625 377 points et la tuile 32 768 dans 72 % des parties.
| Programme | Méthode | Tuile atteinte | Score |
|---|---|---|---|
| Robert Xiao, 2014 | Expectimax, évaluation écrite à la main | 32 768 dans 36 % des parties | 387 222 (médian) |
| Szubert et Jaśkowski, 2014 | Apprentissage seul, sans recherche | 2048 dans plus de 97 % des parties | 100 178 (moyen) |
| Guei, Chen et Wu, 2021 | Apprentissage et expectimax | 32 768 dans 72 % des parties | 625 377 (moyen) |
Ces lignes ne se comparent pas au point près : les conditions de test diffèrent, et un score médian n'est pas un score moyen. Elles donnent un ordre de grandeur. Il n'existe pas de statistique équivalente pour les joueurs humains, faute de parties contrôlées, donc pas de comparaison chiffrée honnête entre l'humain et la machine.
Ces résultats restent en dessous de la limite théorique du jeu. La plus grande tuile possible sur une grille 4×4 est 131 072, comme l'explique le guide sur la tuile maximale et le score maximum.
Que peux-tu en retenir pour tes propres parties ?
Les critères que Robert Xiao a donnés à son programme se lisent comme une liste de conseils, et ce sont ceux que les bons joueurs appliquent déjà :
- garde des cases vides, c'est ce qui laisse le temps de réparer une erreur ;
- range tes grosses tuiles contre un bord, la plus grosse dans un coin ;
- garde tes lignes et tes colonnes dans l'ordre, de la plus grande valeur à la plus petite ;
- cherche les positions où des tuiles égales se touchent.
La leçon de l'expectimax vaut aussi sans ordinateur : ne joue pas le coup qui serait parfait si la tuile tombait au bon endroit, joue celui qui reste correct où qu'elle tombe. Le guide comment gagner au 2048 détaille cette méthode pas à pas.
Pour voir un programme à l'œuvre, lance une partie en mode Entraînement sur la page du jeu : un indice te montre le coup que jouerait l'ordinateur, et tu peux annuler ton dernier coup autant de fois que tu veux pour comparer. Ces parties ne comptent pas au classement. Les débuts du jeu, eux, sont racontés dans l'histoire du 2048.
