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.
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:
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...
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 !
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 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.