Quel est l'algorithme optimal pour le jeu 2048 ?

Question

Je suis récemment tombé sur le jeu 2048 . Vous fusionnez des tuiles similaires en les déplaçant dans l'une des quatre directions pour obtenir des tuiles plus grandes. Après chaque déplacement, une nouvelle tuile apparaît à une position vide aléatoire avec une valeur de soit 2 o 4 . Le jeu se termine lorsque toutes les cases sont remplies et qu'aucun mouvement ne permet de fusionner des tuiles, ou lorsque vous créez une tuile avec une valeur de 2048 .

Premièrement, je dois suivre une stratégie bien définie pour atteindre l'objectif. J'ai donc pensé à écrire un programme pour cela.

Mon algorithme actuel :

while (!game_over) {
    for each possible move:
        count_no_of_merges_for_2-tiles and 4-tiles
    choose the move with a large number of merges
}

Ce que je fais, c'est qu'à tout moment, je vais essayer de fusionner les tuiles avec des valeurs 2 y 4 c'est-à-dire que j'essaie d'avoir 2 y 4 les tuiles, le moins possible. Si j'essaie de cette façon, toutes les autres tuiles sont automatiquement fusionnées et la stratégie semble bonne.

Mais, lorsque j'utilise réellement cet algorithme, je n'obtiens qu'environ 4000 points avant que le jeu ne s'arrête. Le maximum de points AFAIK est légèrement supérieur à 20 000 points, ce qui est bien supérieur à mon score actuel. Existe-t-il un meilleur algorithme que celui décrit ci-dessus ?

Answer 1

J'ai développé une IA de 2048 en utilisant expectimax au lieu de la recherche minimax utilisée par l'algorithme d'@ovolve. L'IA effectue simplement une maximisation sur tous les mouvements possibles, suivie d'une espérance sur toutes les apparitions de tuiles possibles (pondérée par la probabilité des tuiles, c'est-à-dire 10% pour un 4 et 90% pour un 2). Pour autant que je sache, il n'est pas possible d'élaguer l'optimisation expectimax (sauf pour supprimer les branches qui sont excessivement improbables), et l'algorithme utilisé est donc une recherche par force brute soigneusement optimisée.

Performance

Dans sa configuration par défaut (profondeur de recherche maximale de 8), l'IA met entre 10 et 200 ms pour exécuter un coup, en fonction de la complexité de la position sur le plateau. Lors des tests, l'IA atteint un taux de déplacement moyen de 5 à 10 coups par seconde au cours d'une partie entière. Si la profondeur de recherche est limitée à 6 coups, l'IA peut facilement exécuter plus de 20 coups par seconde, ce qui donne lieu à des résultats très intéressants. regard intéressant .

Pour évaluer les performances de l'IA, je l'ai fait tourner 100 fois (connecté au jeu par navigateur via une télécommande). Pour chaque tuile, voici les proportions de jeux dans lesquels cette tuile a été atteinte au moins une fois :

2048: 100%
4096: 100%
8192: 100%
16384: 94%
32768: 36%

Le score minimum sur l'ensemble des runs est de 124024 ; le score maximum atteint est de 794076. Le score médian est de 387222. L'IA n'a jamais échoué à obtenir la tuile 2048 (elle n'a donc jamais perdu la partie, même une fois sur 100 parties) ; en fait, elle a obtenu le score le plus élevé. 8192 tuile au moins une fois dans chaque course !

Voici la capture d'écran de la meilleure course :

Cette partie a nécessité 27830 coups en 96 minutes, soit une moyenne de 4,8 coups par seconde.

Mise en œuvre

Mon approche consiste à encoder l'ensemble du tableau (16 entrées) sous la forme d'un seul entier de 64 bits (où les tuiles sont les nybbles, c'est-à-dire des morceaux de 4 bits). Sur une machine 64 bits, cela permet de faire passer le tableau entier dans un seul registre machine.

Les opérations de décalage de bits sont utilisées pour extraire des lignes et des colonnes individuelles. Une seule ligne ou colonne est une quantité de 16 bits, de sorte qu'une table de taille 65536 peut coder des transformations qui opèrent sur une seule ligne ou colonne. Par exemple, les déplacements sont implémentés sous la forme de 4 consultations d'une "table d'effet de déplacement" précalculée qui décrit comment chaque déplacement affecte une seule ligne ou colonne (par exemple, la table "déplacement vers la droite" contient l'entrée "1122 -> 0023" décrivant comment la ligne [2,2,4,4] devient la ligne [0,0,4,8] lorsqu'elle est déplacée vers la droite).

La notation est également effectuée à l'aide d'une table de consultation. Les tableaux contiennent des scores heuristiques calculés sur toutes les lignes/colonnes possibles, et le score résultant pour une planche est simplement la somme des valeurs du tableau pour chaque ligne et chaque colonne.

Cette représentation du plateau, ainsi que l'approche de consultation des tables pour les mouvements et les scores, permet à l'IA de rechercher un très grand nombre d'états de jeu dans un court laps de temps (plus de 10 000 000 d'états de jeu par seconde sur un cœur de mon ordinateur portable de mi-2011).

La recherche expectimax elle-même est codée comme une recherche récursive qui alterne entre des étapes d'"expectation" (testant tous les emplacements et valeurs possibles des tuiles, et pondérant leurs scores optimisés par la probabilité de chaque possibilité), et des étapes de "maximisation" (testant tous les mouvements possibles et sélectionnant celui qui a le meilleur score). La recherche arborescente se termine lorsqu'elle voit une position précédemment vue (à l'aide de la fonction table de transposition ), lorsqu'il atteint une limite de profondeur prédéfinie, ou lorsqu'il atteint un état du plateau hautement improbable (par exemple, il a été atteint en obtenant 6 tuiles "4" d'affilée depuis la position de départ). La profondeur de recherche typique est de 4 à 8 coups.

Heuristique

Plusieurs heuristiques sont utilisées pour diriger l'algorithme d'optimisation vers des positions favorables. Le choix précis de l'heuristique a un effet considérable sur les performances de l'algorithme. Les différentes heuristiques sont pondérées et combinées en un score positionnel, qui détermine la "bonne" position d'un échiquier donné. La recherche d'optimisation vise alors à maximiser le score moyen de toutes les positions de plateau possibles. Le score réel, tel qu'il apparaît dans le jeu, est le suivant no utilisé pour calculer le score du conseil, car il est trop fortement pondéré en faveur de la fusion des tuiles (lorsque la fusion retardée pourrait produire un grand avantage).

Au départ, j'ai utilisé deux heuristiques très simples, accordant des "bonus" pour les carrés ouverts et pour avoir de grandes valeurs sur le bord. Ces heuristiques ont donné d'assez bons résultats, atteignant fréquemment 16384 mais jamais 32768.

Petr Morávek (@xificurk) a pris mon IA et y a ajouté deux nouvelles heuristiques. La première heuristique consistait en une pénalité pour les rangs et les colonnes non monotones, qui augmentait à mesure que les rangs augmentaient, de sorte que les rangs non monotones de petits nombres n'affectent pas fortement le score, mais que les rangs non monotones de grands nombres le pénalisent considérablement. La deuxième heuristique comptait le nombre de fusions potentielles (valeurs égales adjacentes) en plus des espaces ouverts. Ces deux heuristiques ont servi à pousser l'algorithme vers les tableaux monotones (qui sont plus faciles à fusionner) et vers les positions de tableau avec beaucoup de fusions (l'encourageant à aligner les fusions lorsque cela est possible pour un meilleur effet).

En outre, Petr a également optimisé les poids heuristiques à l'aide d'une stratégie de "méta-optimisation" (en utilisant un algorithme appelé CMA-ES ), où les pondérations elles-mêmes ont été ajustées pour obtenir le score moyen le plus élevé possible.

L'effet de ces changements est extrêmement important. L'algorithme est passé de l'obtention de la tuile 16384 environ 13 % du temps à l'obtention de cette tuile plus de 90 % du temps, et l'algorithme a commencé à obtenir 32768 plus d'un tiers du temps (alors que l'ancienne heuristique ne produisait jamais une tuile 32768).

Je pense qu'il est encore possible d'améliorer l'heuristique. Cet algorithme n'est certainement pas encore "optimal", mais je pense qu'il s'en rapproche.

---

Le fait que l'IA réussisse à atteindre la tuile 32768 dans plus d'un tiers de ses parties est une étape importante ; je serais surpris d'apprendre qu'un joueur humain a réussi à atteindre 32768 sur le jeu officiel (c'est-à-dire sans utiliser d'outils comme les sauvegardes ou l'annulation). Je pense que la tuile 65536 est à portée de main !

Vous pouvez essayer l'IA par vous-même. Le code est disponible à l'adresse suivante https://github.com/nneonneo/2048-ai .

Answer 2

Je suis l'auteur du programme d'IA que d'autres ont mentionné dans ce fil. Vous pouvez voir l'IA dans action ou lire le source .

Actuellement, le programme atteint un taux de victoire d'environ 90 % en fonctionnant en javascript dans le navigateur de mon ordinateur portable, avec un temps de réflexion d'environ 100 millisecondes par coup, donc même s'il n'est pas parfait (encore !), il fonctionne plutôt bien.

Puisque le jeu est un espace d'état discret, une information parfaite, un jeu au tour par tour comme les échecs et les dames, j'ai utilisé les mêmes méthodes qui ont prouvé leur efficacité sur ces jeux, à savoir minimax recherche con élagage alpha-beta . Puisqu'il existe déjà beaucoup d'informations sur cet algorithme, je vais me contenter de parler des deux principales heuristiques que j'utilise dans l'application fonction d'évaluation statique et qui formalisent bon nombre des intuitions que d'autres personnes ont exprimées ici.

Monotonicité

Cette heuristique tente de s'assurer que les valeurs des tuiles sont toutes soit croissantes soit décroissantes dans les directions gauche/droite et haut/bas. Cette heuristique capture à elle seule l'intuition que beaucoup d'autres ont mentionnée, à savoir que les tuiles de valeur supérieure devraient être regroupées dans un coin. Elle permet généralement d'éviter que des tuiles de plus petite valeur ne deviennent orphelines et de garder le plateau très organisé, avec des tuiles de plus petite taille qui s'insèrent en cascade dans les tuiles de plus grande taille.

Voici une capture d'écran d'une grille parfaitement monotone. Je l'ai obtenue en exécutant l'algorithme avec la fonction eval configurée pour ignorer les autres heuristiques et ne considérer que la monotonicité.

Douceur

L'heuristique ci-dessus tend à elle seule à créer des structures dans lesquelles les tuiles adjacentes ont une valeur décroissante, mais bien sûr, pour fusionner, les tuiles adjacentes doivent avoir la même valeur. Par conséquent, l'heuristique de lissage mesure simplement la différence de valeur entre les tuiles voisines, en essayant de minimiser ce compte.

Un commentateur sur Hacker News a donné une formalisation intéressante de cette idée en termes de théorie des graphes.

Voici une capture d'écran d'une grille parfaitement lisse, avec l'aimable autorisation de la Commission européenne. cette excellente fourchette parodique .

Carreaux gratuits

Enfin, le fait d'avoir trop peu de tuiles libres est pénalisant, car les options peuvent rapidement s'épuiser lorsque le plateau de jeu devient trop étroit.

Et c'est tout ! Rechercher dans l'espace de jeu tout en optimisant ces critères permet d'obtenir des performances remarquablement bonnes. L'avantage d'utiliser une approche généralisée comme celle-ci plutôt qu'une stratégie de déplacement explicitement codée est que l'algorithme peut souvent trouver des solutions intéressantes et inattendues. Si vous le regardez fonctionner, il fera souvent des mouvements surprenants mais efficaces, comme changer soudainement le mur ou le coin contre lequel il construit.

Editar:

Voici une démonstration de la puissance de cette approche. Je n'ai pas plafonné les valeurs des tuiles (de sorte qu'il a continué après avoir atteint 2048) et voici le meilleur résultat après huit essais.

Oui, c'est un 4096 à côté d'un 2048. =) Cela signifie qu'il a atteint l'insaisissable tuile 2048 trois fois sur la même planche.

Answer 3

J'ai commencé à m'intéresser à l'idée d'une IA pour ce jeu contenant pas d'intelligence codée en dur (c'est-à-dire pas d'heuristique, de fonctions de notation, etc.) L'IA doit "savoir" seulement les règles du jeu, et "comprendre" le jeu. Ceci est en contraste avec la plupart des IA (comme celles de ce fil) où le jeu est essentiellement de la force brute dirigée par une fonction de notation représentant la compréhension humaine du jeu.

Algorithme d'IA

J'ai trouvé un algorithme de jeu simple mais étonnamment bon : Afin de déterminer le prochain coup pour un plateau donné, l'IA joue le jeu en mémoire en utilisant les éléments suivants mouvements aléatoires jusqu'à ce que le jeu soit terminé. Ceci est fait plusieurs fois tout en gardant la trace du score de fin de partie. Ensuite, le score moyen de fin de partie par coup de départ est calculé. Le coup de départ ayant le score final moyen le plus élevé est choisi comme coup suivant.

Avec seulement 100 exécutions (c'est-à-dire des parties en mémoire) par coup, l'IA atteint la tuile 2048 dans 80 % des cas et la tuile 4096 dans 50 % des cas. En utilisant 10000 exécutions, on obtient la tuile 2048 à 100%, 70% pour la tuile 4096, et environ 1% pour la tuile 8192.

Voyez-le en action

Le meilleur score obtenu est indiqué ici :

Un fait intéressant concernant cet algorithme est que, alors que les jeux aléatoires sont, sans surprise, assez mauvais, le choix du meilleur (ou du moins mauvais) coup conduit à un très bon jeu : Une partie d'IA typique peut atteindre 70000 points et durer 3000 coups, mais les parties aléatoires en mémoire à partir d'une position donnée rapportent en moyenne 340 points supplémentaires en environ 40 coups de plus avant de mourir. (Vous pouvez le constater par vous-même en exécutant l'IA et en ouvrant la console de débogage).

Ce graphique illustre ce point : La ligne bleue montre le score du tableau après chaque coup. La ligne rouge montre le résultat de l'algorithme meilleur un score de fin de partie aléatoire depuis cette position. En fait, les valeurs rouges "tirent" les valeurs bleues vers elles, car elles constituent la meilleure estimation de l'algorithme. Il est intéressant de voir que la ligne rouge est juste un peu au-dessus de la ligne bleue à chaque point, alors que la ligne bleue continue à augmenter de plus en plus.

Je trouve assez surprenant que l'algorithme n'ait pas besoin de prévoir un bon jeu pour choisir les coups qui le produisent.

En cherchant plus tard, j'ai trouvé que cet algorithme pouvait être classé comme un Recherche arborescente pure de Monte Carlo algorithme.

Mise en œuvre et liens

J'ai d'abord créé une version JavaScript qui peut être vu en action ici . Cette version peut exécuter des centaines de courses en un temps raisonnable. Ouvrez la console pour plus d'informations. ( source )

Plus tard, afin de jouer un peu plus, j'ai utilisé l'infrastructure hautement optimisée de @nneonneo et implémenté ma version en C++. Cette version permet jusqu'à 100000 exécutions par coup et même 1000000 si vous avez la patience. Les instructions de construction sont fournies. Il fonctionne dans la console et a aussi une télécommande pour jouer la version web. ( source )

Résultats

De manière surprenante, l'augmentation du nombre de courses n'améliore pas radicalement le jeu. Il semble y avoir une limite à cette stratégie à environ 80000 points avec la tuile 4096 et toutes les plus petites, très proche de la réalisation de la tuile 8192. En augmentant le nombre de courses de 100 à 100000, on augmente le nombre de points. cote d'atteindre cette limite de score (de 5% à 40%) mais de ne pas la franchir.

En effectuant 10000 runs avec une augmentation temporaire à 1000000 près des positions critiques, nous avons réussi à franchir cette barrière moins d'1% du temps en atteignant un score maximal de 129892 et la tuile 8192.

Améliorations

Après avoir implémenté cet algorithme, j'ai essayé de nombreuses améliorations, notamment l'utilisation des scores min ou max, ou une combinaison de min, max et moyenne. J'ai également essayé d'utiliser la profondeur : au lieu d'essayer K courses par coup, j'ai essayé K coups par coup. liste d'une longueur donnée ("haut, haut, gauche" par exemple) et en sélectionnant le premier coup de la liste des coups les mieux notés.

Plus tard, j'ai implémenté un arbre de notation qui prenait en compte la probabilité conditionnelle d'être capable de jouer un coup après une liste de coups donnée.

Cependant, aucune de ces idées ne présentait de réel avantage par rapport à la première idée simple. J'ai laissé le code pour ces idées commenté dans le code C++.

J'ai ajouté un mécanisme de "recherche approfondie" qui augmente temporairement le nombre de passages à 1000000 lorsque l'un d'entre eux réussit à atteindre accidentellement la prochaine tuile la plus élevée. Cela a permis une amélioration du temps.

Je serais intéressé d'entendre si quelqu'un a d'autres idées d'amélioration qui maintiennent l'indépendance de l'IA par rapport au domaine.

2048 Variantes et clones

Juste pour le plaisir, j'ai aussi implémentation de l'IA en tant que bookmarklet en se connectant aux commandes du jeu. Cela permet à l'IA de fonctionner avec le jeu original et plusieurs de ses variantes .

Cela est possible grâce à la nature indépendante du domaine de l'IA. Certaines variantes sont assez distinctes, comme le clone Hexagonal.

Answer 4

EDITAR: Il s'agit d'un algorithme naïf, qui modélise le processus de pensée conscient de l'homme, et qui obtient des résultats très faibles par rapport aux IA qui recherchent toutes les possibilités, car il ne regarde qu'une seule tuile à l'avance. Il a été soumis au début du délai de réponse.

J'ai affiné l'algorithme et battu le jeu ! Il peut échouer à cause d'une simple malchance vers la fin (vous êtes obligé de vous déplacer vers le bas, ce que vous ne devriez jamais faire, et une tuile apparaît là où votre plus haute devrait être. Essayez simplement de garder la rangée supérieure remplie, de sorte qu'un déplacement vers la gauche ne casse pas le motif), mais fondamentalement, vous vous retrouvez avec une partie fixe et une partie mobile avec lesquelles jouer. C'est votre objectif :

C'est le modèle que j'ai choisi par défaut.

1024 512 256 128
  8   16  32  64
  4   2   x   x
  x   x   x   x

Le coin choisi est arbitraire, vous n'appuyez pratiquement jamais sur une touche (le coup interdit), et si vous le faites, vous appuyez à nouveau sur le contraire et essayez de le réparer. Pour les tuiles futures, le modèle s'attend toujours à ce que la prochaine tuile aléatoire soit un 2 et apparaisse du côté opposé au modèle actuel (tant que la première rangée est incomplète, dans le coin inférieur droit, une fois la première rangée terminée, dans le coin inférieur gauche).

Voici l'algorithme. Environ 80% de victoires (il semble qu'il soit toujours possible de gagner avec des techniques d'IA plus "professionnelles", mais je n'en suis pas sûr).

initiateModel();

while(!game_over)
{    
    checkCornerChosen(); // Unimplemented, but it might be an improvement to change the reference point

    for each 3 possible move:
        evaluateResult()
    execute move with best score
    if no move is available, execute forbidden move and undo, recalculateModel()
 }

 evaluateResult() {
     calculatesBestCurrentModel()
     calculates distance to chosen model
     stores result
 }

 calculateBestCurrentModel() {
      (according to the current highest tile acheived and their distribution)
  }

Quelques indications sur les étapes manquantes. Ici :

Le modèle a été modifié par la chance d'être plus proche du modèle attendu. Le modèle que l'IA essaie d'atteindre est

 512 256 128  x
  X   X   x   x
  X   X   x   x
  x   x   x   x

Et la chaîne pour y arriver est devenue :

 512 256  64  O
  8   16  32  O
  4   x   x   x
  x   x   x   x

El O représentent des espaces interdits...

Ainsi, il appuiera à droite, puis à nouveau à droite, puis (à droite ou en haut en fonction de l'endroit où le 4 a créé), puis il continuera à compléter la chaîne jusqu'à ce qu'il obtienne :

Donc maintenant le modèle et la chaîne sont de retour :

 512 256 128  64
  4   8  16   32
  X   X   x   x
  x   x   x   x

Deuxième pointeur, il n'a pas eu de chance et sa place principale a été prise. Il est probable qu'il échoue, mais il peut encore y parvenir :

Voici le modèle et la chaîne :

  O 1024 512 256
  O   O   O  128
  8  16   32  64
  4   x   x   x

Lorsqu'il parvient à atteindre les 128 qu'il a gagnés, une rangée entière est à nouveau gagnée :

  O 1024 512 256
  x   x  128 128
  x   x   x   x
  x   x   x   x

Answer 5

Je copie ici le contenu d'un article sur mon blog

---

La solution que je propose est très simple et facile à mettre en œuvre. Pourtant, elle a atteint le score de 131040. Plusieurs benchmarks des performances de l'algorithme sont présentés.

Algorithme

Algorithme de notation heuristique

L'hypothèse sur laquelle repose mon algorithme est assez simple : si vous voulez obtenir un score plus élevé, le plateau doit être maintenu aussi ordonné que possible. En particulier, la configuration optimale est donnée par un ordre linéaire et monotone décroissant des valeurs des tuiles. Cette intuition vous donnera également la limite supérieure de la valeur d'une tuile : où n est le nombre de tuiles sur le plateau.

(Il y a une possibilité d'atteindre la tuile 131072 si la tuile 4 est générée aléatoirement au lieu de la tuile 2 lorsque cela est nécessaire).

Les images suivantes montrent deux façons possibles d'organiser le tableau :

Pour imposer l'ordination des tuiles dans un ordre décroissant monotone, le score est calculé comme la somme des valeurs linéarisées sur le tableau multipliée par les valeurs d'une séquence géométrique avec un rapport commun r<1 .

Plusieurs chemins linéaires peuvent être évalués en même temps, le score final sera le score maximum de chaque chemin.

Règle de décision

La règle de décision implémentée n'est pas tout à fait intelligente, le code en Python est présenté ici :

@staticmethod
def nextMove(board,recursion_depth=3):
    m,s = AI.nextMoveRecur(board,recursion_depth,recursion_depth)
    return m

@staticmethod
def nextMoveRecur(board,depth,maxDepth,base=0.9):
    bestScore = -1.
    bestMove = 0
    for m in range(1,5):
        if(board.validMove(m)):
            newBoard = copy.deepcopy(board)
            newBoard.move(m,add_tile=True)

            score = AI.evaluate(newBoard)
            if depth != 0:
                my_m,my_s = AI.nextMoveRecur(newBoard,depth-1,maxDepth)
                score += my_s*pow(base,maxDepth-depth+1)

            if(score > bestScore):
                bestMove = m
                bestScore = score
    return (bestMove,bestScore);

Une implémentation du minmax ou de l'Expectiminimax améliorera sûrement l'algorithme. Il est évident qu'une règle de décision plus Bien évidemment, une règle de décision plus sophistiquée ralentira l'algorithme et nécessitera un certain temps pour être mise en œuvre. (restez à l'écoute)

Point de repère

• T1 - 121 tests - 8 chemins différents - r=0.125
• T2 - 122 tests - 8 voies différentes - r=0,25
• T3 - 132 tests - 8 chemins différents - r=0.5
• T4 - 211 tests - 2 chemins différents - r=0.125
• T5 - 274 tests - 2 chemins différents - r=0.25
• T6 - 211 tests - 2 chemins différents - r=0.5

Dans le cas de T2, quatre tests sur dix génèrent la tuile 4096 avec un score moyen de 42000

Code

Le code peut être trouvé sur GiHub au lien suivant : https://github.com/Nicola17/term2048-AI Il est basé sur terme2048 et il est écrit en Python. Je vais implémenter une version plus efficace en C++ dès que possible.