chatroom/app/Services/GomokuAiService.php

<?php

/**
 * 文件功能：五子棋 AI 对战算法服务
 *
 * 实现四个难度的 AI 决策逻辑：
 * - 简单：随机有效落点 + 单步威胁阻挡
 * - 普通：Minimax 深度 3
 * - 困难：Minimax + Alpha-Beta 剪枝 深度 5
 * - 专家：Minimax + Alpha-Beta 剪枝 深度 7 + 进攻优先调整
 *
 * @author  ChatRoom Laravel
 *
 * @version 1.0.0
 */

namespace App\Services;

class GomokuAiService
{
    /** @var int 棋盘尺寸 */
    private const BOARD_SIZE = 15;

    /** @var int 黑棋（玩家先手） */
    private const BLACK = 1;

    /** @var int 白棋/AI */
    private const WHITE = 2;

    /** @var int 无穷大分数 */
    private const INF = 999999;

    /**
     * 根据当前棋盘和 AI 难度，返回最优落点坐标。
     *
     * @param  array  $board  当前棋盘状态（15×15）
     * @param  int  $aiLevel  AI 难度：1=简单 2=普通 3=困难 4=专家
     * @return array{row: int, col: int} 最优落点
     */
    public function think(array $board, int $aiLevel): array
    {
        return match ($aiLevel) {
            1 => $this->thinkMinimax($board, 2),  // 简单：深度2
            2 => $this->thinkMinimax($board, 3),  // 普通：深度3
            3 => $this->thinkMinimax($board, 4),  // 困难：深度4
            default => $this->thinkMinimax($board, 5),  // 专家：深度5
        };
    }

    // ─── 简单难度：随机 + 单步阻挡 ─────────────────────────────────

    /**
     * 简单 AI：先检查是否有必须阻挡的威胁，否则随机落子。
     *
     * @param  array  $board  棋盘
     * @return array{row: int, col: int}
     */
    private function thinkSimple(array $board): array
    {
        // 先检查 AI 自己是否能一步胜利
        $win = $this->findImmediateWin($board, self::WHITE);
        if ($win !== null) {
            return $win;
        }

        // 再检查玩家是否要连成五，必须阻挡
        $block = $this->findImmediateWin($board, self::BLACK);
        if ($block !== null) {
            return $block;
        }

        // 随机选择有棋子附近的空位（增加合理性）
        $candidates = $this->getCandidates($board, 1);

        // 随机选一个候选点
        if (! empty($candidates)) {
            return $candidates[array_rand($candidates)];
        }

        // 棋盘全空时走中心
        return ['row' => 7, 'col' => 7];
    }

    /**
     * 寻找能立即获胜（连成五子）的落点。
     *
     * @param  array  $board  棋盘
     * @param  int  $color  检查哪方颜色
     * @return array{row: int, col: int}|null
     */
    private function findImmediateWin(array $board, int $color): ?array
    {
        for ($r = 0; $r < self::BOARD_SIZE; $r++) {
            for ($c = 0; $c < self::BOARD_SIZE; $c++) {
                if ($board[$r][$c] !== 0) {
                    continue;
                }
                $board[$r][$c] = $color;
                if ($this->checkWinAt($board, $r, $c, $color)) {
                    $board[$r][$c] = 0;

                    return ['row' => $r, 'col' => $c];
                }
                $board[$r][$c] = 0;
            }
        }

        return null;
    }

    // ─── Minimax + Alpha-Beta 剪枝 ──────────────────────────────────

    /**
     * 使用 Minimax 算法（含 Alpha-Beta 剪枝）找最优落点。
     *
     * @param  array  $board  棋盘
     * @param  int  $depth  搜索深度
     * @return array{row: int, col: int}
     */
    private function thinkMinimax(array $board, int $depth): array
    {
        $bestScore = -self::INF;
        $bestMove = ['row' => 7, 'col' => 7];

        // 先检查即时胜利（避免算法绕过）
        $win = $this->findImmediateWin($board, self::WHITE);
        if ($win !== null) {
            return $win;
        }
        $block = $this->findImmediateWin($board, self::BLACK);
        if ($block !== null) {
            return $block;
        }

        // 获取候选点（半径1，避免候选点过多导致超时）
        $candidates = $this->getCandidates($board, 1);

        if (empty($candidates)) {
            return ['row' => 7, 'col' => 7];
        }

        // 对候选点预排序（快速评分优先，提升剪枝效率）
        usort($candidates, function ($a, $b) use ($board) {
            return $this->evaluatePoint($board, $b['row'], $b['col'], self::WHITE)
                - $this->evaluatePoint($board, $a['row'], $a['col'], self::WHITE);
        });

        // 只取前 20 个高分候选点，进一步减少搜索空间
        $candidates = array_slice($candidates, 0, 20);

        foreach ($candidates as $move) {
            $board[$move['row']][$move['col']] = self::WHITE;
            $score = $this->minimax($board, $depth - 1, -self::INF, self::INF, false, $move['row'], $move['col']);
            $board[$move['row']][$move['col']] = 0;

            if ($score > $bestScore) {
                $bestScore = $score;
                $bestMove = $move;
            }
        }

        return $bestMove;
    }

    /**
     * Minimax 递归搜索。
     *
     * @param  array  $board  棋盘
     * @param  int  $depth  剩余深度
     * @param  int  $alpha  Alpha 值（剪枝用）
     * @param  int  $beta  Beta 值（剪枝用）
     * @param  bool  $isMaximize  是否为最大化层（AI 落子）
     * @param  int  $lastRow  上一步落子行（用于快速胜负检测）
     * @param  int  $lastCol  上一步落子列
     */
    private function minimax(
        array $board,
        int $depth,
        int $alpha,
        int $beta,
        bool $isMaximize,
        int $lastRow,
        int $lastCol
    ): int {
        $lastColor = $isMaximize ? self::BLACK : self::WHITE;

        // 终止条件：上一步是否已经胜利
        if ($this->checkWinAt($board, $lastRow, $lastCol, $lastColor)) {
            return $isMaximize ? -self::INF : self::INF;
        }

        // 深度耗尽：评估当前局面
        if ($depth === 0) {
            return $this->evaluateBoard($board);
        }

        // 递归层同样限制候选点范围（半径1，最多15个），防止指数爆炸
        $candidates = array_slice($this->getCandidates($board, 1), 0, 15);
        if (empty($candidates)) {
            return $this->evaluateBoard($board);
        }

        if ($isMaximize) {
            // AI 落子（最大化）
            $best = -self::INF;
            foreach ($candidates as $move) {
                $board[$move['row']][$move['col']] = self::WHITE;
                $score = $this->minimax($board, $depth - 1, $alpha, $beta, false, $move['row'], $move['col']);
                $board[$move['row']][$move['col']] = 0;
                $best = max($best, $score);
                $alpha = max($alpha, $best);
                if ($beta <= $alpha) {
                    break; // Beta 剪枝
                }
            }

            return $best;
        } else {
            // 玩家落子（最小化）
            $best = self::INF;
            foreach ($candidates as $move) {
                $board[$move['row']][$move['col']] = self::BLACK;
                $score = $this->minimax($board, $depth - 1, $alpha, $beta, true, $move['row'], $move['col']);
                $board[$move['row']][$move['col']] = 0;
                $best = min($best, $score);
                $beta = min($beta, $best);
                if ($beta <= $alpha) {
                    break; // Alpha 剪枝
                }
            }

            return $best;
        }
    }

    // ─── 棋盘评估 ────────────────────────────────────────────────────

    /**
     * 整体棋盘评估：AI 得分 - 玩家得分（正值对 AI 有利）。
     *
     * @param  array  $board  棋盘
     */
    private function evaluateBoard(array $board): int
    {
        return $this->evaluateColor($board, self::WHITE) - $this->evaluateColor($board, self::BLACK);
    }

    /**
     * 评估指定颜色在棋盘上的总得分。
     *
     * @param  array  $board  棋盘
     * @param  int  $color  棋子颜色
     */
    private function evaluateColor(array $board, int $color): int
    {
        $score = 0;
        $opponent = $color === self::WHITE ? self::BLACK : self::WHITE;

        // 四个方向
        $directions = [[0, 1], [1, 0], [1, 1], [1, -1]];

        for ($r = 0; $r < self::BOARD_SIZE; $r++) {
            for ($c = 0; $c < self::BOARD_SIZE; $c++) {
                foreach ($directions as [$dr, $dc]) {
                    $score += $this->evaluateLine($board, $r, $c, $dr, $dc, $color, $opponent);
                }
            }
        }

        return $score;
    }

    /**
     * 评估从 (r, c) 出发沿 (dr, dc) 方向的连子得分。
     *
     * @param  array  $board  棋盘
     * @param  int  $r  起始行
     * @param  int  $c  起始列
     * @param  int  $dr  行方向步长
     * @param  int  $dc  列方向步长
     * @param  int  $color  我方颜色
     * @param  int  $opponent  对方颜色
     */
    private function evaluateLine(
        array $board,
        int $r, int $c,
        int $dr, int $dc,
        int $color,
        int $opponent
    ): int {
        // 统计连续同色棋子数
        $count = 0;
        $open = 0; // 两端开口数

        for ($i = 0; $i < 5; $i++) {
            $nr = $r + $dr * $i;
            $nc = $c + $dc * $i;
            if ($nr < 0 || $nr >= self::BOARD_SIZE || $nc < 0 || $nc >= self::BOARD_SIZE) {
                return 0; // 越界，无效
            }
            $cell = $board[$nr][$nc];
            if ($cell === $opponent) {
                return 0; // 被对方截断，无价值
            }
            if ($cell === $color) {
                $count++;
            }
        }

        // 检测前端开口
        $prevR = $r - $dr;
        $prevC = $c - $dc;
        if ($prevR >= 0 && $prevR < self::BOARD_SIZE && $prevC >= 0 && $prevC < self::BOARD_SIZE) {
            if ($board[$prevR][$prevC] === 0) {
                $open++;
            }
        }

        // 检测后端开口
        $nextR = $r + $dr * 5;
        $nextC = $c + $dc * 5;
        if ($nextR >= 0 && $nextR < self::BOARD_SIZE && $nextC >= 0 && $nextC < self::BOARD_SIZE) {
            if ($board[$nextR][$nextC] === 0) {
                $open++;
            }
        }

        // 根据连子数和开口数评分
        return match ($count) {
            5 => 10000,                    // 五连：胜利
            4 => $open >= 1 ? 5000 : 500,  // 四连活四/眠四
            3 => $open === 2 ? 500 : 50,   // 活三/眠三
            2 => $open === 2 ? 50 : 10,    // 活二/眠二
            default => 0,
        };
    }

    /**
     * 评估在指定点落子后的局部得分（用于候选点预排序）。
     *
     * @param  array  $board  棋盘
     * @param  int  $row  行
     * @param  int  $col  列
     * @param  int  $color  落子颜色
     */
    private function evaluatePoint(array $board, int $row, int $col, int $color): int
    {
        $board[$row][$col] = $color;
        $score = $this->evaluateColor($board, $color);

        return $score;
    }

    // ─── 辅助工具 ─────────────────────────────────────────────────────

    /**
     * 获取棋盘上已有棋子周边 $range 格内的所有空位（候选落点）。
     *
     * @param  array  $board  棋盘
     * @param  int  $range  搜索半径（格数）
     * @return array<array{row: int, col: int}>
     */
    private function getCandidates(array $board, int $range = 1): array
    {
        $candidates = [];
        $visited = [];
        $hasStone = false;

        for ($r = 0; $r < self::BOARD_SIZE; $r++) {
            for ($c = 0; $c < self::BOARD_SIZE; $c++) {
                if ($board[$r][$c] === 0) {
                    continue;
                }
                $hasStone = true;
                // 在该棋子周边 $range 格内寻找空位
                for ($dr = -$range; $dr <= $range; $dr++) {
                    for ($dc = -$range; $dc <= $range; $dc++) {
                        $nr = $r + $dr;
                        $nc = $c + $dc;
                        if ($nr < 0 || $nr >= self::BOARD_SIZE || $nc < 0 || $nc >= self::BOARD_SIZE) {
                            continue;
                        }
                        $key = "{$nr},{$nc}";
                        if (! isset($visited[$key]) && $board[$nr][$nc] === 0) {
                            $candidates[] = ['row' => $nr, 'col' => $nc];
                            $visited[$key] = true;
                        }
                    }
                }
            }
        }

        // 棋盘全空时返回中心点
        if (! $hasStone) {
            return [['row' => 7, 'col' => 7]];
        }

        return $candidates;
    }

    /**
     * 检查指定位置落子后是否连成五子。
     *
     * @param  array  $board  棋盘（已包含该子）
     * @param  int  $row  行
     * @param  int  $col  列
     * @param  int  $color  棋子颜色
     */
    private function checkWinAt(array $board, int $row, int $col, int $color): bool
    {
        $directions = [[0, 1], [1, 0], [1, 1], [1, -1]];

        foreach ($directions as [$dr, $dc]) {
            $count = 1;

            for ($i = 1; $i <= 4; $i++) {
                $r = $row + $dr * $i;
                $c = $col + $dc * $i;
                if ($r < 0 || $r >= self::BOARD_SIZE || $c < 0 || $c >= self::BOARD_SIZE) {
                    break;
                }
                if (($board[$r][$c] ?? 0) !== $color) {
                    break;
                }
                $count++;
            }

            for ($i = 1; $i <= 4; $i++) {
                $r = $row - $dr * $i;
                $c = $col - $dc * $i;
                if ($r < 0 || $r >= self::BOARD_SIZE || $c < 0 || $c >= self::BOARD_SIZE) {
                    break;
                }
                if (($board[$r][$c] ?? 0) !== $color) {
                    break;
                }
                $count++;
            }

            if ($count >= 5) {
                return true;
            }
        }

        return false;
    }
}