algorithm - poda - ¿Cómo encontrar al ganador de un juego de tic-tac-toe de cualquier tamaño?

tic tac toe minimax c++

Question

Esta es una pregunta de entrevista . "¿Cómo determinarías si alguien ha ganado un juego de tic-tac-toe en un tablero de cualquier tamaño?" Escuché que la complejidad del algoritmo era O (1). Tiene sentido ? ¿Alguien puede explicar el algoritmo?

Answer 1

Este problema, y ​​un montón de problemas relacionados, se pueden resolver en tiempo O (1), suponiendo que al menos las regiones de memoria existen y suponiendo que una tabla de búsqueda puede ser precomputada. Esta solución no requiere un seguimiento de estado previo, como describen otras respuestas, y la parte del algoritmo en tiempo de ejecución no requiere sumar columnas o filas, como describen otras respuestas.

Trate el estado de la placa n * n como un solo entero B. Para hacer esto, represente una sola celda c en la posición (x, y) como un entero donde = 0 indica O, = 1 indica X, y = 2 indica una celda vacía.

A continuación, representa cada cuadrado como:

Luego, represente a todo el estado del consejo B como:

Asumiendo que usted ha representado a su tablero de esta manera, puede mirar la posición de memoria B dentro de una tabla precalculada que describe la respuesta a la pregunta dada.

La codificación que he proporcionado puede representar cualquier configuración de la tabla n * n tic-tac-toe de forma compacta, incluidas las posiciones a las que no se puede llegar en el juego normal. Sin embargo, puede usar cualquier método de codificación de placa único que desee, como cadenas o matrices, siempre que interprete la representación de la placa como un entero largo y único, indexando en una tabla de soluciones precomputadas. He proporcionado una función hash perfecta aquí, pero existen muchas otras.

Esta representación en el tablero también permite desventajas similares a las de un jugador que recibe un número arbitrario de movimientos iniciales gratuitos.

Curiosamente, si tiene suficiente memoria, en este punto también puede buscar respuestas a preguntas tales como si el juego actual se gana o se pierde con el juego perfecto, cuál es el movimiento ideal desde la posición y si el juego es una victoria garantizada. Pérdida, cuántos movimientos máximos existen para ganar o perder. Esta técnica se utiliza, de manera importante, en el ajedrez informático; La tabla de búsqueda que todos usan se conoce como la base de tabla Nalimov .

La generalización de tic-tac-toe en cualquier tablero de tamaño, donde gana el jugador que consigue k piedras en fila, se llama m, n, k juego y hay muchas pruebas interesantes sobre este tipo de juego.

tl: dr; Si va por un récord de velocidad, es casi imposible superar la tabla de búsqueda humilde.

Answer 2

He escrito una entrada de blog para esta pregunta .

Lo esencial es que mantienes un registro de la cantidad de X que se han colocado en cada fila / columna + 2 diagonales a medida que avanza el juego.

Luego, cada vez que el jugador termina su turno, verifica si la fila y la columna de la última coordenada colocada contienen N números de X. Si es así, entonces el jugador ha ganado.

Answer 3

La forma más rápida de detectar la condición de ganancia es hacer un seguimiento de todas las filas, columnas, diagonales y puntajes anti-diagonales.

Digamos que tienes una cuadrícula de 3x3. Cree una matriz de puntuación de tamaño 2 * 3 + 2 que contendrá las siguientes puntuaciones [row1, row2, row3, col1, col2, col3, diag1, diag2] . Por supuesto no te olvides de inicializarlo con 0.

Después de cada movimiento, sumas +1 para el jugador 1 o restas -1 para el jugador 2 como sigue.

puntuación [fila] + = punto; // donde el punto es +1 o -1

puntuación [gridSize + col] + = punto;

if (row == col) score [2 * gridSize] + = point;

puntaje de [2 * gridSize + 1] + = point (gridSize - 1 - col == row) + = punto;

Luego, todo lo que tiene que hacer es iterar sobre la matriz de puntuación una vez y detectar +3 o -3 (GRID_SIZE o -GRID_SIZE).

Sé que el código dice más que las palabras, así que aquí hay un prototipo en PHP. Es bastante sencillo, así que no creo que tenga problemas para traducirlo a otro idioma.

<?php

class TicTacToe {
    const PLAYER1 = ''X'';
    const PLAYER1_POINT = 1;

    const PLAYER2 = ''O'';
    const PLAYER2_POINT = -1; // must be the opposite of PLAYER1_POINT

    const BLANK = '''';

    /**
    * Level size.
    */
    private $gridSize;

    /** 
    * Level data.
    * Two dimensional array of size GRID_SIZE x GRID_SIZE.
    * Each player move is stored as either ''X'' or ''O''
    */
    private $grid;

    /**
    * Score array that tracks score for rows, cols and diagonals.
    * e.g. for 3x3 grid [row1, row2, row3, col1, col2, col3, diag1, diag2]
    */
    private $score;

    /**
    * Avaialable moves count for current game.
    */
    private $movesLeft = 0;

    /**
    * Winner of the game. 
    */
    private $winner = null;

    public function __construct($size = 3) {
        $this->gridSize = $size;
        $this->grid = array();
        for ($i = 0; $i < $this->gridSize; ++$i) {
            $this->grid[$i] = array_fill(0, $this->gridSize, self::BLANK);
        }

        $this->score = array_fill(0, 2*$this->gridSize + 2, 0);
        $this->movesLeft = $this->gridSize * $this->gridSize;
        $this->winner = null;
    }

    public function getWinner() {
        return $this->winner;
    }

    public function displayGrid() {
        $this->display("--------/n");
        for ($row = 0; $row < $this->gridSize; ++$row) {
            for ($col = 0; $col < $this->gridSize; ++$col) {
                if (self::BLANK == $this->grid[$row][$col]) $this->display(''  '');
                else $this->display($this->grid[$row][$col].'' '');
            }
            $this->display("/n");
        }
        $this->display("--------/n");
    }

    public function play(MoveInput $input) {
        $this->display("NEW GAME/n");
        $nextPlayer = self::PLAYER1;
        $done = false;
        while(!$done) { 
            $move = $input->getNextMove($nextPlayer);
            if (NULL == $move) {
                $this->display("ERROR! NO MORE MOVES/n");
                break;
            }

            $error = false;
            $this->makeMove($move[''player''], $move[''row''], $move[''col''], $error);
            if ($error) {
                $this->display("INVALID MOVE! Please try again./n");
                continue;
            }
            $nextPlayer = ($nextPlayer == self::PLAYER1) ? self::PLAYER2 : self::PLAYER1;
            $this->displayGrid();
            $done = $this->checkScore();
        }
    }

    private function makeMove($player, $row, $col, &$error) {
        $error = false;
        if (!$this->isValidMove($row, $col) || self::BLANK != $this->grid[$row][$col]) {
            $error = true;
            return;
        }

        $this->grid[$row][$col] = $player;
        --$this->movesLeft;

        $point = 0;
        if (self::PLAYER1 == $player) $point = self::PLAYER1_POINT;
        if (self::PLAYER2 == $player) $point = self::PLAYER2_POINT;

        $this->score[$row] += $point;
        $this->score[$this->gridSize + $col] += $point;
        if ($row == $col) $this->score[2*$this->gridSize] += $point;
        if ($this->gridSize - 1 - $col == $row) $this->score[2*$this->gridSize + 1] += $point;
    }

    private function checkScore() {
        if (0 == $this->movesLeft) {
            $this->display("game is a DRAW/n");
            return true;
        }

        for ($i = 0; $i < count($this->score); ++$i) {
            if ($this->player1TargetScore() == $this->score[$i]) {
                $this->display("player 1 WIN/n");
                $this->winner = self::PLAYER1;
                return true;
            }

            if ($this->player2TargetScore() == $this->score[$i]) {
                $this->display("player 2 WIN/n");
                $this->winner = self::PLAYER2;
                return true;
            }
        }

        return false;
    }

    private function isValidMove($row, $col) {
        return (0 <= $row && $row < $this->gridSize) &&
                (0 <= $col && $col < $this->gridSize);
    }

    private function player1TargetScore() {
        return $this->gridSize * self::PLAYER1_POINT;
    }

    private function player2TargetScore() {
        return $this->gridSize * self::PLAYER2_POINT;
    }

    private function display($string) {
        echo $string;
    }
}

interface MoveInput {
    public function getNextMove($player);
}

class QueuedMoveInput implements MoveInput {
    private $moves;

    public function __construct($movesArray) {
        $this->moves = $movesArray;
    }

    public function getNextMove($player) {
        return array_shift($this->moves);
    }
}

class InteractiveMoveInput implements MoveInput {
    public function getNextMove($player) {
        while(true) {
            echo "Please enter next move for player $player: [row,col] ";
            $line = trim(fgets(STDIN));
            list($row, $col) = sscanf($line, "%D,%D");
            if (is_numeric($row) && is_numeric($col)) {
                return array(''player'' => $player, ''row'' => $row, ''col'' => $col);
            }
        }
    }
}

// helpers
function p1($row, $col) {
    return array(''player'' => TicTacToe::PLAYER1, ''row'' => $row, ''col'' => $col);
}

function p2($row, $col) {
    return array(''player'' => TicTacToe::PLAYER2, ''row'' => $row, ''col'' => $col);
}

// TESTING!!!!! ;]

// GAME 1 - testing diagonal (0,0) -> (2,2) win condition
$game = new TicTacToe();
$moves = new QueuedMoveInput(array(p1(1,1), p2(0,1), p1(2,0), p2(0,2), p1(0,0), p2(1,0), p1(2,2), p2(2,1)));
$game->play($moves);
assert($game->getWinner() == TicTacToe::PLAYER1);

// GAME 2 - using invalid move, testing straight line (0,0) -> (0,2) win condition
$game = new TicTacToe();
$moves = new QueuedMoveInput(array(p1(1,1), p2(1,1), p2(2,0), p1(2,1), p2(0,1), p1(2,2), p2(0,0), p1(1,0), p2(0,2)));
$game->play($moves);
assert($game->getWinner() == TicTacToe::PLAYER2);

// GAME 3 - testing draw condition
$game = new TicTacToe();
$moves = new QueuedMoveInput(array(p1(1,1), p2(2, 2), p1(1,2), p2(1,0), p1(2,0), p2(0,2), p1(0,1), p2(2,1), p1(0,0)));
$game->play($moves);
assert($game->getWinner() == NULL);

// GAME 4 - testing diagonal (2,0) -> (0,2) win condition
$game = new TicTacToe();
$moves = new QueuedMoveInput(array(p1(2,0), p2(1, 2), p1(0,2), p2(2,2), p1(0,1), p2(0,0), p1(1,1)));
$game->play($moves);
assert($game->getWinner() == TicTacToe::PLAYER1);

// GAME 5 - testing straight line (0,0) -> (2,0) win condition
$game = new TicTacToe();
$moves = new QueuedMoveInput(array(p2(1,1), p1(0,0), p2(0,2), p1(2,0), p2(2,1), p1(1,0)));
$game->play($moves);
assert($game->getWinner() == TicTacToe::PLAYER1);

// GAME 6 - 5x5 grid, testing diagonal (0,0) -> (4,4) win condition
$game = new TicTacToe(5);
$moves = new QueuedMoveInput(array(p1(1,1), p2(0,1), p1(2,0), p2(0,2), p1(0,0), p2(1,0), p1(2,2), p2(4,2), p1(3,3), p2(4,3), p1(4,4)));
$game->play($moves);
assert($game->getWinner() == TicTacToe::PLAYER1);

// GAME 7 - Interactive game.
$game = new TicTacToe();
$game->play(new InteractiveMoveInput());

Espero que ayude ;]

Answer 4

La respuesta está justo en esa página, pero lo explicaré de todos modos.

La complejidad del algoritmo es O (1) para determinar si un movimiento dado ganará el juego. No puede ser O (1) en general, ya que necesita conocer el estado de la junta para determinar un ganador. Sin embargo, puede generar ese estado de manera incremental de manera que pueda determinar si un movimiento gana en O (1).

Para comenzar, tenga una serie de números para cada fila, columna y diagonal para cada jugador. En cada movimiento, incremente los elementos correspondientes al jugador para la fila, columna y diagonal (el movimiento puede no estar necesariamente en una diagonal) influenciado por ese movimiento. Si la cuenta para ese jugador es igual a la dimensión del tablero, ese jugador gana.

Answer 5

También me hicieron esta pregunta en una entrevista de programación. "Dado un tablero de tres en raya, cómo verificar el movimiento fue un movimiento ganador en tiempo CONSTANTE"

Me tomó más de 20 minutos, pero PIENSO que pude encontrar la respuesta y resolverla en O (1)

Así que digamos que comencemos con una tabla simple de 3 por 3 de tic - tac, ponga un número correspondiente a cada bloque en la tabla 123 456 789

Así que mi respuesta a la pregunta es bastante simple, HASH todas las combinaciones ganadoras en una tabla Hash, como 123, 456, 789, 159 etc ...

Tenga dos listas de números para realizar un seguimiento del movimiento del jugador individual

El alg se describe a continuación

    So when player_1 puts a X on a square, he will get the corresponding
    number into his number list
    When player_2 puts a O on a square, he will also get the corresponding
    number into his number list.
    At the end of every round, look through the Hash table to see if any 
    of the two players have the winning combination

Así que creo que eso es O (1)

Answer 6

    class TicTacToe
{

    //http://basicalgos.blogspot.com/#!/2012/03/13-test-winning-condition-of-tic-tac.html
    //No time for test case

    int[,] board = null;

    int diag = 0;
    int antiDiag = 0;
    int[] rows = null;
    int[] cols = null;


    int diagonalLen = 0;

    public TicTacToe(int rowLen, int colLen)
    {
        board = new int[rowLen, colLen];

        rows = new int[rowLen];
        cols = new int[colLen];

        if (rowLen == colLen)
            diag = (int)(rowLen * Math.Sqrt(2));//Square formula
        else
            diagonalLen = (int)Math.Sqrt(Math.Pow(rowLen, 2) + Math.Pow(colLen, 2));//rectangle formula

    }

    public bool hasWon(int rowIdx, int colIdx, int player)
    {
        if (player == 1)
        {
            rows[rowIdx]++;
            cols[colIdx]++;

            if (rowIdx == colIdx) diag++;
            if (rowIdx + colIdx == rows.Length - 1) antiDiag++;//This is IMPORTANT finding.............

        }
        else
        {
            rows[rowIdx]--;
            cols[colIdx]--;

            if (rowIdx == colIdx) diag--;
            if (rowIdx + colIdx == rows.Length - 1) antiDiag--;
        }

        return diag == diagonalLen || rows[rowIdx] == rows.Length || cols[colIdx] == cols.Length || antiDiag == diagonalLen;
    }

    public void markOnBoard(int row, int col, int player)
    {
        if (player == 1)
            board[row, col]++;
        else
            board[row, col]--;
    }
}