KI für das Spiel Threes! von Sirvo LLC. Sie können das Spiel hier herunterladen: http://asherv.com/ threes/
Der Aufbau dieser KI war die Inspiration für meine spätere KI von 2048, und einige der Ideen der KI von 2048 wurden auch auf diese KI zurückportiert.
Obwohl ich die Leistung dieser KI (noch) nicht offiziell bewertet habe, weiß ich, dass sie mehrmals erfolgreich die 6144-Stufe erreicht hat, was die höchste im Spiel verfügbare Stufe ist. (Höhere Kacheln sind möglich, aber aufgrund starker Zufallseffekte unwahrscheinlich.) Die Höchstpunktzahl (zum Zeitpunkt des Schreibens) beträgt 775.524 Punkte:
Diese KI ist aufgrund der höheren Komplexität von Threes viel experimenteller als ihre neuere Schwester-KI 2048! und weil es nicht so viel Entwicklungszeit erhalten hat. Darüber hinaus ist Threes! ist im Allgemeinen ein bewegliches Ziel, da die Algorithmen zur zufälligen Kachelgenerierung gelegentlich angepasst werden, was Änderungen in der KI erforderlich macht.
Der Algorithmus für diese KI wird in dieser StackOverflow-Antwort, die meine 2048-KI beschreibt, bereits im Wesentlichen detailliert beschrieben. Im Wesentlichen implementiert es eine hochoptimierte Brute-Force-Suche im Spielbaum (alle möglichen Züge, Kachel-Spawn-Werte und Kachel-Werte) und verwendet die Expectimax-Optimierung, um die Ergebnisse zu kombinieren und den „besten“ möglichen Zug zu finden.
Diese Threes-KI ist tatsächlich in vielerlei Hinsicht ausgefeilter als die 2048-KI: Vor allem berücksichtigt sie das „Deck“ der kommenden Kacheln (der gut dokumentierte Prozess, durch den die zufällig eingehenden Kacheln ausgewählt werden) und funktioniert ordnungsgemäß alle möglichen Plättchen-Spawn-Standorte basierend auf den durchgeführten Bewegungen. Kurz gesagt: Diese Threes-KI emuliert (nach meinem besten Wissen) jedes Detail des Threes-Spiels im Rahmen des Expectimax-Optimierungsprozesses korrekt.
Der einfachste Weg, die KI zum Laufen zu bringen, besteht darin, einen der prebuilt/ Zweige zu klonen, der Ihrem Betriebssystem und Prozessor entspricht. Diese Zweige verfügen über vorgefertigte Binärdateien im Verzeichnis bin/ .
Beachten Sie, dass das „Standard“-Python unter Windows 32-Bit ist, während das „Standard“-Python unter OS X und Linux 64-Bit ist. 32-Bit-Builds sind mit i386 gekennzeichnet, während 64-Bit-Builds mit x86_64 gekennzeichnet sind.
Wenn Sie es selbst aus dem Quellcode erstellen möchten (z. B. wenn Sie Änderungen vornehmen), befolgen Sie die nachstehenden Anweisungen.
Ausführen
./configure
make
in einem Terminal. Jeder relativ neue C++-Compiler sollte in der Lage sein, die Ausgabe zu erstellen.
Beachten Sie, dass Sie make install nicht ausführen; Dieses Programm soll von diesem Verzeichnis aus ausgeführt werden.
Je nachdem, was Sie installiert haben, haben Sie mehrere Möglichkeiten.
Pure Cygwin: Befolgen Sie die obigen Anweisungen für Unix/Linux/OS X. Die resultierende DLL kann nur mit Cygwin-Programmen verwendet werden. Um die Browser-Steuerungsversion auszuführen, müssen Sie also Cygwin Python (nicht python.org Python) verwenden. Eine Schritt-für-Schritt-Anleitung mit freundlicher Genehmigung von Tamas Szell (@matukaa) finden Sie in diesem Dokument.
Cygwin mit MinGW: ausführen
CXX=x86_64-w64-mingw32-g++ CXXFLAGS='-static-libstdc++ -static-libgcc -D_WINDLL -D_GNU_SOURCE=1' ./configure ; make
in einer MinGW- oder Cygwin-Shell zu erstellen. Die resultierende DLL kann mit Nicht-Cygwin-Programmen verwendet werden.
Visual Studio: Öffnen Sie eine Visual Studio-Eingabeaufforderung, cd in das Verzeichnis threes-ai und führen Sie make-msvc.bat aus.
Sie benötigen Python 2.7, NumPy und PIL, um die Python-Programme auszuführen.
Führen Sie bin/threes aus, wenn Sie die KI selbst in Aktion sehen möchten.
Es gibt einige webbasierte Versionen von Threes, aber ich wollte die KI gegen die echte App spielen lassen. Deshalb habe ich ein „Assistenten“-Programm für Android-Geräte namens android_assistant.py erstellt, das über ADB mit dem Telefon kommuniziert und Bewegungen völlig automatisch ausführt. Es erfordert nur USB-ADB-Berechtigungen (Standard-Entwicklerzugriff) und erfordert kein Rooten oder andere Änderungen des Geräts oder der App. Es verwendet das standardmäßige Android screencap Dienstprogramm, um den (sichtbaren) Spielstatus zu ermitteln, berechnet den optimalen Zug und verwendet dann das Linux-Eingabeereignis-Subsystem, um Wischereignisse zu generieren.
Um android_assistant.py zu verwenden, müssen Sie das OCR-Subsystem für Ihr Gerät konfigurieren. Sie müssen außerdem Swipe-Ereignisse zur Wiedergabe aufzeichnen. Derzeit sind zwei Geräte konfiguriert: das LG Nexus 5 und das OnePlus One (entsprechend den Telefonen, auf denen ich dies getestet habe). Gerne können Patches hinzugefügt werden, um weitere Telefone hinzuzufügen.
Um das OCR-System zu konfigurieren, sollten Sie in ocr/devices.py einen Eintrag hinzufügen, der Ihrem Gerät entspricht. Den Modellnamen erhalten Sie, indem Sie einfach android_assistant.py ausführen, während Sie mit dem Gerät verbunden sind (es sollte ein Fehler mit dem erwarteten Modellnamen auftreten). Im Wesentlichen müssen Sie einen Screenshot des Spiels erstellen und die Position des Bereichs „Kommende Kachel“ sowie die Position und den Abstand des Kachelrasters ableiten. (Dieser Teil könnte wahrscheinlich mehr Automatisierung und/oder Vereinfachung gebrauchen!)
Um Ereignisse aufzuzeichnen, führen Sie einfach python -m android.inputemu --record up down left right aus und führen Sie die entsprechende Geste auf Ihrem Telefon aus, wenn Sie dazu aufgefordert werden.
Der manuelle Assistent ist ein Allzweck-Dreier! Assistent, der mit jeder Implementierung von Threes! funktioniert. Sie teilen ihm das Spielbrett und den bevorstehenden Steinsatz mit, und der Assistent berechnet den besten Zug.
Führen Sie manual_assistant.py aus, um den manuellen Assistenten zu starten.
Beachten Sie, dass der manuelle Assistent erwartet, dass aufeinanderfolgende Bewegungen angezeigt werden. Wenn Sie weiterspringen (Züge ohne den Assistenten ausführen), beenden Sie den Assistenten durch Drücken von Strg+C und starten Sie ihn erneut. Andernfalls erhalten Sie möglicherweise eine Fehlermeldung wie „unmögliche Situation“, wenn Sie ein Board eingeben, das nicht sequenziell zum vorherigen Board ist.
Beim Betreten der nächsten Tafel können Sie Leerzeichen, Zeilenumbrüche und/oder Kommas verwenden, um Kacheln zu trennen. Lesen Sie von links nach rechts und dann von oben nach unten. Geben Sie für Leerzeichen eine Null ein. Beispieleingabe:
Verwendung von Kommas und Zeilenumbrüchen:
96,2,3,0
2,1,1,0
2,1,0,0
0,0,2,0
Nur Kommas verwenden:
96,2,3,0,2,1,1,0,2,1,0,0,0,0,2,0
Verwendung von Leerzeichen:
96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0
Sie können auch ein „Delta“ vom vorherigen Board eingeben. Geben Sie die Zeile oder Spalte an, in der das neue Plättchen entstanden ist, und den Wert des Plättchens, das entstanden ist (Sie können dies weglassen, wenn beim letzten Zug nur ein neues Plättchen möglich war, z. B. wenn es rot oder blau war). Geben Sie auch den Zug an, den Sie ausgeführt haben, wenn es sich nicht um den von der KI vorgeschlagenen Zug handelte.
Spalten und Zeilen sind von links nach rechts und von oben nach unten nummeriert: Spalte 1 ist die linke Spalte und Zeile 1 ist die oberste Zeile.
Zum Beispiel, wenn das Board nach oben gewischt wird und ausgeht
96 2 3 0
2 1 1 0
2 1 0 0
0 0 2 0
Zu
96 3 3 0
2 1 1 0
2 0 2 0
0 3 0 0
Dann würden Sie 2,3,up schicken (in der 2. Spalte erscheint eine 3). Wenn die KI die up empfohlen hätte, könnten Sie diese einfach weglassen und 2,3 senden. Wenn die bevorstehende Kachel als 3 vorhergesagt worden wäre, könnten Sie die 3 weglassen und nur 2 senden.
Durch die Eingabe von Deltas sparen Sie viel Zeit. In den meisten Fällen müssen Sie nur eine Zahl eingeben (die Spalte/Zeile, die sich geändert hat).
Verwenden Sie beim Eingeben der nächsten Kachel eines der folgenden Formate:
blue (1), red (2) oder white (3+)1 , 2 , 3 , 3+ , 6+ , oder z. B. 24,48,96 , 24 48 963+ bedeutet, dass es eine 3 oder höher sein könnte; Verwenden Sie dies mit älteren Threes! die auf Bonusplättchen kein „Plus“-Zeichen zeigen6+ bedeutet, dass es sich um ein beliebiges Bonusplättchen handelt; Verwenden Sie dies, wenn die kommende Kachel „+“ ist.24,48,96 bedeutet, dass es einer dieser drei ist; Verwenden Sie dies mit neueren Threes! die Ihnen explizite Optionen für den Bonusplättchenwert zeigen.
