Erkenne gewinnendes Spiel in Null und Kreuze

Question

Ich muss den besten Weg kennen, um einen gewinnenden Zug in einem Spiel von Nullen und Kreuzen zu erkennen. Quellcode spielt keine Rolle, ich brauche nur ein Beispiel oder etwas, mit dem ich anfangen kann.

Die einzige Sache, die ich finden kann, ist Schleifen zu verwenden und jede Richtung für jede Bewegung zu testen, die ein Spieler macht, um zum Beispiel fünf hintereinander zu suchen. Gibt es einen schnelleren und effizienteren Weg?

Answer 1

Mir ist keine bessere Methode als Looping bekannt, aber das Board ist so klein, es ist ziemlich trivial.

Ein wenig Python Pseudo-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 2

Es gibt effizientere Wege, aber sie wirklich nur die Materie, wenn Sie dieses Spiel für viel, viel größer Board-Konfigurationen erweitern. Wenn Sie beispielsweise Gruppierungen von Nullen und Kreuzen in direktionalen Objekten (z. B. eine diagonale Konfiguration speichern) speichern, können Sie nach denen mit der Länge winLength-1 sortieren und nur die neue Bewegung gegen diese Gruppierungen testen. Sie speichern einige Iterationen, aber Sie müssen viele zusätzliche Informationen im Speicher verwalten.

Answer 3

Es ist eine Frage der Repräsentation. Wie speicherst du das Spielbrett? Jetzt denke über den Tellerrand hinaus; wie sonst könnten Sie es speichern? Sie könnten zum Beispiel das Board als ein Paar Bitmaps darstellen - eins für Nullen und eins für Kreuze - und dann eine numerische Musterübereinstimmung durchführen, um die Gewinnbedingungen zu erkennen.

Answer 4

Die wirklich einfache Lösung ist es, nur vom letzten Zug aus zu überprüfen ... offensichtlich hätte kein vorheriger Zug das Spiel gewinnen können, oder Sie wären nicht hier ... also müssen Sie nur überprüfen, ob Es gibt 5 (oder wie viele) in einer Reihe/Spalte/Diagonale um den Zug, der gerade platziert wurde.

Zum Beispiel, wenn der Vorstand wie folgt aussieht, und X markiert den jüngsten Schritt:

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

Sie brauchen nichts außerhalb des Bereichs von „C“ zu überprüfen:

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

Hilft das? (Es sah so aus, als ob du in deiner ursprünglichen Frage darauf anspielst, aber ich war mir nicht sicher.)

Darüber hinaus werden einfache Loops dein bester Freund sein. Sie könnten wahrscheinlich einige Mikro-Optimierung, aber (je nachdem, was Ihre eigentliche Anwendung tut) ist es wahrscheinlich nicht wert.

Eine Sache zu verfolgen ist, dass Sie nicht einfach 5 aus dem letzten Zug in jede Richtung springen können, auf der Suche nach dem viele in Folge, weil diese Bewegung in der Mitte einer Streak sein könnte. Also würde ich 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 5

Betrachten Sie das Board 3X3

Sei X = 1 Sei O = -1 und ein Raum, der durch eine Null dargestellt wird.

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

[X] [X] [] ist 2, also wenn es X-Drehung ist, kann er gewinnen, indem er zur Leerstelle wechselt, oder O muss blockieren.

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

In einer 3x3-Platine sind 8 Positionen zu bewerten.

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

wenn N = 8 und eine Reihe oder Spalte Summen bis 7, dann wissen Sie, es für X eine Gewinn Bewegung in dieser Zeile ist/Spalte

Diese Methode arbeitete für mich in der Schule.

Beste Wünsche

Böse

Answer 6

Noughts und Kreuze ist eine saubere Programmierung Herausforderung, denn es gibt eine Menge von mathematischen Tricks ist, das Problem vereinfachen können.

Nullen und Kreuze ist normalerweise ein 3-mal-3-Raster. Wenn Sie jede Position im Raster eine Zahl von eins bis neun (nicht in numerischer Reihenfolge) zuordnen können Sie die Zahlen so anordnen, dass jede horizontale, vertikale und diagonale Reihe summiert sich zu 15

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

Warum das sinnvoll ist? Wenn Sie drei beliebige Quadrate wählen können, die zu 'O' oder 'X' gehören, und diese drei Quadrate zusammen eine Summe von 15 ergeben, wissen Sie, dass der Spieler das Spiel gewonnen hat.