Quel Est L’algorithme Optimal pour le jeu 2048?
Introduction
2048 est un jeu passionnant de changement de tuiles, où nous déplaçons des tuiles pour les combiner, visant des valeurs de tuiles de plus en plus grandes.
Dans ce tutoriel, nous allons étudier un algorithme pour jouer à 2048, qui aidera à déterminer les meilleurs coups à faire à chaque étape pour obtenir le meilleur score.
Comment Jouer à 2048
Un jeu de 2048 est joué sur un 4×4 conseil d’administration., Chaque position sur la carte peut être vide ou peut contenir une tuile, et chaque tuile aura un numéro dessus.
lorsque nous commencerons, le tableau aura deux tuiles dans des endroits aléatoires, chacune ayant un « 2” ou un « 4” – chacune a 10% de chances indépendantes d’être un « 4”, ou sinon a est un « 2”.
Les mouvements sont effectués en déplaçant toutes les tuiles vers un bord – haut, bas, gauche ou droite., Lorsque vous faites cela, toutes les tuiles avec la même valeur qui sont adjacentes les unes aux autres et se déplacent ensemble fusionneront et se retrouveront avec une nouvelle tuile égale à la somme des deux précédentes:
Après avoir fait un mouvement, une nouvelle tuile sera placée sur le tableau. Celui-ci est placé dans un endroit aléatoire, et sera un « 2” ou « 4” de la même manière que la première carreaux – « 2” 90% du temps, et « 4” 10% du temps.
Le jeu continue ensuite jusqu’à ce qu’il n’y ait plus de mouvements possibles.
En général, le but du jeu est d’atteindre une seule tuile avec une valeur de « 2048”., Cependant, le jeu ne s’arrête pas là, et nous pouvons continuer à jouer aussi loin qu’il est possible d’aller, en visant la plus grande tuile possible. En théorie, il s’agit d’une tuile avec la valeur « 131 072”.
explication du problème
résoudre ce jeu est un problème intéressant car il a une composante aléatoire. Il est impossible de prédire correctement non seulement où chaque nouvelle tuile sera placé, mais si ce sera un « 2” ou « 4”.
en tant que tel, il est impossible d’avoir un algorithme qui résoudra correctement le puzzle à chaque fois., Le mieux que nous puissions faire est de déterminer ce qui est susceptible d’être le meilleur mouvement à chaque étape et de jouer le jeu des probabilités.
à tout moment, il n’y a que quatre mouvements possibles que nous pouvons faire. Parfois, certains de ces mouvements n’ont aucun impact sur le plateau et ne valent donc pas la peine d’être effectués – par exemple, dans le tableau ci-dessus, un mouvement de « bas” n’aura aucun impact puisque toutes les tuiles sont déjà sur le bord inférieur.
le défi consiste alors à déterminer lequel de ces quatre mouvements sera celui qui aura le meilleur résultat à long terme.,
notre algorithme est basé sur L’algorithme Expectimax, qui est lui-même une variante de L’algorithme Minimax, mais où les itinéraires possibles à travers notre arbre sont pondérés par la probabilité qu’ils se produisent.
Essentiellement, nous traitons le jeu comme un jeu à deux joueurs:
- Player One-le joueur humain – peut déplacer le plateau dans l’une des quatre directions
- Player Two – Le joueur informatique – peut placer une tuile dans un emplacement vide sur le plateau
sur cette base, Nous pouvons générer un arbre de résultats de chaque mouvement, pondéré par la probabilité que chaque mouvement se produise., Cela peut alors nous donner les détails nécessaires pour déterminer quel mouvement humain est susceptible de donner le meilleur résultat.
3.1. Organigramme du Gameplay
le déroulement général du gameplay:
Nous pouvons immédiatement voir l’aspect aléatoire du jeu dans le processus « Ajouter une tuile aléatoire” – à la fois dans le fait que nous trouvons un carré aléatoire pour ajouter la tuile, et nous sélectionnons une valeur aléatoire pour la tuile.
notre défi est alors de décider quoi faire à l’étape « déterminer le prochain mouvement”. C’est notre algorithme pour jouer le jeu.,
le débordement général de cela semble trompeusement simple:
Tout ce que nous devons faire est de simuler chacun des mouvements possibles, de déterminer lequel donne le meilleur résultat, puis de l’utiliser.
Nous avons donc maintenant réduit notre algorithme en simulant un mouvement donné et en générant un score pour le résultat.
il s’agit d’un processus en deux parties. La première passe consiste à voir si le mouvement est même possible, et sinon, alors abandonnez tôt avec un score de « 0”., Si le déplacement est possible, nous passerons à l’algorithme réel où nous déterminerons à quel point un déplacement est bon:
3.2. Déterminer le prochain mouvement
la partie clé de notre algorithme jusqu’à présent consiste à simuler un mouvement, et la partie clé de cela est la façon dont nous générons un score pour chaque mouvement possible. C’est là que notre algorithme Expectimax entre en jeu.
nous allons simuler tous les mouvements possibles des deux joueurs pendant plusieurs étapes, et voir lequel de ceux-ci donne le meilleur résultat. Pour le joueur humain, cela signifie Chacun des mouvements” haut »,” bas »,” gauche « et” droite ».,
pour le joueur informatique, cela signifie placer une tuile « 2” ou « 4” dans tous les emplacements vides possibles:
Cet algorithme est récursif, chaque étape récursive ne s’arrêtant que si elle est à une certaine profondeur du mouvement réel dans le jeu réel.,pour chacun de ces
- simuler chaque mouvement humain possible
- Pour chacun de ces
- simuler chaque mouvement humain possible
- Pour chacun de ces
- revenir dans l’algorithme
- retourner le score calculé à partir de ce mouvement humain
- ajouter le score calculé à partir de ce mouvement informatique, pondéré par une probabilité que ce mouvement se produise
lorsque nous avons terminé cela, nous additionnons ensuite tous les scores calculés, et c’est le score final pour le mouvement que nous voulons faire à partir du plateau de jeu actuel., Parce que nous faisons cela quatre fois – une pour chaque mouvement possible du plateau de jeu actuel – nous nous retrouvons avec quatre scores, et le plus élevé d’entre eux est le mouvement à faire.
3.3. Notation D’une position de tableau
à ce stade, il ne reste plus qu’à calculer un score pour un tableau. Ce n’est pas le même score que le jeu utilise, mais il doit prendre en compte la bonne position pour continuer à jouer.
Il existe un grand nombre de façons d’y parvenir en ajoutant plusieurs facteurs ainsi que des pondérations appropriées., Par exemple:
- Nombre d’emplacements vides
- Nombre de fusions possibles – c’est – à-dire le nombre de fois que le même nombre se trouve dans deux emplacements adjacents
- la plus grande valeur dans n’importe quel emplacement
- somme de tous les emplacements
- monotonie de la carte-c’est ainsi que la carte est bien structurée, de telle sorte que les valeurs d’emplacement augmentent dans une seule direction.
Pseudo
Maintenant que nous savons comment l’algorithme est d’aller au travail, à quoi cela ressemble? Explorons un pseudocode décrivant l’algorithme plus en détail.,
Nous ne sommes pas intéressés par le jeu réel du jeu, juste par l’algorithme de détermination des mouvements, alors commençons par là:
comme précédemment, cela nous amène au point où nous simulons chacun des mouvements possibles du plateau de départ et renvoyons celui qui marque le meilleur. Cela nous laisse avec la nécessité de générer des scores pour les cartes nouvellement simulées.
nous avons ajouté une limite de profondeur afin que nous puissions arrêter le traitement après un certain temps., Parce que nous travaillons avec un algorithme récursif, nous avons besoin d’un moyen de l’arrêter sinon il fonctionnera potentiellement pour toujours:
cela nous donne notre récursivité, simulant tous les mouvements humains et informatiques possibles pour un certain nombre d’étapes et décidant quels mouvements humains donnent le meilleur résultat possible.
la seule chose qui reste est d’établir un score final pour une position de conseil donnée. Il n’y a pas d’algorithme parfait pour cela, et différents facteurs donneront des résultats différents.,
l’Optimisation de la Performance
jusqu’à présent, nous avons obtenu un algorithme qui tentera de résoudre le jeu, mais il n’est pas aussi efficace qu’elle pourrait l’être. En raison de la nature aléatoire du jeu, il est impossible d’avoir un solveur parfaitement optimisé – il y aura toujours un certain niveau de répétition simplement à cause de la nature du processus.
nous pouvons au moins faire de notre mieux pour réduire le travail que nous n’avons pas besoin de faire.,
Nous faisons déjà un peu d’optimisation dans l’algorithme ci-dessus en ne traitant aucun mouvement qui n’a aucun impact sur le jeu. Il existe cependant d’autres moyens de réduire le travail à faire, tels que le suivi de la probabilité cumulative de mouvements et l’arrêt lorsque cela devient trop faible. Cela a le risque de supprimer la solution parfaite, mais si la probabilité est aussi faible, cela ne se produira presque certainement pas de toute façon.
Nous pouvons également déterminer dynamiquement la limite de profondeur avec laquelle travailler., Notre pseudocode ci-dessus a une limite codée en dur de 3, mais nous pourrions calculer dynamiquement cela en fonction de la forme de la carte au début de nos calculs – par exemple, en la définissant sur le nombre de carrés vides ou le nombre de tuiles distinctes sur la carte. Cela signifierait que nous traversons moins déplacements des planches qui ont moins de possibilités d’expansion.
de plus, comme il est possible de revoir plusieurs fois les mêmes positions de la carte, nous pouvons nous en souvenir et mettre en cache le score de ces positions au lieu de les recalculer à chaque fois., Potentiellement, nous pouvons générer toutes les positions de carte possibles à l’avance, mais il y en a un grand nombre – 281 474 976 710 656 différentes positions de carte possibles en utilisant des tuiles jusqu’à 2048 – donc ce n’est probablement pas possible.
cependant, l’optimisation la plus importante que nous puissions faire est d’ajuster l’algorithme pour générer des scores de carte. Cela fonctionne pour décider à quel point le Conseil est bon pour continuer à Jouer et les facteurs et les pondérations que nous utilisons pour cela sont directement liés à la façon dont notre algorithme joue.,
Conclusion
2048 est un très intéressant jeu pour tenter de le résoudre. Il n’y a pas de moyen idéal pour le résoudre, mais nous pouvons écrire des heuristiques qui rechercheront les meilleurs itinéraires possibles à travers le jeu.
les mêmes principes généraux fonctionnent pour tout jeu à deux joueurs-par exemple, les échecs – où vous ne pouvez pas prédire ce que l’autre joueur fera avec un degré de certitude.
pourquoi ne pas essayer d’écrire une implémentation de ceci et voir à quel point cela fonctionne?