반응형
Tic Tac Toe 게임 오버 결정을위한 알고리즘
저는 Java로 tic-tac-toe 게임을 작성했으며 현재 게임의 끝을 결정하는 방법은 게임이 끝날 때 다음과 같은 가능한 시나리오를 설명합니다.
- 보드가 꽉 찼고 아직 승자가 선언되지 않았습니다. 게임은 무승부입니다.
- 크로스가 이겼습니다.
- 서클이 이겼습니다.
안타깝게도이를 위해 테이블에서 이러한 시나리오의 미리 정의 된 집합을 읽습니다. 보드에 9 개의 공간 만 있고 따라서 테이블이 다소 작다는 점을 고려하면 이것이 반드시 나쁘지는 않지만 게임이 끝났는지 확인하는 더 나은 알고리즘 방식이 있습니까? 누군가가 이겼는지 여부를 결정하는 것은 문제의 핵심입니다. 9 칸이 꽉 찼는 지 확인하는 것은 사소하기 때문입니다.
테이블 방법이 해결책이 될 수 있지만 그렇지 않은 경우 무엇입니까? 또한 보드가 크기가 아니라면 n=9어떻게 될까요? 그것은 무엇 말하자면 훨씬 더 큰 보드된다면 n=16, n=25등 연속적으로 배치 항목의 수를 원인에로 승리 x=4, x=5등? 모두를 위해 사용하는 일반적인 알고리즘 n = { 9, 16, 25, 36 ... }?
이기는 이동은 X 또는 O가 가장 최근에 이동 한 후에 만 발생할 수 있으므로 해당 이동에 포함 된 선택적 진단을 사용하여 행 / 열만 검색하여 승리 한 보드를 결정하려고 할 때 검색 공간을 제한 할 수 있습니다. 또한 무승부 틱택 토 게임에는 고정 된 수의 무브가 있기 때문에 마지막 무브가 한 번 수행되면이기는 무브가 아니라면 기본적으로 무승부 게임입니다.
편집 :이 코드는 n x 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
}
}
}
행, 열 또는 diag의 합이 15가되고 플레이어가이긴 경우 매직 스퀘어 http://mathworld.wolfram.com/MagicSquare.html을 사용할 수 있습니다 .
이것은 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) 시간으로 무승부를 테스트하는 방법을 알 수 있습니까? 그렇다면 무승부에서 게임을 일찍 끝낼 수 있습니다.
이 의사 코드는 어떻습니까?
플레이어가 (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
나는 문자 [n, n]의 배열을 사용하고, O, X와 빈 공간을 사용합니다.
- 단순한.
- 하나의 루프.
- 5 개의 간단한 변수 : 4 개의 정수와 1 개의 부울.
- n의 모든 크기로 확장됩니다.
- 현재 조각 만 확인합니다.
- 마법이 아닙니다. :)
내가 자바 스크립트에서 작업중 인 프로젝트를 위해 작성한 솔루션입니다. 몇 가지 어레이의 메모리 비용에 신경 쓰지 않는다면 아마도 가장 빠르고 간단한 솔루션 일 것입니다. 마지막 움직임의 위치를 알고 있다고 가정합니다.
/*
* 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()함수 에서 내 알고리즘을 찾을 수 있습니다. 승자를 확인하기 위해 매직 넘버 나 멋진 것을 사용하지 않고, 단순히 4 개의 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 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 tic-tac-toe tic-tac-toe.c
% ./tic-tac-toe
| |
--- + --- + ---
| |
--- + --- + ---
| |
이동을 ""로 입력하십시오 (따옴표 없음, 색인 없음).
X의 이동 : 1 2
| |
--- + --- + ---
| | 엑스
--- + --- + ---
| |
O의 움직임 : 1 2
불법 이동 (이미 취함), 다시 시도
오의 움직임 : 3 3
불법 이동 (보드에서 벗어남), 다시 시도
O의 이동 : 2 2
| |
--- + --- + ---
| | 엑스
--- + --- + ---
| | 영형
X의 이동 : 1 0
| |
--- + --- + ---
X | | 엑스
--- + --- + ---
| | 영형
O의 이동 : 1 1
| |
--- + --- + ---
X | O | 엑스
--- + --- + ---
| | 영형
X의 이동 : 00
X | |
--- + --- + ---
X | O | 엑스
--- + --- + ---
| | 영형
O의 이동 : 2 0
X | |
--- + --- + ---
X | O | 엑스
--- + --- + ---
O | | 영형
X의 이동 : 2 1
X | |
--- + --- + ---
X | O | 엑스
--- + --- + ---
O | X | 영형
O의 움직임 : 0 2
X | | 영형
--- + --- + ---
X | O | 엑스
--- + --- + ---
O | X | 영형
틱택 토! O 승리!
% ./tic-tac-toe
| |
--- + --- + ---
| |
--- + --- + ---
| |
이동을 ""로 입력하십시오 (따옴표 없음, 색인 없음).
X의 이동 : 00
X | |
--- + --- + ---
| |
--- + --- + ---
| |
O의 움직임 : 0 1
X | O |
--- + --- + ---
| |
--- + --- + ---
| |
X의 움직임 : 0 2
X | O | 엑스
--- + --- + ---
| |
--- + --- + ---
| |
O의 이동 : 1 0
X | O | 엑스
--- + --- + ---
O | |
--- + --- + ---
| |
X의 이동 : 1 1
X | O | 엑스
--- + --- + ---
O | X |
--- + --- + ---
| |
O의 이동 : 2 0
X | O | 엑스
--- + --- + ---
O | X |
--- + --- + ---
O | |
X의 이동 : 2 1
X | O | 엑스
--- + --- + ---
O | X |
--- + --- + ---
O | X |
O의 이동 : 2 2
X | O | 엑스
--- + --- + ---
O | X |
--- + --- + ---
O | X | 영형
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이어야합니다.
포인트가 안티 진단에 있는지 확인하는 비 루프 방법 :
`if (x + y == n - 1)`
행, 열, 대각선 검사에서 몇 가지 최적화를 수행했습니다. 특정 열이나 대각선을 확인해야하는 경우 주로 첫 번째 중첩 루프에서 결정됩니다. 따라서 우리는 시간을 절약하기 위해 기둥이나 대각선을 확인하지 않습니다. 이것은 보드 크기가 더 많고 많은 수의 셀이 채워지지 않을 때 큰 영향을 미칩니다.
여기에 대한 자바 코드가 있습니다.
int gameState(int values[][], int boardSz) {
boolean colCheckNotRequired[] = new boolean[boardSz];//default is false
boolean diag1CheckNotRequired = false;
boolean diag2CheckNotRequired = false;
boolean allFilled = true;
int x_count = 0;
int o_count = 0;
/* Check rows */
for (int i = 0; i < boardSz; i++) {
x_count = o_count = 0;
for (int j = 0; j < boardSz; j++) {
if(values[i][j] == x_val)x_count++;
if(values[i][j] == o_val)o_count++;
if(values[i][j] == 0)
{
colCheckNotRequired[j] = true;
if(i==j)diag1CheckNotRequired = true;
if(i + j == boardSz - 1)diag2CheckNotRequired = true;
allFilled = false;
//No need check further
break;
}
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}
/* check cols */
for (int i = 0; i < boardSz; i++) {
x_count = o_count = 0;
if(colCheckNotRequired[i] == false)
{
for (int j = 0; j < boardSz; j++) {
if(values[j][i] == x_val)x_count++;
if(values[j][i] == o_val)o_count++;
//No need check further
if(values[i][j] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}
}
x_count = o_count = 0;
/* check diagonal 1 */
if(diag1CheckNotRequired == false)
{
for (int i = 0; i < boardSz; i++) {
if(values[i][i] == x_val)x_count++;
if(values[i][i] == o_val)o_count++;
if(values[i][i] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}
x_count = o_count = 0;
/* check diagonal 2 */
if( diag2CheckNotRequired == false)
{
for (int i = boardSz - 1,j = 0; i >= 0 && j < boardSz; i--,j++) {
if(values[j][i] == x_val)x_count++;
if(values[j][i] == o_val)o_count++;
if(values[j][i] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
x_count = o_count = 0;
}
if( allFilled == true)
{
for (int i = 0; i < boardSz; i++) {
for (int j = 0; j < boardSz; j++) {
if (values[i][j] == 0) {
allFilled = false;
break;
}
}
if (allFilled == false) {
break;
}
}
}
if (allFilled)
return DRAW;
return INPROGRESS;
}
나는 파티에 늦었지만, 매직 스퀘어 를 사용했을 때 발견 한 한 가지 이점을 지적하고 싶었습니다 . 즉, 다음 턴에 승패를 초래할 스퀘어에 대한 참조를 얻는 데 사용할 수 있다는 것입니다. 게임이 끝날 때 계산하는 데 사용됩니다.
이 마법의 광장을 봅시다 :
4 9 2
3 5 7
8 1 6
먼저 scores이동할 때마다 증가 하는 배열을 설정합니다 . 자세한 내용은 이 답변 을 참조하십시오. 이제 불법적으로 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
}
}
}
실제로 구현에는 숫자 키 처리 (자바 스크립트)와 같은 몇 가지 추가 트릭이 필요하지만, 매우 간단하고 레크리에이션 수학을 즐겼습니다.
이 알고리즘은 보드의 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;
}
또 다른 옵션은 코드로 테이블을 생성하는 것입니다. 대칭까지 이길 수있는 방법은 가장자리 행, 중간 행 또는 대각선의 세 가지뿐입니다. 이 세 가지를 가지고 가능한 모든 방향으로 돌리십시오.
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을 형성합니다 (아이디어를 얻을 수 있음). Player-1을 나타내려면 '1'을 사용하고 Player-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
이제 우리는 플레이어 1이 a1을 통과하면 Win-1, Win-4, Win-7의 3 가지 변수의 합을 재평가해야한다는 것을 알고 있습니다. 어떤 'Win-?' 변수가 3 또는 6에 도달하면 먼저 게임에서 승리합니다. Win-1 변수가 먼저 6에 도달하면 Player-2가 승리합니다.
이 솔루션은 쉽게 확장 할 수 없다는 것을 이해합니다.
이것은 확인하는 정말 간단한 방법입니다.
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;
}
더 명확하다고 생각하지만 아마도 가장 최적의 방법은 아닙니다.
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;
}
일정한 시간 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));
I developed an algorithm for this as part of a science project once.
You basically recursively divide the board into a bunch of overlapping 2x2 rects, testing the different possible combinations for winning on a 2x2 square.
It is slow, but it has the advantage of working on any sized board, with fairly linear memory requirements.
I wish I could find my implementation
참고URL : https://stackoverflow.com/questions/1056316/algorithm-for-determining-tic-tac-toe-game-over
반응형
'code' 카테고리의 다른 글
| WPF의 링크 버튼 (0) | 2020.09.11 |
|---|---|
| void 포인터를 삭제하는 것이 안전합니까? (0) | 2020.09.11 |
| MySQL DECLARE의 SELECT INTO 변수로 인해 구문 오류가 발생합니까? (0) | 2020.09.11 |
| pkg-config 검색 경로에서 패키지 cairo를 찾을 수 없습니다. (0) | 2020.09.11 |
| 정의되지 않은 동작을 가진 분기는 도달 할 수없는 것으로 간주되고 데드 코드로 최적화 될 수 있습니까? (0) | 2020.09.10 |