Алгоритм определения игры Tic Tac Toe закончен
Я написал игру в крестики-нолики на Java, и мой текущий метод определения конца игры учитывает следующие возможные сценарии для игры:
- Доска заполнена, и победитель еще не объявлен: игра - ничья.
- Крест победил.
- Круг победил.
К сожалению, для этого он читает предварительно определенный набор этих сценариев из таблицы. Это не обязательно плохо, если учесть, что на доске всего 9 мест, и, следовательно, стол немного мал, но есть ли лучший алгоритмический способ определить, закончена ли игра? Определение того, выиграл кто-то или нет, является основной проблемой, так как проверка, заполнены ли 9 пробелов, тривиальна.
Метод таблицы может быть решением, но если нет, то что? Кроме того, что, если доска не была размером n=9? Что если бы это была намного большая доска, скажем n=16, n=25и так далее, в результате чего количество последовательно размещенных предметов для выигрыша будет x=4, x=5, так далее? Общий алгоритм для использования для всех n = { 9, 16, 25, 36 ... }?
26 ответов
Вы знаете, что выигрышный ход может произойти только после того, как X или O сделали последний ход, поэтому вы можете искать только строку / столбец с необязательной диагональю, содержащейся в этом шаге, чтобы ограничить пространство поиска при попытке определить выигрышную доску. Кроме того, поскольку в игре "крестики-нолики" с фиксированным числом ходов после выполнения последнего хода, если это был не выигрышный ход, по умолчанию игра вничью.
редактировать: этот код предназначен для выигрыша n 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 если какая-либо строка, столбец или диагональ добавляет до 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 и пробелом для пустых.
- просто.
- Одна петля
- Пять простых переменных: 4 целых и одна логическая.
- Весы до любого размера n.
- Проверяет только текущий кусок.
- Нет магии.:)
Это похоже на ответ Усамы ALASSIRY, но оно меняет постоянное пространство и линейное время на линейное пространство и постоянное время. То есть зацикливание после инициализации отсутствует.
Инициализировать пару (0,0) для каждой строки, каждого столбца и двух диагоналей (диагональ и анти-диагональ). Эти пары представляют собой накопленные (sum,sum) частей в соответствующей строке, столбце или диагонали, где
Кусок от игрока А имеет значение (1,0) Кусок от игрока B имеет значение (0,1)
Когда игрок помещает фигуру, обновите соответствующую пару строк, пару столбцов и диагональные пары (если они есть на диагонали). Если любая новая обновленная строка, столбец или диагональная пара равна (n,0) или же (0,n) тогда либо А, либо В выиграли соответственно.
Асимптотический анализ:
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) раз за ход? Если это так, вы можете закончить игру рано на ничью.
Сверхэффективная установка битов
Давайте сохраним игру в двоичном целочисленном и оценим все за один шаг!
- Мы знаем, что ходы X занимают 9 бит:
xxx xxx xxx - Мы знаем, что ходы O занимают 9 бит:
ooo ooo ooo
Итак, позиция платы может быть представлена всего в 18 битах:
xoxoxo xoxoxo xoxoxo
Но, хотя это может показаться эффективным, это не помогает нам определить победу. Нам нужен более полезный битовый шаблон ... такой, который не только кодирует ходы, но также разумным образом кодирует строки, столбцы и диагонали.
Я бы сделал это, используя умное целочисленное значение для каждой позиции доски.
Выбор более полезного представления
Во-первых, нам нужны обозначения на доске, чтобы мы могли это обсудить. Итак, как и в шахматах, давайте пронумеруем строки буквами, а столбцы цифрами - чтобы мы знали, о каком квадрате идет речь.
И дадим каждому двоичное значение.
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
- X начинается с пустой доски:
- O начинается с пустой доски:
000 000 000 000 000 000 000 000
Давайте проследим за ходами X (O будет по тому же принципу)
- X играет A1 ... поэтому мы OR (доска X) со значением A1
- X играет A2 ... поэтому мы выполняем ИЛИ со значением A2
- X играет A3 ... поэтому мы выполняем ИЛИ со значением A3
Как это влияет на значение платы 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 / A win, Yay!) - (Нет позиций) в строке 2
-
000(Нет позиций) в строке 3 - (Одна позиция) Только первая позиция столбца 1
- (Одна позиция) Только первая позиция столбца 1
- (Одна позиция) Только первая позиция столбца 1
- (Одна позиция) Только первая позиция диагонали 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; 0x40008000 -
a3 = 001 0 000 0 000 0 000 0 000 0 100 0 000 0 100 0; 0x20000808 -
b1 = 000 0 100 0 000 0 010 0 000 0 000 0 000 0 000 0; 0x08040000 -
b2 = 000 0 010 0 000 0 000 0 010 0 000 0 010 0 010 0; 0x04004044 -
b3 = 000 0 001 0 000 0 000 0 000 0 010 0 000 0 000 0; 0x02000400 -
c1 = 000 0 000 0 100 0 001 0 000 0 000 0 000 0 001 0; 0x00820002 -
c2 = 000 0 000 0 010 0 000 0 001 0 000 0 000 0 000 0; 0x00402000 -
c3 = 000 0 000 0 001 0 000 0 000 0 001 0 001 0 000 0; 0x00200220
Вы заметите, что для каждой «выигрышной линии» доски теперь требуется 4 бита.
8 выигрышных линий по 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, AND с (XB сдвинут влево) AND (XB сдвинут вправо)
Попробуем на примере ...
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 (Shift вправо 2) - чтобы получить число от 0 до 8 ... которое вы можете использовать в качестве индекса для поиска в массиве строк выигрыша:
{"wins the top row", "takes the middle row!", ... "steals the diagonal!" }
Это делает всю логику игры ... от проверки хода до обновления доски и вплоть до обнаружения выигрыша / проигрыша и соответствующего сообщения об успешном завершении - все это умещается в нескольких инструкциях ASM.
... он крошечный, эффективный и сверхбыстрый!
Проверка возможности игры на ход
Очевидно, если объединить «X's board» с «O's board» = ВСЕ ПОЗИЦИИ
Таким образом, вы можете довольно легко проверить, действителен ли ход. Если пользователь выбирает UpperLeft, эта позиция имеет целочисленное значение. Просто проверьте «И» этого значения с помощью (XB OR OB) ...
... если результат ненулевой, значит позиция уже используется.
Заключение
Если вы ищете эффективные способы обработки доски, не начинайте с объекта доски. Попробуйте найти какую-нибудь полезную абстракцию.
Посмотрите, вписываются ли состояния в целое число, и подумайте, как будет выглядеть «легкая» битовая маска для обработки. С помощью некоторого умного выбора целых чисел для представления ходов, позиций или досок ... вы можете обнаружить, что всю игру можно играть, оценивать и оценивать ОЧЕНЬ эффективно - с использованием простой побитовой логики.
Заключительные извинения
Кстати, я не регулярно здесь, в StackOverflow, поэтому надеюсь, что этот пост не был слишком хаотичным, чтобы следить за ним. Кроме того, будьте добры ... "Человеческий" - мой второй язык, и я пока не совсем бегло;)
В любом случае, я надеюсь, что это кому-то поможет.
Вот мое решение, которое я написал для проекта, над которым я работаю в 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;
}
Постоянное время O(8), в среднем 4 коротких AND. Игрок = короткий номер. Требуются дополнительные проверки, чтобы убедиться, что ход действителен.
// 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));
Я только что написал это для своего класса программирования C.
Я публикую это, потому что ни один из других примеров здесь не будет работать с прямоугольной сеткой любого размера и любым количеством последовательных отметок N-в-ряду, чтобы выиграть.
Вы найдете мой алгоритм, такой как он есть, в 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 < n последовательных квадратов, то это немного сложнее. Наиболее очевидным решением является проверка каждого квадрата x × x на наличие победителя. Вот код, который демонстрирует это.
(Я на самом деле не проверял этот * кашель *, но он скомпилировался с первой попытки, поймите меня!)
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 крестики-нолики крестики-нолики
% ./крестики-нолики
| |
--- + --- + ---
| |
--- + --- + ---
| |
Введите ходы как " " (без кавычек, с нулевым индексированием)
Ход Х: 1 2
| |
---+---+---
| | Икс
--- + --- + ---
| |
Ход O: 1 2
незаконный ход (уже занят), попробуйте еще раз
Ход O: 3 3
незаконный ход (с доски), попробуйте еще раз
Ход O: 2 2
| |
---+---+---
| | Икс
--- + --- + ---
| | О
Ход Х: 1 0
| |
---+---+---
X | | Икс
--- + --- + ---
| | О
Ход O: 1 1
| |
---+---+---
X | O | Икс
--- + --- + ---
| | О
Ход икс: 0 0
X | |
---+---+---
X | O | Икс
--- + --- + ---
| | О
Ход O: 2 0
X | |
---+---+---
X | O | Икс
--- + --- + ---
O | | О
Ход Х: 2 1
X | |
---+---+---
X | O | Икс
--- + --- + ---
O | X | О
Ход O: 0 2
X | | О
--- + --- + ---
X | O | Икс
--- + --- + ---
O | X | О
крестики-нолики! О побеждает!
% ./крестики-нолики
| |
--- + --- + ---
| |
--- + --- + ---
| |
Введите ходы как " " (без кавычек, с нулевым индексированием)
Ход икс: 0 0
X | |
---+---+---
| |
---+---+---
| |
Ход O: 0 1
X | O |
---+---+---
| |
---+---+---
| |
Ход Х: 0 2
X | O | Икс
--- + --- + ---
| |
--- + --- + ---
| |
Ход O: 1 0
X | O | Икс
--- + --- + ---
O | |
--- + --- + ---
| |
Ход Х: 1 1
X | O | Икс
--- + --- + ---
O | X |
--- + --- + ---
| |
Ход O: 2 0
X | O | Икс
--- + --- + ---
O | X |
--- + --- + ---
O | |
Ход Х: 2 1
X | O | Икс
--- + --- + ---
O | X |
--- + --- + ---
O | X |
Ход O: 2 2
X | O | Икс
--- + --- + ---
O | X |
--- + --- + ---
O | X | О
Ход Х: 1 2
X | O | Икс
--- + --- + ---
O | X | Икс
--- + --- + ---
O | X | О
тупик... никто не побеждает:(
%Это было весело, спасибо!
На самом деле, думая об этом, вам не нужен магический квадрат, просто счетчик для каждой строки / столбца / диагонали. Это немного проще, чем обобщение магического квадрата на n × n матрицы, так как вам просто нужно рассчитывать на n,
Мне задали тот же вопрос в одном из моих интервью. Мои мысли: инициализировать матрицу с 0. Держите 3 массива 1)sum_row (размер n) 2) sum_column (размер n) 3) диагональ (размер 2)
Для каждого хода на (X) уменьшайте значение поля на 1, а для каждого хода (0) увеличивайте его на 1. В любой точке, если строка / столбец / диагональ, которая была изменена в текущем движении, имеет сумму либо -3, либо +3 означает, что кто-то выиграл игру. Для рисования мы можем использовать вышеуказанный подход, чтобы сохранить переменную moveCount.
Вы думаете, я что-то упустил?
Изменить: То же самое можно использовать для матрицы nxn. Сумма должна быть даже +3 или -3.
Мне нравится этот алгоритм, поскольку он использует представление доски 1х9 против 3х3.
private int[] board = new int[9];
private static final int[] START = new int[] { 0, 3, 6, 0, 1, 2, 0, 2 };
private static final int[] INCR = new int[] { 1, 1, 1, 3, 3, 3, 4, 2 };
private static int SIZE = 3;
/**
* Determines if there is a winner in tic-tac-toe board.
* @return {@code 0} for draw, {@code 1} for 'X', {@code -1} for 'Y'
*/
public int hasWinner() {
for (int i = 0; i < START.length; i++) {
int sum = 0;
for (int j = 0; j < SIZE; j++) {
sum += board[START[i] + j * INCR[i]];
}
if (Math.abs(sum) == SIZE) {
return sum / SIZE;
}
}
return 0;
}
Я опаздываю на вечеринку, но я хотел указать на одно преимущество, которое я нашел при использовании магического квадрата, а именно на то, что его можно использовать для получения ссылки на квадрат, который вызовет выигрыш или проигрыш на следующем ходу, а не просто используется для расчета, когда игра окончена.
Возьми этот магический квадрат:
4 9 2
3 5 7
8 1 6
Во-первых, настроить scores массив, который увеличивается каждый раз, когда выполняется движение. Смотрите этот ответ для деталей. Теперь, если мы незаконно играем X дважды подряд в [0,0] и [0,1], то scores массив выглядит так:
[7, 0, 0, 4, 3, 0, 4, 0];
И доска выглядит так:
X . .
X . .
. . .
Затем все, что нам нужно сделать, чтобы получить ссылку на то, на каком квадрате выиграть / заблокировать, это:
get_winning_move = function() {
for (var i = 0, i < scores.length; i++) {
// keep track of the number of times pieces were added to the row
// subtract when the opposite team adds a piece
if (scores[i].inc === 2) {
return 15 - state[i].val; // 8
}
}
}
В действительности, реализация требует нескольких дополнительных приемов, таких как обработка пронумерованных ключей (в JavaScript), но я нашел это довольно простым и получил удовольствие от развлекательной математики.
Не петлевой способ определить, была ли точка на анти-диаг:
`if (x + y == n - 1)`
Вот пример реализации в React (ссылка CodeSandbox ).
Алгоритм довольно прост:
For every move:
checkDiagonals()
checkVerticals()
checkHorizontals()
Назначение для входа «O» и для входа «X». Результатом функции проверки может быть либо
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
Я сделал некоторую оптимизацию в строке, кол, диагональные проверки. В первом вложенном цикле в основном решается, нужно ли проверять определенный столбец или диагональ. Таким образом, мы избегаем проверки колонок или диагоналей, экономя время. Это оказывает большое влияние, когда размер доски больше и значительное количество ячеек не заполнено.
Вот код 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);
}
}
Если у вас есть поле границы 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;
}
Я думаю, это более понятно, но, вероятно, это не самый оптимальный способ.
Как насчет следующего подхода для 9 слотов? Объявите 9 целочисленных переменных для матрицы 3x3 (a1,a2....a9), где a1,a2,a3 представляют строку-1, а a1,a4,a7 сформируют столбец-1 (идея понятна). Используйте "1" для обозначения "Игрок-1" и "2" для обозначения "Игрок-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
Теперь мы знаем, что если игрок один пересекает a1, то нам нужно пересмотреть сумму из 3 переменных: Win-1, Win-4 и Win-7. Какой бы "Win-?" Переменные достигают 3 или 6 первых побед в игре. Если переменная Win-1 сначала достигает 6, выигрывает Player-2.
Я понимаю, что это решение не легко масштабируется.
Не уверен, опубликован ли этот подход. Это должно работать для любой доски m*n, и игрок должен занять последовательную позицию "WinPos". Идея основана на бегущем окне.
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;
}
Вот мое решение с использованием 2-мерного массива:
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;
}
Вот решение, которое я придумала, оно хранит символы в виде символов и использует значение int символа, чтобы выяснить, выиграл ли Х или О (см. Код рефери).
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
В другой ветке был вопрос о крестиках-ноликах, который я не могу сейчас найти, но я нашел это, так что вот мой симулятор крестиков-ноликов, который я состряпал после прочтения вопроса:
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)
Другой вариант: создать таблицу с кодом. До симметрии, есть только три способа выиграть: крайний ряд, средний ряд или диагональ. Возьми эти три и покрути их всеми возможными способами:
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))))
Эти симметрии могут найти более широкое применение в вашем игровом коде: если вы попадаете на доску, на которой вы уже видели повернутую версию, вы можете просто взять кэшированное значение или лучший кэшированный ход из этого (и развернуть его обратно). Это обычно намного быстрее, чем оценка игрового поддерева.
(Переключение влево и вправо может помочь одинаково; здесь это не нужно, потому что набор поворотов выигрышных паттернов зеркально симметричен.)
Я просто хочу поделиться тем, что я сделал в 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>
Я разработал алгоритм для этого как часть научного проекта.
Вы в основном рекурсивно делите доску на кучу пересекающихся 2х2 ритов, тестируя различные возможные комбинации для выигрыша на квадрате 2х2.
Он медленный, но имеет преимущество работы на плате любого размера с достаточно линейными требованиями к памяти.
Я хотел бы найти свою реализацию