Quel est l'algorithme optimal pour le jeu 2048?

1920

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?

nitish712
la source
84
Cela pourrait aider! ov3y.github.io/2048-AI
cegprakash
5
@ nitish712 soit dit en passant, votre algorithme est gourmand puisque vous en avez choose the move with large number of mergesqui conduisent rapidement à des optima locaux
Khaled.K
21
@ 500-InternalServerError: Si je devais implémenter une IA avec élagage d'arbre de jeu alpha-bêta, ce serait en supposant que les nouveaux blocs sont placés de manière opposée. C'est une hypothèse du pire des cas, mais pourrait être utile.
Charles
6
Une distraction amusante lorsque vous n'avez pas le temps de viser un score élevé: essayez d'obtenir le score le plus bas possible. En théorie, il s'agit d'alterner 2 et 4.
Mark Hurd
7
Une discussion sur la légitimité de cette question peut être trouvée sur meta: meta.stackexchange.com/questions/227266/…
Jeroen Vannevel

Réponses:

1266

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:

32768 tuile, score 794076

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 .

nneonneo
la source
12
@RobL: 2 apparaissent dans 90% des cas; 4 apparaissent 10% du temps. Il est dans le code source : var value = Math.random() < 0.9 ? 2 : 4;.
nneonneo
35
Portage actuel vers Cuda pour que le GPU fasse le travail pour des vitesses encore meilleures!
nimsson
25
@nneonneo J'ai porté votre code avec emscripten sur javascript, et cela fonctionne très bien dans le navigateur maintenant! Cool à regarder, sans avoir besoin de compiler et tout ... Dans Firefox, les performances sont assez bonnes ...
reverse_engineer
7
La limite théorique dans une grille 4x4 est en réalité 131072 et non 65536. Cependant, cela nécessite d'obtenir un 4 au bon moment (c'est-à-dire que la carte entière est remplie de 4 .. 65536 chaque fois - 15 champs occupés) et la carte doit être configurée à ce niveau. moment afin que vous puissiez réellement combiner.
Bodo Thiesen
5
@nneonneo Vous voudrez peut-être vérifier notre IA, qui semble encore meilleure, arriver à 32k dans 60% des jeux: github.com/aszczepanski/2048
cauchy
1253

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.

Une carte 2048 parfaitement monotone

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 .

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

4096

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.

ovolve
la source
89
Vous pouvez traiter l'ordinateur plaçant les tuiles «2» et «4» comme «l'adversaire».
Wei Yen,
29
@WeiYen Bien sûr, mais le considérer comme un problème minmax n'est pas fidèle à la logique du jeu, car l'ordinateur place des tuiles au hasard avec certaines probabilités, plutôt que de minimiser intentionnellement le score.
koo
57
Même si l'IA place les tuiles au hasard, l'objectif n'est pas de perdre. Être malchanceux, c'est la même chose que l'adversaire qui choisit le pire coup pour vous. La partie "min" signifie que vous essayez de jouer de façon conservatrice afin qu'il n'y ait pas de mouvements horribles que vous pourriez avoir malchanceux.
FryGuy
196
J'ai eu l'idée de créer un fork de 2048, où l'ordinateur au lieu de placer les 2 et les 4 utilise aléatoirement votre IA pour déterminer où mettre les valeurs. Le résultat: une pure impossibilité. Peut être essayé ici: sztupy.github.io/2048-Hard
SztupY
30
@SztupY Wow, c'est mal. Cela me rappelle qntm.org/hatetris Hatetris, qui essaie également de placer l'élément qui améliorera le moins votre situation.
Patashu
145

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:

meilleur score

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.

graphique de notation

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.

Ronenz
la source
7
+1. En tant qu'étudiant en IA, j'ai trouvé cela vraiment intéressant. Va mieux voir ça dans le temps libre.
Isaac
4
Ceci est incroyable! Je viens de passer des heures à optimiser les poids pour une bonne fonction heuristique pour expectimax et je l'implémente en 3 minutes et cela le casse complètement.
Brendan Annable
8
Belle utilisation de la simulation de Monte Carlo.
nneonneo
5
Regarder ce jeu appelle un éclaircissement. Cela fait exploser toutes les heuristiques et pourtant ça marche. Toutes nos félicitations !
Stéphane Gourichon
4
De loin, la solution la plus intéressante ici.
shebaw
126

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:

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

Chaîne terminée

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:

Entrez la description de l'image ici

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
Daren
la source
execute move with best scorecomment pouvez-vous évaluer le meilleur score parmi les prochains états possibles?
Khaled.K
l'heuristique est définie en evaluateResultvous essayez essentiellement de vous rapprocher du meilleur scénario possible.
Daren
@ Daren j'attends vos détails détaillés
ashu
@ashu J'y travaille, des circonstances inattendues m'ont laissé le temps de le terminer. Pendant ce temps, j'ai amélioré l'algorithme et il le résout maintenant 75% du temps.
Daren
13
Ce que j'aime vraiment dans cette stratégie, c'est que je peux l'utiliser lorsque je joue le jeu manuellement, cela m'a permis de gagner jusqu'à 37 000 points.
Céphalopode du
94

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.

But

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: soù 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:

entrez la description de l'image ici

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.

s

s

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

entrez la description de l'image ici entrez la description de l'image ici entrez la description de l'image ici entrez 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 s42000

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.

Nicola Pezzotti
la source
Pas mal, votre illustration m'a donné une idée de la prise en compte des vecteurs de fusion
Khaled.K
Bonjour. Êtes-vous sûr que les instructions fournies dans la page github s'appliquent à votre projet? Je veux l'essayer, mais cela semble être les instructions pour le jeu jouable original et non pour l'exécution automatique de l'IA. Pourriez-vous les mettre à jour? Merci.
JD Gamboa
41

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

caub
la source
3
Je ne sais pas pourquoi cela n'a pas plus de votes positifs. C'est vraiment efficace pour sa simplicité.
David Greydanus
Merci, réponse tardive et elle ne fonctionne pas vraiment bien (presque toujours en [1024, 8192]), la fonction coût / statistiques a besoin de plus de travail
caub
Comment avez-vous pondéré les espaces vides?
David Greydanus
1
C'est tout simplement cost=1x(number of empty tiles)²+1xdotproduct(snakeWeights,grid)et nous essayons de maximiser ce coût
caub
merci @Robusto, je devrais améliorer le code un jour, il peut être simplifié
caub
38

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.

cauchy
la source
4
Résultat assez impressionnant. Cependant, pourriez-vous éventuellement mettre à jour la réponse pour expliquer (en gros, en termes simples ... Je suis sûr que les détails complets seraient trop longs pour être publiés ici) comment votre programme y parvient? Comme dans une explication approximative du fonctionnement de l'algorithme d'apprentissage?
Cedric Mamo
27

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);
}
Vincent Lecrubier
la source
5
J'ai couru 100 000 matchs en testant cela par rapport à la stratégie cyclique triviale "en haut, à droite, en haut, à gauche, ..." (et en bas s'il le faut). La stratégie cyclique a terminé un "score moyen de tuiles" de 770.6, tandis que celui-ci est juste 396.7. Avez-vous une idée de pourquoi cela pourrait être? Je pense que cela fait trop de montées, même lorsque gauche ou droite fusionneraient beaucoup plus.
Thomas Ahle
1
Les tuiles ont tendance à s'empiler de manière incompatible si elles ne sont pas déplacées dans plusieurs directions. En général, l'utilisation d'une stratégie cyclique se traduira par des tuiles plus grandes au centre, ce qui rend les manœuvres beaucoup plus exiguës.
bcdan
25

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.

baltazar
la source
4
Cela devrait être la meilleure réponse, mais il serait bien d'ajouter plus de détails sur la mise en œuvre: par exemple, comment le plateau de jeu est modélisé (sous forme de graphique), l'optimisation utilisée (min-max la différence entre les tuiles), etc.
Alceu Costa
1
Pour les futurs lecteurs: Il s'agit du même programme expliqué par son auteur (ovolve) dans la deuxième réponse en haut ici. Cette réponse, et d'autres mentions du programme d'ovolve dans cette discussion, ont incité ovolve à apparaître et à écrire comment son algorithme fonctionnait; cette réponse a maintenant un score de 1200.
MultiplyByZer0
23

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.

Khaled.K
la source
2
Je modifierai cela plus tard, pour ajouter un code en direct @ nitish712
Khaled.K
9
Quel est le% de gain de cet algorithme?
cegprakash
Pourquoi en avez-vous besoin constant? Si tout ce que vous faites est de comparer les scores, comment cela affecte-t-il le résultat de ces comparaisons?
bcdan
@bcdan l'heuristique (aka comparaison-score) dépend de la comparaison de la valeur attendue de l'état futur, similaire au fonctionnement de l'heuristique d'échecs, sauf qu'il s'agit d'une heuristique linéaire, car nous ne construisons pas d'arbre pour connaître les meilleurs N prochains mouvements
Khaled.K
12

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:

entrez la description de l'image ici

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:

entrez la description de l'image ici

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:

entrez la description de l'image ici entrez la description de l'image ici entrez la description de l'image ici entrez la description de l'image ici entrez la description de l'image ici entrez la description de l'image ici

Sandipan Dey
la source
9

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

wvdz
la source
Essayez de l'étendre avec les règles réelles. C'est un bon défi d'apprendre le générateur aléatoire de Haskell!
Thomas Ahle
J'ai été très frustré par le fait que Haskell essaie de faire ça, mais je vais probablement essayer de nouveau! J'ai trouvé que le jeu devient beaucoup plus facile sans la randomisation.
wvdz
Sans randomisation, je suis presque sûr que vous pourriez trouver un moyen d'obtenir toujours 16k ou 32k. Cependant, la randomisation dans Haskell n'est pas si mauvaise, il vous suffit d'un moyen de contourner la `graine '. Soit explicitement, soit avec la monade aléatoire.
Thomas Ahle
Affiner l'algorithme pour qu'il atteigne toujours 16k / 32k pour un jeu non aléatoire pourrait être un autre défi intéressant ...
wvdz
Vous avez raison, c'est plus difficile que je ne le pensais. J'ai réussi à trouver cette séquence: [UP, LEFT, LEFT, UP, LEFT, DOWN, LEFT] qui gagne toujours la partie, mais elle ne dépasse pas 2048. (En cas de pas de mouvement légal, l'algorithme de cycle choisit simplement le suivant dans le sens des aiguilles d'une montre)
Thomas Ahle
6

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")
  }
API-Beast
la source
10
cela fonctionne mieux si vous dites random from (right, right, right, down, down, up) que tous les coups ne sont pas de probabilité égale. :)
Daren
3
En fait, si vous êtes complètement nouveau dans le jeu, il est vraiment utile de n'utiliser que 3 touches, essentiellement ce que fait cet algorithme. Donc, pas aussi mauvais qu'il n'y paraît à première vue.
Chiffres du
5
Oui, il est basé sur ma propre observation du jeu. Jusqu'à ce que vous deviez utiliser la 4ème direction, le jeu se résoudra pratiquement sans aucune observation. Cette "AI" devrait pouvoir atteindre 512/1024 sans vérifier la valeur exacte d'un bloc.
API-Beast
3
Une IA appropriée essaierait d'éviter d'atteindre un état où elle ne peut se déplacer que dans une seule direction à tout prix.
API-Beast
3
Utiliser seulement 3 directions est en fait une stratégie très décente! Cela m'a amené presque au 2048 en jouant manuellement. Si vous combinez cela avec d'autres stratégies pour décider entre les 3 mouvements restants, cela pourrait être très puissant. Sans oublier que réduire le choix à 3 a un impact énorme sur les performances.
wvdz
4

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.

alan2here
la source
5
Vous décrivez une recherche locale avec des heuristiques. Cela vous bloquera, vous devez donc planifier à l'avance pour les prochains mouvements. Cela vous mène à son tour à une recherche et à une notation des solutions (afin de décider). Donc, ce n'est vraiment pas différent de toute autre solution présentée.
runDOSrun