Algoritmo per determinare la fine del gioco Tic Tac Toe
https://stackoverflow.com/questions/1056316
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho scritto un gioco di tic-tac-toe in Java e il mio attuale metodo per determinare la fine dei conti del gioco per i seguenti possibili scenari per il gioco:
- Il tabellone è pieno e nessun vincitore è stato ancora dichiarato: il gioco è un pareggio.
- Cross ha vinto.
- Il cerchio ha vinto.
Sfortunatamente, per farlo, legge una serie predefinita di questi scenari da una tabella. Ciò non è necessariamente negativo considerando che ci sono solo 9 spazi su una tavola, e quindi il tavolo è piuttosto piccolo, ma esiste un modo algoritmico migliore per determinare se il gioco è finito? La determinazione del fatto che qualcuno abbia vinto o meno è la causa del problema, dal momento che controllare se 9 spazi sono pieni è banale.
Il metodo della tabella potrebbe essere la soluzione, ma in caso contrario, cos'è? Inoltre, se la scheda non avesse dimensioni n=9? E se fosse una tavola molto più grande, diciamo n=16, n=25 e così via, facendo sì che il numero di oggetti posizionati consecutivamente per vincere sia x=4, x=5, ecc.? Un algoritmo generale da utilizzare per tutti n = { 9, 16, 25, 36 ... }?
Soluzione
Sai che una mossa vincente può avvenire solo dopo che X o O hanno effettuato la loro mossa più recente, quindi puoi cercare solo riga / colonna con diag opzionale contenuto in quella mossa per limitare lo spazio di ricerca quando cerchi di determinare una vincita tavola. Inoltre, dato che ci sono un numero fisso di mosse in una partita di pareggio una volta che l'ultima mossa è stata effettuata se non si trattava di una mossa vincente, è di default una partita di pareggio.
modifica: questo codice è per una scheda n by n con n di fila per vincere (3x3 richieste di carte 3 di fila, ecc.)
modifica: aggiunto codice per controllare l'anti diag, non sono riuscito a capire un modo non loop per determinare se il punto era sull'anti diag, quindi ecco perché manca quel passaggio
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
}
}
}
Altri suggerimenti
puoi usare un quadrato magico http://mathworld.wolfram.com/MagicSquare.html se qualsiasi riga, colonna o diag aggiunge fino a 15, allora un giocatore ha vinto.
È simile alla La risposta di Osama ALASSIRY , ma scambia spazio costante e tempo lineare con spazio lineare e tempo costante. Cioè, non c'è loop dopo l'inizializzazione.
Inizializza una coppia (0,0) per ogni riga, ogni colonna e le due diagonali (diagonale & amp; anti-diagonale). Queste coppie rappresentano il (sum,sum) accumulato dei pezzi nella riga, colonna o diagonale corrispondente, dove
A piece from player A has value (1,0) A piece from player B has value (0,1)
Quando un giocatore piazza un pezzo, aggiorna la coppia di righe, coppie di colonne e coppie diagonali corrispondenti (se sulle diagonali). Se qualsiasi riga, colonna o diagonale appena aggiornata è uguale a (n,0) o (0,n), allora A o B hanno vinto rispettivamente.
Analisi asintotica:
O(1) time (per move) O(n) space (overall)
Per l'uso della memoria, si utilizza 4*(n+1) numeri interi.
two_elements*n_rows + two_elements*n_columns + two_elements*two_diagonals = 4*n + 4 integers = 4(n+1) integers
Esercizio: riesci a vedere come testare un pareggio in O (1) tempo per mossa? In tal caso, puoi terminare il gioco in anticipo con un pareggio.
Che ne dici di questo pseudocodice:
Dopo che un giocatore mette un pezzo in posizione (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
Userei un array di caratteri [n, n], con O, X e spazio per vuoto.
- semplice.
- Un ciclo.
- Cinque variabili semplici: 4 numeri interi e un valore booleano.
- Ridimensiona a qualsiasi dimensione di n.
- Controlla solo il pezzo corrente.
- Nessuna magia. :)
Ecco la mia soluzione che ho scritto per un progetto a cui sto lavorando in javascript. Se non ti dispiace il costo della memoria di alcuni array, è probabilmente la soluzione più semplice e veloce che troverai. Presuppone che tu conosca la posizione dell'ultima mossa.
/*
* 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;
}
L'ho appena scritto per la mia classe di programmazione C.
Lo sto pubblicando perché nessuno degli altri esempi qui funzionerà con una griglia rettangolare di qualsiasi dimensione e qualsiasi numero N di fila consecutivi per vincere .
Troverai il mio algoritmo, così com'è, nella funzione checkWinner(). Non usa numeri magici o niente di speciale per cercare un vincitore, ne usa semplicemente quattro per i loop - Il codice è ben commentato, quindi immagino che parlerà da solo.
// 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.
Se la scheda è n & # 215; n quindi ci sono n righe, n colonne e 2 diagonali. Controlla ognuno di questi per tutte le X o tutte le O per trovare un vincitore.
Se ci vuole solo x < Vincere n quadrati consecutivi, quindi è un po 'più complicato. La soluzione più ovvia è controllare ogni x & # 215; x quadrato per un vincitore. Ecco un po 'di codice che lo dimostra.
(In realtà non ho provato questa * tosse *, ma ha compilato al primo tentativo, yay me!)
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;
}
}
}
Non conosco Java così bene, ma conosco C, quindi ho provato idea quadrata magica di adk (insieme a Limitazione della ricerca di 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;
}
Compila e verifica bene.
% 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 :(
%
È stato divertente, grazie!
In realtà, a pensarci bene, non è necessario un quadrato magico, ma solo un conteggio per ogni riga / colonna / diagonale. Questo è un po 'più facile che generalizzare un quadrato magico a n & # 215; <=> matrici, poiché devi solo contare su <=>.
Mi è stata posta la stessa domanda in una delle mie interviste. I miei pensieri: Inizializza la matrice con 0. Mantenere 3 matrici 1) sum_row (dimensione n) 2) sum_column (dimensione n) 3) diagonale (misura 2)
Per ogni mossa di (X) decrementa il valore della casella di 1 e per ogni mossa di (0) incrementale di 1. In qualsiasi momento se la riga / colonna / diagonale che è stata modificata nella mossa corrente ha una somma di -3 o +3 significa che qualcuno ha vinto la partita. Per un pareggio possiamo usare l'approccio sopra per mantenere la variabile moveCount.
Pensi che mi manchi qualcosa?
Modifica: lo stesso può essere usato per la matrice nxn. La somma dovrebbe essere pari a +3 o -3.
un modo non-loop per determinare se il punto era sull'anti diag:
`if (x + y == n - 1)`
Ho fatto delle ottimizzazioni nei controlli di riga, col, diagonali. È deciso principalmente nel primo ciclo nidificato se dobbiamo controllare una colonna o una diagonale particolare. Quindi, evitiamo di controllare colonne o diagonali risparmiando tempo. Ciò ha un grande impatto quando la dimensione della scheda è maggiore e un numero significativo di celle non viene riempito.
Ecco il codice Java per quello.
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;
}
Sono in ritardo per la festa, ma volevo sottolineare un vantaggio che ho riscontrato usando una magic quadrato , vale a dire che può essere utilizzato per ottenere un riferimento al quadrato che causerebbe la vincita o la perdita nel turno successivo, anziché essere utilizzato solo per calcolare quando una partita è finita.
Prendi questo quadrato magico:
4 9 2
3 5 7
8 1 6
Innanzitutto, imposta un array scores che viene incrementato ogni volta che viene effettuata una mossa. Vedi questa risposta per i dettagli. Ora se giochiamo illegalmente X due volte di seguito in [0,0] e [0,1], l'array <=> appare così:
[7, 0, 0, 4, 3, 0, 4, 0];
E il tabellone appare così:
X . .
X . .
. . .
Quindi, tutto ciò che dobbiamo fare per ottenere un riferimento a quale quadrato su cui vincere / bloccare è:
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
}
}
}
In realtà, l'implementazione richiede alcuni trucchi aggiuntivi, come la gestione di chiavi numerate (in JavaScript), ma l'ho trovato abbastanza semplice e mi è piaciuta la matematica ricreativa.
Mi piace questo algoritmo in quanto utilizza una rappresentazione 1x9 vs 3x3 della scheda.
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;
}
Un'altra opzione: genera la tua tabella con il codice. Fino alla simmetria, ci sono solo tre modi per vincere: bordo, fila centrale o diagonale. Prendi quei tre e girali in ogni modo possibile:
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))))
Queste simmetrie possono avere più usi nel tuo codice di gioco: se arrivi a una scheda di cui hai già visto una versione ruotata, puoi semplicemente prendere il valore memorizzato nella cache o muoverti nella cache migliore da quella (e sbloccarlo indietro). Questo di solito è molto più veloce rispetto alla valutazione della sottostruttura del gioco.
(Capovolgere sinistra e destra può aiutare allo stesso modo; non è stato necessario qui perché l'insieme di rotazioni degli schemi vincenti è simmetrico allo specchio.)
Ecco una soluzione che ho trovato, che memorizza i simboli come caratteri e usa il valore int del personaggio per capire se X o O ha vinto (guarda il codice dell'Arbitro)
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;
}
}
}
Anche qui ci sono i miei test unitari per convalidare che funziona davvero
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());
}
}
Soluzione completa: https://github.com/nashjain/tictactoe/tree/master / java
Che ne dici di un seguente approccio per 9 slot? Dichiarare 9 variabili intere per una matrice 3x3 (a1, a2 .... a9) in cui a1, a2, a3 rappresentano la riga 1 e a1, a4, a7 formerebbero la colonna 1 (si ottiene l'idea). Usa '1' per indicare il Giocatore-1 e '2' per indicare il Giocatore-2.
Esistono 8 possibili combinazioni vincenti: Win-1: a1 + a2 + a3 (la risposta potrebbe essere 3 o 6 in base al giocatore vinto) 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
Ora sappiamo che se il giocatore incrocia una a1, dobbiamo rivalutare la somma di 3 variabili: Win-1, Win-4 e Win-7. Qualunque sia "Win-?" le variabili raggiungono 3 o 6 prima vince la partita. Se la variabile Win-1 raggiunge per prima 6, vince il Player-2.
Capisco che questa soluzione non è facilmente scalabile.
Questo è un modo davvero semplice per controllare.
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);
}
}
Se ad esempio hai un campo di confine 5 * 5, utilizzo il metodo di controllo successivo:
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;
}
Penso che sia più chiaro, ma probabilmente non è il modo migliore.
Ecco la mia soluzione usando un array bidimensionale:
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;
}
Tempo costante O (8), in media 4 AND brevi. Giocatore = numero breve. Sono necessari ulteriori controlli per assicurarsi che lo spostamento sia valido.
// 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));
Ho sviluppato un algoritmo per questo come parte di un progetto scientifico una volta.
In pratica, dividi la tavola in modo ricorsivo in un mucchio di rect 2x2 sovrapposti, testando le diverse combinazioni possibili per vincere su un quadrato 2x2.
È lento, ma ha il vantaggio di lavorare su schede di qualsiasi dimensione, con requisiti di memoria abbastanza lineari.
Vorrei poter trovare la mia implementazione
