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 faire des tuiles "plus grandes". Après chaque mouvement, une nouvelle tuile apparaît à une position vide aléatoire avec une valeur de 2ou 4. Le jeu se termine lorsque toutes les cases sont remplies et qu'aucun mouvement ne peut fusionner de tuiles, ou que 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é à lui écrire un programme.

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 à tout moment, j'essaierai de fusionner les tuiles avec des valeurs 2et 4, c'est-à-dire, j'essaierai d'avoir 2et des 4tuiles, le moins possible. Si j'essaye de cette façon, toutes les autres tuiles fusionnent automatiquement et la stratégie semble bonne.

Mais, lorsque j'utilise cet algorithme, je n'obtiens qu'environ 4000 points avant la fin du jeu. Le nombre maximum de points AFAIK est légèrement supérieur à 20 000 points, ce qui est bien plus élevé que mon score actuel. Existe-t-il un meilleur algorithme que celui ci-dessus?

J'ai développé une IA 2048 utilisant l' optimisation expectimax , au lieu de la recherche minimax utilisée par l'algorithme de @ ovolve. L'IA effectue simplement une maximisation sur tous les mouvements possibles, suivie d'une attente sur tous les apparitions de tuiles possibles (pondérées par la probabilité des tuiles, soit 10% pour un 4 et 90% pour un 2). Pour autant que je sache, il n'est pas possible de tailler l'optimisation expectimax (sauf pour supprimer les branches qui sont extrêmement improbables), et donc 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) prend entre 10 ms et 200 ms pour exécuter un mouvement, selon la complexité de la position de la carte. Lors des tests, l'IA atteint un taux de déplacement moyen de 5 à 10 mouvements 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 les performances du score de l'IA, j'ai exécuté l'IA 100 fois (connecté au jeu par navigateur via la 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 de 124024; le score maximum atteint était de 794076. Le score médian est de 387222. L'IA n'a jamais manqué d'obtenir la tuile 2048 (elle n'a donc jamais perdu le jeu même une fois en 100 matchs); en fait, il a atteint la tuile 8192 au moins une fois à chaque passage!

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

Ce match a pris 27830 coups en 96 minutes, soit une moyenne de 4,8 coups par seconde.

la mise en oeuvre

Mon approche code la carte entière (16 entrées) comme un seul entier 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 circuler la carte entière dans un seul registre de 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 coder des transformations qui opèrent sur une seule ligne ou colonne. Par exemple, les déplacements sont implémentés sous forme de 4 recherches dans une «table d'effets de déplacement» précalculée qui décrit comment chaque déplacement affecte une seule ligne ou colonne (par exemple, le tableau «déplacement vers la droite» contient l'entrée «1122 -> 0023» décrivant comment le 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 de la recherche de table. Les tableaux contiennent des scores heuristiques calculés sur toutes les lignes / colonnes possibles, et le score résultant pour un tableau est simplement la somme des valeurs du tableau sur chaque ligne et colonne.

Cette représentation de la carte, ainsi que l'approche de recherche de table pour le mouvement et le score, permettent à l'IA de rechercher un grand nombre d'états de jeu en peu de temps (plus de 10000000 états de jeu par seconde sur un cœur de mon ordinateur portable mi-2011).

La recherche expectimax elle-même est codée comme une recherche récursive qui alterne entre les étapes d '"attente" (tester tous les emplacements et valeurs d'apparition de tuiles possibles et pondérer leurs scores optimisés par la probabilité de chaque possibilité), et les étapes de "maximisation" (tester tous les mouvements possibles et sélectionner celui qui a le meilleur score). La recherche dans l'arborescence se termine lorsqu'elle voit une position précédemment vue (à l'aide d'une table de transposition ), lorsqu'elle atteint une limite de profondeur prédéfinie ou lorsqu'elle atteint un état de planche hautement improbable (par exemple, elle a été atteinte en obtenant 6 tuiles "4"). à la suite de la position de départ). La profondeur de recherche typique est de 4 à 8 mouvements.

Heuristique

Plusieurs heuristiques sont utilisées pour 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 positionnel, qui détermine la «bonne» position d'un conseil d'administration. La recherche d'optimisation visera alors à maximiser le score moyen de toutes les positions possibles du conseil d'administration. Le score réel, comme indiqué par le jeu, n'est pas utilisé pour calculer le score du plateau, 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 plutôt bien fonctionné, atteignant fréquemment 16384 mais n'atteignant jamais 32768.

Petr Morávek (@xificurk) a pris mon IA et a 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 de grands nombres endommageaient considérablement le score. 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 (l'encourageant à aligner les fusions lorsque cela est possible pour plus d'effet).

De plus, Petr a également optimisé les poids heuristiques en utilisant une stratégie de «méta-optimisation» (en 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 significatif. L'algorithme est passé de la réalisation de la tuile 16384 environ 13% du temps à l'atteinte plus de 90% du temps, et l'algorithme a commencé à atteindre 32768 sur 1/3 du temps (alors que l'ancienne heuristique n'a jamais produit une tuile 32768) .

Je pense qu'il y a encore place à amélioration sur l'heuristique. Cet algorithme n'est certainement pas encore "optimal", mais j'ai l'impression qu'il se rapproche assez.

Le fait que l'IA atteigne la tuile 32768 dans plus d'un tiers de ses jeux est une étape importante; Je serai surpris d'apprendre si des joueurs humains ont atteint 32 768 sur le jeu officiel (c'est-à-dire sans utiliser des outils tels que les états de sauvegarde 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 sur https://github.com/nneonneo/2048-ai .

Je suis l'auteur du programme AI 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 victoire d'environ 90% exécuté en javascript dans le navigateur de mon ordinateur portable, compte tenu d'environ 100 millisecondes de temps de réflexion par mouvement, donc bien qu'il ne soit pas parfait (encore!), Il fonctionne plutôt bien.

Comme le jeu est un espace d'état discret, des informations parfaites, un jeu au tour par tour comme les échecs et les dames, j'ai utilisé les mêmes méthodes qui se sont avérées efficaces sur ces jeux, à savoir la recherche minimax avec l' élagage alpha-bêta . Puisqu'il y a déjà beaucoup d'informations sur cet algorithme, je vais simplement parler des deux heuristiques principales que j'utilise dans la fonction d'évaluation statique et qui formalisent bon nombre des intuitions que d'autres personnes ont exprimées ici.

Monotonicité

Cette heuristique essaie de s'assurer que les valeurs des tuiles augmentent ou diminuent toutes le long des directions gauche / droite et haut / bas. Cette heuristique à elle seule capture l'intuition que beaucoup d'autres ont mentionnée, selon laquelle les tuiles de valeur supérieure devraient être regroupées dans un coin. Cela empêchera généralement les petites tuiles de valeur de devenir orphelines et gardera le plateau très organisé, avec de petites tuiles en cascade et se remplissant dans les plus grandes tuiles.

Voici une capture d'écran d'une grille 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.

Douceur

L'heuristique ci-dessus à elle seule tend à créer des structures dans lesquelles les tuiles adjacentes diminuent de valeur, 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 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, gracieuseté de cette excellente fourchette parodique .

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 est trop à l'étroit.

Et c'est tout! La recherche dans l'espace de jeu tout en optimisant ces critères donne des performances remarquablement bonnes. Un avantage à 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 effectuera souvent des mouvements surprenants mais efficaces, comme changer soudainement de mur ou d'angle contre lequel il se construit.

Éditer:

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

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

Je me suis intéressé à l'idée d'une IA pour ce jeu ne contenant aucune intelligence codée en dur (c'est-à-dire pas d'heuristique, de fonctions de notation, etc.). L'IA ne devrait "connaître" que les règles du jeu et "comprendre" le jeu. Cela contraste avec la plupart des IA (comme celles de 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 d'IA

J'ai trouvé un algorithme de jeu simple mais étonnamment bon: pour déterminer le prochain coup pour un plateau 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 final moyen le plus élevé est choisi comme coup suivant.

Avec seulement 100 courses (c'est-à-dire dans les jeux de mémoire) par coup, l'IA atteint la tuile 2048 80% du temps et la tuile 4096 50% du temps. L'utilisation de 10000 exécutions 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 à propos de cet algorithme est que, bien que les jeux à jeu aléatoire soient sans surprise assez mauvais, le choix du meilleur (ou du moins mauvais) coup conduit à un très bon jeu: un jeu d'IA typique peut atteindre 70000 points et 3000 derniers coups, mais le les parties de jeu aléatoire en mémoire d'une position donnée rapportent en moyenne 340 points supplémentaires en environ 40 coups supplémentaires 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 plateau après chaque coup. La ligne rouge montre le meilleur score de fin de partie aléatoire de l'algorithme à partir de cette position. En substance, 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 tout petit peu au-dessus de la ligne bleue à chaque point, mais la ligne bleue continue d'augmenter de plus en plus.

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

En recherchant plus tard, j'ai trouvé que cet algorithme pourrait être classé comme un algorithme de recherche d'arbre Pure Monte Carlo .

Implémentation et liens

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

Plus tard, afin de jouer encore plus, j'ai utilisé l'infrastructure hautement optimisée @nneonneo et implémenté ma version en C ++. Cette version permet jusqu'à 100000 runs par coup et même 1000000 si vous avez la patience. Instructions de montage fournies. Il s'exécute 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 pistes 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 réalisation de la tuile 8192. L'augmentation du nombre d'exécutions de 100 à 100 000 augmente les chances d'atteindre cette limite de score (de 5% à 40%) sans la franchir.

10000 courses avec une augmentation temporaire à 1000000 près des positions critiques ont réussi à franchir cette barrière moins de 1% du temps, atteignant un score maximum de 129892 et la tuile 8192.

Améliorations

Après avoir implémenté cet algorithme, j'ai essayé de nombreuses améliorations, notamment en utilisant les scores min ou max, ou une combinaison de min, max et avg. J'ai également essayé d'utiliser la profondeur: au lieu d'essayer K runs par coup, j'ai essayé K coups par liste de coups 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 tenait compte de 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é un réel avantage par rapport à la première idée simple. J'ai laissé le code de ces idées commentées dans le code C ++.

J'ai ajouté un mécanisme de «recherche approfondie» qui a temporairement augmenté le nombre de courses à 1000000 lorsque l'une des courses a réussi à atteindre accidentellement la prochaine tuile la plus élevée. Cela a offert une amélioration du temps.

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

2048 Variantes et clones

Juste pour le plaisir, j'ai également implémenté l'IA comme un bookmarklet , accroché aux commandes du jeu. Cela permet à l'IA de fonctionner avec le jeu original et bon nombre de ses variantes .

Cela est possible en raison de la nature indépendante du domaine de l'IA. Certaines des variantes sont assez distinctes, comme le clone hexagonal.

EDIT: Ceci est un algorithme naïf, modélisant le processus de pensée consciente de l'homme, et obtient des résultats très faibles par rapport à l'IA qui recherche toutes les possibilités car il ne regarde qu'une seule tuile en avant. 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 en raison d'une simple malchance proche 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 devrait être. Essayez simplement de garder la rangée du haut remplie, donc le déplacement à gauche ne briser le motif), mais vous finissez par avoir une partie fixe et une partie mobile avec lesquelles jouer. Voici 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 sur aucune 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 s'attend toujours à ce que la prochaine tuile aléatoire soit un 2 et apparaisse du côté opposé au modèle actuel (tandis que la première rangée est incomplète, dans le coin inférieur droit, une fois la première rangée terminée, en bas à gauche coin).

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

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 conseils sur les étapes manquantes. Ici:

Le modèle a changé en raison de la chance d'être plus proche du modèle attendu. Le modèle que l'IA essaie de réaliser 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

Les Oespaces interdits représentent ...

Il va donc appuyer à droite, puis à nouveau à droite, puis (à droite ou en haut selon l'endroit où le 4 a créé) puis procédera à la fin de la chaîne jusqu'à ce qu'il obtienne:

Alors 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 toujours 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

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

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

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. Bien qu'il ait atteint le score de 131040. Plusieurs références des performances de l'algorithme sont présentées.

Algorithme

Algorithme de notation heuristique

L'hypothèse sur laquelle mon algorithme est basé est assez simple: si vous voulez obtenir un score plus élevé, le tableau doit être aussi bien rangé 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 d'une valeur de tuile: où n est le nombre de tuiles sur le plateau.

(Il est possible d'atteindre la tuile 131072 si la 4 tuiles est générée aléatoirement au lieu de la 2 tuiles si nécessaire)

Deux images possibles de l'organisation du tableau sont illustrées dans les images suivantes:

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

Plusieurs chemins linéaires pourraient être évalués à la fois, le score final sera le score maximum de tout 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. De toute évidence, une règle de décision plus sophistiquée ralentira l'algorithme et sa mise en œuvre prendra un certain temps. J'essaierai une implémentation minimax dans un avenir proche. (Restez à l'écoute)

Référence

• T1 - 121 tests - 8 voies différentes - r = 0,125
• T2 - 122 tests - 8 voies différentes - r = 0,25
• T3 - 132 tests - 8 voies différentes - r = 0,5
• T4 - 211 tests - 2 voies différentes - r = 0,125
• T5 - 274 tests - 2 voies différentes - r = 0,25
• T6 - 211 tests - 2 voies différentes - 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 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 contrôler 10 millions de mouvements, ce qui correspond à une profondeur d'environ 4 avec 6 tuiles restantes et 4 mouvements possibles (2 * 6 * 4) ⁴ . Dans mon cas, cette profondeur est trop longue à 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 planches sont calculés avec la somme pondérée du carré du nombre de tuiles libres et du produit scalaire de la grille 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 en ordre décroissant en une sorte de serpent à partir de la tuile supérieure gauche.

code ci-dessous ou sur github :

var n = 4,
	M = new MatrixTransform(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);
updateHint(predict(ai));

function runAI() {
	var p = predict(ai);
	if (p != null && ai.running) {
		move(p, ai);
		updateUI(ai);
		updateHint(p);
		requestAnimationFrame(runAI);
	}
}
runai.onclick = function() {
	if (!ai.running) {
		this.innerHTML = 'stop AI';
		ai.running = true;
		runAI();
	} else {
		this.innerHTML = 'run AI';
		ai.running = false;
		updateHint(predict(ai));
	}
}


function updateHint(dir) {
	hintvalue.innerHTML = ['↑', '→', '↓', '←'][dir] || '';
}

document.addEventListener("keydown", function(event) {
	if (!event.target.matches('.r *')) return;
	event.preventDefault(); // avoid scrolling
	if (event.which in map) {
		move(map[event.which], ai)
		console.log(stats(ai.grid))
		updateUI(ai);
		updateHint(predict(ai));
	}
})
var map = {
	38: 0, // Up
	39: 1, // Right
	40: 2, // Down
	37: 3, // Left
};
init.onclick = function() {
	initialize(ai);
	updateUI(ai);
	updateHint(predict(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 {
	font-family: Arial;
}
table, th, td {
	border: 1px solid black;
	margin: 0 auto;
	border-collapse: collapse;
}
td {
	width: 35px;
	height: 35px;
	text-align: center;
}
button {
	margin: 2px;
	padding: 3px 15px;
	color: rgba(0,0,0,.9);
}
.r {
	display: flex;
	align-items: center;
	justify-content: center;
	margin: .2em;
	position: relative;
}
#hintvalue {
	font-size: 1.4em;
	padding: 2px 8px;
	display: inline-flex;
	justify-content: center;
	width: 30px;
}

<table title="press arrow keys"></table>
<div class="r">
    <button id=init>init</button>
    <button id=runai>run AI</button>
    <span id="hintvalue" title="Best predicted move to do, use your arrow keys" tabindex="-1"></span>
</div>

Je suis l'auteur d'un contrôleur 2048 qui marque mieux que tout autre programme mentionné dans ce fil. Une implémentation efficace du contrôleur est disponible sur github . Dans un référentiel séparé, il existe également le code utilisé pour la formation de la fonction d'évaluation de l'état du contrôleur. La méthode de formation est décrite dans l' article .

Le contrôleur utilise la recherche expectimax avec une fonction d'évaluation d'état apprise à partir de zéro (sans expertise humaine 2048) par une variante de l'apprentissage de la différence temporelle (une technique d'apprentissage par renforcement). La fonction état-valeur utilise un réseau à n-tuple , qui est essentiellement une fonction linéaire pondérée des motifs observés sur la carte. Il a impliqué plus d' un milliard de poids au total.

Performance

À 1 coups / s: 609104 (100 parties en moyenne)

À 10 coups / s: 589355 (moyenne de 300 matchs)

À 3 plis (environ 1500 coups / s): 511759 (moyenne de 1000 matchs)

Les statistiques des tuiles pour 10 coups / s sont les suivantes:

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

(La dernière ligne signifie avoir les tuiles données en même temps sur le plateau).

Pour 3 plis:

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

Cependant, je ne l'ai jamais vu obtenir la tuile 65536.

Je pense avoir trouvé un algorithme qui fonctionne assez bien, car j'atteins souvent des scores supérieurs à 10000, mon record personnel étant d'environ 16000. Ma solution ne vise pas à garder les plus grands nombres dans un coin, mais à le maintenir dans la rangée du haut.

Veuillez consulter le code ci-dessous:

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);
}

Il existe déjà une implémentation de l'IA pour ce jeu ici . Extrait de README:

L'algorithme est la profondeur d'approfondissement itérative de la première recherche alpha-bêta. La fonction d'évaluation essaie de garder les lignes et les colonnes monotones (toutes décroissantes ou croissantes) tout en minimisant le nombre de tuiles sur la grille.

Il y a aussi une discussion sur Hacker News à propos de cet algorithme qui peut vous être utile.

Algorithme

while(!game_over)
{
    for each possible move:
        evaluate next state

    choose the maximum evaluation
}

Évaluation

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)

Détails de l'évaluation

128 (Constant)

Il s'agit d'une constante, utilisée comme ligne de base et pour d'autres utilisations comme les tests.

+ (Number of Spaces x 128)

Plus d'espace rend l'état plus flexible, nous multiplions par 128 (ce qui est la médiane) puisqu'un quadrillage rempli de 128 faces est un état impossible optimal.

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

Ici, nous évaluons les faces qui ont la possibilité de fusionner, en les évaluant à l'envers, la tuile 2 prend la valeur 2048, tandis que la tuile 2048 est évaluée 2.

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

Ici, nous devons toujours vérifier les valeurs empilées, mais d'une manière moindre qui n'interrompt pas les paramètres de flexibilité, nous avons donc la somme de {x dans [4,44]}.

+ (Number of possible next moves x 256)

Un État est plus flexible s'il dispose d'une plus grande liberté de transitions possibles.

+ (Number of aligned values x 2)

Il s'agit d'une vérification simplifiée de la possibilité de fusionner au sein de cet état, sans faire d'anticipation.

Remarque: Les constantes peuvent être modifiées.

Ce n'est pas une réponse directe à la question d'OP, c'est plus des trucs (expériences) que j'ai essayés jusqu'à présent pour résoudre le même problème et obtenu quelques résultats et avoir quelques observations que je veux partager, je suis curieux si nous pouvons en avoir d'autres informations à ce sujet.

Je viens d'essayer mon implémentation minimax avec un élagage alpha-bêta avec une coupure de la profondeur de l'arbre de recherche à 3 et 5. J'essayais de résoudre le même problème pour une grille 4x4 qu'une affectation de projet pour le cours edX ColumbiaX: CSMM.101x Intelligence artificielle ( AI) .

J'ai appliqué une combinaison convexe (essayé différents poids heuristiques) de quelques fonctions d'évaluation heuristique, principalement à partir de l'intuition et de celles discutées ci-dessus:

1. Monotonicité
2. Espace libre disponible

Dans mon cas, le lecteur d'ordinateur est complètement aléatoire, mais j'ai tout de même assumé les paramètres contradictoires et implémenté l'agent du joueur AI comme joueur maximum.

J'ai une grille 4x4 pour jouer au jeu.

Observation:

Si j'attribue trop de poids à la première fonction heuristique ou à la deuxième fonction heuristique, les deux cas où les scores obtenus par le joueur IA sont faibles. J'ai joué avec de nombreuses affectations de poids possibles aux fonctions heuristiques et je prends une combinaison convexe, mais très rarement le joueur IA est capable de marquer 2048. La plupart du temps, il s'arrête à 1024 ou 512.

J'ai également essayé l'heuristique du coin, mais pour une raison quelconque, cela aggrave les résultats, une intuition pourquoi?

De plus, j'ai essayé d'augmenter la coupure de la profondeur de recherche de 3 à 5 (je ne peux pas l'augmenter davantage car la recherche que l'espace dépasse le temps autorisé même avec l'élagage) et j'ai ajouté une autre heuristique qui regarde les valeurs des tuiles adjacentes et donne plus de points s'ils sont fusionnables, mais je ne suis toujours pas en mesure d'obtenir 2048.

Je pense qu'il sera préférable d'utiliser Expectimax au lieu de minimax, mais je veux toujours résoudre ce problème avec minimax uniquement et obtenir des scores élevés tels que 2048 ou 4096. Je ne sais pas si je manque quelque chose.

L'animation ci-dessous montre les dernières étapes du jeu jouées par l'agent IA avec le joueur de l'ordinateur:

Toutes les informations seront vraiment très utiles, merci à l'avance. (Voici le lien de mon article de blog pour l'article: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve -2048-jeu-avec-ordinateur / et la vidéo youtube: https://www.youtube.com/watch?v=VnVFilfZ0r4 )

L'animation suivante montre les dernières étapes du jeu où l'agent de l'IA a pu obtenir 2048 scores, en ajoutant cette fois l'heuristique de valeur absolue:

Les figures suivantes montrent l' arborescence de jeu explorée par l'agent IA du joueur en supposant que l'ordinateur est l'adversaire pour une seule étape:

J'ai écrit un solveur 2048 à Haskell, principalement parce que j'apprends cette langue en ce moment.

Mon implémentation du jeu diffère légèrement du jeu réel, en ce sens qu'une nouvelle tuile est toujours un '2' (plutôt que 90% 2 et 10% 4). Et que la nouvelle tuile n'est pas aléatoire, mais toujours la première disponible en haut à gauche. Cette variante est également connue sous le nom de Det 2048 .

Par conséquent, ce solveur est déterministe.

J'ai utilisé un algorithme exhaustif qui favorise les tuiles vides. Il fonctionne assez rapidement pour les profondeurs 1-4, mais à la profondeur 5, il devient plutôt lent à environ 1 seconde par coup.

Ci-dessous, le code implémentant l'algorithme de résolution. La grille est représentée sous la forme d'un tableau de 16 longueurs entières. Et la notation se fait simplement en comptant le nombre de cases vides.

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] ]

Je pense que c'est assez réussi pour sa simplicité. Le résultat qu'il atteint en commençant avec une grille vide et en résolvant à la profondeur 5 est:

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

Game Over

Le code source peut être trouvé ici: https://github.com/popovitsj/2048-haskell

Cet algorithme n'est pas optimal pour gagner le jeu, mais il est assez optimal en termes de performances et de quantité de code nécessaire:

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

Beaucoup d'autres réponses utilisent l'IA avec une recherche coûteuse en calcul sur les futurs possibles, l'heuristique, l'apprentissage, etc. Celles-ci sont impressionnantes et constituent probablement la bonne voie à suivre, mais je souhaite apporter une autre idée.

Modélisez le type de stratégie que les bons joueurs du jeu utilisent.

Par exemple:

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

Lisez les carrés dans l'ordre indiqué ci-dessus jusqu'à ce que la valeur des carrés suivante soit supérieure à la valeur actuelle. Cela pose le problème d'essayer de fusionner une autre tuile de la même valeur dans ce carré.

Pour résoudre ce problème, il existe 2 façons de se déplacer qui ne sont pas laissées ou pire et en examinant les deux possibilités peuvent immédiatement révéler plus de problèmes, cela forme une liste de dépendances, chaque problème nécessitant un autre problème à résoudre en premier. Je pense que j'ai cette chaîne ou, dans certains cas, un arbre de dépendances en interne lors de la décision de mon prochain déménagement, en particulier lorsqu'il est coincé.

La tuile doit fusionner avec le voisin mais est trop petite: fusionnez un autre voisin avec celui-ci.

Plus grande tuile sur le chemin: augmentez la valeur d'une petite tuile environnante.

etc...

L'approche globale sera probablement plus compliquée que cela, mais pas beaucoup plus compliquée. Ce pourrait être cette sensation mécanique qui manque de scores, de poids, de neurones et de recherches approfondies de possibilités. L'arbre des possibilités doit même être assez grand pour avoir besoin de n'importe quelle ramification.