我用 Java 编写了一个井字游戏，我目前确定游戏结束的方法考虑了以下可能的游戏结束情况：
不幸的是，要这样做，它会从表中读取一组预定义的这些场景。考虑到棋盘上只有 9 个空格，这并不一定是坏事，因此桌子有点小，但是是否有更好的算法方法来确定游戏是否结束？确定某人是否获胜是问题的关键，因为检查 9 个空格是否已满是微不足道的。
表方法可能是解决方案，但如果不是，那是什么？另外，如果电路板没有尺寸n=9怎么办？如果它是一个更大的棋盘，比如说n=16,n=25等等，导致连续放置的获胜项目的数量是x=4,x=5等等？一个通用的算法供所有人使用n = { 9, 16, 25, 36 ... }？
您知道只有在 X 或 O 进行了他们最近的移动之后才会发生获胜的移动，因此您只能搜索包含该移动的可选 diag 的行/列，以在尝试确定获胜棋盘时限制您的搜索空间。此外，由于在平局井字游戏中存在固定数量的动作，一旦做出最后一步，如果它不是获胜的动作，则默认情况下是平局游戏。
此代码适用于 n x n 板，连续 n 获胜（3x3 板需要连续 3 个等）
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如果任何行、列或 diag 加起来为 15，则玩家获胜。
这个伪代码怎么样：
玩家在位置 (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 和空格为空。
这类似于Osama ALASSIRY 的答案，但它用常数空间和线性时间换取线性空间和常数时间。也就是说，初始化后没有循环。
(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 个整数 = 4(n+1) 个整数
练习：你能看到如何在每次移动 O(1) 时间内测试平局吗？如果是这样，您可以在平局时提前结束比赛。
这是我为我正在使用 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;
}
我刚刚为我的 C 编程课写了这个。
我发布它是因为这里的其他示例都不适用于任何大小的矩形网格，并且任何数量的N -in-a-row 连续标记都可以获胜。
你会在checkWinner()函数中找到我的算法。它不使用幻数或任何花哨的东西来检查获胜者，它只是使用四个 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 条对角线。检查每一个的全 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;
}
}
}
我不太了解 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 <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
% ./井字游戏
| |
---+---+---
| |
---+---+---
| |
输入移动为“”（无引号，零索引）
X的移动：1 2
| |
---+---+---
| | X
---+---+---
| |
O的移动：1 2
非法移动（已采取），再试一次
O的移动：3 3
非法移动（下棋），再试一次
O的移动：2 2
| |
---+---+---
| | X
---+---+---
| | ○
X的移动：1 0
| |
---+---+---
X | | X
---+---+---
| | ○
O的移动：1 1
| |
---+---+---
X | ○ | X
---+---+---
| | ○
X的移动：0 0
X | |
---+---+---
X | ○ | X
---+---+---
| | ○
O的移动：2 0
X | |
---+---+---
X | ○ | X
---+---+---
○ | | ○
X的移动：2 1
X | |
---+---+---
X | ○ | X
---+---+---
○ | X | ○
O的移动：0 2
X | | ○
---+---+---
X | ○ | X
---+---+---
○ | X | ○
井字游戏！哦，赢了！
% ./井字游戏
| |
---+---+---
| |
---+---+---
| |
输入移动为“”（无引号，零索引）
X的移动：0 0
X | |
---+---+---
| |
---+---+---
| |
O的移动：0 1
X | ○ |
---+---+---
| |
---+---+---
| |
X的移动：0 2
X | ○ | X
---+---+---
| |
---+---+---
| |
O的移动：1 0
X | ○ | X
---+---+---
○ | |
---+---+---
| |
X的移动：1 1
X | ○ | X
---+---+---
○ | X |
---+---+---
| |
O的移动：2 0
X | ○ | X
---+---+---
○ | X |
---+---+---
○ | |
X的移动：2 1
X | ○ | X
---+---+---
○ | X |
---+---+---
○ | X |
O的移动：2 2
X | ○ | X
---+---+---
○ | X |
---+---+---
○ | X | ○
X的移动：1 2
X | ○ | X
---+---+---
○ | X | X
---+---+---
○ | X | ○
僵持...没有人赢:(
%
那很有趣，谢谢！
实际上，考虑一下，您不需要幻方，只需要每行/列/对角线的计数即可。这比将幻方推广到n×n矩阵要容易一些，因为您只需要数到n。
恒定时间解，在 O(8) 中运行。
将板的状态存储为二进制数。最小的位 (2^0) 是棋盘的左上角。然后它向右，然后向下。
IE
+-----------------+ | 2^0 | 2^1 | 2^2 | |-----------------| | 2^3 | 2^4 | 2^5 | |-----------------| | 2^6 | 2^7 | 2^8 | +-----------------+
每个玩家都有自己的二进制数来表示状态（因为井字游戏）有 3 个状态（X、O 和空白），因此单个二进制数无法代表多个玩家的棋盘状态。
例如，像这样的板：
+-----------+ | X | ○ | X | |-----------| | ○ | X | | |-----------| | | ○ | | +-----------+ 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 有棋子的地方，反之亦然。
要检查一个玩家是否赢了，我们需要将该玩家覆盖的所有位置与我们知道是获胜位置的位置进行比较。在这种情况下，最简单的方法是对玩家位置和获胜位置进行与门运算，看看两者是否相等。
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 // 获胜位置，第一行都一样。 ------------ &: 111000000
注意：X & W = W，所以 X 处于胜利状态。
这是一个恒定时间的解决方案，它仅取决于获胜位置的数量，因为应用与门是一个恒定时间操作并且获胜位置的数量是有限的。
它还简化了枚举所有有效电路板状态的任务，它们只是所有可用 9 位表示的数字。但是当然你需要一个额外的条件来保证一个数字是一个有效的棋盘状态（例如，0b111111111是一个有效的 9 位数字，但它不是一个有效的棋盘状态，因为 X 刚刚完成了所有的回合）。
可能的获胜位置的数量可以即时生成，但无论如何它们都在这里。
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));
在我的一次采访中，我被问到了同样的问题。我的想法：用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)`
我迟到了，但我想指出我发现使用幻方的一个好处，即它可以用来获取对下一回合会导致输赢的方的参考，而不是只是用于计算游戏何时结束。
拿这个魔方：
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 中），但我发现它非常简单并且喜欢娱乐性的数学。
我喜欢这个算法，因为它使用 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;
}
超高效的比特登机
让我们将游戏存储在一个二进制整数中，只需一步即可评估所有内容！
xxx xxx xxxooo ooo ooo因此，棋盘位置可以仅用 18 位表示：xoxoxo xoxoxo xoxoxo
但是，虽然这看起来很有效，但它并不能帮助我们确定胜利。我们需要一种更有用的位模式……它不仅可以对移动进行编码，还可以以合理的方式对行、列和对角线进行编码。
我会通过为每个棋盘位置使用一个聪明的整数值来做到这一点。
选择更有用的表示
首先，我们需要一个板符号，以便我们可以讨论这个问题。所以，类似于国际象棋，让我们用字母对行进行编号，用数字对列进行编号——这样我们就知道我们在谈论哪个方格
| 1 | 2 | 3 | |
|---|---|---|---|
| 一种 | a1 | a2 | a3 |
| 乙 | b1 | b2 | b3 |
| C | c1 | c2 | c3 |
让我们给每个二进制值。
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)
...其中，二进制值编码位置出现在哪些行、列和对角线。 （我们稍后会看看它是如何工作的）
我们将使用这些值来构建游戏的两种表示形式，一种用于 X，一种用于 O
000 000 000 000 000 000 000 000000 000 000 000 000 000 000 000让我们跟随X的动作 （O将是相同的原理）
这对 X 的董事会价值有什么影响：
a1 = 100 000 000 100 000 000 100 000... 与a2 = 010 000 000 000 100 000 000 000... 与a3 = 001 000 000 000 000 100 000 100... 等于 ：XB =111 000 000 100 100 100 100 100
从左到右阅读我们看到 X 有：
111（所有位置）在第 1 行（\o/ 赢了，耶！）000（无职位）在第 2 行000（无职位）在第 3 行100（一个位置）只有第1列的第一个位置100（一个位置）只有第1列的第一个位置100（一个位置）只有第1列的第一个位置100（一个位置）只有对角线1的第一个位置100（一个位置）只有对角线2的第一个位置你会注意到，只要 X（或 O）有赢线，那么他的棋盘值中也会有三个连续的位。确切地说，这三位在哪里，决定了他在哪一行/哪一列/对角线上获胜。
所以，现在的诀窍是找到一种方法来在单个操作中检查这个（三个连续的位设置）条件。
修改值以使检测更容易
为了解决这个问题，让我们改变我们的位表示，以便在三个组之间总是有零（因为001 110也是三个连续的位 - 但它们不是有效的胜利......所以，一个固定的零间隔符会打破这些：0 001 0 110)
因此，在添加一些间距零之后，我们可以确信 X 或 O 的棋盘值中的任何三个连续设置位都表示获胜！
因此，我们的新二进制值（带零填充）如下所示：
a1 = 100 0 000 0 000 0 100 0 000 0 000 0 100 0 000 0; 0x80080080（十六进制）a2 = 010 0 000 0 000 0 000 0 100 0 000 0 000 0 000 0; 0x40008000a3 = 001 0 000 0 000 0 000 0 000 0 100 0 000 0 100 0; 0x20000808b1 = 000 0 100 0 000 0 010 0 000 0 000 0 000 0 000 0; 0x08040000b2 = 000 0 010 0 000 0 000 0 010 0 000 0 010 0 010 0; 0x04004044b3 = 000 0 001 0 000 0 000 0 000 0 010 0 000 0 000 0; 0x02000400c1 = 000 0 000 0 100 0 001 0 000 0 000 0 000 0 001 0; 0x00820002c2 = 000 0 000 0 010 0 000 0 001 0 000 0 000 0 000 0; 0x00402000c3 = 000 0 000 0 001 0 000 0 000 0 001 0 001 0 000 0; 0x00200220您会注意到电路板的每个“winline”现在需要 4 位。
8 个赢线 x 每个 4 位 = 32 位！不是很方便吗:)))))
解析
我们可以移动所有的位来寻找三个连续的位，但这需要 32 次移位 x 2 名玩家......以及一个计数器来跟踪。很慢！
我们可以用 0xF 与，寻找值 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?)
现在，让我们通过有效地将三个位合并为一个来检查它是否成功……
简单地使用 :XB AND (XB << 1) AND (XB >> 1)
换句话说：XB ANDed with (XB shift left) AND (XB shift right)
让我们尝试一个例子......
10100100001010000100101011101100 ; whitespaces removed for easy shifting
(AND)
01001000010100001001010111011000 ; XB shifted left
(AND)
01010010000101000010010101110110 ; XB shifted left
(Equals)
00000000000000000000000001000000
看到了吗？任何非零结果都意味着胜利！
但是，他们在哪里赢了
想知道他们在哪里赢了？好吧，您可以只使用第二张表：
0x40000000 = RowA
0x04000000 = RowB
0x00400000 = RowC
0x00040000 = Col1
0x00004000 = Col2
0x00000400 = Col3
0x00000040 = Diag1
0x00000004 = Diag2
但是，我们可以比这更聪明，因为模式非常规则！
例如，在汇编中，您可以使用它BSF (Bit Scan Forward)来查找前导零的数量。然后减去 2 和 /4（右移 2） - 得到一个介于 0 和 8 之间的数字...您可以将其用作索引来查找获胜字符串数组：
{"wins the top row", "takes the middle row!", ... "steals the diagonal!" }
这使得整个游戏逻辑......从移动检查，到棋盘更新，一直到赢/输检测和适当的成功消息，都适合少数 ASM 指令。
...它小巧、高效且超快！
检查移动是否可玩
显然，将“X 板”与“O 板”进行 ORing = ALL POSITIONS
因此，您可以很容易地检查移动是否有效。如果用户选择 UpperLeft，这个位置有一个整数值。只需使用（XB OR OB）检查此值的“与”...
...如果结果非零，则该位置已在使用中。
结论
如果您正在寻找处理板的有效方法，请不要从板对象开始。尝试发现一些有用的抽象。
查看状态是否适合整数，并考虑处理的“简单”位掩码是什么样的。通过一些巧妙的整数选择来表示移动、位置或棋盘......您可能会发现整个游戏可以非常有效地进行、评估和评分 - 使用简单的按位逻辑。
最后道歉
顺便说一句，我不是 StackOverflow 的常客，所以我希望这篇文章不会太混乱而无法关注。另外，请客气……“人类”是我的第二语言，我还不太流利；）
无论如何，我希望这对某人有所帮助。
我在行、列、对角线检查中做了一些优化。如果我们需要检查特定的列或对角线，它主要在第一个嵌套循环中决定。因此，我们避免检查列或对角线以节省时间。当电路板尺寸更大且大量单元未填充时，这会产生很大的影响。
这是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;
}
这是一种非常简单的检查方法。
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);
}
}
这是 React 中的一个示例实现：CodeSandbox Demo。
该算法非常简单：
For every move:
checkDiagonals()
checkVerticals()
checkHorizontals()
分配0给“O”输入和1“X”输入。检查函数的结果可以是0, 或1, 或2(draw)。
这是实现：
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
另一种选择：使用代码生成表。直到对称，只有三种获胜方式：边缘排、中间排或对角线。拿这三个并以各种可能的方式旋转它们：
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 值来确定 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
9 个插槽的以下方法怎么样？为 3x3 矩阵 (a1,a2....a9) 声明 9 个整数变量，其中 a1,a2,a3 表示第 1 行，a1,a4,a7 将形成第 1 列（你明白了）。使用“1”表示 Player-1，使用“2”表示 Player-2。
有 8 种可能的获胜组合： Win-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
现在我们知道，如果玩家 1 越过 a1，那么我们需要重新评估 3 个变量的总和：Win-1、Win-4 和 Win-7。无论是“赢-？” 变量达到3或6首先赢得比赛。如果 Win-1 变量首先达到 6，则 Player-2 获胜。
我明白这个解决方案不容易扩展。
例如，如果您有边界字段 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 棋盘，并且玩家应该填补“ winnerPos ”连续位置。这个想法是基于运行窗口。
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;
}
}
}
此函数可以与两个参数 (x,y) 一起使用，它们是最后一次移动的坐标。在初始执行中，它使用 4 个参数递归地调用四个双向搜索。所有结果都作为长度返回，函数最终在 4 个搜索双向中选择最大长度。
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>我曾经为此开发了一种算法，作为科学项目的一部分。
您基本上递归地将棋盘划分为一堆重叠的 2x2 矩形，测试在 2x2 方格上获胜的不同可能组合。
它很慢，但它具有在任何尺寸的板上工作的优势，并且具有相当线性的内存需求。
我希望我能找到我的实现