如何找到任何规模的井字游戏的赢家?

答案就在那一页上,不过我还是会解释的。

算法的复杂度为o(1),用于确定给定的移动是否会赢得游戏。一般来说,它不能是O(1),因为您需要知道董事会的状态来确定赢家。但是,可以逐步构建该状态,以便确定移动是否在O(1)中获胜。

首先,为每一行、每一列和每一个玩家的对角线设置一个数字数组。在每次移动中,增加受该移动影响的行、列和对角线(移动不一定是在对角线上)对应于播放器的元素。如果该玩家的计数等于棋盘的尺寸,则该玩家获胜。

检测获胜条件的最快方法是跟踪所有的行、列、对角线和反对角线分数。

假设你有3x3网格。创建大小为2*3+2的分数数组,该数组将保存以下分数 [第1行,第2行,第3行,第1列,第2列,第3列,第1张,第2张] . 当然,不要忘记用0初始化它。

下一步,每次移动后,你为玩家1加+1,或为玩家2减去-1,如下所示。

得分[行]+=分; //其中点是+1或-1

得分[网格大小+列]+=分;

if(row==col)得分[2*gridsize]+=分;

if(gridsize-1-col==row)得分[2*gridsize+1]+=分;

然后,您所要做的就是迭代一次分数数组,然后检测+3或-3(网格大小或-网格大小)。

我知道代码比单词更能说明问题,所以这里有一个PHP的原型。这是非常直截了当的,所以我不认为你会有问题把它翻译成其他语言。

<?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());

希望有帮助;]

此问题以及一系列相关问题可以在o(1)时间内解决,前提是至少 = 内存区域存在,并且假设可以预计算查找表。此解决方案不需要像其他答案所描述的那样进行以前的状态跟踪,并且算法的运行时部分不需要求和列或行,就像其他答案所描述的那样。

将n*n板状态视为单个整数b。为此,将位置(x,y)处的单个单元c表示为整数,其中 ==0 indicates o, ==1 indicates x,and ==2 indicates an empty cell.

接下来,代表每个方块 = as:。

然后,将整个董事会状态B表示为:

假设您已经代表了您的董事会,您可以查看一个预先计算的表中的内存位置B,该表描述了给定问题的答案。

我提供的编码可以紧凑地表示任何n*n tic-tac-toe-board配置,包括在正常播放中无法到达的位置。但是,您可以使用任何您喜欢的唯一的板编码方法,例如字符串或数组,只要您将板表示解释为一个长的、唯一的整数,索引到一个预先计算的解决方案表中。我已经提供了一个这样的函数 Perfect hash function here but many others exist.

提供的该董事会代表还允许类似“围棋”的障碍,允许玩家进行任意数量的自由初始移动。

有趣的是,如果你有足够的记忆力,你也可以在这一点上寻找问题的答案,比如当前游戏是在完美的游戏中赢还是输,从位置上看哪个移动是理想的,如果游戏是有保证的赢或输,那么对于赢或输来说,存在多少个最大的移动。此技术在计算机象棋中使用,这一点很重要;每个人都使用的查找表被称为 nalimov tablebase 。

将tic-tac-toe推广到任何尺寸的棋盘上,在棋盘上连续获得k块石头的玩家获胜,称为 m,n,k game 并且有许多有趣的证据证明这种类型的游戏。

tl:dr;如果你想创一个速度记录,几乎不可能打败低水平的查找表。

内存区域存在,并假定可以预计算查阅表格。该解决方案不需要像其他答案所描述的那样进行以前的状态跟踪,并且算法的运行时部分不需要像其他答案所描述的那样求和列或行。

将n*n板状态视为单个整数b。为此,将位置(x,y)处的单个单元格c表示为整数,其中 =0表示O, =1表示x,和 =2表示空单元格。

接下来,代表每个方块 AS:

然后,将整个董事会状态B表示为:

假设你已经代表了你的董事会,你可以看到记忆位置B在一个预先计算的表,描述了回答问题。

我提供的编码可以紧凑地表示任何n*n tic-tac-toe-board配置,包括在正常播放中无法到达的位置。但是,您可以使用任何您喜欢的唯一的板编码方法,例如字符串或数组,只要您将板表示解释为一个长的、唯一的整数,索引到一个预先计算的解决方案表中。我提供了一个这样的 perfect hash function 但还有很多其他的存在。

这种董事会的代表性也允许像残疾人一样的球员被授予任意数量的自由初始移动。

有趣的是,如果你有足够的记忆力,你也可以在这一点上寻找问题的答案,比如当前游戏是在完美的游戏中赢还是输,从位置上看哪个移动是理想的,如果游戏是有保证的赢或输,那么对于赢或输来说,存在多少个最大的移动。这项技术在计算机象棋中被使用,重要的是,每个人使用的查找表被称为 Nalimov tablebase .

把井字游戏推广到任何尺寸的棋盘上,在棋盘上连续获得K石头的玩家获胜,称为 m,n,k game 关于这种类型的游戏有很多有趣的证据。

TL:博士,如果你想创下一个速度记录,那就几乎不可能超越低水平的查找表。

我刚在节目采访中被问到这个问题。 “给定一个井字板,如何检查移动是一个不断获胜的移动。”

我花了20多分钟才找到答案,但我想能用o(1)解出来。

那么让我们从一个简单的3×3井字踢脚板开始,在板上每个区块对应一个数字。 一百二十三 四百五十六 七百八十九

所以我对这个问题的回答很简单,把所有的赢的组合散列成一个散列表,比如123、456、789、159等等。

有两个数字列表来跟踪单个玩家的移动

ALG描述如下

    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

所以我想是O(1)

我已经写了 a blog post for this question .

要点是,随着游戏的进行,您将跟踪每行/每列中放置了多少x+2个对角线。

然后,每次轮到玩家结束时,你都要检查最后一个坐标的行和列是否包含n个x的数字。如果是,那么玩家就赢了。

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