Connect-four游戏Minimax递归算法无限调用问题求助

一、无限递归问题的根源与修复 #

你的代码核心问题是当depth == 0时未直接返回评估值，而是继续执行后续的max/min分支逻辑，导致代码流程混乱，甚至触发非预期的循环或递归。正确的做法是：在函数开头优先判断终端状态或深度耗尽的情况，满足条件时直接返回结果，终止后续逻辑执行。

二、终端状态判定的实现 #

终端状态包含两种核心场景：某一方连成四子获胜，或棋盘已满无可用落子（平局）。以下是完整的状态判定函数：

// 返回值说明：1=Max玩家获胜，-1=Min玩家获胜，0=平局，-2=游戏未结束
private static int CheckTerminalState()
{
    // 检查横向四子连珠
    for (int row = 0; row < 6; row++)
    {
        for (int col = 0; col < 4; col++)
        {
            if (mx[row, col] != 0 && 
                mx[row, col] == mx[row, col+1] && 
                mx[row, col] == mx[row, col+2] && 
                mx[row, col] == mx[row, col+3])
            {
                return mx[row, col];
            }
        }
    }

    // 检查纵向四子连珠
    for (int col = 0; col < 7; col++)
    {
        for (int row = 0; row < 3; row++)
        {
            if (mx[row, col] != 0 && 
                mx[row, col] == mx[row+1, col] && 
                mx[row, col] == mx[row+2, col] && 
                mx[row, col] == mx[row+3, col])
            {
                return mx[row, col];
            }
        }
    }

    // 检查正斜线（左上→右下）四子连珠
    for (int row = 0; row < 3; row++)
    {
        for (int col = 0; col < 4; col++)
        {
            if (mx[row, col] != 0 && 
                mx[row, col] == mx[row+1, col+1] && 
                mx[row, col] == mx[row+2, col+2] && 
                mx[row, col] == mx[row+3, col+3])
            {
                return mx[row, col];
            }
        }
    }

    // 检查反斜线（右上→左下）四子连珠
    for (int row = 3; row < 6; row++)
    {
        for (int col = 0; col < 4; col++)
        {
            if (mx[row, col] != 0 && 
                mx[row, col] == mx[row-1, col+1] && 
                mx[row, col] == mx[row-2, col+2] && 
                mx[row, col] == mx[row-3, col+3])
            {
                return mx[row, col];
            }
        }
    }

    // 检查是否平局（棋盘已满）
    bool isFull = true;
    for (int col = 0; col < 7; col++)
    {
        if (mx[0, col] == 0) // 第一行有空位则棋盘未满
        {
            isFull = false;
            break;
        }
    }
    return isFull ? 0 : -2;
}

三、Minimax函数的正确重构 #

修改后的函数会优先处理终端状态和深度耗尽的情况，同时修正了分数计算逻辑（移除错误的分数叠加），优化了落子遍历逻辑：

public static int Minimax(int depth, int alpha, int beta, bool maximizingPlayer) 
{
    int terminalResult = CheckTerminalState();
    // 终端状态优先判定，不受剩余深度影响
    if (terminalResult != -2)
    {
        if (terminalResult == 1)
        {
            return 10000 + depth; // 剩余深度越高，获胜分数越高，鼓励更快赢
        }
        else if (terminalResult == -1)
        {
            return -10000 - depth; // 剩余深度越高，失败分数越低，避免慢输
        }
        else // 平局
        {
            return 0;
        }
    }

    // 深度耗尽，返回当前局面评估值
    if (depth == 0)
    {
        return evaluate(maximizingPlayer ? 1 : -1);
    }

    if (maximizingPlayer)
    {
        int bestScore = int.MinValue;
        for (int column = 0; column < 7; column++)
        {
            // 找到当前列最下方的可用空位
            int row = -1;
            for (int r = 5; r >= 0; r--)
            {
                if (mx[r, column] == 0)
                {
                    row = r;
                    break;
                }
            }
            if (row == -1) continue; // 当前列已满，跳过

            mx[row, column] = 1; // 落子
            int currentScore = Minimax(depth - 1, alpha, beta, false);
            mx[row, column] = 0; // 回溯

            if (currentScore > bestScore)
            {
                bestScore = currentScore;
                bestRow = row;
                bestCol = column;
            }
            alpha = Math.Max(alpha, bestScore);
            if (beta <= alpha)
            {
                break; // Beta剪枝
            }
        }
        return bestScore;
    }
    else
    {
        int bestScore = int.MaxValue;
        for (int column = 0; column < 7; column++)
        {
            // 找到当前列最下方的可用空位
            int row = -1;
            for (int r = 5; r >= 0; r--)
            {
                if (mx[r, column] == 0)
                {
                    row = r;
                    break;
                }
            }
            if (row == -1) continue; // 当前列已满，跳过

            mx[row, column] = -1; // 落子
            int currentScore = Minimax(depth - 1, alpha, beta, true);
            mx[row, column] = 0; // 回溯

            if (currentScore < bestScore)
            {
                bestScore = currentScore;
                bestRow = row;
                bestCol = column;
            }
            beta = Math.Min(beta, bestScore);
            if (beta <= alpha)
            {
                break; // Alpha剪枝
            }
        }
        return bestScore;
    }
}

四、关键修复点说明 #

• 无限递归解决：函数开头优先判断终端状态和深度耗尽，满足条件直接返回，终止后续逻辑，彻底避免非预期的递归或循环。
• 终端状态覆盖：完整处理了横向、纵向、两种斜线的四子连珠，以及棋盘满的平局场景，确保所有游戏结束情况都能被捕获。
• 逻辑修正：移除了错误的score = score + eval分数叠加逻辑，递归返回值直接作为当前局面的评估结果；优化了列遍历逻辑，先定位可用空位再处理，减少冗余判断。

内容的提问来源于stack exchange，提问作者Frezzy