Quel est l’algorithme optimal pour le jeu 2048?

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 créer des tuiles “plus grandes”. Après chaque mouvement, une nouvelle tuile apparaît au hasard dans une position avec une valeur de 2 ou 4 . Le jeu se termine lorsque toutes les cases sont remplies et qu’aucun mouvement ne peut fusionner les tuiles ou que vous créez une tuile d’une valeur de 2048 .

Premièrement, je dois suivre une stratégie bien définie pour atteindre l’objective. 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 est à tout moment, je vais essayer de fusionner les tuiles avec les valeurs 2 et 4 , c’est-à-dire que j’essaie d’avoir 2 et 4 tuiles au minimum. Si je l’essaye de cette façon, toutes les autres tuiles sont automatiquement fusionnées et la stratégie semble bonne.

Mais lorsque j’utilise cet algorithme, je ne dispose que de 4 000 points environ avant la fin du jeu. Maximum de points L’AFAIK est légèrement supérieur à 20 000 points, ce qui est beaucoup plus important que mon score actuel. Existe-t-il un meilleur algorithme que celui ci-dessus?

    J’ai développé une IA 2048 en utilisant l’optimisation expectimax , au lieu de la recherche minimax utilisée par l’algorithme de @ ovolve. L’IA effectue simplement une maximisation de tous les mouvements possibles, suivie d’une espérance sur toutes les crêtes de tuiles possibles (pondérée par la probabilité des tuiles, soit 10% pour un 4 et 90% pour un 2). Autant que je sache, il n’est pas possible d’élaguer l’optimisation expectimax (sauf pour supprimer des twigs extrêmement improbables), et l’algorithme utilisé est une recherche de force brute soigneusement optimisée.

    Performance

    L’IA dans sa configuration par défaut (profondeur de recherche maximale de 8) peut durer de 10 ms à 200 ms pour exécuter un déplacement, en fonction de la complexité de la position de la carte. 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 mouvements, l’IA peut facilement exécuter plus de 20 mouvements par seconde, ce qui rend la surveillance intéressante .

    Pour évaluer la performance au score de l’IA, j’ai couru l’AI 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é réalisée au moins une fois:

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

    Le score minimum sur toutes les courses était 124024; le score maximum obtenu était de 794076. Le score médian est de 387222. L’IA n’a jamais manqué d’obtenir la tuile de 2048 (elle n’a donc jamais perdu la partie une seule fois en 100 parties); en fait, il a atteint la tuile 8192 au moins une fois dans chaque course!

    Voici la capture d’écran du meilleur run:

    32768 tuile, score 794076

    Ce jeu a nécessité 27830 mouvements en 96 minutes, soit une moyenne de 4,8 coups par seconde.

    la mise en oeuvre

    Mon approche encode la carte entière (16 entrées) sous la forme d’un entier simple de 64 bits (où les tuiles sont les nybbles, c’est-à-dire les morceaux de 4 bits). Sur une machine 64 bits, cela permet de faire circuler l’intégralité de la carte 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, donc une table de taille 65536 peut encoder des transformations qui fonctionnent sur une seule ligne ou colonne. Par exemple, les déplacements sont implémentés comme 4 recherches dans une “table d’effet de déplacement” précalculée, qui décrit comment chaque mouvement affecte une seule ligne ou colonne (par exemple, la table “déplacer à droite” contient l’entrée “1122 -> 0023”). row [2,2,4,4] devient la ligne [0,0,4,8] lorsqu’elle est déplacée vers la droite).

    L’évaluation est également effectuée à l’aide de la table de consultation. Les tableaux contiennent des scores heuristiques calculés sur toutes les lignes / colonnes possibles, et le résultat obtenu pour un tableau est simplement la sum des valeurs des tables sur chaque ligne et chaque colonne.

    Cette représentation de carte, associée à l’approche de recherche de table pour le mouvement et le score, permet à l’IA de rechercher rapidement un grand nombre d’états de jeu (plus de 10 000 000 par seconde).

    La recherche expectimax elle-même est codée comme une recherche récursive qui alterne entre les étapes “d’attente” (test de tous les emplacements et valeurs possibles de pondération et pondération de leurs scores optimisés par la probabilité de chaque possibilité) et les étapes de “maximisation” et en sélectionnant celui qui a le meilleur score). La recherche dans l’arborescence se termine lorsqu’elle détecte une position précédemment vue (à l’aide d’un tableau de transposition ), lorsqu’elle atteint une limite de profondeur prédéfinie ou lorsqu’elle atteint un état hautement improbable (par exemple, elle a obtenu 6 tuiles de 4 pouces) à la suite de la position de départ). La profondeur de recherche typique est de 4 à 8 mouvements.

    Heuristique

    Plusieurs heuristiques permettent d’orienter l’algorithme d’optimisation vers des positions favorables. Le choix précis de l’heuristique a un effet énorme sur les performances de l’algorithme. Les différentes heuristiques sont pondérées et combinées en un score de position qui détermine la “bonne” position du tableau. La recherche d’optimisation visera alors à maximiser le score moyen de toutes les positions possibles du conseil. Le score réel, tel qu’indiqué par le jeu, n’est pas utilisé pour calculer le score du tableau, car il est trop fortement en faveur de la fusion des tuiles (lorsque la fusion retardée peut générer un avantage important).

    Au départ, j’ai utilisé deux heuristiques très simples, accordant des “bonus” pour les carrés ouverts et des valeurs importantes sur le bord. Ces heuristiques ont plutôt bien fonctionné, atteignant fréquemment 16384 mais jamais 32768.

    Petr Morávek (@xificurk) a pris mon IA et ajouté deux nouvelles heuristiques. La première heuristique était une pénalité pour avoir des lignes et des colonnes non monotones qui augmentaient à mesure que les rangs augmentaient, garantissant que les rangées non monotones de petits nombres n’affecteraient pas fortement le score, mais les rangées non monotones La seconde heuristique a compté le nombre de fusions potentielles (valeurs égales adjacentes) en plus des espaces ouverts. Ces deux heuristiques ont servi à pousser l’algorithme vers des cartes monotones (qui sont plus faciles à fusionner) et vers des positions de carte avec beaucoup de fusions (en les encourageant à aligner les fusions si possible pour un effet plus important).

    De plus, Petr a également optimisé les poids heuristiques en utilisant une stratégie de «méta-optimisation» (utilisant un algorithme appelé CMA-ES ), où les poids eux-mêmes ont été ajustés pour obtenir le score moyen le plus élevé possible.

    L’effet de ces changements est extrêmement important. L’algorithme est passé de la réalisation de la mosaïque 16384 à environ 13% du temps pour atteindre 90% du temps, et l’algorithme a commencé à atteindre 32768 sur 1/3 du temps (alors que les anciennes heuristiques ne produisaient jamais une mosaïque 32768) .

    Je pense qu’il y a encore place à l’amélioration de l’heuristique. Cet algorithme n’est certainement pas encore “optimal”, mais je pense que cela devient assez proche.


    Le fait que l’IA atteigne les 32768 dans plus d’un tiers de ses jeux est une étape importante. Je serai surpris d’apprendre si des joueurs humains ont réussi 32768 sur le jeu officiel (sans utiliser d’outils comme des sauvegardes ou des sauvegardes). Je pense que la tuile 65536 est à scope de main!

    Vous pouvez essayer l’IA pour vous-même. Le code est disponible sur https://github.com/nneonneo/2048-ai .

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

    Actuellement, le programme atteint un taux de réussite de 90% en javascript dans le navigateur de mon ordinateur portable, avec environ 100 millisecondes de temps de reflection par mouvement, ce qui n’est pas parfait (encore!) Mais fonctionne plutôt bien.

    Comme 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 éprouvées pour ces jeux, à savoir la recherche minimax avec élagage alpha-bêta . Comme il y a déjà beaucoup d’informations sur cet algorithme, je vais juste parler des deux heuristiques principales que j’utilise dans la fonction d’évaluation statique et qui formalisent beaucoup des intuitions exprimées par d’autres personnes.

    Monotonicité

    Cette heuristique essaie de s’assurer que les valeurs des tuiles augmentent ou diminuent toutes les deux 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 plus grande valeur doivent être regroupées dans un coin. Cela empêchera généralement les petites tuiles de devenir orphelines et gardera la carte très organisée, avec des tuiles plus petites qui se déversent dans les tuiles plus grandes.

    Voici une capture d’écran d’une grid parfaitement monotone. J’ai obtenu cela en exécutant l’algorithme avec la fonction eval définie pour ignorer les autres heuristiques et ne considérer que la monotonie.

    Une carte 2048 parfaitement monotone

    Douceur

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

    Un commentateur de Hacker News a formalisé cette idée en termes de théorie des graphes.

    Voici une capture d’écran d’une grid parfaitement lisse, grâce à cette excellente fourchette de parodie .

    Une planche 2048 parfaitement lisse

    Tuiles Gratuites

    Et enfin, il y a une pénalité pour avoir trop peu de tuiles gratuites, car les options peuvent rapidement s’épuiser lorsque le plateau de jeu devient trop étroit.

    Et c’est tout! La recherche dans l’espace de jeu tout en optimisant ces critères produit des performances remarquables. Un avantage de l’utilisation d’une approche généralisée comme celle-ci plutôt que d’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 tourner, il fera souvent des mouvements surprenants mais efficaces, comme changer soudainement le mur ou le coin contre lequel il se construit.

    Modifier:

    Voici une démonstration de la puissance de cette approche. J’ai décapsulé les valeurs de tuiles (donc il a continué après 2048) et voici le meilleur résultat après huit essais.

    4096

    Oui, c’est un 4096 à côté d’un 2048. =) Cela signifie qu’il a réussi à atteindre l’insaisissable 2048 tuiles trois fois sur le même plateau.

    EDIT: Il s’agit d’un algorithme naïf, qui modélise le processus de la pensée humaine consciente et qui donne de très faibles résultats par rapport à l’IA qui recherche toutes les possibilités car elle ne regarde qu’une seule tuile. Il a été soumis tôt dans la chronologie des réponses.

    J’ai affiné l’algorithme et battu le jeu! Cela peut échouer à cause de la simple malchance près de la fin (vous êtes obligé de descendre, ce que vous ne devriez jamais faire, et une tuile apparaît là où votre plus haut niveau devrait être). briser le modèle), mais fondamentalement, vous finissez par avoir une partie fixe et une partie mobile à jouer avec. Ceci est votre objective:

    Prêt à finir

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

     1024 512 256 128 8 16 32 64 4 2 xx xxxx 

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

    Ici va l’algorithme. Environ 80% des gagnants (il semble qu’il est toujours possible de gagner avec des techniques d’IA plus “professionnelles”, 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 dissortingbution) } 

    Quelques indications sur les étapes manquantes. Ici: changement de modèle

    Le modèle a changé en raison de la chance d’être plus proche du modèle attendu. Le modèle que l’IA tente d’atteindre est

      512 256 128 x XX xx XX xx xxxx 

    Et la chaîne pour y arriver est devenue:

      512 256 64 O 8 16 32 O 4 xxx xxxx 

    Les O représentent des espaces interdits …

    Donc, il va appuyer à droite, puis à nouveau à droite, puis (à droite ou en haut, selon l’endroit où le 4 a été créé), puis procédera à compléter la chaîne jusqu’à ce qu’il obtienne:

    Chaîne terminée

    Alors maintenant, le modèle et la chaîne reviennent à:

      512 256 128 64 4 8 16 32 XX xx xxxx 

    Deuxième pointeur, il a eu de la malchance et sa place principale a été prise. Il est probable que cela échouera, mais il peut toujours y parvenir:

    Entrez la description de l'image ici

    Ici, le modèle et la chaîne sont:

      O 1024 512 256 OOO 128 8 16 32 64 4 xxx 

    Quand il parvient à atteindre les 128, il gagne une ligne entière:

      O 1024 512 256 xx 128 128 xxxx xxxx 

    Je me suis intéressé à l’idée d’une IA pour ce jeu ne contenant aucune intelligence codée en dur (c.-à-d. Pas d’heuristique, de fonctions de notation, etc.). L’IA ne doit “connaître” que les règles du jeu et “comprendre” le jeu. Cela contraste avec la plupart des IA (comme celles dans ce fil) où le jeu est essentiellement une force brute dirigée par une fonction de notation représentant la compréhension humaine du jeu.

    Algorithme AI

    J’ai trouvé un algorithme de jeu simple mais étonnamment bon: pour déterminer le prochain mouvement d’un tableau donné, l’IA joue le jeu en mémoire en utilisant des coups aléatoires jusqu’à la fin du jeu. Cela se fait plusieurs fois tout en gardant une trace du score de fin de partie. Ensuite, le score final moyen par coup de départ est calculé. Le coup de départ avec le score de fin moyen le plus élevé est choisi comme prochain coup.

    Avec seulement 100 courses (c.-à-d. Dans les jeux de mémoire) par coup, l’IA atteint les 2048 tuiles 80% des fois et les 4096 tuiles 50% des fois. En utilisant 10000 courses, vous obtenez 2048 tuiles 100%, 70% pour 4096 tuiles et environ 1% pour la tuile 8192.

    Voir en action

    Le meilleur score obtenu est montré ici:

    meilleur score

    Un fait intéressant à propos de cet algorithme est que, bien que les jeux aléatoires soient sans surprise assez mauvais, le choix du meilleur (ou du moins mauvais) jeu conduit à un très bon jeu: un jeu AI typique peut atteindre 70000 points et 3000 derniers mouvements. Les jeux en mémoire aléatoires à partir de n’importe quelle position donnent en moyenne 340 points supplémentaires en environ 40 coups supplémentaires avant de mourir. (Vous pouvez le voir 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 indique le score du tableau après chaque coup. La ligne rouge indique le meilleur score de fin de partie aléatoire de l’algorithme à partir de cette position. Essentiellement, les valeurs rouges tirent les valeurs bleues vers le haut, car elles sont 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, mais la ligne bleue continue à augmenter de plus en plus.

    graphique de notation

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

    En cherchant plus tard, j’ai trouvé que cet algorithme pouvait être classé comme un algorithme de recherche Pure Monte Carlo .

    Mise en œuvre et liens

    J’ai d’abord créé une version JavaScript visible en action ici . Cette version peut exécuter 100 des exécutions en temps décent. Ouvrez la console pour plus d’informations. ( source )

    Plus tard, pour jouer encore un peu, j’ai utilisé une infrastructure hautement optimisée @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. Instructions de construction fournies. Il fonctionne dans la console et dispose également d’une télécommande pour lire la version Web. ( source )

    Résultats

    Étonnamment, l’augmentation du nombre de courses n’améliore pas considérablement le jeu. Il semble y avoir une limite à cette stratégie autour de 80000 points avec la tuile 4096 et toutes les plus petites, très proches de la tuile 8192. L’augmentation du nombre de passages de 100 à 100 000 augmente les chances de parvenir à cette limite de score (de 5% à 40%), mais sans la dépasser.

    En exécutant 10000 exécutions avec une augmentation temporaire à 1000000 près des positions critiques, nous avons réussi à franchir cette barrière moins de 1% des fois, obtenant un score maximum de 129892 et une tuile 8192.

    Améliorations

    Après avoir implémenté cet algorithme, j’ai essayé de nombreuses améliorations, y compris l’utilisation des scores min ou max, ou une combinaison de min, max et avg. J’ai aussi essayé d’utiliser la profondeur: au lieu d’essayer K courses par coup, j’ai essayé K coups par liste de mouvement d’une longueur donnée (“haut, haut, gauche” par exemple) et sélection du premier mouvement de la liste des meilleurs scores.

    Plus tard, j’ai implémenté un arbre de notation prenant en compte la probabilité conditionnelle de pouvoir jouer un coup après une liste de coups donnée.

    Cependant, aucune de ces idées n’a montré d’avantage réel 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 “Deep Search” qui a augmenté temporairement le nombre d’exécutions à 1000000 lorsque l’une des exécutions a réussi à atteindre accidentellement la tuile suivante. Cela a offert une amélioration de temps.

    Je serais intéressé d’apprendre si quelqu’un a d’autres idées d’amélioration qui préservent l’indépendance de domaine de l’IA.

    2048 Variantes et clones

    Juste pour le fun, j’ai également implémenté l’IA comme bookmarklet , en m’accrochant aux commandes du jeu. Cela permet à l’IA de travailler avec le jeu d’origine et plusieurs de ses variantes .

    Ceci est possible en raison de la nature indépendante du domaine de l’IA. Certaines variantes sont assez distinctes, telles que le clone hexagonal.

    Je copie ici le contenu d’un post sur mon blog


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

    But

    Algorithme

    Algorithme de notation heuristique

    L’hypothèse sur laquelle est basé mon algorithme est plutôt simple: si vous souhaitez obtenir un score plus élevé, le tableau doit être aussi soigné que possible. En particulier, la configuration optimale est donnée par un ordre décroissant linéaire et monotone des valeurs de tuile. Cette intuition vous donnera également la limite supérieure pour une valeur de tuile: s où n est le nombre de tuiles sur le tableau.

    (Il y a une possibilité d’atteindre la tuile 131072 si les 4 tuiles sont générées au hasard au lieu des 2 tuiles si nécessaire)

    Les deux manières suivantes d’organiser le tableau sont présentées dans les images suivantes:

    entrer la description de l'image ici

    Pour imposer l’ordination des carreaux dans un ordre décroissant monotone, le score si calculé comme la sum des valeurs linéarisées sur le tableau multiplié par les valeurs d’une séquence géomésortingque avec un rapport commun r <1.

    s

    s

    Plusieurs trajectoires linéaires pourraient être évaluées à la fois, le score final étant le score maximum de n’importe quel chemin.

    Règle de décision

    La règle de décision implémentée n’est pas très 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. Évidemment, une règle de décision plus sophistiquée ralentira l’algorithme et il faudra du temps pour la mettre en œuvre. Je tenterai une implémentation de minimax dans un avenir proche. (Restez à l’écoute)

    Référence

    • T1 – 121 tests – 8 chemins différents – r = 0,125
    • T2 – 122 tests – 8 chemins différents – 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

    entrer la description de l'image icientrer la description de l'image icientrer la description de l'image icientrer la description de l'image ici

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

    Code

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

    Ma tentative utilise expectimax comme les autres solutions ci-dessus, mais sans bitboard. La solution de Nneonneo peut vérifier 10 millions de mouvements, soit une profondeur d’environ 4 avec 6 cases restantes et 4 mouvements possibles (2 * 6 * 4) 4 . Dans mon cas, cette profondeur prend trop de temps à explorer, j’ajuste la profondeur de la recherche expectimax en fonction du nombre de tuiles libres restantes:

     depth = free > 7 ? 1 : (free > 4 ? 2 : 3) 

    Les scores des cartes sont calculés avec la sum pondérée du carré du nombre de tuiles libres et du produit scalaire de la grid 2D avec ceci:

     [[10,8,7,6.5], [.5,.7,1,3], [-.5,-1.5,-1.8,-2], [-3.8,-3.7,-3.5,-3]] 

    ce qui oblige à organiser les tuiles de manière descendante dans une sorte de serpent de la tuile supérieure gauche.

    Code ci-dessous ou jsbin :

     var n = 4, M = new MasortingxTransform(n); var ai = {weights: [1, 1], depth: 1}; // depth=1 by default, but we adjust it on every prediction according to the number of free tiles var snake= [[10,8,7,6.5], [.5,.7,1,3], [-.5,-1.5,-1.8,-2], [-3.8,-3.7,-3.5,-3]] snake=snake.map(function(a){return a.map(Math.exp)}) initialize(ai) function run(ai) { var p; while ((p = predict(ai)) != null) { move(p, ai); } //console.log(ai.grid , maxValue(ai.grid)) ai.maxValue = maxValue(ai.grid) console.log(ai) } function initialize(ai) { ai.grid = []; for (var i = 0; i < n; i++) { ai.grid[i] = [] for (var j = 0; j < n; j++) { ai.grid[i][j] = 0; } } rand(ai.grid) rand(ai.grid) ai.steps = 0; } function move(p, ai) { //0:up, 1:right, 2:down, 3:left var newgrid = mv(p, ai.grid); if (!equal(newgrid, ai.grid)) { //console.log(stats(newgrid, ai.grid)) ai.grid = newgrid; try { rand(ai.grid) ai.steps++; } catch (e) { console.log('no room', e) } } } function predict(ai) { var free = freeCells(ai.grid); ai.depth = free > 7 ? 1 : (free > 4 ? 2 : 3); var root = {path: [],prob: 1,grid: ai.grid,children: []}; var x = expandMove(root, ai) //console.log("number of leaves", x) //console.log("number of leaves2", countLeaves(root)) if (!root.children.length) return null var values = root.children.map(expectimax); var mx = max(values); return root.children[mx[1]].path[0] } function countLeaves(node) { var x = 0; if (!node.children.length) return 1; for (var n of node.children) x += countLeaves(n); return x; } function expectimax(node) { if (!node.children.length) { return node.score } else { var values = node.children.map(expectimax); if (node.prob) { //we are at a max node return Math.max.apply(null, values) } else { // we are at a random node var avg = 0; for (var i = 0; i < values.length; i++) avg += node.children[i].prob * values[i] return avg / (values.length / 2) } } } function expandRandom(node, ai) { var x = 0; for (var i = 0; i < node.grid.length; i++) for (var j = 0; j < node.grid.length; j++) if (!node.grid[i][j]) { var grid2 = M.copy(node.grid), grid4 = M.copy(node.grid); grid2[i][j] = 2; grid4[i][j] = 4; var child2 = {grid: grid2,prob: .9,path: node.path,children: []}; var child4 = {grid: grid4,prob: .1,path: node.path,children: []} node.children.push(child2) node.children.push(child4) x += expandMove(child2, ai) x += expandMove(child4, ai) } return x; } function expandMove(node, ai) { // node={grid,path,score} var isLeaf = true, x = 0; if (node.path.length < ai.depth) { for (var move of[0, 1, 2, 3]) { var grid = mv(move, node.grid); if (!equal(grid, node.grid)) { isLeaf = false; var child = {grid: grid,path: node.path.concat([move]),children: []} node.children.push(child) x += expandRandom(child, ai) } } } if (isLeaf) node.score = dot(ai.weights, stats(node.grid)) return isLeaf ? 1 : x; } var cells = [] var table = document.querySelector("table"); for (var i = 0; i < n; i++) { var tr = document.createElement("tr"); cells[i] = []; for (var j = 0; j < n; j++) { cells[i][j] = document.createElement("td"); tr.appendChild(cells[i][j]) } table.appendChild(tr); } function updateUI(ai) { cells.forEach(function(a, i) { a.forEach(function(el, j) { el.innerHTML = ai.grid[i][j] || '' }) }); } updateUI(ai) function runAI() { var p = predict(ai); if (p != null && ai.running) { move(p, ai) updateUI(ai) requestAnimationFrame(runAI) } } runai.onclick = function() { if (!ai.running) { this.innerHTML = 'stop AI'; ai.running = true; runAI(); } else { this.innerHTML = 'run AI'; ai.running = false; } } hint.onclick = function() { hintvalue.innerHTML = ['up', 'right', 'down', 'left'][predict(ai)] } document.addEventListener("keydown", function(event) { if (event.which in map) { move(map[event.which], ai) console.log(stats(ai.grid)) updateUI(ai) } }) var map = { 38: 0, // Up 39: 1, // Right 40: 2, // Down 37: 3, // Left }; init.onclick = function() { initialize(ai); updateUI(ai) } function stats(grid, previousGrid) { var free = freeCells(grid); var c = dot2(grid, snake); return [c, free * free]; } function dist2(a, b) { //squared 2D distance return Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2) } function dot(a, b) { var r = 0; for (var i = 0; i < a.length; i++) r += a[i] * b[i]; return r } function dot2(a, b) { var r = 0; for (var i = 0; i < a.length; i++) for (var j = 0; j < a[0].length; j++) r += a[i][j] * b[i][j] return r; } function product(a) { return a.reduce(function(v, x) { return v * x }, 1) } function maxValue(grid) { return Math.max.apply(null, grid.map(function(a) { return Math.max.apply(null, a) })); } function freeCells(grid) { return grid.reduce(function(v, a) { return v + a.reduce(function(t, x) { return t + (x == 0) }, 0) }, 0) } function max(arr) { // return [value, index] of the max var m = [-Infinity, null]; for (var i = 0; i < arr.length; i++) { if (arr[i] > m[0]) m = [arr[i], i]; } return m } function min(arr) { // return [value, index] of the min var m = [Infinity, null]; for (var i = 0; i < arr.length; i++) { if (arr[i] < m[0]) m = [arr[i], i]; } return m } function maxScore(nodes) { var min = { score: -Infinity, path: [] }; for (var node of nodes) { if (node.score > min.score) min = node; } return min; } function mv(k, grid) { var tgrid = M.itransform(k, grid); for (var i = 0; i < tgrid.length; i++) { var a = tgrid[i]; for (var j = 0, jj = 0; j < a.length; j++) if (a[j]) a[jj++] = (j < a.length - 1 && a[j] == a[j + 1]) ? 2 * a[j++] : a[j] for (; jj < a.length; jj++) a[jj] = 0; } return M.transform(k, tgrid); } function rand(grid) { var r = Math.floor(Math.random() * freeCells(grid)), _r = 0; for (var i = 0; i < grid.length; i++) { for (var j = 0; j < grid.length; j++) { if (!grid[i][j]) { if (_r == r) { grid[i][j] = Math.random() < .9 ? 2 : 4 } _r++; } } } } function equal(grid1, grid2) { for (var i = 0; i < grid1.length; i++) for (var j = 0; j < grid1.length; j++) if (grid1[i][j] != grid2[i][j]) return false; return true; } function conv44valid(a, b) { var r = 0; for (var i = 0; i < 4; i++) for (var j = 0; j < 4; j++) r += a[i][j] * b[3 - i][3 - j] return r } function MatrixTransform(n) { var g = [], ig = []; for (var i = 0; i < n; i++) { g[i] = []; ig[i] = []; for (var j = 0; j < n; j++) { g[i][j] = [[j, i],[i, n-1-j],[j, n-1-i],[i, j]]; // transformation matrix in the 4 directions g[i][j] = [up, right, down, left] ig[i][j] = [[j, i],[i, n-1-j],[n-1-j, i],[i, j]]; // the inverse tranformations } } this.transform = function(k, grid) { return this.transformer(k, grid, g) } this.itransform = function(k, grid) { // inverse transform return this.transformer(k, grid, ig) } this.transformer = function(k, grid, mat) { var newgrid = []; for (var i = 0; i < grid.length; i++) { newgrid[i] = []; for (var j = 0; j < grid.length; j++) newgrid[i][j] = grid[mat[i][j][k][0]][mat[i][j][k][1]]; } return newgrid; } this.copy = function(grid) { return this.transform(3, grid) } } 
     body { text-align: center } table, th, td { border: 1px solid black; margin: 5px auto; } td { width: 35px; height: 35px; text-align: center; } 
     

    I am the author of a 2048 controller that scores better than any other program mentioned in this thread. An efficient implementation of the controller is available on github . In a separate repo there is also the code used for training the controller’s state evaluation function. The training method is described in the paper .

    The controller uses expectimax search with a state evaluation function learned from scratch (without human 2048 expertise) by a variant of temporal difference learning (a reinforcement learning technique). The state-value function uses an n-tuple network , which is basically a weighted linear function of patterns observed on the board. It involved more than 1 billion weights , in total.

    Performance

    At 1 moves/s: 609104 (100 games average)

    At 10 moves/s: 589355 (300 games average)

    At 3-ply (ca. 1500 moves/s): 511759 (1000 games average)

    The tile statistics for 10 moves/s are as follows:

     2048: 100% 4096: 100% 8192: 100% 16384: 97% 32768: 64% 32768,16384,8192,4096: 10% 

    (The last line means having the given tiles at the same time on the board).

    For 3-ply:

     2048: 100% 4096: 100% 8192: 100% 16384: 96% 32768: 54% 32768,16384,8192,4096: 8% 

    However, I have never observed it obtaining the 65536 tile.

    I think I found an algorithm which works quite well, as I often reach scores over 10000, my personal best being around 16000. My solution does not aim at keeping biggest numbers in a corner, but to keep it in the top row.

    Please see the code below:

     while( !game_over ) { move_direction=up; if( !move_is_possible(up) ) { if( move_is_possible(right) && move_is_possible(left) ){ if( number_of_empty_cells_after_moves(left,up) > number_of_empty_cells_after_moves(right,up) ) move_direction = left; else move_direction = right; } else if ( move_is_possible(left) ){ move_direction = left; } else if ( move_is_possible(right) ){ move_direction = right; } else { move_direction = down; } } do_move(move_direction); } 

    There is already an AI implementation for this game: here . Excerpt from README:

    The algorithm is iterative deepening depth first alpha-beta search. The evaluation function sortinges to keep the rows and columns monotonic (either all decreasing or increasing) while minimizing the number of tiles on the grid.

    There is also a discussion on ycombinator about this algorithm that you may find useful.

    Algorithm

     while(!game_over) { for each possible move: evaluate next state choose the maximum evaluation } 

    Evaluation

     Evaluation = 128 (Constant) + (Number of Spaces x 128) + Sum of faces adjacent to a space { (1/face) x 4096 } + Sum of other faces { log(face) x 4 } + (Number of possible next moves x 256) + (Number of aligned values x 2) 

    Evaluation Details

     128 (Constant) 

    This is a constant, used as a base-line and for other uses like testing.

     + (Number of Spaces x 128) 

    More spaces makes the state more flexible, we multiply by 128 (which is the median) since a grid filled with 128 faces is an optimal impossible state.

     + Sum of faces adjacent to a space { (1/face) x 4096 } 

    Here we evaluate faces that have the possibility to getting to merge, by evaluating them backwardly, tile 2 become of value 2048, while tile 2048 is evaluated 2.

     + Sum of other faces { log(face) x 4 } 

    In here we still need to check for stacked values, but in a lesser way that doesn’t interrupt the flexibility parameters, so we have the sum of { x in [4,44] }.

     + (Number of possible next moves x 256) 

    A state is more flexible if it has more freedom of possible transitions.

     + (Number of aligned values x 2) 

    This is a simplified check of the possibility of having merges within that state, without making a look-ahead.

    Note: The constants can be tweaked..

    This is not a direct answer to OP’s question, this is more of the stuffs (experiments) I sortinged so far to solve the same problem and obtained some results and have some observations that I want to share, I am curious if we can have some further insights from this.

    I just sortinged my minimax implementation with alpha-beta pruning with search-tree depth cutoff at 3 and 5. I was trying to solve the same problem for a 4×4 grid as a project assignment for the edX course ColumbiaX: CSMM.101x Artificial Intelligence (AI) .

    I applied convex combination (sortinged different heuristic weights) of couple of heuristic evaluation functions, mainly from intuition and from the ones discussed above:

    1. Monotonicity
    2. Free Space Available

    In my case, the computer player is completely random, but still i assumed adversarial settings and implemented the AI player agent as the max player.

    I have 4×4 grid for playing the game.

    Observation:

    If I assign too much weights to the first heuristic function or the second heuristic function, both the cases the scores the AI player gets are low. I played with many possible weight assignments to the heuristic functions and take a convex combination, but very rarely the AI player is able to score 2048. Most of the times it either stops at 1024 or 512.

    I also sortinged the corner heuristic, but for some reason it makes the results worse, any intuition why?

    Also, I sortinged to increase the search depth cut-off from 3 to 5 (I can’t increase it more since searching that space exceeds allowed time even with pruning) and added one more heuristic that looks at the values of adjacent tiles and gives more points if they are merge-able, but still I am not able to get 2048.

    I think it will be better to use Expectimax instead of minimax, but still I want to solve this problem with minimax only and obtain high scores such as 2048 or 4096. I am not sure whether I am missing anything.

    Below animation shows the last few steps of the game played by the AI agent with the computer player:

    entrer la description de l'image ici

    Any insights will be really very helpful, thanks in advance. (This is the link of my blog post for the article: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/ )

    The following animation shows the last few steps of the game played where the AI player agent could get 2048 scores, this time adding the absolute value heuristic too:

    entrer la description de l'image ici

    The following figures show the game tree explored by the player AI agent assuming the computer as adversary for just a single step:

    entrer la description de l'image ici entrer la description de l'image ici entrer la description de l'image ici entrer la description de l'image ici entrer la description de l'image ici entrer la description de l'image ici

    I wrote a 2048 solver in Haskell, mainly because I’m learning this language right now.

    My implementation of the game slightly differs from the actual game, in that a new tile is always a ‘2’ (rather than 90% 2 and 10% 4). And that the new tile is not random, but always the first available one from the top left. This variant is also known as Det 2048 .

    As a consequence, this solver is deterministic.

    I used an exhaustive algorithm that favours empty tiles. It performs pretty quickly for depth 1-4, but on depth 5 it gets rather slow at a around 1 second per move.

    Below is the code implementing the solving algorithm. The grid is represented as a 16-length array of Integers. And scoring is done simply by counting the number of empty squares.

     bestMove :: Int -> [Int] -> Int bestMove depth grid = maxTuple [ (gridValue depth (takeTurn x grid), x) | x < - [0..3], takeTurn x grid /= [] ] gridValue :: Int -> [Int] -> Int gridValue _ [] = -1 gridValue 0 grid = length $ filter (==0) grid -- < = SCORING gridValue depth grid = maxInList [ gridValue (depth-1) (takeTurn x grid) | x <- [0..3] ] 

    I thinks it's quite successful for its simplicity. The result it reaches when starting with an empty grid and solving at depth 5 is:

     Move 4006 [2,64,16,4] [16,4096,128,512] [2048,64,1024,16] [2,4,16,2] Game Over 

    Source code can be found here: https://github.com/popovitsj/2048-haskell

    This algorithm is not optimal for winning the game, but it is fairly optimal in terms of performance and amount of code needed:

      if(can move neither right, up or down) direction = left else { do { direction = random from (right, down, up) } while(can not move in "direction") } 

    Many of the other answers use AI with computationally expensive searching of possible futures, heuristics, learning and the such. These are impressive and probably the correct way forward, but I wish to consortingbute another idea.

    Model the sort of strategy that good players of the game use.

    Par exemple:

     13 14 15 16 12 11 10 9 5 6 7 8 4 3 2 1 

    Read the squares in the order shown above until the next squares value is greater than the current one. This presents the problem of trying to merge another tile of the same value into this square.

    To resolve this problem, their are 2 ways to move that aren’t left or worse up and examining both possibilities may immediately reveal more problems, this forms a list of dependancies, each problem requiring another problem to be solved first. I think I have this chain or in some cases tree of dependancies internally when deciding my next move, particularly when stuck.


    Tile needs merging with neighbour but is too small: Merge another neighbour with this one.

    Larger tile in the way: Increase the value of a smaller surrounding tile.

    etc…


    The whole approach will likely be more complicated than this but not much more complicated. It could be this mechanical in feel lacking scores, weights, neurones and deep searches of possibilities. The tree of possibilities rairly even needs to be big enough to need any branching at all.