TicTacToe diagonal check function

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

How to fix the function "checkDiagonals", so that the processing of the diagonal as in the photo occurred correctly and returned the correct result?

If do a check on the diagonal, as in the photo, it works correctly.

I can not think of an algorithm for checking diagonals, so I took it from here: https://stackoverflow.com/a/34257658/10261980

The commented function "checkLanes" works correctly, so it is hidden from the code.

Answer 1

Here are the coordinates of the diagonals your algorithm is currently checking:

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

You can see an index is out of bounds, one iteration is checking 4 squares which is more than the requirement and there aren't enough checks to cover both diagonals.

It looks like you're attempting to start at each index that can "fit" a diagonal of the required size and move down and to the right checking for a mismatch along the diagonal. Let's enumerate the checks by hand:

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

This is three nested loops: rows, columns and diagonals:

• The row loop starts at 0 and runs to $sizeY - $requiredMarks.
• The first column loop starts at 0 and runs to $sizeX - $requiredMarks checking left to right diagonals.
• The second column loop runs from $sizeX - $requiredMarks + 1 to $sizeX checking right to left diagonals.
• The innermost diagonal loop starts at 0 and runs to $requiredMarks.

Indexing into a cell is as follows: row: ($row + $diag), column: ($col + $diag * $xDirection). The $xDirection multiplier (either 1 or -1) enables a diagonal-checking function to move in either direction (left or right).

Here's the code that does this:

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

These are the diagonals it checks:

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

This isn't terribly efficient because it involves visiting squares multiple times, but it should at least get you operational. If speed is important, consider using bitboards which can check the whole board with a few operations but requires adjusting your approach quite a bit. An easier refactor is keeping track of the player's last move and only checking possible wins from that square.