Question 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 vide avec une valeur de 2 ou 4. Le jeu se termine lorsque toutes les cases sont remplies et qu'aucun mouvement ne peut fusionner des 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é à écrire un programme pour ça.

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 des valeurs 2 et 4c'est-à-dire que j'essaie d'avoir 2 et 4 tuiles, aussi minime que possible. Si je l'essaye de cette façon, toutes les autres tuiles sont automatiquement fusionnées et la stratégie semble bonne.

Mais, quand j'utilise cet algorithme, je n'ai que 4000 points avant la fin du jeu. Le maximum de points AFAIK est légèrement supérieur à 20 000 points, ce qui est beaucoup plus important que mon score actuel. Y a-t-il un meilleur algorithme que celui ci-dessus?


1753
2018-03-12 05:37


origine


Réponses:


J'ai développé une IA 2048 en utilisant expectimax optimisation, 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 toutes les occurrences de tuiles possibles (pondérée par la probabilité des tuiles, c'est-à-dire 10% pour un 4 et 90% pour un 2). Autant que je sache, il n'est pas possible d'élaguer l'optimisation d'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 10ms et 200ms pour exécuter un mouvement, en fonction de la complexité de la position de la carte. Lors des tests, l'IA obtient un taux de déplacement moyen de 5 à 10 coups par seconde tout au long d'une partie. Si la profondeur de recherche est limitée à 6 coups, l'IA peut facilement exécuter 20+ mouvements par seconde, ce qui fait que regarder intéressant.

Pour évaluer la performance de score de l'IA, j'ai couru l'IA 100 fois (connecté au jeu du navigateur via la télécommande). Pour chaque tuile, voici les proportions des parties dans lesquelles 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 atteint était 794076. Le score médian est 387222. L'IA n'a jamais manqué d'obtenir la tuile 2048 (donc elle n'a jamais perdu la partie une seule fois en 100 parties); en fait, il a atteint le 8192 tuile au moins une fois dans chaque course!

Voici la capture d'écran du meilleur tirage:

32768 tile, score 794076

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

la mise en oeuvre

Mon approche code la totalité de la carte (16 entrées) sous la forme d'un seul entier de 64 bits (où les mosaïques sont les nybbles, c'est-à-dire les fragments de 4 bits). Sur une machine 64 bits, cela permet de transmettre la totalité de la carte 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 en 4 recherches dans une "table d'effets de mouvement" précalculée qui décrit comment chaque déplacement affecte une seule ligne ou colonne (par exemple, la table "déplacer vers la droite" contient l'entrée "1122 -> 0023" la ligne [2,2,4,4] devient la ligne [0,0,4,8] quand elle est déplacée vers la droite).

L'évaluation est également effectuée à l'aide de la recherche de table. Les tables 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 de table sur chaque ligne et colonne.

Cette représentation du tableau, associée à l'approche de recherche de mouvement et de notation, permet à l'IA de rechercher un grand nombre d'états de jeu dans un court laps de temps (plus de 10 000 000 jeux par seconde sur un ordinateur portable mi-2011).

La recherche expectimax elle-même est codée comme une recherche récursive qui alterne entre les étapes "expectative" (test de tous les emplacements et valeurs de spawn possibles, pondération de leurs scores optimisés par la probabilité de chaque possibilité) et les étapes de "maximisation" (test de tous les mouvements possibles). et en sélectionnant celui avec le meilleur score). La recherche d'arborescence se termine lorsqu'elle voit une position précédemment vue (en utilisant table de transposition), quand il atteint une limite de profondeur prédéfinie, ou lorsqu'il atteint un état de plateau hautement improbable (par exemple, il a été atteint en obtenant 6 "4" tuiles dans une rangée à partir de 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 énorme sur la performance 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 d'un tableau donné. La recherche d'optimisation visera alors à maximiser le score moyen de toutes les positions possibles du conseil. Le score réel, comme indiqué par le jeu, est ne pas Utilisé pour calculer le score au tableau, car il est trop pondéré en faveur de la fusion des tuiles (lorsque la fusion différée pourrait produire un avantage important).

Initialement, 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 se sont plutôt bien déroulées, atteignant fréquemment le niveau 16384 mais n'atteignant 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 au fur et à mesure que les rangs augmentaient, assurant que les rangs non monotones de petits nombres n'affectaient pas fortement le score, mais les rangées non monotones de grands nombres blessaient considérablement le score. La deuxième 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 forum avec beaucoup de fusions (l'encourageant à aligner des fusions si possible pour plus d'effet).

En outre, 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 important. L'algorithme est passé de la réalisation de la tuile 16384 environ 13% du temps à l'atteindre sur 90% du temps, et l'algorithme a commencé à atteindre 32768 sur 1/3 du temps (alors que l'ancienne heuristique n'a jamais produit de tuile 32768) .

Je crois qu'il est encore possible d'améliorer les heuristiques. Cet algorithme n'est certainement pas encore "optimal", mais j'ai l'impression que ça devient assez proche.


Que l'IA atteigne la tuile 32768 dans plus d'un tiers de ses parties est une étape importante; Je serai surpris d'entendre si des joueurs humains ont atteint 32768 sur le jeu officiel (c'est-à-dire sans utiliser d'outils comme les savestats ou annuler). Je pense que la tuile 65536 est à portée de main!

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


1130
2018-03-19 07:22



Je suis l'auteur du programme AI que d'autres ont mentionné dans ce fil. Vous pouvez voir l'IA dans action ou lisez le 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 réflexion par mouvement, donc pas parfait (mais!) 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 été prouvées pour fonctionner sur ces jeux, à savoir minimax  chercher 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 le fonction d'évaluation statique et qui formalisent beaucoup d'intuitions que d'autres personnes ont exprimées ici.

Monotonie

Cette heuristique essaie de s'assurer que les valeurs des tuiles augmentent ou diminuent le long des directions gauche / droite et haut / bas. Cette heuristique capture seule l'intuition que beaucoup d'autres ont mentionnée, à savoir que les tuiles les plus valorisées devraient être regroupées dans un coin. Il empêche généralement les tuiles de plus petite valeur de devenir orphelines et maintient le tableau très organisé, avec des tuiles plus petites en cascade et se remplissant dans les plus grandes tuiles.

Voici une capture d'écran d'une grille parfaitement monotone. J'ai obtenu ceci en exécutant l'algorithme avec la fonction eval réglée pour ne pas tenir compte des autres heuristiques et considérer seulement la monotonie.

A perfectly monotonic 2048 board

Douceur

L'heuristique ci-dessus seule a tendance à créer des structures dans lesquelles les tuiles adjacentes ont une valeur décroissante, mais bien sûr, afin de 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 nombre.

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, gracieuseté de cette excellente fourchette de parodie.

A perfectly smooth 2048 board

Tuiles libres

Et enfin, il y a une pénalité pour avoir trop peu de tuiles libres, puisque les options peuvent rapidement s'épuiser quand le plateau de jeu devient trop exigu.

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 courir, il fera souvent des mouvements surprenants mais efficaces, comme le changement soudain du mur ou du coin contre lequel il se construit.

Modifier:

Voici une démonstration de la puissance de cette approche. J'ai décapsulé les valeurs des tuiles (donc ça continue 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 atteint la tuile 2048 insaisissable trois fois sur le même plateau.


1224
2018-03-13 20:04



MODIFIER: C'est un algorithme naïf, qui modélise le processus de la pensée humaine consciente, et obtient des résultats très faibles comparés à l'intelligence artificielle qui recherche toutes les possibilités puisqu'elle ne regarde qu'une seule case 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 malchance simple à proximité de la fin (vous êtes obligé de descendre, ce que vous ne devriez jamais faire, et une tuile apparaît là où vous deviez être le plus haut. briser le modèle), mais vous finissez par avoir une partie fixe et une partie mobile pour jouer avec. C'est ton objectif:

Ready to finish

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'avez en principe jamais appuyer sur une touche (le mouvement interdit), et si vous le faites, vous appuyez à nouveau sur le contraire et essayez de le réparer. Pour les futures tuiles, le modèle s'attend toujours à ce que la prochaine tuile aléatoire soit 2 et apparaisse du côté opposé au modèle actuel (alors 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).

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

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: model change

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

le O représentent des espaces interdits ...

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

Chain completed

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 a eu de la malchance et sa place principale a été prise. Il est probable qu'il échouera, mais il peut encore l'atteindre:

Enter image description here

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 une rangée entière est encore gagné:

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

119
2018-03-12 16:05



Je me suis intéressé à 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 devrait "connaître" 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 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 pour un tableau donné, l'IA joue le jeu en mémoire en utilisant mouvements aléatoires jusqu'à ce que le jeu soit terminé. Ceci est fait plusieurs fois tout en gardant une trace du score final. Ensuite, le score final moyen par mouvement de départ est calculé. Le mouvement de départ avec le score final moyen le plus élevé est choisi comme mouvement suivant.

Avec seulement 100 courses (c'est-à-dire dans les jeux de mémoire) par coup, l'IA atteint la tuile 2048 80% des fois et la tuile 4096 50% des fois. L'utilisation de 10000 points obtient la tuile 2048 100%, 70% pour la tuile 4096 et environ 1% pour la tuile 8192.

Voyez-le en action

Le meilleur résultat obtenu est indiqué ici:

best score

Un fait intéressant à propos de cet algorithme est que, bien que les jeux aléatoires soient plutôt mauvais, choisir le meilleur (ou le moins mauvais) mouvement mène à un très bon jeu: un jeu d'IA typique peut atteindre 70000 points et 3000 mouvements, Les jeux aléatoires en mémoire d'une position donnée 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 montre le score au tableau après chaque coup. La ligne rouge montre l'algorithme de meilleur score de jeu de fin aléatoire 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 peu au-dessus de la ligne bleue à chaque point, mais la ligne bleue continue d'augmenter de plus en plus.

scoring graph

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

En cherchant plus tard, j'ai trouvé cet algorithme pourrait être classé comme Pure Monte Carlo Tree Recherche algorithme.

Implémentation 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 runs dans un temps décent. Ouvrez la console pour plus d'informations. (la source)

Plus tard, afin de jouer un peu plus, j'ai utilisé @nneonneo une infrastructure hautement optimisée et implémenté ma version en C ++. Cette version permet jusqu'à 100 000 passages 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. (la source)

Résultats

Étonnamment, augmenter le nombre de courses n'améliore pas radicalement 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. Augmenter le nombre de passages de 100 à 100 000 augmente la chances d'atteindre cette limite de score (de 5% à 40%) sans la franchir.

Courir 10000 courses avec une augmentation temporaire à 1000000 près des positions critiques a réussi à briser cette barrière moins de 1% des fois atteindre 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, 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 par mouvement, j'ai essayé K coups par mouvement liste d'une longueur donnée ("en haut, en haut, à gauche" par exemple) et en sélectionnant le premier mouvement de la liste des coups les mieux notés.

Plus tard, j'ai mis en place 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é de réel avantage par rapport à la première idée simple. J'ai laissé le code pour ces idées commentées dans le code C ++.

J'ai ajouté un mécanisme de "recherche en profondeur" qui augmentait temporairement le nombre d'exécutions à 1000000 lorsque l'un des passages réussissait à atteindre accidentellement la prochaine tuile la plus haute. Cela a offert 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 du domaine de l'IA.

2048 Variantes et clones

Juste pour le fun, j'ai aussi mis en œuvre l'IA comme un bookmarklet, accrocher dans les contrôles du jeu. Cela permet à l'IA de travailler avec le jeu original et beaucoup de ses variantes.

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


114
2018-05-25 09:25



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


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

Score

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 tableau doit être aussi propre que possible. En particulier, la configuration optimale est donnée par un ordre décroissant linéaire et monotone des valeurs de pavé. 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 est possible d'atteindre la tuile 131072 si la tuile 4 est générée aléatoirement au lieu de la tuile 2 si nécessaire)

Deux manières possibles d'organiser le tableau sont montrées dans les images suivantes:

enter image description here

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

s

s

Plusieurs trajectoires linéaires pourraient être évaluées en même temps, le score final sera 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 de la minmax ou de l'Expectiminimax améliorera sûrement l'algorithme. De toute évidence un plus Une règle de décision sophistiquée ralentira l'algorithme et il faudra du temps pour être implémenté. J'essaierai une implémentation de minimax dans un proche avenir. (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
  • Tests T4 - 211 - 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

enter image description here enter image description here enter image description here enter image description here

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 C'est basé sur term2048 et c'est écrit en Python. Je vais implémenter une version plus efficace en C ++ dès que possible.


88
2018-03-26 22:13



Ma tentative utilise expectimax comme les autres solutions ci-dessus, mais sans bitboards. La solution de Nneonneo peut vérifier 10millions de mouvements, soit environ une profondeur de 4 avec 6 tuiles restantes et 4 coups possibles (2 * 6 * 4)4. Dans mon cas, cette profondeur prend trop de temps à explorer, j'ajuste la profondeur de 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 descendant dans une sorte de serpent de la tuile en haut à gauche.

Code ci-dessous ou jsbin:

  
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)

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;
}
<table></table>
<button id=init>init</button><button id=runai>run AI</button><button id=hint>hint</button><span id=hintvalue></span>


30
2018-03-03 05:35



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 16 000. Ma solution ne vise pas à garder les plus gros chiffres dans un coin, mais à rester dans la rangée supérieure.

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

25
2018-03-12 18:57



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 dépôt séparé il y a aussi le code utilisé pour l'apprentissage de la fonction d'évaluation d'état du contrôleur. La méthode d'entraînement est décrite dans le papier.

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

Performance

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

À 10 coups / s: 589355 (300 jeux en moyenne)

À 3 plis (environ 1500 mouvements / s): 511759 (1000 jeux en moyenne)

Les statistiques de 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 n'ai jamais observé l'obtention de la tuile 65536.


25
2017-12-21 10:49



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

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

Il y a aussi une discussion sur ycombinateur à propos de cet algorithme que vous pouvez trouver utile.


21
2018-03-13 09:16



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)

C'est une constante, utilisée comme base et pour d'autres utilisations comme les tests.

+ (Number of Spaces x 128)

Plus les espaces rendent l'état plus flexible, nous multiplions par 128 (qui est la médiane) puisqu'une grille remplie 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 vers l'arrière, la tuile 2 devient de valeur 2048, alors que la tuile 2048 est évaluée 2.

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

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

+ (Number of possible next moves x 256)

Un état est plus flexible s'il a plus de liberté de transitions possibles.

+ (Number of aligned values x 2)

C'est une vérification simplifiée de la possibilité d'avoir fusionné dans cet état, sans faire de prévision.

Note: Les constantes peuvent être modifiées.


20
2018-03-12 20:15



Ce n'est pas une réponse directe à la question d'OP, c'est plus des expériences que j'ai essayées jusqu'ici pour résoudre le même problème et obtenu des résultats et des observations que je veux partager, je suis curieux de savoir si nous pouvons en avoir d'autres idées à partir de cela.

J'ai juste essayé ma mise en œuvre de minimax avec l'élagage alpha-bêta avec la limite de profondeur de l'arbre de recherche à 3 et 5. J'essayais de résoudre le même problème pour une grille 4x4 comme une affectation de projet pour le cours edX ColumbiaX: CSMM.101x Intelligence Artificielle (IA).

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

  1. Monotonie
  2. Espace libre disponible

Dans mon cas, le joueur de l'ordinateur est complètement aléatoire, mais j'ai toujours supposé les paramètres adversaires et mis en œuvre l'agent AI joueur comme le joueur max.

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 pour les fonctions heuristiques et prendre 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 aussi essayé l'heuristique de coin, mais pour une raison quelconque cela rend les résultats plus mauvais, n'importe quelle intuition pourquoi?

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

Je pense qu'il vaudra mieux utiliser Expectimax au lieu de minimax, mais je veux quand même résoudre ce problème avec minimax seulement et obtenir des scores élevés comme 2048 ou 4096. Je ne suis pas sûr de savoir s'il me manque quelque chose.

Ci-dessous l'animation montre les dernières étapes du jeu joué par l'agent AI avec le lecteur de l'ordinateur:

enter image description here

Toute idée sera vraiment très utile, merci d'avance. (Ceci est le lien de mon blog pour l'article: https://sandipanweb.wordpress.com/2017/03/06/using-minimax-with-alpha-beta-pruning-and-heuristic-evaluation-to-solve-2048-game-with-computer/)

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

enter image description here

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

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here


8
2018-03-06 21:37