Fast optimale Lösung für dreidimensionale 4x4x4-Nullen und -Kreuze

    Jeder kennt das Spiel Tic-Tac-Toe 3x3. Mit dem richtigen Spiel beim ersten Kreuzzug ist das Ergebnis ein Unentschieden. Sie können manuell einen Baum von Zügen erstellen, wobei bei jeder Bewegung von Nullen eine Bewegung von Kreuzen erfolgt, die zum besten Ergebnis (für Kreuze) führt, dh zu einem Unentschieden oder Gewinn. Dieser Bewegungsbaum erschöpft alle Optionen, so dass das Spiel "gelöst" ist. Es gibt einen dreidimensionalen Typ von 4x4x4-Tic-Tac-Toe, für den die Antwort auf die Frage, wer im ersten Kreuzzug gewinnen wird, nicht offensichtlich ist. Darüber hinaus stellt sich die Frage, ob es möglich ist, einen minimalen Baum zu konstruieren, der dieses Problem löst.

    Die Antwort auf diese Frage im Schnitt.

    Ich möchte Sie daran erinnern, dass es ein 4x4x4-Tic-Tac-Toe-Spiel (auch als Qubic bezeichnet) ist.
    Dies ist ein Würfel, der aus 64 Feldern besteht, in denen Sie gewinnen müssen, indem Sie 4 aufeinanderfolgende Kreuze oder Nullen setzen. Diese können sich entlang jeder Linie erstrecken, einschließlich der Hauptdiagonalen. Insgesamt gibt es 76 solcher Linien - 48 Höhenlinien und Vertikale, 24 Diagonalen und 4 Hauptdiagonalen. Aus diesem Grund können Sie sehen, dass nicht alle Felder gleich sind: Es gibt 8 Winkelfelder und 8 Mittelfelder, die 7 Zeilen steuern, und 48 andere Felder, die 4 Zeilen steuern. Daher ist es sinnvoll zu versuchen, Positionen einzunehmen, die mehr Linien kontrollieren.

    Bild

    Was ist die Schwierigkeit, einen Entscheidungsbaum für dieses Spiel zu erstellen? Es kann grob als zwei bis 64 Varianten geschätzt werden, was ziemlich viel ist. Natürlich werden nicht alle diese Optionen im Spiel realisiert und viele Äste des Baums werden ziemlich schnell abgeschnitten. In diesem Fall ist es jedoch nicht möglich, einen solchen Baum durch einfache Aufzählung zu erstellen. Wie können wir die Obergrenze reduzieren, um dieses Problem zu lösen? Es kann bemerkt werden, dass nach mehreren Kreuzungs- und Nullbewegungen eine Situation entstehen kann, in der es möglich ist, eine Bedrohung für den Feind zu erzeugen, indem drei Kreuze oder Nullen in einer einzigen Zeile platziert werden. Bei einer solchen Bedrohung muss der Feind seinen nächsten Zug auf den verbleibenden leeren Platz in dieser Zeile machen, andernfalls wird er im nächsten Zug verlieren. Solche Bewegungen mit der Bedrohung können mehrere hintereinander ausgeführt werden, wenn eine ausreichende Anzahl von Zeilen vorhanden ist. auf denen es nur zwei Kreuze bzw. Nullen gibt. Wenn eine solche Bewegungskette zu einer Situation führt, in der es zwei Linien mit drei Kreuzen oder Nullen gibt, verliert der entsprechende Spieler. Dies wird als erzwungener Sieg bezeichnet.

    Lassen Sie uns alle Felder mit Zahlen von 0 bis 63 nummerieren, beginnend am oberen Rand und durch horizontale Linien von links nach rechts.

    Bild

    Wir veranschaulichen dies am Beispiel eines Spiels:

    0-3-60-21-15-51-12-63 4x8x5x10x20x40x28x44x24x16x36x52x48

    Hier machen die Kreuze zuerst die linke lange Ecke der oberen Fläche (0), dann die Zehen auf die rechte breite Ecke derselben Fläche (3). Kreuze gehen in der Nähe der Ecke an der unteren Kante (60) nach links, der Zeh wird im Feld in der zweiten von der oberen Seite beantwortet usw. Nach dem Verschieben der Nullen in 63 beginnen die Kreuze mit einer Reihe von erzwungenen Bewegungen: 4 - überprüfen. Der Zeh wird gezwungen, um 8 zu antworten, das Kreuz wird 5 geprüft, der Zeh wird um 10 beantwortet usw. bis ein Kreuz zwei Linien mit drei Kreuzen hat. Nullen verloren

    Um dieses Spiel zu lösen, müssen Sie solche Sequenzen für alle möglichen Nullbewegungen finden. Für eine optimale Lösung sollten solche Sequenzen minimal sein.

    Historische Exkursion


    Der erste, der dieses Spiel entschied, war Patashnik (Patashnik) in den frühen 80er Jahren. Er hat die Anfangskombinationen manuell ausgewählt und dann mit einem Computer nach einem Gewinnzug gesucht. Er zeigte, dass, wenn die Kreuze in eine Ecke gehen, sie immer mit dem richtigen Spiel gewinnen. Der nächste Schritt wurde von Victor Allis unternommen. In seiner Dissertation Mitte der 90er Jahre zeigte er, dass die Lösung vollständig am Computer erhalten werden kann. Er hat jedoch nicht alle Optionen geprüft, mit denen die Kreuze gewinnen konnten, sondern nur die ersten zehn vielversprechendsten. Daher war seine Entscheidung nicht optimal und er überließ diese Aufgabe anderen Forschern.

    Die Lösung dieses Problems in optimaler Weise, das heißt, ich entschied mich dafür, den Mindestbaum zu finden. Offensichtlich müssen Sie dazu die Suche in der Breite verwenden, im Gegensatz zur Tiefensuche für Allis. Zunächst wurde die Suche des erzwungenen Gewinns nach einer beliebigen Situation durchgeführt. Es stellte sich jedoch heraus, dass es sich als eher langsam herausstellte, da die Tiefensuche nach erzwungener Verstärkung für lange Kombinationen ziemlich teuer ist. Die Lösung wurde gefunden, indem ein Repository mit bereits berechneten Optionen zu std :: unordered_set hinzugefügt wurde. Das Spielfeld wurde als zwei 64-Bit-Variablen codiert, eine für Kreuze, eine für Nullen, wobei 1 das Vorhandensein eines Kreuzes oder einer Null in dem entsprechenden Feld bedeutet. Diese Zwischenspeicherung führte zu einer erheblichen Beschleunigung. Jedoch Das Hauptproblem bestand darin, ein breites Feld für ungezwungene Züge zu finden. Bei einer typischen Suche ohne Optimierung endete die Berechnung nicht in angemessener Zeit.

    Ich musste mich wieder dem Caching zuwenden. Dem berechneten Spielfeld wurde ein weiteres Byte hinzugefügt, mit dem Ergebnis der Teilbaumberechnung für diese Variante der Anordnung von Kreuzen und Nullen. In diesem Fall begann die Kodierung des Spielfelds 17 Bytes zu belegen. Bei der Suche in der Breite und der allmählichen Erhöhung der Tiefe des Baums konnten somit bereits berechnete Teilbäume verworfen werden. Damit konnte ich die minimalen Bäume
    für die erste Bewegung des Kreuzes in der Ecke (Quadrat 0) und die Antworten der Nullen auf alle Felder berechnen, die vier Zeilen steuern.

    Schwierigkeiten traten auf, wenn die Nullen in der ersten wechselseitigen Bewegung das Feld besetzten, das sieben Zeilen kontrollierte. In diesem Fall überschritt der von dem Cache belegte Arbeitsspeicher 32 GB RAM, und mein Linux wurde umgestellt. Es war notwendig, nach einer anderen Lösung zu suchen.

    Hier habe ich mich der Tatsache zuwendet, dass das Spielfeld viele Automorphismen hat, das heißt, wenn Sie eine Lösung für eine Kombination von Kreuzen und Nullen finden, dann haben Kombinationen, die verschiedenen Kurven und Reflexionen entsprechen, auch eine Lösung. Es sei hier darauf hingewiesen, dass dank dieser Automorphismen die erste Bewegung der Kreuze nur zwei Optionen hat - eine im Feld 0 (Steuern von 7 Zeilen) und eine im Feld 1 (Steuern von 4 Zeilen). Daher wird in meinem Fall der erste Zug immer durch Kreuze in Feld 0 ausgeführt. Dies gilt jedoch nur für ein leeres Feld.

    Wir kehren jedoch zu Automorphismen für ein beliebiges Spielfeld zurück. Wie finde ich alle?
    Ich habe die folgende Methode verwendet: Da der Würfel eine Dimension von drei hat, ist es möglich, die Koordinaten neu anzuordnen (es werden 6 solcher Permutationen vorhanden sein) und Reflexionen vorzunehmen (es werden 8 davon vorhanden sein). Daher ist der gesamte räumliche Automorphismus 48. Der Würfel weist jedoch zwei weitere interne Automorphismen auf. Einer ordnet die Koordinaten der Felder im ersten und zweiten Paar in jeder Zeile neu an,
    und der zweite belässt das erste und das letzte Feld an Ort und ordnet nur die Koordinaten für das zweite und das dritte Feld an. Diese beiden Automorphismen können auch gleichzeitig angewendet werden. Somit gibt es für jeden der 48 räumlichen Automorphismen vier
    (einschließlich trivialer) innerer Automorphismen. Ansonsten gibt es für den gesamten Würfel 192 Automorphismen. Dies lässt hoffen, dass die Anzahl der bereits berechneten Felder erheblich reduziert wird.

    Ein anderes Problem tritt jedoch auf: Wenn Sie alle 192 Automorphismen überprüfen, müssen Sie das Spielfeld schnell umwandeln, indem Sie die Bits verschieben. Wenn diese Umwandlung nicht schnell durchgeführt wird, wird sie die ganze Zeit, in der sie ausgeführt wird, keinen Performance-Gewinn erzielen, und die gesamte Idee der Automorphismen wird in die Röhre hineinfliegen. Daher habe ich im Internet nach einer schnellen Möglichkeit gesucht, die Bits neu anzuordnen. Um ehrlich zu sein, habe ich nichts Passendes gefunden. Die einzige akzeptable schnelle Möglichkeit, die Bits neu anzuordnen, ist das Erstellen einer Tabelle im Voraus und die Auswahl einer fertigen Lösung mit dem aktuellen Spielfeld als Index. Für mich funktionierte diese Methode nicht, da es notwendig war, ein Array von 2 mit 64 sechzig-Bit-Wörtern zu haben.

    Ich wollte diese Idee wirklich verlassen, aber ich hatte die Idee, dass es nicht notwendig ist, einen großen Tisch zu haben, aber Sie könnten mehrere kleine haben. Im Prinzip war es möglich, eine andere Anzahl solcher Tabellen zu wählen, aber ich hielt bei 8 Tabellen mit 256 Wörtern (für jeden Automorphismus) an. Um die Bits neu anzuordnen, nehme ich ein Byte aus dem 64-Bit-Feld und wähle in einer vorberechneten Tabelle ein Muster aus, in dem die Bits bereits vorhanden sind (wenn sie im ursprünglichen Feld natürlich nicht null sind). Dann nehme ich das nächste Byte aus dem 64-Bit-Feld und wähle in der nächsten vorberechneten Tabelle eine andere Vorlage aus und mache ein logisches "oder" mit der ersten. Und so 8 mal. Da diese Operationen keine bedingten Übergänge enthalten, müssen sie ziemlich schnell ausgeführt werden, ohne die Pipeline im Prozessor zu stören.

    Das alles sieht zwar ziemlich gut aus, aber es ist ziemlich problematisch, all diese Automorphismen und die schnelle Permutation von Bits manuell und fehlerfrei zu kodieren. Daher wurde ein zusätzliches Programm erstellt, das C-Code generiert, der wiederum
    im Hauptprogramm enthalten ist.

    Fazit und spätere Entwicklung


    Nachdem das obige Programm erstellt wurde, war es in wenigen Tagen möglich, einen nahezu optimalen Baum für Tic-Tac-Toe 4x4x4 zu finden. Warum "fast optimal"? Weil die Gesamtlänge der erzwungenen Bewegungen nicht berücksichtigt wird, kann es vorkommen, dass ein Baum für die nicht erzwungenen Bewegungen derselben Tiefe vorhanden ist, jedoch mit einer geringeren Gesamttiefe der erzwungenen Bewegungen. Aber ich denke, das ist kein großer Nachteil.

    Somit ist das 4x4x4-Tic-Tac-Toe-Spiel vollständig berechnet, die Kreuze gewinnen immer und kann dieses Thema geschlossen werden? Nicht wirklich. Tatsache ist, dass, da die Kreuze zuerst gehen, sie einen Vorteil haben. Was ist, wenn Sie versuchen, diesen Vorteil auszugleichen? Ich schlage folgende Idee vor: die Kreuze mit dem ersten Schritt zu verbieten, ein Kreuz in ein Feld zu setzen, das 7 Zeilen steuert, und diese nur auf Felder beschränken, die nur 4 Zeilen steuern. Trotz der Tatsache, dass dies eine kleine Änderung zu sein scheint, kann sich das Ergebnis des Spiels erheblich ändern, und Nullen können das Spiel auf ein Unentschieden reduzieren und möglicherweise gewinnen. Also, was gibt es zu entdecken?

    Jetzt auch beliebt: