Ich möchte eine Textdatei erstellen, die alle 19.683 Tic-Tac-Toe Board-Layouts enthält die Struktur von 0 = Blank, 1 = X und 2 = O. Leider ist Mathe nicht meine Stärke und ich kann nirgends Beispiele dafür finden.
Dies ist nicht für Hausaufgaben, versichere ich Ihnen. Ich beabsichtige, diese Daten durch einen Minimax-Rechner laufen zu lassen, um ein Bild zu erzeugen, das RGB-Werte enthält, die die optimale Bewegung basierend auf dem Board-Setup darstellen. Ich entwickle Tic-Tac-Toe für eine Plattform, die keine Funktionen unterstützt (es ist ereignisgesteuert), also werde ich das Board in eine Nummer in meinem Spiel umwandeln und dann das RGB eines Pixels in einem Bild nachschlagen, das anzeigt, was das Beste ist bewegen ist. Es ist ein frecher Workaround, aber einer, der nicht mehr RAM benötigt als ein 145x145 Pixel Bild (145x145 = 21.025, also stellt jedes Pixel den empfohlenen Zug basierend auf dem Board dar). Dies bedeutet auch, dass ich keine CPU-Zeit kauen muss, was ein weiteres Plus ist.
Da Sie Board-Layouts wollen, gibt es nur eine kleine Anzahl (19683).
Sie können nur Brute-Force generieren all diese. Jede Box hat nur 3 Möglichkeiten. Und es gibt 9 Boxen, einfach alle durchlaufen.
BEARBEITEN:
%Vor%Damit werden alle 19,683 Layouts ausgedruckt. Ich bin nicht sicher, welches Format Sie wollen, aber es sollte ziemlich einfach sein, das aus der Ausgabe zu extrahieren.
Es gibt 9 Positionen und ein Alphabet mit 3 Buchstaben (X, O, leer). Die Gesamtzahl der möglichen Kombinationen ist 3 ^ 9 = 19683.
%Vor%Meine Minimax für Tic Tac Toe Implementierung erzeugt einen Baum von 5477 Knoten. Jeder Knoten enthält einen Tic Tac Toe-Platinenstatus und erfüllt die folgenden Bedingungen:
Der Board-Status ist laut Tic Tac Toe-Regel gültig, dass Spieler abwechselnd Xs und Os platzieren müssen. d. h. es gibt keine Brettpositionen wie:
XXX
XXX
XXO
alle Blätter des Baumes enthalten Board Staaten, die End-Game-Staaten wie pro Tic Tac Toe Regeln (Spieler 1 gewinnt, Spieler 2 Siege oder Unentschieden) werden in Betracht ziehen. d. h. es gibt keinen Zweig des Baumes wie:
XOX
OXO
X
XOX
OXO & lt; - Es hat keinen Sinn, diesen Knoten zu haben, da sein Elternteil eine Endspielposition hat (X hat gewonnen)
XO
Ein gegebener Baumknoten kann mehrere Eltern haben (mehrere Baumknoten können dasselbe Kind haben).
d. da ein bestimmte Bord Zustand kann durch mehrere unterschiedliche Bewegung Sequenzen erhalten werden kann, wenn der Baumknoten erstellt werden, ob bereits ein Knoten den Platine Zustand enthält, die ich bin zu (re) generiert, I Wiederverwendung (wieder anbringen), die vorhandenen Knoten . Auf diese Weise, wenn ich den Baum Knoten von unten nach oben (nach Minimax Theorie) Partitur, ich habe nicht die gleiche Punktzahl mehrmals für einige Teilmengen der Baumzweige berechnen (das identisch sein würde, wenn ich nicht wiederverwenden vorhandene Knoten).
Tic-Tac-Toe hat 5477 gültige Zustände mit Ausnahme der leeren Position
Das Erzeugen aller möglichen Spielkarten (die Tiefensuche funktioniert am besten) und das Ausschließen von Duplikaten unter Rotation und Spiegeln führt zu 765 Boards. 626 sind Mid Game, 91 Spiele X hat gewonnen, 44 Spiele O hat gewonnen und 3 Spiele sind ein Unentschieden.
Wenn Sie nur in die optimalen Moves eingebunden sind, können Sie diese einfach verwenden Ссылка als Referenz. Macht ein schönes Poster.
Aber der ganze Spaß bei Tic-Tac-Toe ist bei der Umsetzung. Das überlasse ich dem Leser. Nur ein paar Tipps:
Jede Kachel auf der Platine hat 3 Zustände, so dass Sie die Platine als Zahl in der Basis 3 kodieren können. Für einfachere Berechnungen verwende ich Base 4 (2 Bit pro Kachel, also muss ich nur verschieben). Ich habe dann eine Hash-Funktion, die diese Zahl für ein Board unter allen möglichen Rotationen und Spiegelungen (8 Fälle) generiert und den Minimalwert zurückgibt. Damit kann ich nachsehen, ob ich dieses Board schon gespielt habe.
Beginne mit einem leeren Brett, setze in jeder möglichen Position eine Markierung auf das Brett, überprüfe, ob das Brett bereits gespielt wurde, markiere es, überprüfe, ob das Spiel vorbei ist und zähle das Brett, ansonsten wende abwechselnd Spieler ab.
Das erste X kann nur an drei Stellen gesetzt werden (unter Berücksichtigung von Drehung und Spiegelung) und alle späteren Züge haben höchstens 8 Wahlmöglichkeiten. Anstatt die absolute Kachel zu kodieren, können Sie nur leere Kacheln zählen und diese in 3 Bit kodieren.
Mit der obigen Hash-Funktion erhalten wir 626 Boards, wo wir eine Bewegung machen müssen (Sie müssen nur die Rotation / Spiegelung umkehren, um die reale Bewegung der Daten zu erhalten). Es gibt wahrscheinlich eine nicht viel größere relative Primzahl, so dass jedes Board ohne Kollisionen in eine Hash-Tabelle passt. Sagen wir, die Zahl ist 696 (ich weiß, nicht relativ prim). Bei 3 Bits pro Karte würde man nur 261 Byte Daten benötigen, um die beste Bewegung für jedes mögliche Spiel zu speichern.
Da Sie perfekt spielen, geht die Anzahl der erreichbaren Boards wieder zurück. Erstellen Sie einen Datensatz für die Wiedergabe von X und einen für die Wiedergabe von O, und Sie können diesen wieder abschneiden.
Willst du es noch kleiner machen? Programmieren Sie einfach ein paar Grundregeln wie: Das erste O sollte in der Mitte sein, wenn es frei ist. Mit 2 "meine Farbe" in Folge vervollständigen Sie die Reihe. Mit 2 "andere Farbe" in einer Reihe blockieren Sie die Reihe und so weiter. Wikipedia hat eine Liste von 8 Regeln, aber ich denke, ich hatte weniger, als ich es so gemacht habe.
Ein perfekter Tic-Tac-Toe-Gegner ist langweilig. Du kannst niemals gewinnen. Warum nicht das Spiel vom Scheitern lernen lassen? Verfolgen Sie alle 626 Boards und ihre möglichen Züge. Wenn eine Bewegung zu einem Verlust führt, entferne diese Bewegung von der Tafel. Wenn das Board keine weiteren Züge mehr hat, entferne von allen Brettern, die zu diesem führen, die Bewegung, die es verursacht (rekursiv, wenn das den letzten Zug dort entfernt). Dein Spiel wird niemals zweimal den gleichen Weg verlieren. Ähnlich wie bei Moves, die zu einem Gewinn führen, entfernen Sie die Gegner aus der Liste der möglichen, und wenn keine übrig sind, markieren Sie den vorherigen Zug als sicheren Sieg. Auf diese Weise, wenn Sie einen Gewinn erzwingen können, werden Sie es von jetzt an immer zwingen. Kann man X auf 91 Arten verlieren? Wenn du O spielst, kannst du alle 44 Wege verlieren?
Sie können sich einfach brutal durchsetzen. Jedes der Quadrate ist 0, 1 oder 2, also ...:
%Vor%Oder, wenn Sie damit nicht belästigt werden;) dann können Sie eine rekursive Funktion dafür schreiben:
%Vor%Dann mach einfach:
%Vor%und Magie wird auftreten.
Das ist übrigens in C ++.
Tags und Links algorithm tic-tac-toe