Algorithme pour déterminer le jeu de Tic Tac Toe

J’ai écrit un jeu de tic-tac-toe en Java et ma méthode actuelle de détermination de la fin du jeu tient compte des scénarios possibles suivants pour la fin du jeu:

  1. Le plateau est plein et aucun gagnant n’a encore été déclaré: le match est un match nul.
  2. Cross a gagné.
  3. Cercle a gagné.

Malheureusement, pour ce faire, il lit un ensemble prédéfini de ces scénarios à partir d’une table. Ce n’est pas forcément mauvais, car il n’y a que 9 espaces sur un tableau, et la table est donc un peu petite, mais existe-t-il un meilleur moyen algorithmique de déterminer si le jeu est terminé? La question de savoir si quelqu’un a gagné ou non est la clé du problème, car vérifier si 9 espaces sont pleins est sortingvial.

La méthode de la table peut être la solution, mais sinon, qu’est-ce que c’est? De plus, que se passe-t-il si le tableau n’a pas la taille n=9 ? Et si c’était un tableau beaucoup plus grand, disons n=16 , n=25 , et ainsi de suite, provoquant le nombre d’éléments consécutivement placés à x=4 , x=5 , etc.? Un algorithme général à utiliser pour tout n = { 9, 16, 25, 36 ... } ?

Vous savez qu’un mouvement gagnant ne peut avoir lieu que lorsque X ou O ont effectué leur déplacement le plus récent. Vous ne pouvez donc rechercher des lignes / colonnes qu’avec un message facultatif contenu dans ce mouvement pour limiter votre espace de recherche. Etant donné qu’il y a un nombre fixe de coups dans un jeu de tic-tac-toe une fois que le dernier coup a été effectué s’il ne s’agissait pas d’un coup gagnant, il s’agit par défaut d’un jeu de tirage.

edit: ce code est pour un tableau n par n avec n dans une rangée à gagner (le tableau 3×3 nécessite 3 fois de suite, etc.)

edit: ajouté du code pour vérifier l’anti-diag, je ne pouvais pas trouver un moyen non-boucle pour déterminer si le point était sur l’anti diag alors thats pourquoi cette étape est manquante

 public class TripleT { enum State{Blank, X, O}; int n = 3; State[][] board = new State[n][n]; int moveCount; void Move(int x, int y, State s){ if(board[x][y] == State.Blank){ board[x][y] = s; } moveCount++; //check end conditions //check col for(int i = 0; i < n; i++){ if(board[x][i] != s) break; if(i == n-1){ //report win for s } } //check row for(int i = 0; i < n; i++){ if(board[i][y] != s) break; if(i == n-1){ //report win for s } } //check diag if(x == y){ //we're on a diagonal for(int i = 0; i < n; i++){ if(board[i][i] != s) break; if(i == n-1){ //report win for s } } } //check anti diag (thanks rampion) if(x + y == n - 1){ for(int i = 0; i < n; i++){ if(board[i][(n-1)-i] != s) break; if(i == n-1){ //report win for s } } } //check draw if(moveCount == (Math.pow(n, 2) - 1)){ //report draw } } } 

vous pouvez utiliser un carré magique http://mathworld.wolfram.com/MagicSquare.html si une ligne, une colonne ou un diag totalise 15, alors un joueur a gagné.

Ceci est similaire à la réponse d’Osama ALASSIRY , mais il échange un espace constant et un temps linéaire pour un espace linéaire et un temps constant. C’est-à-dire qu’il n’y a pas de boucle après l’initialisation.

Initialiser une paire (0,0) pour chaque ligne, chaque colonne et les deux diagonales (diagonale et anti-diagonale). Ces paires représentent la (sum,sum) des pièces dans la rangée, la colonne ou la diagonale correspondante, où

 Un morceau du joueur A a une valeur (1,0)
 Un morceau du joueur B a une valeur (0,1)

Lorsqu’un joueur place un morceau, mettez à jour la paire de lignes, la paire de colonnes et les paires de diagonales correspondantes (si elles se trouvent sur les diagonales). Si une ligne, une colonne ou une paire de diagonales nouvellement mises à jour est égale à (n,0) ou (0,n) A ou B ont gagné respectivement.

Analyse asymptotique:

 O (1) heure (par coup)
 O (n) espace (global)

Pour l’utilisation de la mémoire, vous utilisez 4*(n+1) entiers 4*(n+1) .

 two_elements * n_rows + two_elements * n_columns +
 two_elements * two_diagonals = 4 * n + 4 entiers = 4 (n + 1) entiers

Exercice: Pouvez-vous voir comment tester un tirage au sort dans O (1) par coup? Si tel est le cas, vous pouvez terminer la partie au début du tirage.

Que diriez-vous de ce pseudocode:

Après qu’un joueur pose un morceau à la position (x, y):

 col=row=diag=rdiag=0 winner=false for i=1 to n if cell[x,i]=player then col++ if cell[i,y]=player then row++ if cell[i,i]=player then diag++ if cell[i,n-i+1]=player then rdiag++ if row=n or col=n or diag=n or rdiag=n then winner=true 

J’utiliserais un tableau de char [n, n], avec O, X et un espace vide.

  1. simple.
  2. Une boucle
  3. Cinq variables simples: 4 entiers et un booléen.
  4. Échelles à n’importe quelle taille de n.
  5. Ne vérifie que la pièce en cours.
  6. Pas de magie 🙂

Voici ma solution pour un projet sur lequel je travaille en javascript. Si cela ne vous dérange pas le coût de la mémoire de quelques baies, c’est probablement la solution la plus rapide et la plus simple que vous trouverez. Cela suppose que vous connaissiez la position du dernier coup.

 /* * Determines if the last move resulted in a win for either player * board: is an array representing the board * lastMove: is the boardIndex of the last (most recent) move * these are the boardIndexes: * * 0 | 1 | 2 * ---+---+--- * 3 | 4 | 5 * ---+---+--- * 6 | 7 | 8 * * returns true if there was a win */ var winLines = [ [[1, 2], [4, 8], [3, 6]], [[0, 2], [4, 7]], [[0, 1], [4, 6], [5, 8]], [[4, 5], [0, 6]], [[3, 5], [0, 8], [2, 6], [1, 7]], [[3, 4], [2, 8]], [[7, 8], [2, 4], [0, 3]], [[6, 8], [1, 4]], [[6, 7], [0, 4], [2, 5]] ]; function isWinningMove(board, lastMove) { var player = board[lastMove]; for (var i = 0; i < winLines[lastMove].length; i++) { var line = winLines[lastMove][i]; if(player === board[line[0]] && player === board[line[1]]) { return true; } } return false; } 

Je viens d’écrire ceci pour ma classe de programmation C.

Je le publie parce qu’aucun des autres exemples ici ne fonctionnera avec une grid rectangular de n’importe quelle taille, et aucun nombre consécutif de points N -in-a-row pour gagner.

Vous trouverez mon algorithme tel qu’il est dans la fonction checkWinner() . Il n’utilise pas de chiffres magiques ou quelque chose de compliqué pour rechercher un gagnant, il utilise simplement quatre pour les boucles – Le code est bien commenté, donc je le laisse parler pour lui-même, je suppose.

 // This program will work with any whole number sized rectangular gameBoard. // It checks for N marks in straight lines (rows, columns, and diagonals). // It is prettiest when ROWS and COLS are single digit numbers. // Try altering the constants for ROWS, COLS, and N for great fun! // PPDs come first #include  #define ROWS 9 // The number of rows our gameBoard array will have #define COLS 9 // The number of columns of the same - Single digit numbers will be prettier! #define N 3 // This is the number of contiguous marks a player must have to win #define INITCHAR ' ' // This changes the character displayed (a ' ' here probably looks the best) #define PLAYER1CHAR 'X' // Some marks are more aesthetically pleasing than others #define PLAYER2CHAR 'O' // Change these lines if you care to experiment with them // Function prototypes are next int playGame (char gameBoard[ROWS][COLS]); // This function allows the game to be replayed easily, as desired void initBoard (char gameBoard[ROWS][COLS]); // Fills the ROWSxCOLS character array with the INITCHAR character void printBoard (char gameBoard[ROWS][COLS]); // Prints out the current board, now with pretty formatting and #s! void makeMove (char gameBoard[ROWS][COLS], int player); // Prompts for (and validates!) a move and stores it into the array int checkWinner (char gameBoard[ROWS][COLS], int player); // Checks the current state of the board to see if anyone has won // The starting line int main (void) { // Inits char gameBoard[ROWS][COLS]; // Our gameBoard is declared as a character array, ROWS x COLS in size int winner = 0; char replay; //Code do // This loop plays through the game until the user elects not to { winner = playGame(gameBoard); printf("\nWould you like to play again? Y for yes, anything else exits: "); scanf("%c",&replay); // I have to use both a scanf() and a getchar() in replay = getchar(); // order to clear the input buffer of a newline char // (http://cboard.cprogramming.com/c-programming/121190-problem-do-while-loop-char.html) } while ( replay == 'y' || replay == 'Y' ); // Housekeeping printf("\n"); return winner; } int playGame(char gameBoard[ROWS][COLS]) { int turn = 0, player = 0, winner = 0, i = 0; initBoard(gameBoard); do { turn++; // Every time this loop executes, a unique turn is about to be made player = (turn+1)%2+1; // This mod function alternates the player variable between 1 & 2 each turn makeMove(gameBoard,player); printBoard(gameBoard); winner = checkWinner(gameBoard,player); if (winner != 0) { printBoard(gameBoard); for (i=0;i<19-2*ROWS;i++) // Formatting - works with the default shell height on my machine printf("\n"); // Hopefully I can replace these with something that clears the screen for me printf("\n\nCongratulations Player %i, you've won with %i in a row!\n\n",winner,N); return winner; } } while ( turn < ROWS*COLS ); // Once ROWS*COLS turns have elapsed printf("\n\nGame Over!\n\nThere was no Winner :-(\n"); // The board is full and the game is over return winner; } void initBoard (char gameBoard[ROWS][COLS]) { int row = 0, col = 0; for (row=0;row ROWS-1 || col > COLS-1) // We are not using a do... while because { // I wanted the prompt to change printBoard(gameBoard); for (i=0;i<20-2*ROWS;i++) printf("\n"); printf("\nPlayer %i, please enter a valid move! Column first, then row.\n",player); scanf("%i %i",&col,&row); row--; // See above ^^^ col--; } gameBoard[row][col] = currentChar; // Finally, we store the correct mark into the given location return; // And pop back out of this function } int checkWinner(char gameBoard[ROWS][COLS], int player) // I've commented the last (and the hardest, for me anyway) { // check, which checks for backwards diagonal runs below >>> int row = 0, col = 0, i = 0; char currentChar; if (player == 1) currentChar = PLAYER1CHAR; else currentChar = PLAYER2CHAR; for ( row = 0; row < ROWS; row++) // This first for loop checks every row { for ( col = 0; col < (COLS-(N-1)); col++) // And all columns until N away from the end { while (gameBoard[row][col] == currentChar) // For consecutive rows of the current player's mark { col++; i++; if (i == N) { return player; } } i = 0; } } for ( col = 0; col < COLS; col++) // This one checks for columns of consecutive marks { for ( row = 0; row < (ROWS-(N-1)); row++) { while (gameBoard[row][col] == currentChar) { row++; i++; if (i == N) { return player; } } i = 0; } } for ( col = 0; col < (COLS - (N-1)); col++) // This one checks for "forwards" diagonal runs { for ( row = 0; row < (ROWS-(N-1)); row++) { while (gameBoard[row][col] == currentChar) { row++; col++; i++; if (i == N) { return player; } } i = 0; } } // Finally, the backwards diagonals: for ( col = COLS-1; col > 0+(N-2); col--) // Start from the last column and go until N columns from the first { // The math seems strange here but the numbers work out when you trace them for ( row = 0; row < (ROWS-(N-1)); row++) // Start from the first row and go until N rows from the last { while (gameBoard[row][col] == currentChar) // If the current player's character is there { row++; // Go down a row col--; // And back a column i++; // The i variable tracks how many consecutive marks have been found if (i == N) // Once i == N { return player; // Return the current player number to the } // winnner variable in the playGame function } // If it breaks out of the while loop, there weren't N consecutive marks i = 0; // So make i = 0 again } // And go back into the for loop, incrementing the row to check from } return 0; // If we got to here, no winner has been detected, } // so we pop back up into the playGame function // The end! // Well, almost. // Eventually I hope to get this thing going // with a dynamically sized array. I'll make // the CONSTANTS into variables in an initGame // function and allow the user to define them. 

Si le tableau est n × n, il y a n lignes, n colonnes et 2 diagonales. Vérifiez chacun de ceux pour tous les X ou tous les O pour trouver un gagnant.

S’il ne faut que x < n places consécutives pour gagner, alors c’est un peu plus compliqué. La solution la plus évidente consiste à vérifier chaque carré x × x pour un gagnant. Voici un code qui le démontre.

(Je n’ai pas vraiment testé cette * toux *, mais elle a été compilée au premier essai, oui!)

 public class TicTacToe { public enum Square { X, O, NONE } /** * Returns the winning player, or NONE if the game has * finished without a winner, or null if the game is unfinished. */ public Square findWinner(Square[][] board, int lengthToWin) { // Check each lengthToWin x lengthToWin board for a winner. for (int top = 0; top <= board.length - lengthToWin; ++top) { int bottom = top + lengthToWin - 1; for (int left = 0; left <= board.length - lengthToWin; ++left) { int right = left + lengthToWin - 1; // Check each row. nextRow: for (int row = top; row <= bottom; ++row) { if (board[row][left] == Square.NONE) { continue; } for (int col = left; col <= right; ++col) { if (board[row][col] != board[row][left]) { continue nextRow; } } return board[row][left]; } // Check each column. nextCol: for (int col = left; col <= right; ++col) { if (board[top][col] == Square.NONE) { continue; } for (int row = top; row <= bottom; ++row) { if (board[row][col] != board[top][col]) { continue nextCol; } } return board[top][col]; } // Check top-left to bottom-right diagonal. diag1: if (board[top][left] != Square.NONE) { for (int i = 1; i < lengthToWin; ++i) { if (board[top+i][left+i] != board[top][left]) { break diag1; } } return board[top][left]; } // Check top-right to bottom-left diagonal. diag2: if (board[top][right] != Square.NONE) { for (int i = 1; i < lengthToWin; ++i) { if (board[top+i][right-i] != board[top][right]) { break diag2; } } return board[top][right]; } } } // Check for a completely full board. boolean isFull = true; full: for (int row = 0; row < board.length; ++row) { for (int col = 0; col < board.length; ++col) { if (board[row][col] == Square.NONE) { isFull = false; break full; } } } // The board is full. if (isFull) { return Square.NONE; } // The board is not full and we didn't find a solution. else { return null; } } } 

Je ne connais pas bien Java, mais je connais le C, alors j’ai essayé l’ idée du carré magique d’Adk (avec la ressortingction de recherche de Hardwareguy ).

 // tic-tac-toe.c // to comstack: // % gcc -o tic-tac-toe tic-tac-toe.c // to run: // % ./tic-tac-toe #include  // the two types of marks available typedef enum { Empty=2, X=0, O=1, NumMarks=2 } Mark; char const MarkToChar[] = "XO "; // a structure to hold the sums of each kind of mark typedef struct { unsigned char of[NumMarks]; } Sum; // a cell in the board, which has a particular value #define MAGIC_NUMBER 15 typedef struct { Mark mark; unsigned char const value; size_t const num_sums; Sum * const sums[4]; } Cell; #define NUM_ROWS 3 #define NUM_COLS 3 // create a sum for each possible tic-tac-toe Sum row[NUM_ROWS] = {0}; Sum col[NUM_COLS] = {0}; Sum nw_diag = {0}; Sum ne_diag = {0}; // initialize the board values so any row, column, or diagonal adds to // MAGIC_NUMBER, and so they each record their sums in the proper rows, columns, // and diagonals Cell board[NUM_ROWS][NUM_COLS] = { { { Empty, 8, 3, { &row[0], &col[0], &nw_diag } }, { Empty, 1, 2, { &row[0], &col[1] } }, { Empty, 6, 3, { &row[0], &col[2], &ne_diag } }, }, { { Empty, 3, 2, { &row[1], &col[0] } }, { Empty, 5, 4, { &row[1], &col[1], &nw_diag, &ne_diag } }, { Empty, 7, 2, { &row[1], &col[2] } }, }, { { Empty, 4, 3, { &row[2], &col[0], &ne_diag } }, { Empty, 9, 2, { &row[2], &col[1] } }, { Empty, 2, 3, { &row[2], &col[2], &nw_diag } }, } }; // print the board void show_board(void) { size_t r, c; for (r = 0; r < NUM_ROWS; r++) { if (r > 0) { printf("---+---+---\n"); } for (c = 0; c < NUM_COLS; c++) { if (c > 0) { printf("|"); } printf(" %c ", MarkToChar[board[r][c].mark]); } printf("\n"); } } // run the game, asking the player for inputs for each side int main(int argc, char * argv[]) { size_t m; show_board(); printf("Enter moves as \" \" (no quotes, zero indexed)\n"); for( m = 0; m < NUM_ROWS * NUM_COLS; m++ ) { Mark const mark = (Mark) (m % NumMarks); size_t c, r; // read the player's move do { printf("%c's move: ", MarkToChar[mark]); fflush(stdout); scanf("%d %d", &r, &c); if (r >= NUM_ROWS || c >= NUM_COLS) { printf("illegal move (off the board), try again\n"); } else if (board[r][c].mark != Empty) { printf("illegal move (already taken), try again\n"); } else { break; } } while (1); { Cell * const cell = &(board[r][c]); size_t s; // update the board state cell->mark = mark; show_board(); // check for tic-tac-toe for (s = 0; s < cell->num_sums; s++) { cell->sums[s]->of[mark] += cell->value; if (cell->sums[s]->of[mark] == MAGIC_NUMBER) { printf("tic-tac-toe! %c wins!\n", MarkToChar[mark]); goto done; } } } } printf("stalemate... nobody wins :(\n"); done: return 0; } 

Il comstack et teste bien.

 % gcc -o tic-tac-toe tic-tac-toe.c
 % ./tic-tac-toe
      |  |
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   Entrer se déplace comme "" (pas de guillemets, zéro indexé)
   Le coup de X: 1 2
      |  |
   --- + --- + ---
      |  |  X
   --- + --- + ---
      |  |
   Le coup de O: 1 2
   déménagement illégal (déjà pris), réessayez
   Le coup de O: 3 3
   déménagement illégal (hors du tableau), essayez à nouveau
   Le coup de O: 2 2
      |  |
   --- + --- + ---
      |  |  X
   --- + --- + ---
      |  |  O
   Le coup de X: 1 0
      |  |
   --- + --- + ---
    X |  |  X
   --- + --- + ---
      |  |  O
   Le coup de O: 1 1
      |  |
   --- + --- + ---
    X |  O |  X
   --- + --- + ---
      |  |  O
   Le coup de X: 0 0
    X |  |
   --- + --- + ---
    X |  O |  X
   --- + --- + ---
      |  |  O
   Le coup de O: 2 0
    X |  |
   --- + --- + ---
    X |  O |  X
   --- + --- + ---
    O |  |  O
   Le coup de X: 2 1
    X |  |
   --- + --- + ---
    X |  O |  X
   --- + --- + ---
    O |  X |  O
   Le coup de O: 0 2
    X |  |  O
   --- + --- + ---
    X |  O |  X
   --- + --- + ---
    O |  X |  O
   tic-tac-toe!  O gagne!
 % ./tic-tac-toe
      |  |
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   Entrer se déplace comme "" (pas de guillemets, zéro indexé)
   Le coup de X: 0 0
    X |  |
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   Le coup de O: 0 1
    X |  O |
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   Le coup de X: 0 2
    X |  O |  X
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   Le coup de O: 1 0
    X |  O |  X
   --- + --- + ---
    O |  |
   --- + --- + ---
      |  |
   Le coup de X: 1 1
    X |  O |  X
   --- + --- + ---
    O |  X |
   --- + --- + ---
      |  |
   Le coup de O: 2 0
    X |  O |  X
   --- + --- + ---
    O |  X |
   --- + --- + ---
    O |  |
   Le coup de X: 2 1
    X |  O |  X
   --- + --- + ---
    O |  X |
   --- + --- + ---
    O |  X |
   Le coup de O: 2 2
    X |  O |  X
   --- + --- + ---
    O |  X |
   --- + --- + ---
    O |  X |  O
   Le coup de X: 1 2
    X |  O |  X
   --- + --- + ---
    O |  X |  X
   --- + --- + ---
    O |  X |  O
   impasse ... personne ne gagne :(
 %

C’était amusant, merci!

En fait, en y réfléchissant, vous n’avez pas besoin d’un carré magique, juste un compte pour chaque ligne / colonne / diagonale. C’est un peu plus facile que de généraliser un carré magique à n × n masortingces, puisqu’il suffit de compter jusqu’à n .

On m’a posé la même question dans l’une de mes interviews. Mes pensées: Initialiser la masortingce avec 0. Garder 3 tableaux 1) sum_row (taille n) 2) sum_column (taille n) 3) diagonale (taille 2)

Pour chaque déplacement de (X), décrémenter la valeur de la boîte de 1 et pour chaque déplacement de (0) l’incrémenter de 1. À tout moment si la ligne / colonne / diagonale modifiée dans le déplacement actuel a une sum de -3 ou + 3 signifie que quelqu’un a gagné la partie. Pour un tirage au sort, nous pouvons utiliser l’approche ci-dessus pour conserver la variable moveCount.

Pensez-vous que je manque quelque chose?

Edit: Same peut être utilisé pour la masortingce nxn. La sum devrait être égale à +3 ou -3.

un moyen non-boucle pour déterminer si le point était sur l’anti diag:

 `if (x + y == n - 1)` 

J’ai effectué quelques optimisations dans les contrôles de ligne, de col et de diagonale. Son principalement décidé dans la première boucle nestede si nous devons vérifier une colonne ou une diagonale particulière. Ainsi, nous évitons de vérifier le gain de temps des colonnes ou des diagonales. Cela a un impact important lorsque la taille de la carte est supérieure et qu’un nombre important de cellules ne sont pas remplies.

Voici le code Java pour cela.

  int gameState(int values[][], int boardSz) { boolean colCheckNotRequired[] = new boolean[boardSz];//default is false boolean diag1CheckNotRequired = false; boolean diag2CheckNotRequired = false; boolean allFilled = true; int x_count = 0; int o_count = 0; /* Check rows */ for (int i = 0; i < boardSz; i++) { x_count = o_count = 0; for (int j = 0; j < boardSz; j++) { if(values[i][j] == x_val)x_count++; if(values[i][j] == o_val)o_count++; if(values[i][j] == 0) { colCheckNotRequired[j] = true; if(i==j)diag1CheckNotRequired = true; if(i + j == boardSz - 1)diag2CheckNotRequired = true; allFilled = false; //No need check further break; } } if(x_count == boardSz)return X_WIN; if(o_count == boardSz)return O_WIN; } /* check cols */ for (int i = 0; i < boardSz; i++) { x_count = o_count = 0; if(colCheckNotRequired[i] == false) { for (int j = 0; j < boardSz; j++) { if(values[j][i] == x_val)x_count++; if(values[j][i] == o_val)o_count++; //No need check further if(values[i][j] == 0)break; } if(x_count == boardSz)return X_WIN; if(o_count == boardSz)return O_WIN; } } x_count = o_count = 0; /* check diagonal 1 */ if(diag1CheckNotRequired == false) { for (int i = 0; i < boardSz; i++) { if(values[i][i] == x_val)x_count++; if(values[i][i] == o_val)o_count++; if(values[i][i] == 0)break; } if(x_count == boardSz)return X_WIN; if(o_count == boardSz)return O_WIN; } x_count = o_count = 0; /* check diagonal 2 */ if( diag2CheckNotRequired == false) { for (int i = boardSz - 1,j = 0; i >= 0 && j < boardSz; i--,j++) { if(values[j][i] == x_val)x_count++; if(values[j][i] == o_val)o_count++; if(values[j][i] == 0)break; } if(x_count == boardSz)return X_WIN; if(o_count == boardSz)return O_WIN; x_count = o_count = 0; } if( allFilled == true) { for (int i = 0; i < boardSz; i++) { for (int j = 0; j < boardSz; j++) { if (values[i][j] == 0) { allFilled = false; break; } } if (allFilled == false) { break; } } } if (allFilled) return DRAW; return INPROGRESS; } 

Je suis en retard à la fête, mais je voulais souligner un avantage que j’ai trouvé en utilisant un carré magique , à savoir qu’il peut être utilisé pour obtenir une référence au carré qui entraînerait la victoire ou la perte au prochain tour, plutôt que juste utilisé pour calculer quand un jeu est terminé.

Prenez ce carré magique:

 4 9 2 3 5 7 8 1 6 

Tout d’abord, configurez un tableau de scores incrémenté chaque fois qu’un déplacement est effectué. Voir cette réponse pour plus de détails. Maintenant, si nous jouons illégalement X deux fois de suite à [0,0] et [0,1], le tableau des scores ressemble à ceci:

 [7, 0, 0, 4, 3, 0, 4, 0]; 

Et le tableau ressemble à ceci:

 X . . X . . . . . 

Ensuite, tout ce que nous avons à faire pour obtenir une référence à quelle case gagner / bloquer est:

 get_winning_move = function() { for (var i = 0, i < scores.length; i++) { // keep track of the number of times pieces were added to the row // subtract when the opposite team adds a piece if (scores[i].inc === 2) { return 15 - state[i].val; // 8 } } } 

En réalité, l'implémentation nécessite quelques astuces supplémentaires, comme la manipulation de clés numérotées (en JavaScript), mais je l'ai trouvé assez simple et j'ai apprécié les mathématiques récréatives.

J’aime cet algorithme car il utilise une représentation de 1×9 vs 3×3 du tableau.

 private int[] board = new int[9]; private static final int[] START = new int[] { 0, 3, 6, 0, 1, 2, 0, 2 }; private static final int[] INCR = new int[] { 1, 1, 1, 3, 3, 3, 4, 2 }; private static int SIZE = 3; /** * Determines if there is a winner in tic-tac-toe board. * @return {@code 0} for draw, {@code 1} for 'X', {@code -1} for 'Y' */ public int hasWinner() { for (int i = 0; i < START.length; i++) { int sum = 0; for (int j = 0; j < SIZE; j++) { sum += board[START[i] + j * INCR[i]]; } if (Math.abs(sum) == SIZE) { return sum / SIZE; } } return 0; } 

Une autre option: générer votre table avec du code. Jusqu’à la symésortinge, il n’y a que trois manières de gagner: la ligne de bord, la ligne du milieu ou la diagonale. Prenez ces trois et faites-les tourner de toutes les manières possibles:

 def spin(g): return set([g, turn(g), turn(turn(g)), turn(turn(turn(g)))]) def turn(g): return tuple(tuple(g[y][x] for y in (0,1,2)) for x in (2,1,0)) X,s = 'X.' XXX = X, X, X sss = s, s, s ways_to_win = ( spin((XXX, sss, sss)) | spin((sss, XXX, sss)) | spin(((X,s,s), (s,X,s), (s,s,X)))) 

Ces symésortinges peuvent être plus utiles dans votre code de jeu: si vous obtenez une carte dont vous avez déjà vu une version pivotée, vous pouvez simplement prendre la valeur en cache ou la meilleure mise en cache de celle-ci (et la rouvrir). C’est généralement beaucoup plus rapide que d’évaluer le sous-arbre du jeu.

(Inverser à gauche et à droite peut aider de la même manière; il n’était pas nécessaire ici car l’ensemble des rotations des motifs gagnants est symésortingque par rapport au miroir.)

Voici une solution que j’ai trouvée, celle-ci stocke les symboles sous forme de caractères et utilise la valeur int du caractère pour déterminer si X ou O a gagné (consultez le code de l’arbitre).

 public class TicTacToe { public static final char BLANK = '\u0000'; private final char[][] board; private int moveCount; private Referee referee; public TicTacToe(int gridSize) { if (gridSize < 3) throw new IllegalArgumentException("TicTacToe board size has to be minimum 3x3 grid"); board = new char[gridSize][gridSize]; referee = new Referee(gridSize); } public char[][] displayBoard() { return board.clone(); } public String move(int x, int y) { if (board[x][y] != BLANK) return "(" + x + "," + y + ") is already occupied"; board[x][y] = whoseTurn(); return referee.isGameOver(x, y, board[x][y], ++moveCount); } private char whoseTurn() { return moveCount % 2 == 0 ? 'X' : 'O'; } private class Referee { private static final int NO_OF_DIAGONALS = 2; private static final int MINOR = 1; private static final int PRINCIPAL = 0; private final int gridSize; private final int[] rowTotal; private final int[] colTotal; private final int[] diagonalTotal; private Referee(int size) { gridSize = size; rowTotal = new int[size]; colTotal = new int[size]; diagonalTotal = new int[NO_OF_DIAGONALS]; } private String isGameOver(int x, int y, char symbol, int moveCount) { if (isWinningMove(x, y, symbol)) return symbol + " won the game!"; if (isBoardCompletelyFilled(moveCount)) return "Its a Draw!"; return "continue"; } private boolean isBoardCompletelyFilled(int moveCount) { return moveCount == gridSize * gridSize; } private boolean isWinningMove(int x, int y, char symbol) { if (isPrincipalDiagonal(x, y) && allSymbolsMatch(symbol, diagonalTotal, PRINCIPAL)) return true; if (isMinorDiagonal(x, y) && allSymbolsMatch(symbol, diagonalTotal, MINOR)) return true; return allSymbolsMatch(symbol, rowTotal, x) || allSymbolsMatch(symbol, colTotal, y); } private boolean allSymbolsMatch(char symbol, int[] total, int index) { total[index] += symbol; return total[index] / gridSize == symbol; } private boolean isPrincipalDiagonal(int x, int y) { return x == y; } private boolean isMinorDiagonal(int x, int y) { return x + y == gridSize - 1; } } } 

Aussi voici mes tests unitaires pour valider que cela fonctionne réellement

 import static com.agilefaqs.tdd.demo.TicTacToe.BLANK; import static org.junit.Assert.assertArrayEquals; import static org.junit.Assert.assertEquals; import org.junit.Test; public class TicTacToeTest { private TicTacToe game = new TicTacToe(3); @Test public void allCellsAreEmptyInANewGame() { assertBoardIs(new char[][] { { BLANK, BLANK, BLANK }, { BLANK, BLANK, BLANK }, { BLANK, BLANK, BLANK } }); } @Test(expected = IllegalArgumentException.class) public void boardHasToBeMinimum3x3Grid() { new TicTacToe(2); } @Test public void firstPlayersMoveMarks_X_OnTheBoard() { assertEquals("continue", game.move(1, 1)); assertBoardIs(new char[][] { { BLANK, BLANK, BLANK }, { BLANK, 'X', BLANK }, { BLANK, BLANK, BLANK } }); } @Test public void secondPlayersMoveMarks_O_OnTheBoard() { game.move(1, 1); assertEquals("continue", game.move(2, 2)); assertBoardIs(new char[][] { { BLANK, BLANK, BLANK }, { BLANK, 'X', BLANK }, { BLANK, BLANK, 'O' } }); } @Test public void playerCanOnlyMoveToAnEmptyCell() { game.move(1, 1); assertEquals("(1,1) is already occupied", game.move(1, 1)); } @Test public void firstPlayerWithAllSymbolsInOneRowWins() { game.move(0, 0); game.move(1, 0); game.move(0, 1); game.move(2, 1); assertEquals("X won the game!", game.move(0, 2)); } @Test public void firstPlayerWithAllSymbolsInOneColumnWins() { game.move(1, 1); game.move(0, 0); game.move(2, 1); game.move(1, 0); game.move(2, 2); assertEquals("O won the game!", game.move(2, 0)); } @Test public void firstPlayerWithAllSymbolsInPrincipalDiagonalWins() { game.move(0, 0); game.move(1, 0); game.move(1, 1); game.move(2, 1); assertEquals("X won the game!", game.move(2, 2)); } @Test public void firstPlayerWithAllSymbolsInMinorDiagonalWins() { game.move(0, 2); game.move(1, 0); game.move(1, 1); game.move(2, 1); assertEquals("X won the game!", game.move(2, 0)); } @Test public void whenAllCellsAreFilledTheGameIsADraw() { game.move(0, 2); game.move(1, 1); game.move(1, 0); game.move(2, 1); game.move(2, 2); game.move(0, 0); game.move(0, 1); game.move(1, 2); assertEquals("Its a Draw!", game.move(2, 0)); } private void assertBoardIs(char[][] expectedBoard) { assertArrayEquals(expectedBoard, game.displayBoard()); } } 

Full solution: https://github.com/nashjain/tictactoe/tree/master/java

How about a following approach for 9 slots? Declare 9 integer variables for a 3×3 masortingx (a1,a2….a9) where a1,a2,a3 represent row-1 and a1,a4,a7 would form column-1 (you get the idea). Use ‘1’ to indicate Player-1 and ‘2’ to indicate Player-2.

There are 8 possible win combinations: Win-1: a1+a2+a3 (answer could be 3 or 6 based on which player won) Win-2: a4+a5+a6 Win-3: a7+a8+a9 Win-4: a1+a4+a7 …. Win-7: a1+a5+a9 Win-8: a3+a5+a7

Now we know that if player one crosses a1 then we need to reevaluate sum of 3 variables: Win-1, Win-4 and Win-7. Whichever ‘Win-?’ variables reaches 3 or 6 first wins the game. If Win-1 variable reaches 6 first then Player-2 wins.

I do understand that this solution is not scalable easily.

Constant time O(8), on average 4 short AND’s. Player = short number. Needs additional checks for making sure move is valid.

 // O(8) boolean isWinner(short X) { for (int i = 0; i < 8; i++) if ((X & winCombinations[i]) == winCombinations[i]) return true; return false; } short[] winCombinations = new short[]{ 7, 7 << 3, 7 << 6, // horizontal 73, 73 << 1, 73 << 2, // vertical 273, // diagonal 84 // anti-diagonal }; for (short X = 0; X < 511; X++) System.out.println(isWinner(X)); 

This is a really simple way to check.

  public class Game() { Game player1 = new Game('x'); Game player2 = new Game('o'); char piece; Game(char piece) { this.piece = piece; } public void checkWin(Game player) { // check horizontal win for (int i = 0; i <= 6; i += 3) { if (board[i] == player.piece && board[i + 1] == player.piece && board[i + 2] == player.piece) endGame(player); } // check vertical win for (int i = 0; i <= 2; i++) { if (board[i] == player.piece && board[i + 3] == player.piece && board[i + 6] == player.piece) endGame(player); } // check diagonal win if ((board[0] == player.piece && board[4] == player.piece && board[8] == player.piece) || board[2] == player.piece && board[4] == player.piece && board[6] == player.piece) endGame(player); } 

}

If you have boarder field 5*5 for examle, I used next method of checking:

 public static boolean checkWin(char symb) { int SIZE = 5; for (int i = 0; i < SIZE-1; i++) { for (int j = 0; j  

I think, it's more clear, but probably is not the most optimal way.

I developed an algorithm for this as part of a science project once.

You basically recursively divide the board into a bunch of overlapping 2×2 rects, testing the different possible combinations for winning on a 2×2 square.

It is slow, but it has the advantage of working on any sized board, with fairly linear memory requirements.

I wish I could find my implementation