确定井字游戏结束的算法

you can use a magic square http://mathworld.wolfram.com/MagicSquare.html if any row, column, or diag adds up to 15 then a player has won.

如果黑板是 N & times; N，那么就有 N行，N列和2条对角线。检查这些全 X 或全 O 的每一个，以找到一个赢家。

如果只需要 X < N的连续平方就可以获胜，那就有点复杂了。最明显的解决方案是检查每个 X & 乘以; X正方形为一个赢家。下面的代码演示了这一点。

(实际上我并没有测试这个 * cough * ，但是它在第一次尝试时就进行了 是的编译，太棒了!)

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

你知道一个成功的移动只能发生在 X 或 O 最近的移动，所以你只能搜索行/列与可选的对话框包含在该移动，以限制您的搜索空间时，试图确定一个成功的棋盘。此外，因为在一个抽签井字游戏中有一个固定的步数，一旦最后一步是作出的，如果它不是一个获胜的举动，它的默认平局游戏。

This code is for an n by n board with n in a row to win (3x3 board requires 3 in a row, etc)

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

I don't know Java that well, but I do know C, so I tried Adk 的魔方主意 (along with 硬件工人的搜索限制).

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

它编译和测试都很好。

% gcc -o tic-tac-toe tic-tac-toe.c
% ./tic-tac-toe
|   |
---+---+---
|   |
---+---+---
|   |
Enter moves as " " (no quotes, zero indexed)
X's move: 1 2
|   |
---+---+---
|   | X
---+---+---
|   |
O's move: 1 2
illegal move (already taken), try again
O's move: 3 3
illegal move (off the board), try again
O's move: 2 2
|   |
---+---+---
|   | X
---+---+---
|   | O
X's move: 1 0
|   |
---+---+---
X |   | X
---+---+---
|   | O
O's move: 1 1
|   |
---+---+---
X | O | X
---+---+---
|   | O
X's move: 0 0
X |   |
---+---+---
X | O | X
---+---+---
|   | O
O's move: 2 0
X |   |
---+---+---
X | O | X
---+---+---
O |   | O
X's move: 2 1
X |   |
---+---+---
X | O | X
---+---+---
O | X | O
O's move: 0 2
X |   | O
---+---+---
X | O | X
---+---+---
O | X | O
tic-tac-toe! O wins!
% ./tic-tac-toe
|   |
---+---+---
|   |
---+---+---
|   |
Enter moves as " " (no quotes, zero indexed)
X's move: 0 0
X |   |
---+---+---
|   |
---+---+---
|   |
O's move: 0 1
X | O |
---+---+---
|   |
---+---+---
|   |
X's move: 0 2
X | O | X
---+---+---
|   |
---+---+---
|   |
O's move: 1 0
X | O | X
---+---+---
O |   |
---+---+---
|   |
X's move: 1 1
X | O | X
---+---+---
O | X |
---+---+---
|   |
O's move: 2 0
X | O | X
---+---+---
O | X |
---+---+---
O |   |
X's move: 2 1
X | O | X
---+---+---
O | X |
---+---+---
O | X |
O's move: 2 2
X | O | X
---+---+---
O | X |
---+---+---
O | X | O
X's move: 1 2
X | O | X
---+---+---
O | X | X
---+---+---
O | X | O
stalemate... nobody wins :(
%

很有趣，谢谢！

实际上，仔细想想，你并不需要一个神奇的正方形，只需要对每一行/每一列/每一条对角线进行计数。这比将一个幻方泛化为 n & times; n矩阵要容易一些，因为您只需要计数到 n。

这个伪代码怎么样:

当一个玩家在位置(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. Five simple variables: 4 integers and one boolean.
4. 任意大小的 n 的刻度。
5. 只检查当前的一块。
6. No magic. :)

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

你基本上是递归地将棋盘划分成一组重叠的2x2矩形，测试在2x2正方形上获胜的不同可能的组合。

它的速度很慢，但它的优点是可以在任何大小的板上工作，并且具有相当的线性内存需求。

我希望我能找到我的实现

这类似于 奥萨马 · 阿拉西里的回答，但是它将恒定空间和线性时间换成了线性空间和恒定时间。也就是说，在初始化之后没有循环。

为每一行、每一列和两条对角线(对角线和反对角线)初始化一对 (0,0)。这些对表示相应行、列或对角线中的片段的累积 (sum,sum)，其中

A piece from player A has value (1,0)
A piece from player B has value (0,1)

当玩家放置棋子时，更新相应的行对、列对和对角线对(如果在对角线上)。如果任何新更新的行、列或对角线对等于 (n,0)或 (0,n)，则 A 或 B 分别获胜。

Asymptotic analysis:

O(1) time (per move)
O(n) space (overall)

对于内存使用，可以使用 4*(n+1)整数。

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

练习: 你能看到如何测试每次移动 O (1)时间内的平局吗？如果是这样，你可以在平局时提前结束比赛。

判断点是否在反斜线上的非循环方法:

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

我刚为我的 C 编程课写了这个。

我发布它，因为没有其他的例子在这里将工作与任何大小的 长方形网格，任何数字 N在一行连续标记的胜利。

您可以在 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 <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.

我做了一些优化，在行，领口，对角线检查。它主要决定在第一个嵌套循环，如果我们需要检查一个特定的列或对角线。因此，我们避免检查列或对角线节省时间。当板子大小较大且有相当数量的单元格没有填充时，这会产生很大的影响。

Here is the java code for that.

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

另一种选择: 使用代码生成表。到对称性，只有三种方法可以获胜: 边行，中间行，或对角线。拿着这三个，把它们旋转起来:

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

这些对称性在你的游戏代码中可以有更多的用途: 如果你到达一个你已经看到了一个旋转版本的棋盘，你可以直接从那个棋盘中取出缓存的值或者缓存的最佳移动(然后取消旋转)。这通常比评估游戏子树要快得多。

(向左和向右翻转也可以起到同样的作用; 这里不需要这样做，因为获胜模式的旋转集是镜像对称的。)

这是我想到的一个解决方案，它将符号存储为 char，并使用 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;
}
}
}

这里也是我的单元测试，以验证它实际上工作

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

完整解决方案: https://github.com/nashjain/tictactoe/tree/master/java

How about a following approach for 9 slots? Declare 9 integer variables for a 3x3 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.

有8种可能的胜利组合: 获胜-1: a1 + a2 + a3(答案可能是3或6基于哪个玩家获胜) 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.

我迟到了，但是我想指出我发现使用 魔方的一个好处，那就是它可以用来得到下一个回合的胜负方的参考，而不仅仅是用来计算比赛什么时候结束。

拿这个神奇的方块来说:

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 中) ，但是我发现它非常简单，并且非常享受这种娱乐性的数学运算。

这里是我的解决方案，我写的一个项目，我的工作在 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;
}

我在一次采访中也被问到同样的问题。 我的想法是: Initialize the matrix with 0. 保留3个数组 1) sum _ row (size n) 2) sum _ column (size n) 3)对角线(尺寸2)

对于(X)移动的每一步，盒子值减1，对于(0)移动的每一步，盒子值增1。 在任何时候，如果在当前移动中被修改的行/列/对角线的和或者 -3或者 + 3意味着有人赢得了比赛。 For a draw we can use above approach to keep the moveCount variable.

Do you think I am missing something ?

Edit: Same can be used for nxn matrix. Sum should be even +3 or -3.

我喜欢这个算法，因为它使用了1x9对3x3的董事会表示。

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

常数时间解，在 O (8)中运行。

将电路板的状态存储为二进制数。最小的位(2 ^ 0)是黑板的左上行。然后向右，然后向下。

也就是说。

+-----------------+
| 2^0 | 2^1 | 2^2 |
|-----------------|
| 2^3 | 2^4 | 2^5 |
|-----------------|
| 2^6 | 2^7 | 2^8 |
+-----------------+

每个玩家都有自己的二进制数来表示状态(因为井字游戏)有3个状态(X，O 和空白) ，所以一个二进制数不能代表多个玩家的棋盘状态。

例如:

+-----------+
| X | O | X |
|-----------|
| O | X |   |
|-----------|
|   | O |   |
+-----------+


0 1 2 3 4 5 6 7 8
X: 1 0 1 0 1 0 0 0 0
O: 0 1 0 1 0 0 0 1 0

注意，玩家 X 的比特和玩家 O 的比特是不相交的，这很明显，因为 X 不能把一个棋子放在 O 有一个棋子的地方，反之亦然。

To check whether a player has won, we need to compare all the positions covered by that player to a position we know is a win-position. In this case, the easiest way to do that would be by AND-gating the player-position and the win-position and seeing if the two are equal.

boolean isWinner(short X) {
for (int i = 0; i < 8; i++)
if ((X & winCombinations[i]) == winCombinations[i])
return true;
return false;
}

例如。

X: 111001010
W: 111000000 // win position, all same across first row.
------------
&: 111000000

注意: X & W = W，因此 X 处于胜利状态。

This is a constant time solution, it depends only on the number of win-positions, because applying AND-gate is a constant time operation and the number of win-positions is finite.

It also simplifies the task of enumerating all valid board states, their just all the numbers representable by 9 bits. But of course you need an extra condition to guarantee a number is a valid board state (eg. 0b111111111 is a valid 9-bit number, but it isn't a valid board state because X has just taken all the turns).

可能获胜的位置的数量可以产生的飞行，但在这里，他们是无论如何。

short[] winCombinations = new short[] {
// each row
0b000000111,
0b000111000,
0b111000000,
// each column
0b100100100,
0b010010010,
0b001001001,
// each diagonal
0b100010001,
0b001010100
};

若要枚举所有棋盘位置，可以运行以下循环。尽管我将把确定一个数字是否是一个有效的董事会状态留给其他人。

注意: (2 * * 9-1) = (2 * * 8) + (2 * * 7) + (2 * * 6) + ... (2 * * 1) + (2 * * 0)

for (short X = 0; X < (Math.pow(2,9) - 1); X++)
System.out.println(isWinner(X));

这是一个非常简单的检查方法。

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

}

例如，如果你有边界字段5 * 5，我使用下一种检查方法:

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

我认为，这是更清楚的，但可能不是最理想的方式。

下面是我使用二维数组的解决方案:

private static final int dimension = 3;
private static final int[][] board = new int[dimension][dimension];
private static final int xwins = dimension * 1;
private static final int owins = dimension * -1;


public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int count = 0;
boolean keepPlaying = true;
boolean xsTurn = true;
while (keepPlaying) {
xsTurn = (count % 2 == 0);
System.out.print("Enter i-j in the format:");
if (xsTurn) {
System.out.println(" X plays: ");
} else {
System.out.println(" O plays: ");
}
String result = null;
while (result == null) {
result = parseInput(scanner, xsTurn);
}
String[] xy = result.split(",");
int x = Integer.parseInt(xy[0]);
int y = Integer.parseInt(xy[1]);
keepPlaying = makeMove(xsTurn, x, y);
count++;
}
if (xsTurn) {
System.out.print("X");
} else {
System.out.print("O");
}
System.out.println(" WON");
printArrayBoard(board);
}


private static String parseInput(Scanner scanner, boolean xsTurn) {
String line = scanner.nextLine();
String[] values = line.split("-");
int x = Integer.parseInt(values[0]);
int y = Integer.parseInt(values[1]);
boolean alreadyPlayed = alreadyPlayed(x, y);
String result = null;
if (alreadyPlayed) {
System.out.println("Already played in this x-y. Retry");
} else {
result = "" + x + "," + y;
}
return result;
}


private static boolean alreadyPlayed(int x, int y) {
System.out.println("x-y: " + x + "-" + y + " board[x][y]: " + board[x][y]);
if (board[x][y] != 0) {
return true;
}
return false;
}


private static void printArrayBoard(int[][] board) {
for (int i = 0; i < dimension; i++) {
int[] height = board[i];
for (int j = 0; j < dimension; j++) {
System.out.print(height[j] + " ");
}
System.out.println();
}
}


private static boolean makeMove(boolean xo, int x, int y) {
if (xo) {
board[x][y] = 1;
} else {
board[x][y] = -1;
}
boolean didWin = checkBoard();
if (didWin) {
System.out.println("keep playing");
}
return didWin;
}


private static boolean checkBoard() {
//check horizontal
int[] horizontalTotal = new int[dimension];
for (int i = 0; i < dimension; i++) {
int[] height = board[i];
int total = 0;
for (int j = 0; j < dimension; j++) {
total += height[j];
}
horizontalTotal[i] = total;
}
for (int a = 0; a < horizontalTotal.length; a++) {
if (horizontalTotal[a] == xwins || horizontalTotal[a] == owins) {
System.out.println("horizontal");
return false;
}
}
//check vertical
int[] verticalTotal = new int[dimension];


for (int j = 0; j < dimension; j++) {
int total = 0;
for (int i = 0; i < dimension; i++) {
total += board[i][j];
}
verticalTotal[j] = total;
}
for (int a = 0; a < verticalTotal.length; a++) {
if (verticalTotal[a] == xwins || verticalTotal[a] == owins) {
System.out.println("vertical");
return false;
}
}
//check diagonal
int total1 = 0;
int total2 = 0;
for (int i = 0; i < dimension; i++) {
for (int j = 0; j < dimension; j++) {
if (i == j) {
total1 += board[i][j];
}
if (i == (dimension - 1 - j)) {
total2 += board[i][j];
}
}
}
if (total1 == xwins || total1 == owins) {
System.out.println("diagonal 1");
return false;
}
if (total2 == xwins || total2 == owins) {
System.out.println("diagonal 2");
return false;
}
return true;
}

不确定这种方法是否已经发布。这应该工作的任何 m * n 董事会和球员应该填补“ 冠军 Pos”连续的立场。这个想法是基于运行窗口。

private boolean validateWinner(int x, int y, int player) {
//same col
int low = x-winnerPos-1;
int high = low;
while(high <= x+winnerPos-1) {
if(isValidPos(high, y) && isFilledPos(high, y, player)) {
high++;
if(high - low == winnerPos) {
return true;
}
} else {
low = high + 1;
high = low;
}
}


//same row
low = y-winnerPos-1;
high = low;
while(high <= y+winnerPos-1) {
if(isValidPos(x, high) && isFilledPos(x, high, player)) {
high++;
if(high - low == winnerPos) {
return true;
}
} else {
low = high + 1;
high = low;
}
}
if(high - low == winnerPos) {
return true;
}


//diagonal 1
int lowY = y-winnerPos-1;
int highY = lowY;
int lowX = x-winnerPos-1;
int highX = lowX;
while(highX <= x+winnerPos-1 && highY <= y+winnerPos-1) {
if(isValidPos(highX, highY) && isFilledPos(highX, highY, player)) {
highX++;
highY++;
if(highX - lowX == winnerPos) {
return true;
}
} else {
lowX = highX + 1;
lowY = highY + 1;
highX = lowX;
highY = lowY;
}
}


//diagonal 2
lowY = y+winnerPos-1;
highY = lowY;
lowX = x-winnerPos+1;
highX = lowX;
while(highX <= x+winnerPos-1 && highY <= y+winnerPos-1) {
if(isValidPos(highX, highY) && isFilledPos(highX, highY, player)) {
highX++;
highY--;
if(highX - lowX == winnerPos) {
return true;
}
} else {
lowX = highX + 1;
lowY = highY + 1;
highX = lowX;
highY = lowY;
}
}
if(highX - lowX == winnerPos) {
return true;
}
return false;
}


private boolean isValidPos(int x, int y) {
return x >= 0 && x < row && y >= 0 && y< col;
}
public boolean isFilledPos(int x, int y, int p) throws IndexOutOfBoundsException {
return arena[x][y] == p;
}

我只是想分享我在 Javascript 中做的事情。我的想法是有搜索方向; 在网格中它可以是8个方向，但搜索应该是双向的，所以8/2 = 4个方向。当玩家移动时，搜索从位置开始。它搜索4个不同的双向，直到它的价值不同于球员的石头(O 或 X)。

每个双向搜索，可以添加两个值，但需要减去一个，因为起始点是重复的。

getWin(x,y,value,searchvector) {
if (arguments.length==2) {
var checkTurn = this.state.squares[y][x];
var searchdirections = [[-1,-1],[0,-1],[1,-1],[-1,0]];
return searchdirections.reduce((maxinrow,searchdirection)=>Math.max(this.getWin(x,y,checkTurn,searchdirection)+this.getWin(x,y,checkTurn,[-searchdirection[0],-searchdirection[1]]),maxinrow),0);
} else {
if (this.state.squares[y][x]===value) {
var result = 1;
if (
x+searchvector[0] >= 0 && x+searchvector[0] < 3 &&
y+searchvector[1] >= 0 && y+searchvector[1] < 3
) result += this.getWin(x+searchvector[0],y+searchvector[1],value,searchvector);
return result;
} else {
return 0;
}
}

}

This function can be used with two parameters (x,y), which are coordinates of the last move. In initial execution, it calls four bi-direction searches recursively with 4 parameters. All results are returned as lengths and the function finally picks the maximum length among 4 search bi-directions.

class Square extends React.Component {
constructor(props) {
super(props);
this.state = {value:null};
}
render() {
return (
<button className="square" onClick={() => this.props.onClick()}>
{this.props.value}
</button>
);
}
}


class Board extends React.Component {
renderSquare(x,y) {
return <Square value={this.state.squares[y][x]} onClick={() => this.handleClick(x,y)} />;
}
handleClick(x,y) {
const squares = JSON.parse(JSON.stringify(this.state.squares));
if (!squares[y][x] && !this.state.winner) {
squares[y][x] = this.setTurn();
this.setState({squares: squares},()=>{
console.log(`Max in a row made by last move(${squares[y][x]}): ${this.getWin(x,y)-1}`);
if (this.getWin(x,y)==4) this.setState({winner:squares[y][x]});
});
}
}
setTurn() {
var prevTurn = this.state.turn;
this.setState({turn:prevTurn == 'X' ? 'O':'X'});
return prevTurn;
}
  

getWin(x,y,value,searchvector) {
if (arguments.length==2) {
var checkTurn = this.state.squares[y][x];
var searchdirections = [[-1,-1],[0,-1],[1,-1],[-1,0]];
return searchdirections.reduce((maxinrow,searchdirection)=>Math.max(this.getWin(x,y,checkTurn,searchdirection)+this.getWin(x,y,checkTurn,[-searchdirection[0],-searchdirection[1]]),maxinrow),0);
} else {
if (this.state.squares[y][x]===value) {
var result = 1;
if (
x+searchvector[0] >= 0 && x+searchvector[0] < 3 &&
y+searchvector[1] >= 0 && y+searchvector[1] < 3
) result += this.getWin(x+searchvector[0],y+searchvector[1],value,searchvector);
return result;
} else {
return 0;
}
}
}
  

constructor(props) {
super(props);
this.state = {
squares: Array(3).fill(Array(3).fill(null)),
turn: 'X',
winner: null
};
}
render() {
const status = !this.state.winner?`Next player: ${this.state.turn}`:`${this.state.winner} won!`;


return (
<div>
<div className="status">{status}</div>
<div className="board-row">
{this.renderSquare(0,0)}
{this.renderSquare(0,1)}
{this.renderSquare(0,2)}
</div>
<div className="board-row">
{this.renderSquare(1,0)}
{this.renderSquare(1,1)}
{this.renderSquare(1,2)}
</div>
<div className="board-row">
{this.renderSquare(2,0)}
{this.renderSquare(2,1)}
{this.renderSquare(2,2)}
</div>
</div>
);
}
}


class Game extends React.Component {
render() {
return (
<div className="game">
<div className="game-board">
<Board />
</div>
<div className="game-info">
<div>{/* status */}</div>
<ol>{/* TODO */}</ol>
</div>
</div>
);
}
}


// ========================================


ReactDOM.render(
<Game />,
document.getElementById('root')
);

body {
font: 14px "Century Gothic", Futura, sans-serif;
margin: 20px;
}


ol, ul {
padding-left: 30px;
}


.board-row:after {
clear: both;
content: "";
display: table;
}


.status {
margin-bottom: 10px;
}


.square {
background: #fff;
border: 1px solid #999;
float: left;
font-size: 24px;
font-weight: bold;
line-height: 34px;
height: 34px;
margin-right: -1px;
margin-top: -1px;
padding: 0;
text-align: center;
width: 34px;
}


.square:focus {
outline: none;
}


.kbd-navigation .square:focus {
background: #ddd;
}


.game {
display: flex;
flex-direction: row;
}


.game-info {
margin-left: 20px;
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/react/16.6.3/umd/react.production.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/react-dom/16.6.3/umd/react-dom.production.min.js"></script>
<div id="errors" style="
background: #c00;
color: #fff;
display: none;
margin: -20px -20px 20px;
padding: 20px;
white-space: pre-wrap;
"></div>
<div id="root"></div>
<script>
window.addEventListener('mousedown', function(e) {
document.body.classList.add('mouse-navigation');
document.body.classList.remove('kbd-navigation');
});
window.addEventListener('keydown', function(e) {
if (e.keyCode === 9) {
document.body.classList.add('kbd-navigation');
document.body.classList.remove('mouse-navigation');
}
});
window.addEventListener('click', function(e) {
if (e.target.tagName === 'A' && e.target.getAttribute('href') === '#') {
e.preventDefault();
}
});
window.onerror = function(message, source, line, col, error) {
var text = error ? error.stack || error : message + ' (at ' + source + ':' + line + ':' + col + ')';
errors.textContent += text + '\n';
errors.style.display = '';
};
console.error = (function(old) {
return function error() {
errors.textContent += Array.prototype.slice.call(arguments).join(' ') + '\n';
errors.style.display = '';
old.apply(this, arguments);
}
})(console.error);
</script>

超高效的比特寄存

让我们把游戏存储为一个二进制整数，并且只用一个步骤来计算所有的东西！

• 我们知道 X 的移动占据9位: xxx xxx xxx
• 我们知道 O 的移动占据9位: ooo ooo ooo

因此，董事会的位置可以用18位来表示: xoxoxo xoxoxo xoxoxo

但是，虽然这看起来很有效率，但它并不能帮助我们决定胜负。我们需要一个更有用的位模式... 一个不仅编码的动作，而且编码的行，列和对角线在一个合理的方式。

我会使用一个聪明的整数值为每个董事会的立场这样做。

选择一个更有用的表现形式

First, we need a board notation, just so that we can discuss this. So, similar to Chess, lets number the rows with letters and the columns with numbers - so we know which square we're talking about

And let's give each a binary value.

a1 = 100 000 000 100 000 000 100 000 ; Row A Col 1 (top left corner)
a2 = 010 000 000 000 100 000 000 000 ; Row A Col 2 (top edge)
a3 = 001 000 000 000 000 100 000 100 ; Row A Col 3 (top right corner)
b1 = 000 100 000 010 000 000 000 000 ; Row B Col 1 (left edge)
b2 = 000 010 000 000 010 000 010 010 ; Row B Col 2 (middle square)
b3 = 000 001 000 000 000 010 000 000 ; Row B Col 4 (right edge)
c1 = 000 000 100 001 000 000 000 001 ; Row C Col 1 (bottom left corner)
c2 = 000 000 010 000 001 000 000 000 ; Row C Col 2 (bottom edge)
c3 = 000 000 001 000 000 001 001 000 ; Row C Col 3 (bottom right corner)

... where, the binary values encode which rows, columns and diagonals the position appears in. (稍后我们将看看这是如何工作的)

We will use these values to build two representations of the game, one for X and one for O

• X 以一个空白板开始: 000 000 000 000 000 000 000 000
• O 以一个空白板开始: 000 000 000 000 000 000 000 000

让我们按照 X 的移动 < em > (O 将是相同的原则)

• X 选择 A1... 所以我们用值 A1或(X 板)
• X 选择 A2... 所以我们选择值 A2
• X 选择 A3... 所以我们选择值 A3

这对 X 的董事会价值有什么影响:

1. a1 = 100 000 000 100 000 000 100 000... 用
2. a2 = 010 000 000 000 100 000 000 000... 用
3. 等于:

XB = 111 000 000 100 100 100 100 100

从左往右读，我们看到 X 有:

• 第一排 111(所有职位)
• 第二排 000(无头寸)
• 000 (No positions) in Row 3
• 100(一个位置)只有第一列的第一个位置
• 100(一个位置)只有第一列的第一个位置
• 100(一个位置)只有第一列的第一个位置
• 100(一个位置)只有对角线1的第一个位置
• 100(一个位置)只有对角线2的第一个位置

您会注意到，每当 X (或 O)有一个获胜线，那么在他的板值中也会有三个连续的位。确切地说，这三个位置决定了他在哪一行/哪一列/哪一条对角线上获胜。

因此，现在的技巧是找到一种方法，在一个操作中检查这个(三个连续的位集)条件。

修改值以使检测更容易

为了帮助解决这个问题，让我们改变我们的位表示，使得三组之间总是有零(因为 001 110也是三个连续的位——但它们不是一个有效的胜利... 所以，一个固定的零间隔将打破这些: 0 001 0 110)

因此，在增加了一些间隔零，我们可以相信，任何三个连续设置位在 X 或 O 的董事会值表明胜利！

So, our new binary values (with zero-padding) look like this :

• a1 = 100 0 000 0 000 0 100 0 000 0 000 0 100 0 000 0; 0x80080080(十六进制)
• 0x40008000
• 0x20000808
• 0x08040000
• 第一季，第4集
• b3 = 000 0 001 0 000 0 000 0 000 0 010 0 000 0 000 0 ; 0x02000400
• 0x00820002
• 0x00402000
• 0x00200220

你会注意到，现在每个“ Winline”的董事会需要4位。

8行 x 每行4比特 = 32比特! 是不是很方便:))))

解析

我们可以移动所有的比特寻找三个连续的比特，但那将需要32次移动 x2个球员... 和一个计数器来跟踪。太慢了！

我们可以使用0xF 进行 AND，查找值8 + 4 + 2 = 14。这样我们就可以一次检查4位。把班次减少四分之一。但是再说一次，这太慢了！

所以，相反，让我们一次检查所有的可能性..。

超高效的胜利探测

假设我们想要评估 A3 + A1 + B2 + C3的情况(在对角线上的胜利)

a1 = 100 0 000 0 000 0 100 0 000 0 000 0 100 0 000 0, OR
a3 = 001 0 000 0 000 0 000 0 000 0 100 0 000 0 100 0, OR
b2 = 000 0 010 0 000 0 000 0 010 0 000 0 010 0 010 0, OR
c3 = 000 0 000 0 001 0 000 0 000 0 001 0 001 0 000 0, =


XB = 101 0 010 0 001 0 100 0 010 0 101 0 111 0 110 0  (See the win, on Diagonal 1?)

Now, let's check it for a win, by efficiently merging three bits into one...

简单使用: XB AND (XB << 1) AND (XB >> 1) 换句话说: XB AND with (XB 向左移动) AND (XB 向右移动)

Let's try an example...

10100100001010000100101011101100 ; whitespaces removed for easy shifting
(AND)
01001000010100001001010111011000 ; XB shifted left
(AND)
01010010000101000010010101110110 ; XB shifted left
(Equals)
00000000000000000000000001000000

看到了吗? 任何非零的结果都意味着胜利！

但是，他们在哪里赢了

Want to know where they won? Well, you could just use a second table :

0x40000000 = RowA
0x04000000 = RowB
0x00400000 = RowC
0x00040000 = Col1
0x00004000 = Col2
0x00000400 = Col3
0x00000040 = Diag1
0x00000004 = Diag2

然而，我们可以更聪明，因为模式是非常有规律的！

例如，在汇编中可以使用 BSF (Bit Scan Forward)查找前导零的数目。然后减去2，再减去/4(Shift Right 2)——得到一个介于0和8之间的数字... ... 你可以用这个数字作为索引来查看一个由 win 字符串组成的数组:

{"wins the top row", "takes the middle row!", ... "steals the diagonal!" }

这使得整个游戏的逻辑... 从移动检查，董事会更新和权利通过的胜利/失败检测和适当的成功信息，所有适合在少数 ASM 指令。

... it's tiny, efficient and ultrafast!

检查一个动作是否可玩

显然，将“ X 的董事会”与“ O 的董事会”= 所有的职位

因此，你可以很容易地检查一个移动是否有效。如果用户选择 UpperLeft，则此位置具有整数值。只需用(XB 或 OB)检查该值的“ AND”..。

如果结果是非零，那么位置已经在使用了。

结论

如果你正在寻找有效的方法来处理一个棋盘，不要从一个棋盘对象开始。尝试发现一些有用的抽象概念。

看看这些状态是否适合一个整数，然后想想一个容易处理的位掩码是什么样子的。有了一些聪明的整数选择来表示移动，位置或棋盘... 你可能会发现，整个游戏可以玩，评估和得分非常有效-使用简单的位逻辑。

最后一次道歉

顺便说一句，我并不是 StackOverflow 的常客，所以我希望这篇文章不会太混乱而无法跟上。还有，请友好一点... ... “人类”是我的第二语言，我还不是很流利;)

不管怎样，我希望这能帮到别人。

下面是 React: 代码沙盒演示中的一个实现示例。

算法很简单:

For every move:
checkDiagonals()
checkVerticals()
checkHorizontals()

为“ O”输入指定 0，为“ X”输入指定 1。检查函数的结果可以是 0、 1或 2(绘图)。

下面是实施方案:

    const checkDiagonals = () => {
if ((state[0][0] === val && state[1][1] === val && state[2][2] === val) ||
(state[0][2] === val && state[1][1] === val && state[2][0] === val)) {
return val;
}
return -1;
}


const checkVerticals = () => {
for (let i = 0; i <= 2; i++) {
if (state[0][i] === val && state[1][i] === val && state[2][i] === val) {
return val;
}
}
return -1;
}


const checkHorizontals = () => {
for (let i = 0; i <= 2; i++) {
if (state[i][0] === val && state[i][1] === val && state[i][2] === val) {
return val;
}
}
return -1;
}

剩下的就是创建一个函数来触发每个用户的输入:

const updateWinningPlayer = () => {


const diagonals = checkDiagonals();
const verticals = checkVerticals();
const horizontals = checkHorizontals();


if (diagonals !== -1) {
setWinner(diagonals)
return;
}


if (verticals !== -1) {
setWinner(verticals);
return;
}


if (horizontals !== -1) {
setWinner(horizontals);
return;
}


if (isDraw()) {
setWinner(2);
}
}

就是这样！

GitHub 回购链接: https://github.com/mkotsollaris/tic-tac-toe

另一个帖子上有一个井字游戏的问题，我现在找不到了，但是我找到了这个，所以这是我的井字游戏模拟器，我在读了这个问题之后迅速做出来的:

from random import randint
from time import sleep


# Tic-tac-toe simulator
# The grid:
#  0 | 1 | 2
# -----------
#  3 | 4 | 5
# -----------
#  6 | 7 | 8
# -----------


# create winning lines
winlines = tuple(
map(
set,
(
(0, 1, 2),  # across
(3, 4, 5),
(6, 7, 8),
(0, 3, 6),  # down
(1, 4, 7),
(2, 5, 8),
(0, 4, 8),  # diagonals
(2, 4, 6),
),
)
)


for trials in range(10):
# clear the table
available = list(range(9))  # 9 positions 0-8
xPlacement = set()
oPlacement = set()


winner = None


while len(available):
index = randint(0, len(available) - 1)
move = available[index]
if index < len(available) - 1:
available[index] = available.pop()
else:
available.pop()
print("X takes ", move)
xPlacement.add(move)
if any(((xPlacement & winline) == winline) for winline in winlines):
winner = "X"
break
if len(available) == 0:
break


index = randint(0, len(available) - 1)
move = available[index]
if index < len(available) - 1:
available[index] = available.pop()
else:
available.pop()
print("O takes ", move)
oPlacement.add(move)
if any(((oPlacement & winline) == winline) for winline in winlines):
winner = "O"
break


print(
" {} | {} | {}\n-----------\n {} | {} | {}\n-----------\n {} | {} | {}".format(
*[
"X" if pos in xPlacement else "O" if pos in oPlacement else " "
for pos in range(9)
]
)
)
if winner:
print(f"{winner} wins!")
else:
print("It's a tie!")
sleep(1)