Utiliser l'intelligence artificielle pour résoudre le jeu 2048 (code JAVA)

• 7 avril 2014
• Vassilis Vryniotis
• . 6 Commentaires

A présent, la plupart d'entre vous ont entendu / joué le 2048 jeu par Gabriele Cirulli. C'est un jeu de société simple mais très addictif qui vous oblige à combiner les nombres des cellules pour atteindre le nombre 2048. Comme prévu, la difficulté du jeu augmente à mesure que de plus en plus de cellules sont remplies de valeurs élevées. Personnellement, même si j'ai passé pas mal de temps à jouer au jeu, je n'ai jamais pu atteindre 2048. Donc, la chose naturelle à faire est d'essayer de développer un solveur IA en JAVA pour battre le jeu 2048. 🙂

Dans cet article, je discuterai brièvement de mon approche pour construire le solveur d'intelligence artificielle du jeu 2048, je décrirai l'heuristique que j'ai utilisée et je fournirai le code complet qui est écrit en JAVA. Le code est open-source sous licence GPL v3 et vous pouvez le télécharger depuis Github.

Développer le jeu 2048 en JAVA

Le jeu original est écrit en JavaScript, j'ai donc dû le réécrire en JAVA à partir de zéro. L'idée principale du jeu est que vous avez une grille 4 × 4 avec des valeurs entières, qui sont toutes des puissances de 2. Les cellules de valeur zéro sont considérées comme vides. À chaque moment du jeu, vous pouvez déplacer les valeurs vers 4 directions vers le haut, le bas, la droite ou la gauche. Lorsque vous effectuez un déplacement, toutes les valeurs de la grille se déplacent vers cette direction et elles s'arrêtent soit lorsqu'elles atteignent les bordures de la grille, soit lorsqu'elles atteignent une autre cellule avec une valeur différente de zéro. Si cette cellule précédente a la même valeur, les deux cellules sont fusionnées en une seule cellule avec une valeur double. À la fin de chaque mouvement, une valeur aléatoire est ajoutée dans le tableau dans l'une des cellules vides et sa valeur est soit 2 avec une probabilité de 0.9 ou 4 avec une probabilité de 0.1. Le jeu se termine lorsque le joueur parvient à créer une cellule de valeur 2048 (gagner) ou lorsqu'il n'y a pas d'autres coups à faire (perdre).

Dans l'implémentation originale du jeu, l'algorithme de déplacement-fusion est un peu compliqué car il prend en compte toutes les directions. Une belle simplification de l'algorithme peut être effectuée si nous fixons la direction dans laquelle nous pouvons combiner les pièces et faire pivoter la planche en conséquence pour effectuer le mouvement. Maurits van der Schee a récemment écrit un article à ce sujet qui, à mon avis, vaut le détour.

Toutes les classes sont documentées avec des commentaires Javadoc. Ci-dessous, nous fournissons une description de haut niveau de l'architecture de l'implémentation:

1. Classe du conseil

La classe de plateau contient le code principal du jeu, qui est chargé de déplacer les pièces, de calculer le score, de valider si le jeu est terminé, etc.

2. ActionStatus et Direction Enum

L'ActionStatus et la Direction sont 2 énumérations essentielles qui stockent le résultat d'un mouvement et sa direction en conséquence.

3. Classe ConsoleGame

Le ConsoleGame est la classe principale qui nous permet de jouer au jeu et de tester la précision de l'IA Solver.

4. Classe AIsolver

L'AIsolver est la classe principale du module d'Intelligence Artificielle qui est responsable de l'évaluation du prochain meilleur coup donné à un tableau particulier.

Techniques d'intelligence artificielle: taille Minimax vs Alpha-beta

Plusieurs approches ont été publiées pour résoudre automatiquement ce jeu. Le plus notable est celui développé par Matt Overlan. Pour résoudre le problème, j'ai essayé deux approches différentes, en utilisant l'algorithme Minimax et en utilisant l'élagage Alpha-beta.

Algorithme Minimax

Les Minimax est un algorithme récursif qui peut être utilisé pour résoudre des jeux à somme nulle à deux joueurs. A chaque état du jeu on associe une valeur. L'algorithme Minimax recherche dans l'espace des états de jeu possibles en créant un arbre qui est développé jusqu'à ce qu'il atteigne une profondeur prédéfinie particulière. Une fois ces états feuilles atteints, leurs valeurs sont utilisées pour estimer celles des nœuds intermédiaires.

L'idée intéressante de cet algorithme est que chaque niveau représente le tour de l'un des deux joueurs. Pour gagner, chaque joueur doit sélectionner le coup qui minimise le gain maximum de l'adversaire. Voici une belle présentation vidéo de l'algorithme minimax:

[Contenu intégré]

Ci-dessous vous pouvez voir le pseudo-code de l'algorithme Minimax:

fonction minimax (nœud, profondeur, maximizingPlayer)
    if profondeur = 0 or node est un nœud terminal
        retourner la valeur heuristique du nœud
    if maximizingPlayer bestValue: = -∞
        pour chaque enfant du nœud val: = minimax (enfant, profondeur - 1, FALSE)) bestValue: = max (bestValue, val);
        retourner meilleure valeur
    d'autre
        bestValue: = + ∞
        pour chaque enfant du nœud val: = minimax (enfant, profondeur - 1, TRUE)) bestValue: = min (bestValue, val);
        retourner meilleure valeur
(* Premier appel pour maximiser le joueur *)
minimax (origine, profondeur, VRAI)

Taille alpha-bêta

Les Algorithme d'élagage alpha-bêta est une expansion de minimax, qui diminue fortement (élague) le nombre de nœuds que nous devons évaluer / étendre. Pour y parvenir, l'algorithme estime deux valeurs alpha et bêta. Si dans un nœud donné la bêta est inférieure à alpha, alors le reste des sous-arbres peut être élagué. Voici une belle présentation vidéo de l'algorithme alphabeta:

[Contenu intégré]

Ci-dessous vous pouvez voir le pseudocode de l'algorithme d'élagage Alpha-beta:

fonction alphabeta (nœud, profondeur, α, β, maximizingPlayer)
    if profondeur = 0 or node est un nœud terminal
        retourner la valeur heuristique du nœud
    if maximisation du joueur
        pour chaque enfant du nœud α: = max (α, alphabeta (enfant, profondeur - 1, α, β, FALSE))
            if ≤ α
                pause (* seuil β *)
        retourner α
    d'autre
        pour chaque enfant du nœud β: = min (β, alphabeta (enfant, profondeur - 1, α, β, TRUE))
            if ≤ α
                pause (* seuil α *)
        retourner β
(* Premier appel *)
alphabeta (origine, profondeur, -∞, + ∞, TRUE)

Comment l'IA est-elle utilisée pour résoudre le jeu 2048?

Afin d'utiliser les algorithmes ci-dessus, nous devons d'abord identifier les deux joueurs. Le premier joueur est la personne qui joue au jeu. Le deuxième joueur est l'ordinateur qui insère aléatoirement des valeurs dans les cellules du plateau. De toute évidence, le premier joueur essaie de maximiser son score et de réaliser la fusion 2048. D'un autre côté, l'ordinateur du jeu original n'est pas spécifiquement programmé pour bloquer l'utilisateur en sélectionnant le pire coup possible pour lui, mais insère plutôt au hasard des valeurs sur les cellules vides.

Alors pourquoi utilisons-nous des techniques d'IA qui résolvent des jeux à somme nulle et qui supposent spécifiquement que les deux joueurs sélectionnent le meilleur coup possible pour eux? La réponse est simple; malgré le fait que seul le premier joueur essaie de maximiser son score, les choix de l'ordinateur peuvent bloquer la progression et empêcher l'utilisateur de terminer la partie. En modélisant le comportement de l'ordinateur comme un joueur orthologique non aléatoire, nous nous assurons que notre choix sera solide indépendamment de ce que joue l'ordinateur.

La deuxième partie importante est d'attribuer des valeurs aux états du jeu. Ce problème est relativement simple car le jeu lui-même nous donne un score. Malheureusement, essayer de maximiser le score seul n'est pas une bonne approche. Une des raisons à cela est que la position des valeurs et le nombre de cellules de valeurs vides sont très importants pour gagner la partie. Par exemple, si nous dispersons les grandes valeurs dans des cellules distantes, il nous serait très difficile de les combiner. De plus, si nous n'avons pas de cellules vides disponibles, nous risquons de perdre la partie à tout moment.

Pour toutes les raisons ci-dessus, plusieurs heuristiques ont été suggérés tels que la monoticité, la douceur et les tuiles gratuites du plateau. L'idée principale n'est pas d'utiliser le score seul pour évaluer chaque état du jeu, mais plutôt de construire un score composite heuristique qui inclut les scores susmentionnés.

Enfin, nous devons noter que même si j'ai développé une implémentation de l'algorithme Minimax, le grand nombre d'états possibles rend l'algorithme très lent et donc l'élagage est nécessaire. En conséquence, dans l'implémentation JAVA, j'utilise l'extension de l'algorithme d'élagage Alpha-beta. De plus, contrairement à d'autres implémentations, je ne taille pas agressivement les choix de l'ordinateur en utilisant des règles arbitraires, mais je les prends toutes en compte afin de trouver le meilleur mouvement possible du joueur.

Développer une fonction de score heuristique

Afin de battre le jeu, j'ai essayé plusieurs fonctions heuristiques différentes. Celui que j'ai trouvé le plus utile est le suivant:

private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
     int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
     return Math.max(score, Math.min(actualScore, 1));
}

La fonction ci-dessus combine le score réel du plateau, le nombre de cellules / tuiles vides et une métrique appelée score de clustering que nous discuterons plus tard. Voyons chaque composant plus en détail:

1. Score réel: Pour des raisons évidentes, lorsque nous calculons la valeur d'une planche, nous devons prendre en compte son score. Les conseils avec des scores plus élevés sont généralement préférés par rapport aux conseils avec des scores inférieurs.
2. Nombre de cellules vides: Comme nous l'avons mentionné précédemment, il est important de garder quelques cellules vides pour s'assurer que nous ne perdrons pas la partie lors des prochains coups. Les états de carte avec plus de cellules vides sont généralement préférés par rapport aux autres avec moins. Une question se pose quant à la valeur de ces cellules vides? Dans ma solution, je les pondère par le logarithme du score réel. Cela a l'effet suivant: Plus le score est bas, moins il est important d'avoir de nombreuses cellules vides (car au début du jeu, combiner les cellules est assez facile). Plus le score est élevé, plus il est important de s'assurer que nous avons des cellules vides dans notre jeu (en effet, à la fin du jeu, il est plus probable de perdre en raison du manque de cellules vides.
3. Score de clustering: Nous utilisons le score de clustering qui mesure la dispersion des valeurs de notre tableau. Lorsque des cellules avec des valeurs similaires sont proches, elles sont plus faciles à combiner, ce qui signifie qu'il est plus difficile de perdre la partie. Dans ce cas, le score de clustering a une valeur faible. Si les valeurs du tableau sont dispersées, alors ce score prend une très grande valeur. Ce score est soustrait des deux scores précédents et agit comme une pénalité qui garantit que les tableaux groupés seront préférés.

Dans la dernière ligne de la fonction, nous nous assurons que le score est non négatif. Le score doit être strictement positif si le score du tableau est positif et zéro uniquement lorsque le tableau du score est nul. Les fonctions max et min sont construites de manière à obtenir cet effet.

Enfin, nous devons noter que lorsque le joueur atteint un état de jeu terminal et qu'aucun autre mouvement n'est autorisé, nous n'utilisons pas le score ci-dessus pour estimer la valeur de l'état. Si la partie est gagnée, nous attribuons la valeur entière la plus élevée possible, tandis que si la partie est perdue, nous attribuons la valeur non négative la plus basse (0 ou 1 avec une logique similaire à celle du paragraphe précédent).

En savoir plus sur le score de clustering

Comme nous l'avons dit précédemment, le score de regroupement mesure à quel point les valeurs du tableau sont dispersées et agit comme une pénalité. J'ai construit cette partition de telle manière qu'elle intègre les astuces / règles des utilisateurs qui ont «maîtrisé» le jeu. La première règle suggérée est que vous essayez de garder les cellules avec des valeurs similaires proches afin de les combiner plus facilement. La deuxième règle est que les cellules de valeur élevée doivent être proches les unes des autres et n'apparaître pas au milieu du plateau mais plutôt sur les côtés ou les coins.

Voyons comment le score de clustering est estimé. Pour chaque cellule du tableau, nous estimons la somme des différences absolues par rapport à ses voisins (à l'exclusion des cellules vides) et nous prenons la différence moyenne. La raison pour laquelle nous prenons les moyennes est d'éviter de compter plus d'une fois l'effet de deux cellules voisines. Le score total de regroupement est la somme de toutes ces moyennes.

Le score de clustering a les attributs suivants:

1. Il obtient une valeur élevée lorsque les valeurs du tableau sont dispersées et une valeur faible lorsque des cellules avec des valeurs similaires sont proches les unes des autres.
2. Il ne surpasse pas l'effet de deux cellules voisines.
3. Les cellules dans les marges ou les coins ont moins de voisins et donc des scores inférieurs. En conséquence, lorsque les valeurs élevées sont placées près des marges ou des coins, elles ont des scores plus petits et donc la pénalité est plus petite.

La précision de l'algorithme

Comme prévu, la précision (c'est-à-dire le pourcentage de jeux gagnés) de l'algorithme dépend fortement de la profondeur de recherche que nous utilisons. Plus la recherche est approfondie, plus la précision est élevée et plus elle nécessite de temps pour s'exécuter. Dans mes tests, une recherche avec une profondeur 3 dure moins de 0.05 seconde mais donne 20% de chances de gagner, une profondeur de 5 dure environ 1 seconde mais donne 40% de chance de gagner et enfin une profondeur de 7 dure 27-28 secondes et donne environ 70 à 80% de chances de gagner.

Expansions futures

Pour ceux d'entre vous qui souhaitent améliorer le code, voici quelques points à examiner:

1. Améliorez la vitesse: Améliorer la vitesse de l'algorithme vous permettra d'utiliser une plus grande profondeur et ainsi d'obtenir une meilleure précision.
2. Créer des graphiques: Il y a une bonne raison pour laquelle l'implémentation de Gabriele Cirulli est devenue si célèbre. C'est joli! Je n'ai pas pris la peine de développer une interface graphique mais j'imprime plutôt les résultats sur console ce qui rend le jeu plus difficile à suivre et à jouer. Créer une belle interface graphique est un must.
3. Tune Heuristique: Comme je l'ai mentionné précédemment, plusieurs utilisateurs ont suggéré différentes heuristiques. On peut expérimenter la façon dont les scores sont calculés, les poids et les caractéristiques du plateau qui sont pris en compte. Mon approche de mesure du score de cluster est censée combiner d'autres suggestions telles que la monotonie et la douceur, mais il y a encore place à l'amélioration.
4. Réglage de la profondeur: On peut également essayer de régler / ajuster la profondeur de la recherche en fonction de l'état du jeu. Vous pouvez également utiliser le Recherche itérative d'approfondissement en profondeur d'abord algorithme connu pour améliorer l'algorithme d'élagage alpha-bêta.

N'oubliez pas de télécharger le code JAVA depuis Github et expérimenter. J'espère que vous avez apprécié ce post! Si vous l'avez fait, veuillez prendre un moment pour partager l'article sur Facebook et Twitter. 🙂