TicTacToe 对角线检查功能

Question

class Board
{
    const MARK_0 = 0;
    const MARK_X = 1;

    /** @var int */
    private $sizeX;

    /** @var int */
    private $sizeY;

    /** @var int */
    private $requiredMarks;

    /** @var array */
    private $map = [];

    /**
     * @param int $sizeX
     * @param int $sizeY
     */
    public function __construct (int $sizeX = 3, int $sizeY = 3)
    {
        $this->sizeX = $sizeX;
        $this->sizeY = $sizeY;

        $this->requiredMarks = $sizeX;
    }

    /**
     * @return int
     */
    public function getSizeX() : int
    {
        return $this->sizeX;
    }

    /**
     * @return int
     */
    public function getSizeY() : int
    {
        return $this->sizeY;
    }

    /**
     * @return int
     */
    public function getRequiredMarks() : int
    {
        return $this->requiredMarks;
    }

    /**
     * @param int $count
     */
    public function setRequiredMarks (int $count) : void
    {
        $this->requiredMarks = $count;
    }

    /**
     * @param int $x
     * @param int $y
     * @param int $mark
     */
    public function setMark (int $x, int $y, int $mark) : void
    {
        $this->map[$x][$y] = $mark;
    }

    /**
     * @param int $x
     * @param int $y
     *
     * @return int|null
     */
    public function getMark (int $x, int $y) : ?int
    {
        return $this->map[$x][$y] ?? null;
    }

    /**
     * @return int|null
     */
    public function checkWin() : ?int
    {
        foreach([self::MARK_0, self::MARK_X] as $mark)
        {
            if(/* $this->checkLanes($mark) ||  */ $this->checkDiagonals($mark))
            {
                return $mark;
            }
        }

        return null;
    }

    /**
     * @param int $mark
     *
     * @return bool
     */
    private function checkDiagonals (int $mark) : bool
    {
        $sizeX = $this->getSizeX();
        $sizeY = $this->getSizeY();

        $required = $this->getRequiredMarks();

        $size = max($sizeX, $sizeY);

        for($k = $required - $size; $k <= ($size - $required); $k++)
        {
            $score1 = 0;
            $score2 = 0;

            $startI = max(0, $k);
            $endI = min($size, $size + $k);

            for($i = $startI; $i < $endI; $i++)
            {
                if($this->getMark($i, $k + $i) === $mark)
                {
                    if(++$score1 >= $required)
                    {
                        return true;
                    }
                }
                else
                {
                    $score1 = 0;
                }

                if($this->getMark($i, $size - 1 + $k - $i) === $mark)
                {
                    if(++$score2 >= $required)
                    {
                        return true;
                    }
                }
                else
                {
                    $score2 = 0;
                }
            }
        }

        return false;
    }
}

$b = new Board (4, 4);
$b->setRequiredMarks(3);

$b->setMark(0, 1, Board::MARK_X);
$b->setMark(1, 2, Board::MARK_X);
$b->setMark(2, 3, Board::MARK_X);

$winner = $b->checkWin();

if($winner === null)
{
    $winner = "nobody";
}
elseif($winner === Board::MARK_X)
{
    $winner = "X";
}
else
{
    $winner = "0";
}

var_dump($winner);

如何修复函数 "checkDiagonals"，以便 photo 中的对角线处理正确发生并返回正确的结果？

如果像 photo 那样检查对角线，它会正常工作。

我想不出检查对角线的算法，所以我从这里获取：

注释函数 "checkLanes" 工作正常，因此它在代码中被隐藏了。

Answer 1

以下是您的算法当前正在检查的对角线坐标：

x: 0, y: -1
x: 1, y: 0
x: 2, y: 1

x: 0, y: 0
x: 1, y: 1
x: 2, y: 2
x: 3, y: 3

x: 1, y: 2
x: 2, y: 3
x: 3, y: 4

您可以看到一个索引超出范围，一次迭代正在检查 4 个正方形，这超出了要求并且没有足够的检查来覆盖两条对角线。

您似乎正试图从每个可以“适合”所需大小的对角线的索引开始，然后向下和向右移动检查沿对角线的不匹配。让我们手动枚举支票：

1...  .1..  ....  ....  ...1  ..1.  ....  ....
.2..  ..2.  1...  .1..  ..2.  .2..  ...1  ..1.
..3.  ...3  .2..  ..2.  .3..  3...  ..2.  .2..
....  ....  ..3.  ...3  ....  ....  .3..  3...

这是三个嵌套循环：行、列和对角线：

行循环从0开始，运行到$sizeY - $requiredMarks。
第一列循环从 0 开始并运行到 $sizeX - $requiredMarks 检查从左到右的对角线。
第二列循环从 $sizeX - $requiredMarks + 1 运行到 $sizeX 检查从右到左的对角线。
最里面的对角线循环从 0 开始，运行到 $requiredMarks。

单元格索引如下：行：($row + $diag)，列：($col + $diag * $xDirection)。 $xDirection 乘数（1 或 -1）使对角线检查函数可以在任一方向（左或右）移动。

这是执行此操作的代码：

private function checkDiagonals(int $mark) : bool {
    $required = $this->getRequiredMarks();

    for ($row = 0; $row <= $this->getSizeY() - $required; $row++) {
        for ($col = 0; $col <= $this->getSizeX() - $required; $col++) {
            if ($this->checkDiagonal($mark, $row, $col, 1)) {
                return true;
            }
        }

        for ($col = $this->getSizeX() - $required + 1; $col < $this->getSizeX(); $col++) {
            if ($this->checkDiagonal($mark, $row, $col, -1)) {
                return true;
            }
        }
    }

    return false;
}

private function checkDiagonal(int $mark, int $row, int $col, int $xDir) : bool {
    for ($i = 0; $i < $this->getRequiredMarks(); $i++) {
        if ($this->getMark($col + $i * $xDir, $row++) !== $mark) {
            return false;
        }
    }

    return true;
}

这些是它检查的对角线：

x: 0, y: 0
x: 1, y: 1
x: 2, y: 2

x: 1, y: 0
x: 2, y: 1
x: 3, y: 2

x: 2, y: 0
x: 1, y: 1
x: 0, y: 2

x: 3, y: 0
x: 2, y: 1
x: 1, y: 2

x: 0, y: 1
x: 1, y: 2
x: 2, y: 3

x: 1, y: 1
x: 2, y: 2
x: 3, y: 3

x: 2, y: 1
x: 1, y: 2
x: 0, y: 3

x: 3, y: 1
x: 2, y: 2
x: 1, y: 3

这不是非常有效，因为它涉及多次访问方块，但它至少应该让您可以操作。如果速度很重要，请考虑使用 bitboards，它可以通过一些操作检查整个电路板，但需要对您的方法进行相当多的调整。一个更简单的重构是跟踪玩家的最后一步并只检查该方块可能获胜。

TicTacToe 对角线检查功能

TicTacToe diagonal check function

php

tic-tac-toe