Connect 4 Check für einen Gewinn-Algorithmus

Ich weiß, dass es viele Fragen bezüglich connect 4 nach einem Gewinn gibt. Das Problem ist, dass die meisten anderen Algorithmen zu Laufzeiterrorsn in meinem Programm führen, weil sie versuchen, auf einen Index außerhalb meines Arrays zuzugreifen. Mein Algorithmus ist so:

private int checkWin(int[][] gridTable,int rowNum,int colNum, int maxRow, int maxCol) { // For checking whether any win or lose condition is reached. Returns 1 if win or lose is reached. else returns 0 // gridTable[][] is the game matrix(can be any number of rows and columns between 4 and 40) // colNum is the column number where the last token was placed // rowNum is the row number where the last token was placed // maxRow is the number of rows in my grid // maxCol is the number of columns in my grid int player = gridTable[rowNum][colNum]; //player ID int count=0; // Horizontal check for (int i=0;i=4) return 1; } //Vertical check for (int i=0;i=4) return 1; } count=0; // 4 in a row diagonally for(int i=colNum+1,j=rowNum+1;i<maxRow && j=0 && j>=0;i--,j--) { if(gridTable[j][i]!=player) { count=1; break; } count++; } // 4 in a row diagonally for(int i=colNum+1,j=rowNum-1;i=0;i++,j--) { if(gridTable[j][i]!=player) { count=1; break; } count++; } for(int i=colNum-1,j=rowNum+1;i>=0 && j=4) return 1; return 0; } 

count ist die Variable, die nach einem Gewinn sucht, wenn die Anzahl gleich oder größer als 4 ist. Das bedeutet, dass sie 4 oder mehr aufeinanderfolgende Tokens desselben Spielers sein sollten.

DAS PROBLEM: Manchmal prüft die Methode auf einen Gewinn, ohne 4 Token in der richtigen Reihenfolge zu haben, und andere Zeiten prüfen nicht auf einen Gewinn, wenn 4 Token in Ordnung sind.

   

Offensichtlich ist Ihr Code für die horizontalen und vertikalen Fälle korrekt. Der knifflige Teil ist der diagonale Fall.

Lass uns ein Bild versuchen:

Bildbeschreibung hier eingeben

Für die grünen Zeilen ist Ihre Startzeilenposition 0 … maxRow – 4. Die Spalte wäre 0 … startingRow –

Pseudocode:

 // top-left to bottom-right - green diagonals for( rowStart = 0; rowStart < rowMax - 4; rowStart++){ count = 0; int row, col; for( row = rowStart, col = 0; row < rowMax && col < colMax; row++, col++ ){ if(gridTable[row][col] == player){ count++; if(count >= 4) return 1; } else { count = 0; } } } // top-left to bottom-right - red diagonals for( colStart = 1; colStart < colMax - 4; rowStart++){ count = 0; int row, col; for( row = 0, col = colStart; row < rowMax && col < colMax; row++, col++ ){ if(gridTable[row][col] == player){ count++; if(count >= 4) return 1; } else { count = 0; } } } 

Sie könnten etwas Ähnliches für Diagonalen machen, die in die andere Richtung gehen (von unten links nach oben rechts).

Aus irgendeinem Grund mag ich Zähler nicht so gern, also habe ich es so gemacht (es funktioniert für Boards mit verschiedenen Größen).

 public boolean areFourConnected(int player){ // horizontalCheck for (int j = 0; j 

Nachdem Sie Ihren Code durchforstet haben, scheint es, dass die Diagonalüberprüfung nur in einer Richtung gewinnen kann (was passiert, wenn ich ein Token zu der untersten Zeile und der untersten Spalte hinzufüge?)

Stattdessen ist der grundlegende Prüfalgorithmus immer derselbe process, unabhängig davon, in welche Richtung Sie einchecken.

Sie benötigen einen Startpunkt (x / y) und x / y delta (Bewegungsrichtung). Sie können dies in einer einzigen Methode zusammenfassen …

 public boolean didWin(int[][] grid, int check, int row, int col, int rowDelta, int colDelta) { boolean win = true; for (int count = 0; count < 4; count++) { if (row < ROWS && row >= 0 && col < COLUMNS && col >= 0) { int test = grid[row][col]; if (test != check) { win = false; break; } } row += rowDelta; col += colDelta; } return win; } 

Dies ermöglicht Ihnen grundsätzlich, in vier Richtungen zu prüfen, aber auch rückwärts

Also, wenn wir etwas wie …

 int[][] gridTable = new int[ROWS][COLUMNS]; gridTable[ROWS - 1][3] = 1; gridTable[ROWS - 2][3] = 1; gridTable[ROWS - 3][3] = 1; gridTable[ROWS - 4][3] = 1; System.out.println("Vertical"); System.out.println(didWin(gridTable, 1, ROWS - 4, 3, 1, 0) ? "Win" : "Lose"); System.out.println(didWin(gridTable, 1, ROWS - 1, 3, -1, 0) ? "Win" : "Lose"); System.out.println(didWin(gridTable, 1, 0, 3, 1, 0) ? "Win" : "Lose"); gridTable = new int[ROWS][COLUMNS]; gridTable[3][1] = 1; gridTable[3][2] = 1; gridTable[3][3] = 1; gridTable[3][4] = 1; System.out.println(""); System.out.println("Horizontal"); System.out.println(didWin(gridTable, 1, 3, 1, 0, 1) ? "Win" : "Lose"); System.out.println(didWin(gridTable, 1, 3, 4, 0, -1) ? "Win" : "Lose"); System.out.println(didWin(gridTable, 1, 3, 0, 0, 1) ? "Win" : "Lose"); gridTable = new int[ROWS][COLUMNS]; gridTable[0][1] = 1; gridTable[1][2] = 1; gridTable[2][3] = 1; gridTable[3][4] = 1; System.out.println(""); System.out.println("Diag"); System.out.println(didWin(gridTable, 1, 0, 1, 1, 1) ? "Win" : "Lose"); System.out.println(didWin(gridTable, 1, 3, 4, -1, -1) ? "Win" : "Lose"); System.out.println(didWin(gridTable, 1, 1, 2, 1, 1) ? "Win" : "Lose"); 

Welche Ausgänge …

 Vertical Win Win Lose Horizontal Win Win Lose Diag Win Win Lose 

Jetzt könnten Sie es einfach zusammenfassen …

 public boolean didWin(int[][] grid, int check, int row, int col) { return didWin(grid, check, row, col, 1, 0) || didWin(grid, check, row, col, -1, 0) || didWin(grid, check, row, col, 0, 1) || didWin(grid, check, row, col, 0, -1) || didWin(grid, check, row, col, 1, 1) || didWin(grid, check, row, col, -1, -1) || didWin(grid, check, row, col, -1, 1) || didWin(grid, check, row, col, 1, -1); } 

Also, mit etwas wie …

 int[][] gridTable = new int[ROWS][COLUMNS]; gridTable[ROWS - 1][3] = 1; gridTable[ROWS - 2][3] = 1; gridTable[ROWS - 3][3] = 1; gridTable[ROWS - 4][3] = 1; System.out.println("Vertical"); System.out.println(didWin(gridTable, 1, ROWS - 1, 3) ? "Win" : "Lose"); System.out.println(didWin(gridTable, 1, ROWS - 4, 3) ? "Win" : "Lose"); gridTable = new int[ROWS][COLUMNS]; gridTable[3][1] = 1; gridTable[3][2] = 1; gridTable[3][3] = 1; gridTable[3][4] = 1; System.out.println(""); System.out.println("Horizontal"); System.out.println(didWin(gridTable, 1, 3, 1) ? "Win" : "Lose"); System.out.println(didWin(gridTable, 1, 3, 4) ? "Win" : "Lose"); gridTable = new int[ROWS][COLUMNS]; gridTable[0][1] = 1; gridTable[1][2] = 1; gridTable[2][3] = 1; gridTable[3][4] = 1; System.out.println(""); System.out.println("Diag"); System.out.println(didWin(gridTable, 1, 0, 1) ? "Win" : "Lose"); System.out.println(didWin(gridTable, 1, 3, 4) ? "Win" : "Lose"); 

Was druckt so etwas aus …

 Vertical Win Win Horizontal Win Win Diag Win Win 

Ich würde hinzufügen, dass dieser Ansatz nur funktioniert, wenn Sie den richtigen Start der 4 Chips in einer Reihe bereitstellen. Zum Beispiel liefert didWin (gridTable, 1, 3, 3) false anstelle von true für Ihre horizontale Prüfung, da die Schleife nur eine Richtung prüfen kann.

Die Absicht war nicht, eine “vollständige” Out-of-the-Box “-Lösung bereitzustellen, sondern ein Konzept, aus dem eine breitere Lösung entwickelt werden könnte (ich meine, ich würde es hassen, wenn die Leute tatsächlich denken müssen;)). Ich habe die Lösung auch basierend auf der Idee entwickelt, dass das OP wissen würde, wo das letzte Stück platziert wurde, dh der Startpunkt;)

Durch eine geringfügige Änderung der didWin Methode ist es möglich, ein n mal n Gitter von jedem Punkt aus zu überprüfen …

 public boolean didWin(int[][] grid, int check, int row, int col, int rowDelta, int colDelta) { boolean match = false; int matches = 0; while (row < ROWS && row >= 0 && col < COLUMNS && col >= 0) { int test = grid[row][col]; if (test != check && match) { break; } else if (test == check) { match = true; matches++; } row += rowDelta; col += colDelta; } return matches == 4; } 

Also, ich habe …

 public static final int ROWS = 8; public static final int COLUMNS = 8; //... int[][] gridTable = new int[ROWS][COLUMNS]; gridTable[ROWS - 1][3] = 1; gridTable[ROWS - 2][3] = 1; gridTable[ROWS - 3][3] = 1; gridTable[ROWS - 4][3] = 1; for (int[] row : gridTable) { StringJoiner sj = new StringJoiner("|", "|", "|"); for (int col : row) { sj.add(Integer.toString(col)); } System.out.println(sj); } System.out.println(didWin(gridTable, 1, 3, 3)); 

und konnte es zur Arbeit bringen. Manchmal ist eine Antwort keine vollständige Lösung, sondern ein Keim für eine Idee, die jemanden an einen neuen Ort bringt;)

Eine weitere Verbesserung würde beinhalten, die Anzahl der erwarteten verbundenen Stücke zu liefern, aber ich bin mir ziemlich sicher, dass das eine Verbesserung ist, die ich wirklich nicht demonstrieren muss;)

das hat bei mir funktioniert, es hat auch nicht so lange gedauert wie es scheint:
dies sind Methoden mit Zeile, Spalte, Diagonale und Antidiagonale für x und o;

 public static void checkVertO(){ if (board[0][0] == 'O' && board[1][0] == 'O' && board[2][0] == 'O' && board[3][0] == 'O' || board[1][0] == 'O' && board[2][0] == 'O' && board[3][0] == 'O' && board[4][0] == 'O' || board[2][0] == 'O' && board[3][0] == 'O' && board[4][0] == 'O' && board[5][0] == 'O' || board[0][1] == 'O' && board[1][1] == 'O' && board[2][1] == 'O' && board[3][1] == 'O' || board[1][1] == 'O' && board[2][1] == 'O' && board[3][1] == 'O' && board[4][1] == 'O' || board[2][1] == 'O' && board[3][1] == 'O' && board[4][1] == 'O' && board[5][1] == 'O' || board[0][2] == 'O' && board[1][2] == 'O' && board[2][2] == 'O' && board[3][2] == 'O' || board[1][2] == 'O' && board[2][2] == 'O' && board[3][2] == 'O' && board[4][2] == 'O' || board[2][2] == 'O' && board[3][2] == 'O' && board[4][2] == 'O' && board[5][2] == 'O' || board[0][3] == 'O' && board[1][3] == 'O' && board[2][3] == 'O' && board[3][3] == 'O' || board[1][3] == 'O' && board[2][3] == 'O' && board[3][3] == 'O' && board[4][3] == 'O' || board[2][3] == 'O' && board[3][3] == 'O' && board[4][3] == 'O' && board[5][3] == 'O' || board[0][4] == 'O' && board[1][4] == 'O' && board[2][4] == 'O' && board[3][4] == 'O' || board[1][4] == 'O' && board[2][4] == 'O' && board[3][4] == 'O' && board[4][4] == 'O' || board[2][4] == 'O' && board[3][4] == 'O' && board[4][4] == 'O' && board[5][4] == 'O' || board[0][5] == 'O' && board[1][5] == 'O' && board[2][5] == 'O' && board[3][5] == 'O' || board[1][5] == 'O' && board[2][5] == 'O' && board[3][5] == 'O' && board[4][5] == 'O' || board[2][5] == 'O' && board[3][5] == 'O' && board[4][5] == 'O' && board[5][5] == 'O' || board[0][6] == 'O' && board[1][6] == 'O' && board[2][6] == 'O' && board[3][6] == 'O' || board[1][6] == 'O' && board[2][6] == 'O' && board[3][6] == 'O' && board[4][6] == 'O'|| board[2][6] == 'O' && board[3][6] == 'O' && board[4][6] == 'O' && board[5][6] == 'O'){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } } public static void checkHorzO(){ if (board[0][0] == 'O' && board[0][1] == 'O' && board[0][2] == 'O' && board[0][3] == 'O' || board[0][1] == 'O' && board[0][2] == 'O' && board[0][3] == 'O' && board[0][4] == 'O' || board[0][2] == 'O' && board[0][3] == 'O' && board[0][4] == 'O' && board[0][5] == 'O' || board[0][3] == 'O' && board[0][4] == 'O' && board[0][5] == 'O' && board[0][6] == 'O' || board[1][0] == 'O' && board[1][1] == 'O' && board[1][2] == 'O' && board[1][3] == 'O' || board[1][1] == 'O' && board[1][2] == 'O' && board[1][3] == 'O' && board[1][4] == 'O' || board[1][2] == 'O' && board[1][3] == 'O' && board[1][4] == 'O' && board[1][5] == 'O' || board[1][3] == 'O' && board[1][4] == 'O' && board[1][5] == 'O' && board[1][6] == 'O' || board[2][0] == 'O' && board[2][1] == 'O' && board[2][2] == 'O' && board[2][3] == 'O' || board[2][1] == 'O' && board[2][2] == 'O' && board[2][3] == 'O' && board[2][4] == 'O' || board[2][2] == 'O' && board[2][3] == 'O' && board[2][4] == 'O' && board[2][5] == 'O' || board[2][3] == 'O' && board[2][4] == 'O' && board[2][5] == 'O' && board[2][6] == 'O' || board[3][0] == 'O' && board[3][1] == 'O' && board[3][2] == 'O' && board[3][3] == 'O' || board[3][1] == 'O' && board[3][2] == 'O' && board[3][3] == 'O' && board[3][4] == 'O' || board[3][2] == 'O' && board[3][3] == 'O' && board[3][4] == 'O' && board[3][5] == 'O' || board[3][3] == 'O' && board[3][4] == 'O' && board[3][5] == 'O' && board[3][6] == 'O' || board[4][0] == 'O' && board[4][1] == 'O' && board[4][2] == 'O' && board[4][3] == 'O' || board[4][1] == 'O' && board[4][2] == 'O' && board[4][3] == 'O' && board[4][4] == 'O' || board[4][2] == 'O' && board[4][3] == 'O' && board[4][4] == 'O' && board[4][5] == 'O' || board[4][3] == 'O' && board[4][4] == 'O' && board[4][5] == 'O' && board[4][6] == 'O' || board[5][0] == 'O' && board[5][1] == 'O' && board[5][2] == 'O' && board[5][3] == 'O' || board[5][1] == 'O' && board[5][2] == 'O' && board[5][3] == 'O' && board[5][4] == 'O' || board[5][2] == 'O' && board[5][3] == 'O' && board[5][4] == 'O' && board[5][5] == 'O' || board[5][3] == 'O' && board[5][4] == 'O' && board[5][5] == 'O' && board[5][6] == 'O' ){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } } public static void checkHorzX(){ if (board[0][0] == 'X' && board[0][1] == 'X' && board[0][2] == 'X' && board[0][3] == 'X' || board[0][1] == 'X' && board[0][2] == 'X' && board[0][3] == 'X' && board[0][4] == 'X' || board[0][2] == 'X' && board[0][3] == 'X' && board[0][4] == 'X' && board[0][5] == 'X' || board[0][3] == 'X' && board[0][4] == 'X' && board[0][5] == 'X' && board[0][6] == 'X' || board[1][0] == 'X' && board[1][1] == 'X' && board[1][2] == 'X' && board[1][3] == 'X' || board[1][1] == 'X' && board[1][2] == 'X' && board[1][3] == 'X' && board[1][4] == 'X' || board[1][2] == 'X' && board[1][3] == 'X' && board[1][4] == 'X' && board[1][5] == 'X' || board[1][3] == 'X' && board[1][4] == 'X' && board[1][5] == 'X' && board[1][6] == 'X' || board[2][0] == 'X' && board[2][3] == 'X' && board[2][4] == 'X' && board[2][5] == 'X' || board[2][3] == 'X' && board[2][4] == 'X' && board[2][5] == 'X' && board[2][6] == 'X' || board[3][0] == 'X' && board[3][1] == 'X' && board[3][2] == 'X' && board[3][3] == 'X' || board[3][1] == 'X' && board[3][2] == 'X' && board[3][3] == 'X' && board[3][4] == 'X' || board[3][2] == 'X' && board[3][3] == 'X' && board[3][4] == 'X' && board[3][5] == 'X' || board[3][3] == 'X' && board[3][4] == 'X' && board[3][5] == 'X' && board[3][6] == 'X' || board[4][0] == 'X' && board[4][3] == 'X' && board[4][4] == 'X' && board[4][5] == 'X' || board[4][3] == 'X' && board[4][4] == 'X' && board[4][5] == 'X' && board[4][6] == 'X' || board[5][0] == 'X' && board[5][1] == 'X' && board[5][2] == 'X' && board[5][3] == 'X' || board[5][1] == 'X' && board[5][2] == 'X' && board[5][3] == 'X' && board[5][4] == 'X' || board[5][2] == 'X' && board[5][3] == 'X' && board[5][4] == 'X' && board[5][5] == 'X' || board[5][3] == 'X' && board[5][4] == 'X' && board[5][5] == 'X' && board[5][6] == 'X' ){ System.out.println("Game over, X won."); printBoard(); doIt(); }else { return; } } public static void checkDiagX(){ if (board[2][0] == 'X' && board[3][1] == 'X' && board[4][2] == 'X' && board[5][3] == 'X'|| board[1][0] == 'X' && board[2][1] == 'X' && board[3][2] == 'X' && board[4][3] == 'X'|| board[0][0] == 'X' && board[1][1] == 'X' && board[2][2] == 'X' && board[3][3] == 'X'|| board[0][1] == 'X' && board[1][2] == 'X' && board[2][3] == 'X' && board[3][4] == 'X'|| board[1][1] == 'X' && board[2][2] == 'X' && board[3][3] == 'X' && board[4][4] == 'X'|| board[2][1] == 'X' && board[3][2] == 'X' && board[4][3] == 'X' && board[5][4] == 'X'|| board[0][2] == 'X' && board[1][3] == 'X' && board[2][4] == 'X' && board[3][5] == 'X'|| board[1][2] == 'X' && board[2][3] == 'X' && board[3][4] == 'X' && board[4][5] == 'X'|| board[2][2] == 'X' && board[3][3] == 'X' && board[4][4] == 'X' && board[5][5] == 'X'|| board[0][3] == 'X' && board[1][4] == 'X' && board[2][5] == 'X' && board[3][6] == 'X'|| board[1][3] == 'X' && board[2][4] == 'X' && board[3][5] == 'X' && board[4][6] == 'X'|| board[2][3] == 'X' && board[3][4] == 'X' && board[4][5] == 'X' && board[5][6] == 'X'){ System.out.println("Game over, X won."); printBoard(); doIt(); }else { return; } } public static void checkDiagO(){ if (board[2][0] == 'O' && board[3][1] == 'O' && board[4][2] == 'O' && board[5][3] == 'O'|| board[1][0] == 'O' && board[2][1] == 'O' && board[3][2] == 'O' && board[4][3] == 'O'|| board[0][0] == 'O' && board[1][1] == 'O' && board[2][2] == 'O' && board[3][3] == 'O'|| board[0][1] == 'O' && board[1][2] == 'O' && board[2][3] == 'O' && board[3][4] == 'O'|| board[1][1] == 'O' && board[2][2] == 'O' && board[3][3] == 'O' && board[4][4] == 'O'|| board[2][1] == 'O' && board[3][2] == 'O' && board[4][3] == 'O' && board[5][4] == 'O'|| board[0][2] == 'O' && board[1][3] == 'O' && board[2][4] == 'O' && board[3][5] == 'O'|| board[1][2] == 'O' && board[2][3] == 'O' && board[3][4] == 'O' && board[4][5] == 'O'|| board[2][2] == 'O' && board[3][3] == 'O' && board[4][4] == 'O' && board[5][5] == 'O'|| board[0][3] == 'O' && board[1][4] == 'O' && board[2][5] == 'O' && board[3][6] == 'O'|| board[1][3] == 'O' && board[2][4] == 'O' && board[3][5] == 'O' && board[4][6] == 'O'|| board[2][3] == 'O' && board[3][4] == 'O' && board[4][5] == 'O' && board[5][6] == 'O'){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } } public static void checkAntiDiagX(){ if (board[3][0] == 'X' && board[2][1] == 'X' && board[1][2] == 'X' && board[0][3] == 'X'|| board[4][0] == 'X' && board[3][1] == 'X' && board[2][2] == 'X' && board[1][3] == 'X'|| board[3][1] == 'X' && board[2][2] == 'X' && board[1][3] == 'X' && board[0][4] == 'X'|| board[5][0] == 'X' && board[4][1] == 'X' && board[3][2] == 'X' && board[2][3] == 'X'|| board[4][1] == 'X' && board[3][2] == 'X' && board[2][3] == 'X' && board[1][4] == 'X'|| board[3][2] == 'X' && board[2][2] == 'X' && board[1][4] == 'X' && board[0][5] == 'X'|| board[5][1] == 'X' && board[4][2] == 'X' && board[3][3] == 'X' && board[2][4] == 'X'|| board[4][2] == 'X' && board[3][3] == 'X' && board[2][4] == 'X' && board[1][5] == 'X'|| board[3][3] == 'X' && board[2][4] == 'X' && board[1][5] == 'X' && board[0][6] == 'X'|| board[5][2] == 'X' && board[4][3] == 'X' && board[3][4] == 'X' && board[2][5] == 'X'|| board[4][3] == 'X' && board[3][4] == 'X' && board[2][5] == 'X' && board[1][6] == 'X'|| board[5][3] == 'X' && board[4][4] == 'X' && board[3][5] == 'X' && board[2][6] == 'X'){ System.out.println("Game over, X won."); printBoard(); doIt(); }else { return; } } public static void checkAntiDiagO(){ if (board[3][0] == 'O' && board[2][1] == 'O' && board[1][2] == 'O' && board[0][3] == 'O'|| board[4][0] == 'O' && board[3][1] == 'O' && board[2][2] == 'O' && board[1][3] == 'O'|| board[3][1] == 'O' && board[2][2] == 'O' && board[1][3] == 'O' && board[0][4] == 'O'|| board[5][0] == 'O' && board[4][1] == 'O' && board[3][2] == 'O' && board[2][3] == 'O'|| board[4][1] == 'O' && board[3][2] == 'O' && board[2][3] == 'O' && board[1][4] == 'O'|| board[3][2] == 'O' && board[2][2] == 'O' && board[1][4] == 'O' && board[0][5] == 'O'|| board[5][1] == 'O' && board[4][2] == 'O' && board[3][3] == 'O' && board[2][4] == 'O'|| board[4][2] == 'O' && board[3][3] == 'O' && board[2][4] == 'O' && board[1][5] == 'O'|| board[3][3] == 'O' && board[2][4] == 'O' && board[1][5] == 'O' && board[0][6] == 'O'|| board[5][2] == 'O' && board[4][3] == 'O' && board[3][4] == 'O' && board[2][5] == 'O'|| board[4][3] == 'O' && board[3][4] == 'O' && board[2][5] == 'O' && board[1][6] == 'O'|| board[5][3] == 'O' && board[4][4] == 'O' && board[3][5] == 'O' && board[2][6] == 'O'){ System.out.println("Game over, O won."); printBoard(); doIt(); }else { return; } }