"2048" dans quelques semaines marque 5 ans, ce qui signifie qu'il est temps d'écrire quelque chose de dédié à ce merveilleux jeu.
Le sujet d'un jeu indépendant d'intelligence artificielle dans un puzzle est particulièrement informatif. Il existe différentes manières de le mettre en œuvre et aujourd'hui nous allons en analyser une relativement facile. À savoir, nous apprendrons à l'esprit informatique à collecter des degrés de deux en utilisant la méthode de Monte Carlo.
Cet article a été rédigé avec le soutien d'EDISON Software, une société qui développe des applications mobiles et fournit des services de test de logiciels .
L'inspiration pour ce travail a été une discussion sur stackoverflow, où
des gars intelligents ont suggéré des moyens efficaces de jouer sur ordinateur . Apparemment, le meilleur moyen est la méthode minimax avec écrêtage alpha-bêta et dans quelques jours la prochaine publication lui sera consacrée.
Méthode de casino suggérée par l'utilisateur stackoverflow
Ronenz dans le cadre de la discussion ci-dessus. La section suivante entière est une traduction de sa publication.
Méthode Monte Carlo
Je me suis intéressé à l'idée de l'IA pour ce jeu, dans lequel
il n'y a
pas d'intelligence codée en dur (c'est-à-dire qu'il n'y a pas d'heuristique, de score, etc.). L'IA ne doit «connaître» que les règles du jeu et «comprendre» le jeu. Cela le distingue de la plupart des IA (comme dans ce fil), car le gameplay est, en fait, une force brute contrôlée par la fonction de notation, reflétant 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 état de terrain donné, l'IA joue le jeu en RAM, effectuant
des mouvements aléatoires jusqu'à ce que le jeu se termine par une défaite. Cela se fait plusieurs fois, le score final étant suivi. Ensuite, le score final moyen est calculé en tenant compte du parcours initial. Le coup initial qui a montré le résultat moyen le plus élevé est sélectionné comme le coup déjà choisi.
Avec 100 points pour chaque tour initial, l'IA atteint la tuile 2048 dans 80% des cas et la tuile 4096 dans 50% des cas. En utilisant 10000 essais, 2048 sont obtenus dans 100% des cas, 70% pour 4096 et environ 1% pour 8192.
Voir en actionLe meilleur résultat obtenu est illustré dans la capture d'écran:
Un fait intéressant pour cet algorithme est que, bien que les jeux avec des mouvements exécutés de manière aléatoire soient censés être assez mauvais, néanmoins, choisir le meilleur (ou le moins mauvais, si vous le souhaitez) conduit à un très bon gameplay: un jeu typique de Monte Carlo AI peut marquer 70 000 points pour 3000 coups, mais les jeux avec un jeu arbitraire en mémoire à partir d'une position donnée donnent en moyenne 340 points supplémentaires pour environ 40 coups supplémentaires avant de perdre. (Vous pouvez le vérifier vous-même en démarrant l'IA et en ouvrant la console de débogage.)
Ce graphique illustre ce concept: la ligne bleue montre le score de la partie après chaque coup. La ligne rouge montre le
meilleur résultat de l'algorithme, effectuant arbitrairement des mouvements de cette position à la fin de la partie. En fait, les valeurs rouges «tirent» les bleues, car ce sont les meilleures phrases de l'algorithme. Fait intéressant, la ligne rouge est légèrement au-dessus de la ligne bleue à chaque point, mais la ligne bleue réduit de plus en plus l'écart.
Je trouve plutôt surprenant que l'algorithme n'anticipe pas nécessairement un bon gameplay, et choisisse néanmoins les coups qui le produisent (un bon processus).
Plus tard, j'ai découvert que cette méthode peut être classée comme
un algorithme de recherche d'arbre Monte Carlo .
Implémentation et liens
Tout d'abord, j'ai créé une version JavaScript qui peut être
vue en action ici . Cette version est capable d'exécuter 100 exécutions dans un délai raisonnable. Ouvrez la console pour plus d'informations. (
source )
Plus tard, pour jouer, j'ai utilisé l'infrastructure @nneonneo hautement optimisée et implémenté ma version en C ++. Cette version permet jusqu'à 100 000 courses par tour et même 1 000 000 si vous êtes prêt à attendre. Instructions de montage incluses. Tout fonctionne dans la console et dispose également d'une télécommande pour la lecture dans la version Web. (
source )
Résultats
Étonnamment, une augmentation du nombre de runs n'améliore pas fondamentalement le gameplay. Il semble que cette stratégie ait une limite de 80 000 points avec une tuile de 4096 et tous les petits résultats très proches d'atteindre la tuile 8192. Une augmentation du nombre de pistes de 100 à 100 000 augmente les chances d'atteindre cette limite (de 5% à 40%), mais pas le surmonte.
La réalisation de 10 000 descentes avec une augmentation temporaire de jusqu'à 1 000 000 de positions proches des points critiques a permis de surmonter cette barrière dans moins de 1% des cas avec le nombre maximum de points marqués 129892 et les tuiles 8192.
Améliorations et optimisations
Après avoir implémenté cet algorithme, j'ai essayé de nombreuses améliorations, notamment l'utilisation de notes minimales ou maximales ou une combinaison de valeurs minimales, maximales et moyennes. J'ai également essayé d'utiliser la profondeur: au lieu d'essayer de terminer K courses par tour, j'ai essayé K mouvements par liste de mouvements d'une longueur donnée (par exemple, «haut, haut, gauche») et j'ai choisi le premier mouvement de la liste des mouvements avec la meilleure victoire.
Plus tard, j'ai implémenté un arbre de score qui tenait compte de la probabilité conditionnelle qu'il soit capable de terminer un mouvement après une liste donnée de mouvements.
Cependant, aucune de ces idées n'a montré un réel avantage sur une simple première idée. J'ai laissé du code commenté pour ces idées dans la source C ++.
J'ai ajouté le mécanisme de recherche approfondie, qui a temporairement augmenté le nombre d'exécutions à 1 000 000 lorsque l'une des exécutions a accidentellement réussi à atteindre la tuile la plus élevée suivante. Cela a conduit à une amélioration des performances temporelles.
J'aimerais savoir si quelqu'un a d'autres idées d'amélioration qui soutiennent l'indépendance de l'IA par rapport au sujet?
Options et clones 2048
Pour le plaisir, j'ai également implémenté l'IA en tant que bookmarklet, en le connectant aux commandes du jeu. Cela vous permet de travailler à la fois 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 options sont assez originales, comme un clone hexagonal.
2048.xlsm
L'application Excel elle-même
peut être téléchargée depuis Google .
L'image est cliquable - une image en taille réelle s'ouvrira.
Brièvement sur l'interface et les fonctionnalités de l'application.
Pour commencer à jouer, vous devez cliquer sur le bouton "
Utilisateur: démarrer le jeu ". Lorsque vous appuyez à nouveau sur ce bouton, l'inscription passe de "
Utilisateur: démarrer le jeu " à "
Utilisateur: terminer le jeu " et vice versa, c'est-à-dire qu'à tout moment vous pouvez arrêter le jeu puis le redémarrer. Lorsque le jeu s'arrête, vous pouvez modifier manuellement l'alignement sur le terrain, en améliorant ou en aggravant votre position afin de tester ou de vérifier certaines idées.
Pendant le jeu lui-même, vous pouvez effectuer des mouvements de deux manières:
- Clavier: en appuyant simplement sur les touches "haut", "bas", "gauche", "droite".
- Avec la souris: cliquer sur les cellules avec de grandes flèches indiquant la direction souhaitée.
Le bouton "
New Field " efface le terrain de jeu et place aléatoirement les "deux" et "quatre" dessus.
La chose la plus intéressante est que la méthode Monte Carlo a été implémentée, exactement sous la forme dans laquelle elle a été proposée par le mec avec stackoverflow. À chaque position, l'ordinateur en mémoire passe par des branches aléatoires pour chaque premier mouvement («haut», «bas», «gauche», «droite») jusqu'à ce qu'il entraîne une perte. Statistiquement, la direction la plus favorable est surlignée en rouge dans un tableau spécial ci-dessous. Vous pouvez l'utiliser comme indice si vous voyez que votre propre jeu est à l'arrêt et que vous devez vous sauver d'une manière ou d'une autre. ;)
Au-dessus du tableau se trouvent des cases à cocher avec des options d'analyse. Pour le moment, seul Monte Carlo a été décidé, le reste sera ajouté dans les prochains jours (à la suite de quoi il y aura plus de harastas avec la mise à jour de l'application Excel et des explications de la théorie).
Il y a aussi un bouton
AI: game . En cliquant dessus, l'assistant informatique effectuera un mouvement conformément à la méthode de Monte Carlo ou à un autre qui est sélectionné dans le groupe de commutateurs (minimax et réseau de neurones fonctionneront dans cette liste un peu plus tard).
Tous les articles des séries AI et 2048