Алгоритм определения игры Tic Tac Toe Over

Я написал игру tic-tac-toe в Java, и мой текущий метод определения конца игры учитывает следующие возможные сценарии для игры:

  1. Доска заполнена, и победитель еще не объявлен: игра – ничья.
  2. Крест выиграл.
  3. Круг победил.

К сожалению, для этого он читает через предопределенный набор этих сценариев из таблицы. Это не обязательно плохо, учитывая, что на доске всего 9 пробелов, и, следовательно, таблица несколько невелика, но есть ли лучший алгоритмический способ определения, закончилась ли игра? Определение того, выиграл ли кто-то или нет, является проблемой проблемы, так как проверка заполнения 9 пробелов тривиальна.

Метод таблицы может быть решением, но если нет, то что? Кроме того, что, если плата не была размером n=9 ? Что, если это была гораздо большая доска, скажем n=16 , n=25 и т. Д., Заставляя число последовательно помещенных предметов выигрывать как x=4 , x=5 и т. Д.? Общий алгоритм для всех n = { 9, 16, 25, 36 ... } ?

Вы знаете, что выигрышный ход может произойти только после того, как X или O сделали свой последний ход, поэтому вы можете искать только строку / столбец с необязательным диагетом, который содержится в этом переходе, чтобы ограничить пространство поиска при попытке определить выигрышную панель. Также, поскольку есть фиксированное количество ходов в ничью tic-tac-toe-game после того, как последний ход сделан, если он не был выигрышным движением, по умолчанию игра-ничья.

edit: этот код предназначен для n-й доски с n в строке, чтобы выиграть (3×3 доски платы 3 в строке и т. д.)

edit: добавлен код для проверки антидиаграфа, я не мог понять, нет ли способа, чтобы определить, была ли точка в антидиапазоне, поэтому почему этот шаг отсутствует

 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 } } } 

вы можете использовать магический квадрат http://mathworld.wolfram.com/MagicSquare.html, если какая-либо строка, столбец или диаг добавляет до 15, тогда игрок выиграл.

Это похоже на ответ Усамы Алассири , но он торгует постоянным пространством и линейным временем для линейного пространства и постоянного времени. То есть после инициализации цикла нет.

Инициализируйте пару (0,0) для каждой строки, каждого столбца и двух диагоналей (диагональных и антидиагональных). Эти пары представляют собой накопленные (sum,sum) частей в соответствующей строке, столбце или диагонали, где

 Кусок от игрока A имеет значение (1,0)
 Кусок от игрока B имеет значение (0,1)

Когда игрок кладет кусок, обновите соответствующую пару строк, пару столбцов и диагональные пары (если на диагоналях). Если какая-либо новая обновленная строка, столбец или диагональ равна либо (n,0) либо (0,n) то либо A, либо B выиграли соответственно.

Асимптотический анализ:

 O (1) время (за ход)
 O (n) пространство (общее)

Для использования памяти вы используете целые числа 4*(n+1) .

 two_elements * n_rows + two_elements * n_columns +
 two_elements * two_diagonals = 4 * n + 4 integers = 4 (n + 1) целые числа

Упражнение: Можете ли вы проверить, как тестировать ничью в течение O (1) за ход? Если это так, вы можете закончить игру на ранней стадии ничьей.

Как насчет этого псевдокода:

После того как игрок кладет кусок в позицию (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 

Я бы использовал массив char [n, n], с O, X и пробелом для пустого.

  1. просто.
  2. Один цикл.
  3. Пять простых переменных: 4 целых числа и один булев.
  4. Весы до любого размера n.
  5. Проверяет только текущую деталь.
  6. Никакой магии. 🙂

Вот мое решение, которое я написал для проекта, над которым я работаю в javascript. Если вы не против стоимости памяти нескольких массивов, это, вероятно, самое быстрое и простое решение, которое вы найдете. Предполагается, что вы знаете позицию последнего хода.

 /* * 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; } 

Я просто написал это для своего classа программирования C.

Я размещаю его, потому что ни один из других примеров здесь не будет работать с прямоугольной сеткой любого размера, и любое число N -in-рядных последовательных марок для победы.

Вы найдете мой алгоритм, например, в функции checkWinner() . Он не использует магические числа или что-то интересное для проверки победителя, он просто использует четыре для циклов. Код хорошо прокомментирован, поэтому я позволю ему говорить сам по себе, я думаю.

 // 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. 

Если плата равна n × n, то существует n строк, n столбцов и 2 диагоналя. Проверьте каждый из них для all-X или all-O, чтобы найти победителя.

Если для победы требуется только x < n последовательных квадратов, то это немного сложнее. Наиболее очевидным решением является проверка каждого квадрата x × x для победителя. Вот какой код, который демонстрирует это.

(Я действительно не проверял этот * кашель *, но он скомпилировался с первой попытки, yay me!)

 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; } } } 

Я не очень хорошо знаю Java, но я знаю C, поэтому я попробовал магическую квадратную идею adk (наряду с ограничением поиска Hardwareguy ).

 // tic-tac-toe.c // to compile: // % 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; } 

Он хорошо компилируется и тестируется.

 % gcc -o tic-tac-toe tic-tac-toe.c
 % ./крестики-нолики
      |  |
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   Введите ходы как «" (без кавычек, с нулевой индексацией)
   Ход X: 1 2
      |  |
   --- + --- + ---
      |  |  Икс
   --- + --- + ---
      |  |
   Движение O: 1 2
   незаконный ход (уже принят), повторите попытку
   Движение О: 3 3
   незаконный ход (с доски), повторите попытку
   Переезд О: 2 2
      |  |
   --- + --- + ---
      |  |  Икс
   --- + --- + ---
      |  |  О
   Ход X: 1 0
      |  |
   --- + --- + ---
    X |  |  Икс
   --- + --- + ---
      |  |  О
   Движение O: 1 1
      |  |
   --- + --- + ---
    X |  O |  Икс
   --- + --- + ---
      |  |  О
   Ход X: 0 0
    X |  |
   --- + --- + ---
    X |  O |  Икс
   --- + --- + ---
      |  |  О
   O: 2 0
    X |  |
   --- + --- + ---
    X |  O |  Икс
   --- + --- + ---
    O |  |  О
   Ход X: 2 1
    X |  |
   --- + --- + ---
    X |  O |  Икс
   --- + --- + ---
    O |  X |  О
   Движение O: 0 2
    X |  |  О
   --- + --- + ---
    X |  O |  Икс
   --- + --- + ---
    O |  X |  О
   крестики-нолики!  О побеждает!
 % ./крестики-нолики
      |  |
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   Введите ходы как «" (без кавычек, с нулевой индексацией)
   Ход X: 0 0
    X |  |
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   Движение O: 0 1
    X |  O |
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   Ход X: 0 2
    X |  O |  Икс
   --- + --- + ---
      |  |
   --- + --- + ---
      |  |
   О: 1 0
    X |  O |  Икс
   --- + --- + ---
    O |  |
   --- + --- + ---
      |  |
   Ход X: 1 1
    X |  O |  Икс
   --- + --- + ---
    O |  X |
   --- + --- + ---
      |  |
   O: 2 0
    X |  O |  Икс
   --- + --- + ---
    O |  X |
   --- + --- + ---
    O |  |
   Ход X: 2 1
    X |  O |  Икс
   --- + --- + ---
    O |  X |
   --- + --- + ---
    O |  X |
   Переезд О: 2 2
    X |  O |  Икс
   --- + --- + ---
    O |  X |
   --- + --- + ---
    O |  X |  О
   Ход X: 1 2
    X |  O |  Икс
   --- + --- + ---
    O |  X |  Икс
   --- + --- + ---
    O |  X |  О
   stalemate ... никто не выигрывает :(
 %

Это было весело, спасибо!

Собственно, думая об этом, вам не нужен волшебный квадрат, просто счет для каждой строки / столбца / диагонали. Это немного проще, чем обобщение магического квадрата на n × n матриц, так как вам просто нужно подсчитать до n .

Мне задали один и тот же вопрос в одном из моих интервью. Мои мысли: Инициализировать матрицу с 0. Держите 3 массива 1) sum_row (размер n) 2) sum_column (размер n) 3) диагональ (размер 2)

Для каждого перемещения по (X) уменьшите значение поля на 1 и для каждого перемещения по (0) добавьте его на 1. В любой точке, если строка / столбца / диагональ, которая была изменена в текущем движении, имеет сумму либо -3, либо + 3 означает, что кто-то выиграл игру. Для ничьей мы можем использовать вышеприведенный подход, чтобы сохранить переменную moveCount.

Как вы думаете, я что-то упускаю?

Изменить. То же самое можно использовать для матрицы nxn. Сумма должна быть равна +3 или -3.

метод без петли, чтобы определить, была ли точка на антидиапазоне:

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

Я сделал некоторую оптимизацию в строке, col, диагональные проверки. Его главным образом решили в первом вложенном цикле, если нам нужно проверить конкретный столбец или диагональ. Таким образом, мы избегаем проверки столбцов или диагоналей, экономящих время. Это имеет большое значение, когда размер платы больше, и значительное количество ячеек не заполнено.

Вот код Java для этого.

  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; } 

Я опаздываю на вечеринку, но я хотел указать на одно преимущество, которое я нашел, используя магический квадрат , а именно, что его можно использовать для получения ссылки на квадрат, который приведет к победе или проигрышу на следующем ходу, а не просто используется для расчета, когда игра окончена.

Возьмите этот волшебный квадрат:

 4 9 2 3 5 7 8 1 6 

Сначала настройте массив scores который увеличивается каждый раз, когда выполняется перемещение. Подробнее см. В этом ответе . Теперь, если мы незаконно проигрываем X дважды подряд в [0,0] и [0,1], то массив scores выглядит следующим образом:

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

И панель выглядит так:

 X . . X . . . . . 

Затем все, что нам нужно сделать, чтобы получить ссылку на квадрат, чтобы выиграть / заблокировать:

 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 } } } 

В действительности реализация требует нескольких дополнительных трюков, таких как обработка пронумерованных ключей (в JavaScript), но я нашел это довольно простым и наслаждался рекреационной математикой.

Мне нравится этот алгоритм, поскольку он использует представление 1×9 против 3×3 платы.

 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; } 

Другой вариант: создать таблицу с кодом. До симметрии можно выиграть только три способа: крайний ряд, средний ряд или диагональ. Возьмите этих троих и покрутите их всеми возможными способами:

 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)))) 

Эти симметрии могут иметь больше использования в вашем игровом коде: если вы попадете на доску, на которой вы уже видели повернутую версию, вы можете просто взять кешированное значение или кэшировать лучший переход от этого (и отменить его обратно). Это обычно намного быстрее, чем оценка поддерева игры.

(Отражение влево и вправо может помочь так же, здесь оно не понадобилось, потому что набор поворотов выигрышных шаблонов зеркально-симметричный.)

Вот решение, которое я придумал, оно хранит символы как символы и использует значение int char, чтобы выяснить, выиграл ли X или O (посмотрите на код Рефери)

 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; } } } 

Также здесь мои модульные тесты, чтобы проверить его на самом деле работает

 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 matrix (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

  • как обеспечить функцию подкачки для моего classа?
  • Хороший и универсальный способ преобразования списка элементов в дерево
  • Хороший метод GetHashCode () для объектов списка Foo, соответствующих порядку
  • Поиск максимума для каждого windows размера k в массиве
  • Переупорядочение элементов массива
  • Как определить BPM песни в php
  • Как рассчитать угол из трех точек?
  • Как работает алгоритм HyperLogLog?
  • Создание всех перестановок заданной строки
  • Получение фактической длины кодированной std :: string UTF-8?
  • Распечатайте самые большие K-элементы в заданной куче в O (K * log (K))?
  • Давайте будем гением компьютера.