Detektieren Sie das Spiel in Null und Kreuz

Question

Ich muss wissen, wie man am besten einen Gewinnzug in einem Noughts and Crosses-Spiel erkennt. Der Quellcode spielt keine Rolle, ich brauche nur ein Beispiel oder etwas, mit dem ich anfangen kann.

Das Einzige, was mir einfällt, ist, Schleifen zu verwenden und jede Richtung für jeden Zug eines Spielers zu testen, um z. B. nach fünf Zügen hintereinander zu suchen. Gibt es einen schnelleren und effizienteren Weg?

Answer 1

Die wirklich einfache Lösung ist, einfach vom letzten Zug aus zu prüfen... offensichtlich kann kein vorheriger Zug das Spiel gewonnen haben, sonst wären Sie nicht hier... also müssen Sie nur prüfen, ob es 5 (oder wie viele auch immer) in einer Reihe/Spalte/Diagonale um den Zug gibt, der gerade gesetzt wurde.

Wenn das Brett zum Beispiel so aussieht und X den letzten Zug markiert:

.............
.............
.............
.............
.....X.......
.............
.............
.............
.............
.............

Sie brauchen nichts außerhalb des Bereichs "C" zu prüfen:

.C...C...C...
..C..C..C....
...C.C.C.....
....CCC......
.CCCCXCCCC...
....CCC......
...C.C.C.....
..C..C..C....
.C...C...C...
.............

Ist das hilfreich? (Es sah so aus, als würden Sie in Ihrer ursprünglichen Frage darauf anspielen, aber ich war mir nicht sicher).

Darüber hinaus werden einfache Schleifen Ihr bester Freund sein. Sie könnten wahrscheinlich einige Mikro-Optimierung zu tun, aber (je nachdem, was Ihre tatsächliche Anwendung tut) ist es wahrscheinlich nicht wert.

Eine Sache, die man im Auge behalten sollte, ist, dass man nicht einfach 5 in eine beliebige Richtung vom letzten Zug aus springen kann, wenn man nach so vielen Zügen in einer Reihe sucht, weil dieser Zug in der Mitte einer Serie liegen könnte. Ich würde also etwas tun wie

From the new move
    left = how many in a row we have to the left of the lastest move
    right = how many in a row we have to the right of the latest move
    if (left + right + 1 >= 5) then you have a winner

    up = how many in a row we have above the latest move
    down = how many in a row we have below the latest move
    if (up + down + 1 >= 5) then you have a winner

    // repeat for both diagonal directions.

Answer 2

Noughts and Crosses ist eine nette Programmierherausforderung, denn es gibt eine Menge mathematischer Tricks, mit denen man das Problem vereinfachen kann.

Noughts and Crosses ist normalerweise ein 3-mal-3-Raster. Wenn Sie jeder Position in Ihrem Raster eine Zahl von eins bis neun zuweisen (nicht in numerischer Reihenfolge), können Sie die Zahlen so anordnen, dass jede horizontale, vertikale und diagonale Reihe 15 ergibt

+----+----+----+
| 4  | 3  | 8  |
|    |    |    |
+----+----+----+
| 9  | 5  | 1  |
|    |    |    |
+----+----+----+
| 2  | 7  | 6  |
|    |    |    |
+----+----+----+ 

Warum ist das nützlich? Wenn Sie drei beliebige Felder auswählen können, die entweder zu "O" oder "X" gehören, und diese drei Felder eine Gesamtsumme von 15 ergeben, wissen Sie, dass dieser Spieler das Spiel gewonnen hat.

Answer 3

Betrachten Sie das 3X3-Brett

Es sei X = 1 Es sei O = -1 und ein Leerzeichen wird durch eine Null dargestellt.

Wenn also die oberste Zeile wie folgt aussieht [X][X][X], ist die Summe 3, also ein Gewinn [O][O][O] die Summe ist -3, also ist es der andere Gewinn.

[X][X][ ] ist 2. Wenn X am Zug ist, kann er also gewinnen, indem er auf das Feld zieht, oder O muss blockieren.

[X][O][X] ist 1, also kein Gewinn.

Bei einem 3x3-Brett gibt es 8 Positionen zu bewerten.

In NXN wird die Zahl größer, aber die Idee bleibt dieselbe

Wenn N=8 ist und eine Zeile oder Spalte die Summe 7 ergibt, dann weiß man, dass es einen Gewinnzug für X in dieser Zeile/Spalte gibt.

Diese Methode hat bei mir in der High School funktioniert.

Beste Wünsche

Böse

Answer 4

Ich kenne keine bessere Methode als die Schleifenbildung, aber das Board ist so klein, dass es ziemlich trivial ist.

Ein wenig Python-Psuedo-Code:

def get_winner(board):
    if board[0][0] != EMPTY and board[0][0] == board[1][1] == board[2][2]:
        return board[0][0]
    if board[2][0] != EMPTY and board[2][0] == board[1][1] == board[0][2]:
        return board[2][0]
    for i in xrange(3):
        if board[i][0] != EMPTY and board[i][0] == board[i][1] == board[i][2]:
            return board[i][0]
        if board[0][i] != EMPTY and board[0][i] == board[1][i] == board[2][i]:
            return board[0][i]

Answer 5

Es gibt effizientere Methoden, aber die sind nur wichtig, wenn man das Spiel auf viel, viel größere Spielbrettkonfigurationen ausdehnt. Wenn Sie zum Beispiel Gruppierungen von Nullen und Kreuzen in Richtungsobjekten speichern (z. B. eine diagonale Konfiguration), könnten Sie nach denjenigen mit der Länge winLength-1 und testen Sie den neuen Zug nur anhand dieser Gruppierungen. Sie sparen einige Iterationen, müssen aber eine Menge zusätzlicher Informationen im Speicher halten.