Für diejenigen, die nicht wissen, was Pentago ist, ist es nicht so wichtig für das Problem, aber es genügt zu sagen, dass Sie ein 6x6 Board mit vier Quadranten haben. Jeder Spieler legt abwechselnd ein Stück ab und dreht dann einen Quadranten. Das Spiel wird gewonnen, wenn ein Spieler fünf hintereinander kommt (entweder vor oder nach der Rotationsphase des Spielers).
Ich schreibe einen Algorithmus, um viele verschiedene zufällige Pentago-Spiele zu spielen. Da es jedoch völlig zufällig ist, sehe ich keinen guten Weg, um zu überprüfen, ob jemand zwischen der Orts- und der Rotationsphase des Turns gewinnt (andernfalls könnte man versehentlich die Gewinnbewegung drehen). Irgendwann plane ich das neu zu schreiben, wo es ein bisschen mehr Strategie beinhaltet, anstatt völlig zufällig, aber das ist für statistische Zwecke, so dass Zufälligkeit einfach gut ist (und in der Tat ziemlich nützlich ist).
Wie auch immer, momentan programmiere ich in Matlab, und eine leere Tafel sieht so aus
%Vor% Im Verlauf des Spiels füllt sich das Board mit w und b . Die Art, wie ich nach einem gewinnenden Board suche, durchläuft buchstäblich jede Spalte und jede Zeile (und jede Diagonale), um zu sehen, ob es einen Gewinner gibt, indem man eine reguläre Ausdrucksprüfung auf die zurückgegebene "Zeichenkette" durchführt.
Kurz gesagt, meine Frage ist dies:
Gibt es eine effizientere Methode, um die Gewinner eines Pentago-Boards zu bestimmen?
BEARBEITEN:
Es gibt zwei Lösungen, die ich mir ausgedacht habe: eine, die auf Convolution basiert (mit der Funktion CONV2 <) / a>) und basierend auf der Brute-Force-Indexierung für alle möglichen Strings von 5 Elementen (ähnlich wie bei b3's neuere Antwort ). Hier sind sie:
Faltung:
%Vor%Indizierung:
%Vor%Aus Neugierde dachte ich, ich würde die Geschwindigkeit und Genauigkeit dieser Lösungen im Vergleich zu b3's neuere Antwort . Ich habe 4 Testboards erstellt: -1 Siege, kein Sieger, 1 Gewinn, beide gewinnen (Unentschieden). Dann habe ich jede Lösung 10.000 Mal für jedes Board ausgeführt und sie zeitlich abgestimmt. Hier sind die Ergebnisse:
%Vor%Beachten Sie, dass die Lösung von b3 keine Zeichnung erkennt. Obwohl der Code für die faltungsbasierte Lösung am kürzesten und am einfachsten zu implementieren war (ich musste keine Indexliste manuell erstellen), ist die obige Indexierungslösung am schnellsten.
Verwenden Sie ein 6x6 numerisches Array, um das Spielbrett zu repräsentieren, Null, um eine leere Position anzuzeigen, 1 um Schwarz anzuzeigen und -1 um Weiß anzuzeigen. Eine Karte wird dann initialisiert durch:
%Vor%Um nach einem gewinnbringenden Board zu suchen, verwenden Sie SUM , das auf den Board-Array-Spalten funktioniert. Durch Subtrahieren der MIN Spalte wird der Fall aufgelöst, in dem die Spalte Teile von beiden Spielern enthält. Verwenden Sie das Dimensionsargument der SUM- und MIN-Funktionen, um dieselbe Überprüfung der Zeilen durchzuführen. Erstellen Sie mit DIAG ein Array der drei möglichen Diagonalen und füllen Sie die beiden kürzeren Diagonalen mit Nullen auf. Führen Sie dieselbe Überprüfung der Spalten dieses Arrays durch.
%Vor% Sie können nun die Tafel mit einem Aufruf von checkBoard :
Unter Verwendung von vorberechneten Nachschlagetabellen ist es möglich, in etwa 18 Anweisungen zu erkennen, ob ein Spieler fünf in einer Reihe hat. Die folgende Routine nimmt alle Steine eines Spielers, die in einen 64-Bit-Int gepackt sind, als Eingabe:
%Vor%Der vollständige Quellcode ist hier:
EDIT: Aktualisiert mit Gnovices neue Algorithmen (für insgesamt 3 richtig? Sie verwendet Filter () jetzt verwenden Sie conv2 ()).
Neue Zahlen:
%Vor%Das war zu lustig, um zu widerstehen. Ohne den Code von B3 und Gnovice wäre meins mit Fehlern gespickt gewesen. Der Code von Gnovice scheint 100% genau zu sein, soweit ich das beurteilen kann. B3 reichte zwei Funktionen ein, die erste fälschte fälschlicherweise einen Gewinner, wenn es 4 in einer Reihe gab, ein Leerzeichen und eine weitere. Der zweite Eintrag von B3 erkennt keinen Gewinner auf der Diagonale von oben rechts nach unten links. B3 hat auch den Fall nicht berücksichtigt, in dem beide Spieler Gewinnpositionen haben. (Wie ich das Spiel verstehe, könnte eine Quadrantenrotation beide Spieler gleichzeitig gewinnen lassen?)
Hier ist die Aufstellung für 1000 zufällige Boards.
%Vor%Gnovice war der erste, der die 100% ige Genauigkeit erreichte, kam aber zur höchsten Ausführungszeit. B3 könnte seinen Code wahrscheinlich ändern, um die Fehler zu beheben, und dann den schnellsten Code haben. Und ich könnte wahrscheinlich ein Leben anstatt Rennen 4 Code miteinander verbinden bekommen.
Hier ist mein Code:
%Vor%Hier ist der Treibercode
%Vor%FYI B3 Hier ist ein Beispielboard, das Ihr Code nicht erkennen konnte.
%Vor%Sowie
%Vor%Tags und Links math performance matlab