# java - 用於確定Tic Tac Toe遊戲結束的算法

## algorithm tic-tac-toe (14)

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

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

short[] winCombinations = new short[]{
7, 7 << 3, 7 << 6, // horizontal
73, 73 << 1, 73 << 2, // vertical
273, // diagonal
84   // anti-diagonal
};

for (short X = 0; X < 511; X++)
System.out.println(isWinner(X));

1. 董事會已滿，尚未宣布獲勝者：遊戲是平局。
2. 克羅斯贏了。
3. 圈子贏了。

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.

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

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

I do understand that this solution is not scalable easily.

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

public static boolean checkWin(char symb) {
int SIZE = 5;

for (int i = 0; i < SIZE-1; i++) {
for (int j = 0; j <SIZE-1 ; j++) {
//vertical checking
if (map[0][j] == symb && map[1][j] == symb && map[2][j] == symb && map[3][j] == symb && map[4][j] == symb) return true;      // j=0
}
//horisontal checking
if(map[i][0] == symb && map[i][1] == symb && map[i][2] == symb && map[i][3] == symb && map[i][4] == symb) return true;  // i=0
}
//diagonal checking (5*5)
if (map[0][0] == symb && map[1][1] == symb && map[2][2] == symb && map[3][3] == symb && map[4][4] == symb) return true;
if (map[4][0] == symb && map[3][1] == symb && map[2][2] == symb && map[1][3] == symb && map[0][4] == symb) return true;

return false;
}

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

This is a really simple way to check.

public class Game() {

Game player1 = new Game('x');
Game player2 = new Game('o');

char piece;

Game(char piece) {
this.piece = piece;
}

public void checkWin(Game player) {

// check horizontal win
for (int i = 0; i <= 6; i += 3) {

if (board[i] == player.piece &&
board[i + 1] == player.piece &&
board[i + 2] == player.piece)
endGame(player);
}

// check vertical win
for (int i = 0; i <= 2; i++) {

if (board[i] == player.piece &&
board[i + 3] == player.piece &&
board[i + 6] == player.piece)
endGame(player);
}

// check diagonal win
if ((board[0] == player.piece &&
board[4] == player.piece &&
board[8] == player.piece) ||
board[2] == player.piece &&
board[4] == player.piece &&
board[6] == player.piece)
endGame(player);
}

}

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

private boolean isPrincipalDiagonal(int x, int y) {
return x == y;
}

private boolean isMinorDiagonal(int x, int y) {
return x + y == gridSize - 1;
}
}
}

import static com.agilefaqs.tdd.demo.TicTacToe.BLANK;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class TicTacToeTest {
private TicTacToe game = new TicTacToe(3);

@Test
public void allCellsAreEmptyInANewGame() {
assertBoardIs(new char[][] { { BLANK, BLANK, BLANK },
{ BLANK, BLANK, BLANK },
{ BLANK, BLANK, BLANK } });
}

@Test(expected = IllegalArgumentException.class)
public void boardHasToBeMinimum3x3Grid() {
new TicTacToe(2);
}

@Test
public void firstPlayersMoveMarks_X_OnTheBoard() {
assertEquals("continue", game.move(1, 1));
assertBoardIs(new char[][] { { BLANK, BLANK, BLANK },
{ BLANK, 'X', BLANK },
{ BLANK, BLANK, BLANK } });
}

@Test
public void secondPlayersMoveMarks_O_OnTheBoard() {
game.move(1, 1);
assertEquals("continue", game.move(2, 2));
assertBoardIs(new char[][] { { BLANK, BLANK, BLANK },
{ BLANK, 'X', BLANK },
{ BLANK, BLANK, 'O' } });
}

@Test
public void playerCanOnlyMoveToAnEmptyCell() {
game.move(1, 1);
assertEquals("(1,1) is already occupied", game.move(1, 1));
}

@Test
public void firstPlayerWithAllSymbolsInOneRowWins() {
game.move(0, 0);
game.move(1, 0);
game.move(0, 1);
game.move(2, 1);
assertEquals("X won the game!", game.move(0, 2));
}

@Test
public void firstPlayerWithAllSymbolsInOneColumnWins() {
game.move(1, 1);
game.move(0, 0);
game.move(2, 1);
game.move(1, 0);
game.move(2, 2);
assertEquals("O won the game!", game.move(2, 0));
}

@Test
public void firstPlayerWithAllSymbolsInPrincipalDiagonalWins() {
game.move(0, 0);
game.move(1, 0);
game.move(1, 1);
game.move(2, 1);
assertEquals("X won the game!", game.move(2, 2));
}

@Test
public void firstPlayerWithAllSymbolsInMinorDiagonalWins() {
game.move(0, 2);
game.move(1, 0);
game.move(1, 1);
game.move(2, 1);
assertEquals("X won the game!", game.move(2, 0));
}

@Test
public void whenAllCellsAreFilledTheGameIsADraw() {
game.move(0, 2);
game.move(1, 1);
game.move(1, 0);
game.move(2, 1);
game.move(2, 2);
game.move(0, 0);
game.move(0, 1);
game.move(1, 2);
assertEquals("Its a Draw!", game.move(2, 0));
}

private void assertBoardIs(char[][] expectedBoard) {
assertArrayEquals(expectedBoard, game.displayBoard());
}
}

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

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

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

（我沒有真正測試這個*咳嗽*，但是它在第一次嘗試編譯了，對我來說！）

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

// 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 :(
%

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

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

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

1. 簡單。
2. 一個循環。
3. 五個簡單變量：4個整數和一個布爾值。
4. 可以縮放到n的任意大小。
5. 只檢查當前件。
6. 沒有魔法。 :)

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

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

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