unbeatable toe tic tac poda algoritmo alfa java algorithm tic-tac-toe

java - poda - tic tac toe minimax



Algoritmo para determinar el juego Tic Tac Toe Over (20)

He escrito un juego de tres en raya en Java, y mi método actual de determinar el final de las cuentas del juego para los siguientes escenarios posibles para el final del juego:

  1. El tablero está lleno, y aún no se ha declarado ganador: el juego es un empate.
  2. Cross ha ganado.
  3. Circle ha ganado.

Desafortunadamente, para hacerlo, lee a través de un conjunto predefinido de estos escenarios desde una tabla. Esto no es necesariamente malo teniendo en cuenta que solo hay 9 espacios en un tablero, y por lo tanto, la tabla es algo pequeña, pero ¿hay una mejor manera algorítmica de determinar si el juego ha terminado? La determinación del hecho de si alguien ha ganado o no es la base del problema, ya que comprobar si 9 espacios están llenos es trivial.

El método de tabla podría ser la solución, pero si no, ¿qué es? Además, ¿qué pasa si el tablero no tiene el tamaño n=9 ? ¿Qué pasaría si fuera una placa mucho más grande, digamos n=16 , n=25 , y así sucesivamente, haciendo que el número de elementos colocados consecutivamente para ganar sea x=4 , x=5 , etc.? Un algoritmo general para usar para todos n = { 9, 16, 25, 36 ... } ?

¿Qué tal este pseudocódigo?

Después de que un jugador deja una pieza en la posición (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

Usaría una matriz de char [n, n], con O, X y espacio para vacío.

  1. sencillo.
  2. Un bucle
  3. Cinco variables simples: 4 enteros y un booleano.
  4. Escalas a cualquier tamaño de n.
  5. Solo revisa la pieza actual.
  6. Sin magia :)

Acabo de escribir esto para mi clase de programación C.

Lo estoy publicando porque ninguno de los otros ejemplos aquí funcionará con cuadrícula rectangular de cualquier tamaño, y cualquier número N en una fila marcas consecutivas para ganar.

Encontrarás mi algoritmo, tal como está, en la función checkWinner() . No usa números mágicos ni nada sofisticado para buscar un ganador, simplemente usa cuatro bucles for - El código está bien comentado, así que lo dejaré hablar por sí mismo, supongo.

// 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.

Aquí está mi solución que escribí para un proyecto en el que estoy trabajando en javascript. Si no te importa el costo de memoria de algunas matrices, probablemente sea la solución más rápida y simple que puedas encontrar. Asume que sabes la posición del último movimiento.

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

Aquí hay una solución que se me ocurrió, esta almacena los símbolos como caracteres y usa el valor int del char para descubrir si X o O ha ganado (mira el código del árbitro)

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

También aquí están mis pruebas unitarias para validar que realmente funciona

import static com.agilefaqs.tdd.demo.TicTacToe.BLANK; import static org.junit.Assert.assertArrayEquals; import static org.junit.Assert.assertEquals; import org.junit.Test; public class TicTacToeTest { private TicTacToe game = new TicTacToe(3); @Test public void allCellsAreEmptyInANewGame() { assertBoardIs(new char[][] { { BLANK, BLANK, BLANK }, { BLANK, BLANK, BLANK }, { BLANK, BLANK, BLANK } }); } @Test(expected = IllegalArgumentException.class) public void boardHasToBeMinimum3x3Grid() { new TicTacToe(2); } @Test public void firstPlayersMoveMarks_X_OnTheBoard() { assertEquals("continue", game.move(1, 1)); assertBoardIs(new char[][] { { BLANK, BLANK, BLANK }, { BLANK, ''X'', BLANK }, { BLANK, BLANK, BLANK } }); } @Test public void secondPlayersMoveMarks_O_OnTheBoard() { game.move(1, 1); assertEquals("continue", game.move(2, 2)); assertBoardIs(new char[][] { { BLANK, BLANK, BLANK }, { BLANK, ''X'', BLANK }, { BLANK, BLANK, ''O'' } }); } @Test public void playerCanOnlyMoveToAnEmptyCell() { game.move(1, 1); assertEquals("(1,1) is already occupied", game.move(1, 1)); } @Test public void firstPlayerWithAllSymbolsInOneRowWins() { game.move(0, 0); game.move(1, 0); game.move(0, 1); game.move(2, 1); assertEquals("X won the game!", game.move(0, 2)); } @Test public void firstPlayerWithAllSymbolsInOneColumnWins() { game.move(1, 1); game.move(0, 0); game.move(2, 1); game.move(1, 0); game.move(2, 2); assertEquals("O won the game!", game.move(2, 0)); } @Test public void firstPlayerWithAllSymbolsInPrincipalDiagonalWins() { game.move(0, 0); game.move(1, 0); game.move(1, 1); game.move(2, 1); assertEquals("X won the game!", game.move(2, 2)); } @Test public void firstPlayerWithAllSymbolsInMinorDiagonalWins() { game.move(0, 2); game.move(1, 0); game.move(1, 1); game.move(2, 1); assertEquals("X won the game!", game.move(2, 0)); } @Test public void whenAllCellsAreFilledTheGameIsADraw() { game.move(0, 2); game.move(1, 1); game.move(1, 0); game.move(2, 1); game.move(2, 2); game.move(0, 0); game.move(0, 1); game.move(1, 2); assertEquals("Its a Draw!", game.move(2, 0)); } private void assertBoardIs(char[][] expectedBoard) { assertArrayEquals(expectedBoard, game.displayBoard()); } }

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

Esto es similar a la respuesta de Osama ALASSIRY , pero intercambia el espacio constante y el tiempo lineal para el espacio lineal y el tiempo constante. Es decir, no hay bucle después de la inicialización.

Inicialice un par (0,0) para cada fila, cada columna y las dos diagonales (diagonal y anti-diagonal). Estos pares representan el acumulado (sum,sum) de las piezas en la fila, columna o diagonal correspondiente, donde

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

Cuando un jugador coloca una pieza, actualice el par de filas correspondiente, el par de columnas y los pares diagonales (si están en las diagonales). Si cualquier fila, columna o par diagonal recientemente actualizado es igual a (n,0) o (0,n) entonces A o B ganaron, respectivamente.

Análisis asintótico

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

Para el uso de memoria, usa números enteros 4*(n+1) .

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

Ejercicio: ¿Puedes ver cómo probar un sorteo en O (1) tiempo por movimiento? Si es así, puedes terminar el juego temprano en un sorteo.

Hice algunas optimizaciones en la fila, col, controles diagonales. Se decide principalmente en el primer ciclo anidado si necesitamos verificar una columna o diagonal en particular. Por lo tanto, evitamos el control de columnas o diagonales que ahorran tiempo. Esto tiene un gran impacto cuando el tamaño de la placa es mayor y un número significativo de las celdas no se llenan.

Aquí está el código de Java para eso.

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

Llego tarde a la fiesta, pero quería señalar un beneficio que encontré utilizando un cuadrado mágico , es decir, que se puede usar para obtener una referencia al cuadrado que causaría la ganancia o pérdida en el siguiente turno, en lugar de solo se usa para calcular cuándo termina un juego.

Toma este cuadrado mágico:

4 9 2 3 5 7 8 1 6

Primero, configure una matriz de scores que se incrementa cada vez que se realiza un movimiento. Vea esta respuesta para más detalles. Ahora si ilegalmente jugamos X dos veces seguidas en [0,0] y [0,1], la matriz de scores ve así:

[7, 0, 0, 4, 3, 0, 4, 0];

Y el tablero se ve así:

X . . X . . . . .

Entonces, todo lo que tenemos que hacer para obtener una referencia de qué casilla ganar / bloquear es:

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

En realidad, la implementación requiere algunos trucos adicionales, como manejar las teclas numeradas (en JavaScript), pero me pareció bastante sencillo y disfruté de las matemáticas recreativas.

Me gusta este algoritmo, ya que utiliza una representación de 1x9 vs 3x3 del tablero.

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

Me hicieron la misma pregunta en una de mis entrevistas. Mis pensamientos: inicializar la matriz con 0. Mantener 3 matrices 1) sum_row (tamaño n) 2) sum_column (tamaño n) 3) diagonal (tamaño 2)

Para cada movimiento por (X) disminuya el valor del cuadro por 1 y para cada movimiento por (0) incremente por 1. En cualquier punto si la fila / columna / diagonal que se ha modificado en movimiento actual tiene suma -3 o + 3 significa que alguien ha ganado el juego. Para un sorteo, podemos usar el enfoque anterior para mantener la variable moveCount.

¿Crees que me estoy perdiendo algo?

Editar: Lo mismo se puede usar para la matriz nxn. La suma debe ser de +3 o -3.

No conozco Java tan bien, pero sí conozco C, así que probé la idea cuadrada mágica de Adk (junto con la restricción de búsqueda de 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 y prueba bien.

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

Eso fue divertido, gracias!

En realidad, al pensarlo, no necesitas un cuadrado mágico, solo un conteo por cada fila / columna / diagonal. Esto es un poco más fácil que generalizar un cuadrado mágico para n × n matrices, ya que solo necesita contar para n .

Otra opción: genera tu tabla con código. Hasta la simetría, solo hay tres formas de ganar: fila de borde, fila central o diagonal. Tome esos tres y gírelos de todas las maneras posibles:

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

Estas simetrías pueden tener más usos en su código de juego: si llega a un tablero que ya ha visto una versión girada, puede simplemente tomar el valor almacenado en caché o el mejor movimiento guardado en caché desde ese (y deshacerlo de nuevo). Esto suele ser mucho más rápido que evaluar el subárbol del juego.

(Al mover hacia la izquierda y hacia la derecha puede ayudar de la misma manera; no fue necesario aquí porque el conjunto de rotaciones de los patrones ganadores es simétrico en espejo).

Si el tablero es n × n, entonces hay n filas, n columnas y 2 diagonales. Compruebe cada uno de ellos para todas las X o todas las O para encontrar un ganador.

Si solo se necesitan x < n cuadrados consecutivos para ganar, entonces es un poco más complicado. La solución más obvia es verificar cada x x x cuadrado para un ganador. Aquí hay un código que demuestra eso.

(En realidad, no probé esta * tos *, pero compiló en el primer intento, ¡yay!)

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

Usted sabe que un movimiento ganador solo puede suceder después de que X o O haya realizado su movimiento más reciente, por lo que solo puede buscar fila / columna con diag opcional que esté contenido en ese movimiento para limitar su espacio de búsqueda al intentar determinar un tablero ganador. Además, dado que hay un número fijo de movimientos en un juego de dibujar tres en raya una vez que se realiza el último movimiento si no fue un movimiento ganador, es por defecto un juego de sorteo.

editar: este código es para un n por el tablero con n en una fila para ganar (3x3 requisitos del tablero 3 en una fila, etc.)

editar: código agregado para verificar anti diag, no pude encontrar una forma de no bucle para determinar si el punto estaba en el antidiagnóstico, por eso falta ese paso

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

una forma no loop para determinar si el punto estaba en el anti diag:

`if (x + y == n - 1)`

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

// O(8) boolean isWinner(short X) { for (int i = 0; i < 8; i++) if ((X & winCombinations[i]) == winCombinations[i]) return true; return false; } short[] winCombinations = new short[]{ 7, 7 << 3, 7 << 6, // horizontal 73, 73 << 1, 73 << 2, // vertical 273, // diagonal 84 // anti-diagonal }; for (short X = 0; X < 511; X++) System.out.println(isWinner(X));

How about a following approach for 9 slots? Declare 9 integer variables for a 3x3 matrix (a1,a2....a9) where a1,a2,a3 represent row-1 and a1,a4,a7 would form column-1 (you get the idea). Use ''1'' to indicate Player-1 and ''2'' to indicate Player-2.

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

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

I do understand that this solution is not scalable easily.

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

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

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

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

This is a really simple way to check.

public class Game() { Game player1 = new Game(''x''); Game player2 = new Game(''o''); char piece; Game(char piece) { this.piece = piece; } public void checkWin(Game player) { // check horizontal win for (int i = 0; i <= 6; i += 3) { if (board[i] == player.piece && board[i + 1] == player.piece && board[i + 2] == player.piece) endGame(player); } // check vertical win for (int i = 0; i <= 2; i++) { if (board[i] == player.piece && board[i + 3] == player.piece && board[i + 6] == player.piece) endGame(player); } // check diagonal win if ((board[0] == player.piece && board[4] == player.piece && board[8] == player.piece) || board[2] == player.piece && board[4] == player.piece && board[6] == player.piece) endGame(player); }

}