确定Tic Tac Toe游戏结束的algorithm
我用Java编写了一个井字棋的游戏，而我目前确定游戏结束的方法解释了游戏结束时的以下可能的场景：
- 董事会已经满员，还没有赢家宣布：比赛是平局。
- 克罗斯赢了。
- 圈子赢了。
不幸的是，为了做到这一点，它从表中读取了一组预定义的场景。 考虑到棋盘上只有9个空格，所以这不一定是不好的，因此桌子有点小，但是有更好的algorithm来判断游戏是否结束？ 确定是否有人获胜是问题的核心，因为检查9个空间是否满是微不足道的。
表格方法可能是解决scheme，但如果没有，是什么？ 另外，如果董事会不是大小n=9 ？ 如果是一个更大的棋盘，比如说n=16 ， n=25等等，那么连续放置棋子的数量是x=4 ， x=5等等。 用于所有n = { 9, 16, 25, 36 ... }通用algorithm？
只有在X或O进行了最后一次移动后，才会发生胜出动作，因此您只能使用包含在该移动中的可选诊断的行/列进行search，以在尝试确定获胜的棋盘时限制search空间。 此外，由于如果不是获胜的移动，在最后一步移动时在抽取井字游戏中有一定数量的移动，所以它默认为抽签游戏。
编辑：这个代码是一个n的n板连赢（3×3板连续3等）
编辑：添加代码来检查anti diag，我找不到一个非循环的方式来确定点是否在反diag，这就是为什么这一步是失踪
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 == (n^2 - 1)){ //report draw } } }
如果任何行，列或诊断加起来为15，那么你可以使用魔术方块http://mathworld.wolfram.com/MagicSquare.html ，然后玩家赢了。
这与Osama ALASSIRY的答案类似，但它为线性空间和恒定时间交易恒定空间和线性时间。 也就是说，初始化后没有循环。
为每行，每列和两个对angular线（对angular线和反对angular线）初始化一对(0,0) ）。 这些对表示对应的行，列或对angular线中的块的累积(sum,sum) ，其中
玩家A的一块有价值（1,0） 玩家B的棋子有值（0,1）
当玩家放置棋子时，更新相应的行对，列对和对angular线对（如果在对angular线上）。 如果任何新更新的行，列或对angular线对等于(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整数= 4（n + 1）个整数
练习：你能看到如何在O（1）每次移动的时间testing平局吗？ 如果是这样，你可以提前结束游戏。
这个伪代码如何：
玩家在位置（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和空格为空。
- 简单。
- 一个循环。
- 五个简单的variables：4个整数和一个布尔值。
- 可以缩放到任何大小的n。
- 只检查当前件。
- 没有魔法。 🙂
下面是我为JavaScript编写的一个项目的解决scheme。 如果您不介意几个arrays的内存成本，那么这可能是您find的最快最简单的解决scheme。 它假定你知道最后一步的位置。
/* * 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; }
我刚刚为我的C编程类写了这个。
我张贴它，因为这里没有其他的例子将使用任何大小的矩形网格，并在任何数量的N在一个连续的行赢得胜利。
你可以在checkWinner()函数中find我的algorithm，比如它。 它不会使用幻数或任何幻想来检查赢家，它只是使用四个for循环 – 代码是很好的评论，所以我会让它为我自己说话。
// 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 <stdio.h> #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;row++) { for (col=0;col<COLS;col++) { gameBoard[row][col] = INITCHAR; // Fill the gameBoard with INITCHAR characters } } printBoard(gameBoard); // Having this here prints out the board before return; // the playGame function asks for the first move } void printBoard (char gameBoard[ROWS][COLS]) // There is a ton of formatting in here { // That I don't feel like commenting :P int row = 0, col = 0, i=0; // It took a while to fine tune // But now the output is something like: printf("\n"); // // 1 2 3 for (row=0;row<ROWS;row++) // 1 | | { // ----------- if (row == 0) // 2 | | { // ----------- printf(" "); // 3 | | for (i=0;i<COLS;i++) { printf(" %i ",i+1); } printf("\n\n"); } for (col=0;col<COLS;col++) { if (col==0) printf("%i ",row+1); printf(" %c ",gameBoard[row][col]); if (col<COLS-1) printf("|"); } printf("\n"); if (row < ROWS-1) { for(i=0;i<COLS-1;i++) { if(i==0) printf(" ----"); else printf("----"); } printf("---\n"); } } return; } void makeMove (char gameBoard[ROWS][COLS],int player) { int row = 0, col = 0, i=0; char currentChar; if (player == 1) // This gets the correct player's mark currentChar = PLAYER1CHAR; else currentChar = PLAYER2CHAR; for (i=0;i<21-2*ROWS;i++) // Newline formatting again :-( printf("\n"); printf("\nPlayer %i, please enter the column of your move: ",player); scanf("%i",&col); printf("Please enter the row of your move: "); scanf("%i",&row); row--; // These lines translate the user's rows and columns numbering col--; // (starting with 1) to the computer's (starting with 0) while(gameBoard[row][col] != INITCHAR || 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个对angular线。 检查所有的X或所有O的每一个find一个胜利者。
如果只需要x < n个连续的方格就可以获胜，那就更复杂了。 最明显的解决scheme是检查每个x × x方块赢家。 这是一些演示的代码。
（我没有真正testing这个*咳嗽*，但它确实编译了第一次尝试，耶！
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的search限制 ）。
// tic-tac-toe.c // to compile: // % gcc -o tic-tac-toe tic-tac-toe.c // to run: // % ./tic-tac-toe #include <stdio.h> // 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 \"<row> <col>\" (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; }
它编译和testing好。
％gcc -o tic-tac-toe tic-tac-toe.c
％./tic-tac-toe
| |
--- + --- + ---
| |
--- + --- + ---
| |
input移动为“”（不包括引号，零索引）
X的举动：1 2
| |
--- + --- + ---
| | X
--- + --- + ---
| |
O的举动：1 2
非法动作（已经采取），再试一次
O的举动：3 3
非法移动（closures），再试一次
O的举动：2 2
| |
--- + --- + ---
| | X
--- + --- + ---
| | Ø
X的举动：1 0
| |
--- + --- + ---
X | | X
--- + --- + ---
| | Ø
O的举动：1 1
| |
--- + --- + ---
X | O | X
--- + --- + ---
| | Ø
X的举动：0 0
X | |
--- + --- + ---
X | O | X
--- + --- + ---
| | Ø
O的举动：2 0
X | |
--- + --- + ---
X | O | X
--- + --- + ---
O | | Ø
X的举动：2 1
X | |
--- + --- + ---
X | O | X
--- + --- + ---
O | X | Ø
O的举动：0 2
X | | Ø
--- + --- + ---
X | O | X
--- + --- + ---
O | X | Ø
井字棋！ 哦胜！
％./tic-tac-toe
| |
--- + --- + ---
| |
--- + --- + ---
| |
input移动为“”（不包括引号，零索引）
X的举动：0 0
X | |
--- + --- + ---
| |
--- + --- + ---
| |
O的举动：0 1
X | O |
--- + --- + ---
| |
--- + --- + ---
| |
X的举动：0 2
X | O | X
--- + --- + ---
| |
--- + --- + ---
| |
O的举动：1 0
X | O | X
--- + --- + ---
O | |
--- + --- + ---
| |
X的举动：1 1
X | O | X
--- + --- + ---
O | X |
--- + --- + ---
| |
O的举动：2 0
X | O | X
--- + --- + ---
O | X |
--- + --- + ---
O | |
X的举动：2 1
X | O | X
--- + --- + ---
O | X |
--- + --- + ---
O | X |
O的举动：2 2
X | O | X
--- + --- + ---
O | X |
--- + --- + ---
O | X | Ø
X的举动：1 2
X | O | X
--- + --- + ---
O | X | X
--- + --- + ---
O | X | Ø
僵持...没有人赢得:(
％
这很有趣，谢谢！
其实，考虑一下，你不需要一个神奇的方块，只需要每行/一列/对angular线的计数。 这比简单地把一个幻方变成n × nmatrix容易一些，因为你只需要计算n 。
在我的一次采访中，我被问到了同样的问题。 我的想法：用0初始化matrix。保留3个数组1）sum_row（size n）2）sum_column（size n）3）对angular线（size 2）
对于（X）的每一个移动，将盒子值减1，对于每一个移动，（0）将其增加1.在任何点，如果在当前移动中修改过的行/列/对angular线的和为-3或+ 3意味着有人赢得了比赛。 对于平局，我们可以使用上面的方法来保持moveCountvariables。
你觉得我错过了什么吗？
编辑：同样可以用于nxnmatrix。 总和应该是+3或-3。
一个非循环的方式来确定点是否在反diag：
`if (x + y == n - 1)`
我在行，对angular线检查中做了一些优化。 它主要决定于第一个嵌套循环中，如果我们需要检查一个特定的列或对angular线。 所以，我们避免检查列或对angular线节省时间。 当电路板尺寸更大并且没有填充大量的单元时，这会产生很大的影响。
这是这个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数组。 看到这个答案的细节。 现在，如果我们在[0,0]和[0,1]连续两次非法地播放X，那么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中），但是我发现它很简单，并且享受了娱乐math。
我喜欢这个algorithm，因为它使用了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; }
另一种select：用代码生成你的表。 直到对称，只有三种方式可以获胜：边缘排，中间排或对angular线。 采取这三个，并尽可能地旋转他们：
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))))
这些对称性可以在你的游戏代码中有更多的用处：如果你看到一个你已经看过旋转版本的板子，你可以把caching的值或者caching的最好的值移到那个值上（然后把它移回去）。 这通常比评估游戏子树快得多。
（左右翻转可以同样的方式进行;这里没有必要，因为获胜模式的旋转是镜像对称的）。
这是我提出的解决scheme，它将符号存储为字符，并使用char的int值来确定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; } } }
另外这里是我的unit testing来validation它实际工作
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 <SIZE-1 ; j++) { //vertical checking if (map[0][j] == symb && map[1][j] == symb && map[2][j] == symb && map[3][j] == symb && map[4][j] == symb) return true; // j=0 } //horisontal checking if(map[i][0] == symb && map[i][1] == symb && map[i][2] == symb && map[i][3] == symb && map[i][4] == symb) return true; // i=0 } //diagonal checking (5*5) if (map[0][0] == symb && map[1][1] == symb && map[2][2] == symb && map[3][3] == symb && map[4][4] == symb) return true; if (map[4][0] == symb && map[3][1] == symb && map[2][2] == symb && map[1][3] == symb && map[0][4] == symb) return true; return false; }
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
