Vous souvenez-vous du 2048 ? Le jeu consiste à bouger des briques dans différentes directions en utilisant les flèches du clavier : lorsque deux briques identiques entrent en collision, elles fusionnent pour donner une nouvelle brique dont la valeur est la somme des deux précédentes. L'objectif du jeu est d'arriver à créer la brique 2048 sans bloquer le jeu.
On s'est lancé le défi de coder un bot qui permet de battre le jeu : voici nos différentes approches et le résultat en vidéo !

Sur cette vidéo, notre bot prend le contrôle d'un naviguateur web pour résoudre le 2048 en ligne grâce à la méthode de Monte-Carlo.

Méthode 1 : Force Brute et Scoring

Comme tout programmeur entêté, nous avons d'abord voulu essayer de résoudre le problème par la force. En théorie, cela consisterait en la simulation de toutes les parties possibles afin de trouver la série de coups qui donne le meilleur score. Comme vous pouvez vous en douter, cette méthode basique ne peut pas fonctionner avec le 2048 : il y a une part d'aléatoire dans le jeu (apparition d'une nouvelle brique à chaque coup). De plus, une partie de 2048 contient plusieurs centaines (voire des milliers) de coups : rien que pour évaluer toutes les séries de coups possibles dans une partie de 100 coups, il faudrait simuler 4^100 ≈ 1.6 e60 coups!
Comme il est impossible de simuler entièrement une partie jusqu'à la défaite, nous avons essayé d'attribuer des scores aux configurations pour pouvoir les comparer entre elles et déterminer les plus prometteuses (Scoring).
Un touche du clavier qui génère une configuration avec un bon score sera préféré à une autre.
De nombreuses approches sont possibles : on pourrait par exemple dire que le score d'une configuration est la somme des valeurs de ses briques, ou son nombre de cases vides...
Le choix que nous avons fait est de multiplier la configuration par une matrice, puis de calculer la somme des coefficients de la matrice obtenue, et enfin d'ajouter le nombre de cases vides.

filter_matrix = numpy.matrix([
    [-1, -1, -1, -1],
    [-1, -1, -1, -1],
    [-1, -1, -1, 100],
    [-1, -1, 100, 200]
])
score = numpy.multiply(board, filter_matrix).sum() + np.count_nonzero(board == 0)

L'objectif de la matrice était d'encourager les coups menant à une structure pyramidale des valeurs des briques, en mettant dans le coin en bas à droite de la grille la brique la plus grande. Cette stratégie est très répandue parmi les joueurs du jeu !

Voici comment nous avons procédé pour déterminer le meilleur coup à jouer à chaque tour:

Profondeur de recherche à 6 coups :
Pour chaque coup, on simule tous les enchaînements de 5 coups possibles par la suite ([bas, bas, bas,bas ,bas], [bas, bas, bas, bas, haut]...).

Chaque enchaînement de 6 coups est fait 20 fois afin de moyenner l'apparition aléatoire des briques.

On donne un score à chaque coup (Scoring) :
On attribue un score à chaque coup en faisant la moyenne des scores obtenus dans les simulations des enchaînements. Le coup au meilleur score est ensuite effectué !

En analysant seulement 6 coups à l'avance, on doit tout de même faire par coup joué 4^6*20 = 81 920 simulations. Cette version du bot est malheureusement un peu lente, et n'a jamais réussi à atteindre la case 2048...

Méthode 2 : Reinforcement Learning

Nous avons ensuite exploré la piste du deep learning.
Le Reinforcement learning est une technique de deep learning très utilisée pour construire des intelligences artificielles de jeux. (Exemples : Backgammon en 1995, jeux Atari, le Go en 2016). On a donc essayé de l'adapter au 2048.
Le principe du Reinforcment Learning est de trouver une règle de jeu qui maximise une récompense. Cette recherche de règle se fait à travers un apprentissage : elle évolue en fonction des récompenses obtenues au fil des parties. Ainsi, si une action faite dans un état particulier a donné une forte récompense, elle est consolidée, et inversement. En pratique, nous avons entraîné un réseau de neuronnes à l'aide de la librairie Tensorflow afin de maximiser la durée de partie. En entrée, le réseau reçoit la configuration de la partie, ainsi que les deux derniers coups joués. En sortie, ce réseau renvoie 4 scores : un pour chaque coup possible. Ce score est transformé en probabilités, et le coup prochain est tiré au sort selon ces dernières.
La récompense de chaque coup est calculée à la fin de chaque partie de la manière suivante, pour une partie en N coups :

score[N] = 0
pour 0 < n < N ; score[n] = 1 + r*score[n+1]  avec 0 < r < 1, le discount rate

L'idée derrière cette méthode de calcul est de prendre en compte les conséquences d'un coup à long terme : un coup fait 3 coups avant la défaite a donc un score très faible, décourageant ce coup dans une situation similaire. Pour atténuer l'effet aléatoire du jeu, les récompenses sont aussi moyennées sur 20 parties.

Après des heures d'entraînement, le bot utilisant le Reinforcement Learning est plus performant que la Force brute, mais il ne parvient tout de même pas à obtenir la brique 2048. Il est en effet difficile d'attribuer une récompense à un coup qui ne fait pas bouger la grille, et la part d'aléatoire dans le jeu demande un entraînement très long ! On a été rassurés de voir qu'une équipe du MIT n'avait pas réussi non plus (voir l'article)... Peut-être qu'en laissant l'algorithme s'entraîner sur plusieurs jours les résultats auraient été meilleurs, mais on n'a pas eu la patience !

Méthode 3 : Monte Carlo Tree Search

On a essayé une dernière méthode pour vaincre le 2048 : le Monte Carlo Tree Search. Le principe de cette méthode est très simple. Pour chacun des 4 coups possibles :

On simule le coup
À partir de la nouvelle configuration, on effectue 100 parties en jouant aléatoirement
On fait la moyenne des scores obtenus
On choisit de faire le coup qui a obtenu le meilleur score moyen !

On effectue ainsi pour chaque coup 100 trajectoires aléatoires dans l'univers des possibles qui servent à estimer la valeur du coup. On est donc affranchis d'une méthode de scoring, puisqu'on joue jusqu'à la défaite. C'est un gros avantage car ces dernières sont très subjectives.
Le score est alors simplement le score de base du jeu (somme de la valeur de toutes les tuiles combinées au fil de la partie).
Malgré sa simplicité, cette méthode (avec un nombre de parties simulées supérieur à 100) gagne régulièrement le jeu !
Voici les stats par nombre de simulations. Pour 170 simulations, plus de 90% des parties passent le cap du 2048, et 30% celui des 4096.

Si vous êtes curieux(se), le code est ici.

Un bot qui gagne au 2048