IA pour le jeu Threes ! par Sirvo LLC. Vous pouvez obtenir le jeu ici : http://asherv.com/trois/
La construction de cette IA a été l'inspiration de mon IA 2048 ultérieure, et certaines des idées de l'IA 2048 ont également été rétroportées sur cette IA.
Bien que je n'aie pas (encore) formellement évalué les performances de cette IA, je sais qu'elle a réussi à atteindre plusieurs fois la tuile 6144, qui est la tuile la plus élevée disponible dans le jeu. (Des tuiles plus hautes sont possibles mais peu probables, en raison d'effets aléatoires importants). Le meilleur score (au moment de la rédaction) est de 775 524 points :
Cette IA est beaucoup plus expérimentale que sa nouvelle sœur, l'IA 2048, en raison de la complexité accrue de Threes ! et parce qu'il n'a pas bénéficié d'autant de temps de développement. De plus, Trois ! est en général une cible un peu mouvante car les algorithmes de génération aléatoire de tuiles sont parfois modifiés, ce qui nécessite des changements dans l'IA.
L'algorithme de cette IA est déjà essentiellement détaillé dans cette réponse StackOverflow décrivant mon IA 2048. Essentiellement, il implémente une recherche par force brute hautement optimisée dans l'arborescence du jeu (tous les mouvements possibles, les valeurs d'apparition des tuiles et les valeurs des tuiles), en utilisant l'optimisation Expectimax pour combiner les résultats et trouver le « meilleur » mouvement possible.
Cette IA Threes est en réalité plus sophistiquée que l'IA 2048 à plusieurs égards : plus particulièrement, elle prend en compte le "deck" des tuiles à venir (le processus bien documenté par lequel les tuiles entrantes aléatoires sont sélectionnées), et elle gère correctement tous les emplacements d'apparition de tuiles possibles en fonction des mouvements effectués. En bref : cette IA Threes émule correctement (au meilleur de ma connaissance) chaque détail du jeu Threes dans le cadre du processus d'optimisation Expectimax.
Le moyen le plus simple de faire fonctionner l'IA est de cloner l'une des branches prebuilt/ correspondant à votre système d'exploitation et à votre processeur. Ces branches ont des binaires prédéfinis dans le répertoire bin/ .
Notez que le Python « par défaut » sur Windows est en 32 bits, tandis que le Python « par défaut » sur OS X et Linux est en 64 bits. Les versions 32 bits sont étiquetées i386 tandis que les versions 64 bits sont étiquetées x86_64 .
Si vous souhaitez le construire vous-même à partir des sources (par exemple si vous apportez des modifications), suivez les instructions ci-dessous.
Exécuter
./configure
make
dans une borne. Tout compilateur C++ relativement récent devrait être capable de générer la sortie.
Notez que vous ne faites pas make install ; ce programme est destiné à être exécuté à partir de ce répertoire.
Vous disposez de quelques options, en fonction de ce que vous avez installé.
Pure Cygwin : suivez les instructions Unix/Linux/OS X ci-dessus. La DLL résultante ne peut être utilisée qu'avec les programmes Cygwin, donc pour exécuter la version de contrôle du navigateur, vous devez utiliser le Python Cygwin (pas le Python python.org). Pour des instructions étape par étape, avec l'aimable autorisation de Tamas Szell (@matukaa), consultez ce document.
Cygwin avec MinGW : exécuter
CXX=x86_64-w64-mingw32-g++ CXXFLAGS='-static-libstdc++ -static-libgcc -D_WINDLL -D_GNU_SOURCE=1' ./configure ; make
dans un shell MinGW ou Cygwin à construire. La DLL résultante peut être utilisée avec des programmes non Cygwin.
Visual Studio : ouvrez une invite de commande Visual Studio, cd au répertoire threes-ai et exécutez make-msvc.bat .
Vous aurez besoin de Python 2.7, NumPy et PIL pour exécuter les programmes Python.
Exécutez bin/threes si vous voulez voir l'IA seule en action.
Il existe des versions Web de Threes, mais je voulais que l'IA joue contre la vraie application. J'ai donc créé un programme "assistant" pour les appareils Android, appelé android_assistant.py , qui communique avec le téléphone via ADB et effectue des mouvements de manière entièrement automatique. Il nécessite uniquement des autorisations USB ADB (accès développeur standard) et ne nécessite pas de root ou toute autre modification de l'appareil ou de l'application. Il utilise l'utilitaire standard Android screencap pour obtenir l'état (visible) du jeu, calcule le mouvement optimal, puis utilise le sous-système d'événements d'entrée Linux pour générer des événements de balayage.
Pour utiliser android_assistant.py , vous devrez configurer le sous-système OCR pour votre appareil. Vous devrez également enregistrer les événements de balayage pour les rejouer. Actuellement, deux appareils sont configurés : le LG Nexus 5 et le OnePlus One (correspondant aux téléphones sur lesquels j'ai testé cela). Les correctifs sont les bienvenus pour ajouter plus de téléphones.
Pour configurer le système OCR, vous devez ajouter une entrée dans ocr/devices.py correspondant à votre appareil. Le nom du modèle peut être obtenu en exécutant simplement android_assistant.py lorsque vous êtes connecté à l'appareil (il devrait afficher une erreur avec le nom du modèle attendu). Essentiellement, vous devrez prendre une capture d'écran du jeu et en déduire la position du volet « tuile à venir », ainsi que la position et l'espacement de la grille de tuiles. (Cette partie pourrait probablement nécessiter plus d'automatisation et/ou de simplification !)
Pour enregistrer des événements, exécutez simplement python -m android.inputemu --record up down left right et exécutez le geste approprié sur votre téléphone lorsque vous y êtes invité.
L'assistant manuel est un Threes polyvalent ! assistant qui fonctionne avec n'importe quelle implémentation de Threes !. Vous lui indiquez le tableau et le jeu de tuiles à venir, et l'assistant calcule le meilleur coup.
Exécutez manual_assistant.py pour démarrer l'assistant manuel.
Notez que l'assistant manuel s'attend à voir des mouvements séquentiels. Si vous avancez (en effectuant des mouvements sans l'assistant), quittez l'assistant en appuyant sur Ctrl+C et redémarrez-le. Sinon, vous pourriez recevoir un message d'erreur du type « situation impossible » si vous entrez dans un tableau qui n'est pas séquentiel par rapport au tableau précédent.
Lorsque vous entrez dans le tableau suivant, vous pouvez utiliser des espaces, des nouvelles lignes et/ou des virgules pour séparer les tuiles. Lisez de gauche à droite, puis de haut en bas. Entrez un zéro pour les espaces vides. Exemple d'entrée :
Utiliser des virgules et des sauts de ligne :
96,2,3,0
2,1,1,0
2,1,0,0
0,0,2,0
En utilisant uniquement des virgules :
96,2,3,0,2,1,1,0,2,1,0,0,0,0,2,0
Utilisation des espaces :
96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0
Vous pouvez également saisir un "delta" du tableau précédent. Spécifiez la ligne ou la colonne dans laquelle la nouvelle tuile est apparue, ainsi que la valeur de la tuile qui est apparue (vous pouvez l'omettre s'il n'y avait qu'une seule nouvelle tuile possible lors du dernier mouvement, par exemple si elle était rouge ou bleue). Précisez également le mouvement que vous avez effectué s'il ne s'agit pas du mouvement suggéré par l'IA.
Les colonnes et les lignes sont numérotées de gauche à droite et de haut en bas : la colonne 1 est la colonne de gauche et la ligne 1 est la ligne du haut.
Par exemple, si le tableau est balayé vers le haut et passe de
96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0
à
96 3 3 0
2 1 1 0
2 0 2 0
0 3 0 0
alors vous enverriez 2,3,up comme tableau (dans la 2ème colonne, un 3 apparaît). Si l'IA avait recommandé le mouvement up , vous pourriez simplement l'omettre et envoyer 2,3 . Si la tuile à venir avait été prévue comme étant 3, vous pourriez omettre le 3 et n'envoyer que 2 .
En entrant dans les deltas, vous gagnerez beaucoup de temps. Dans la plupart des cas, il vous suffit de saisir un seul chiffre (la colonne/ligne qui a changé).
Lors de la saisie de la vignette à venir, utilisez l'un des formats suivants :
blue (1), red (2) ou white (3+)1 , 2 , 3 , 3+ , 6+ , ou par exemple 24,48,96 , 24 48 963+ signifie qu'il pourrait s'agir d'un 3 ou plus ; utilisez-le avec des Threes plus âgés ! qui n'affichent pas de signe "plus" sur les tuiles bonus6+ signifie qu’il s’agit de n’importe quelle tuile bonus ; utilisez-le si la tuile à venir est "+"24,48,96 signifie que c'est l'un de ces trois ; utilisez-le avec les nouveaux Threes ! qui vous montrent des options explicites pour la valeur de la tuile bonus.
