3

我正在使用 Unity3D (C#) 中的 AI 开发 Connect Four 游戏。我根据this (German) Pseudocode使用 MiniMax 算法。

AI的表现仍然很糟糕。它试图连续获得 4 个，尽管只有三个空闲字段。AI 总是在需要时穿过行并阻塞。不幸的是，它也不总是阻塞。

哪里隐藏问题？我忘记了什么？

当下一步没有人赢或输时，我如何整合人工智能的随机动作。

这是我的源代码：

最小最大深度 = 4

函数调用：Max (minimaxDepth, fieldCopy);

int Max (int depth, int[,] fieldCopy)
{
    int maxValue = -9999;
    int moveValue;
    bool winAI = false;
    bool winHuman = false;
    bool isStoneBelow = false;

    for (int y = 0; y < 6; y++) {
        for (int x = 0; x < 7; x++) {
            if (y > 0) {
                //is a stone under it?
                if (fieldCopy [x, y - 1] == 1 || fieldCopy [x, y - 1] == 2) {
                    isStoneBelow = true;
                } else {
                    isStoneBelow = false;
                }
            } else {
                isStoneBelow = true;
            }

            // possible move?
            if (fieldCopy [x, y] != 1 && fieldCopy [x, y] != 2 && isStoneBelow == true) {   
                isStoneBelow = false;
                fieldCopy [x, y] = 2; //simulate move
                winAI = false;
                winHuman = false;

                //Is there a winner?
                if (CheckWin (x, y, 2, fieldCopy)) {
                    winAI = true;
                    winHuman = false;
                }

                //No more moves possible?
                if (depth <= 1 || winAI == true) { 
                    moveValue = evaluationFunction (winAI, winHuman);       //evaluate the move
                } else {
                    moveValue = Min (depth - 1, fieldCopy);
                }

                fieldCopy [x, y] = 0; //Reset simulated move

                if (moveValue > maxValue) {
                    maxValue = moveValue;
                    if (depth == minimaxDepth) {
                        aiMoveX = x; // next move
                    }
                }
            }
        }
    }
    return maxValue;
}

int Min (int depth, int[,] fieldCopy)
{
    int minValue = 9999;
    int moveValue;
    bool winAI = false;
    bool winHuman = false;
    bool isStoneBelow = false;
    bool loopBreak = false;

    for (int y = 0; y < 6; y++) {
        for (int x = 0; x < 7; x++) {
            if (y > 0) {
                //is a stone under it?
                if (fieldCopy [x, y - 1] == 1 || fieldCopy [x, y - 1] == 2) {
                    isStoneBelow = true;
                } else {
                    isStoneBelow = false;
                }
            } else {
                isStoneBelow = true;
            }

            // possible move?
            if (fieldCopy [x, y] != 1 && fieldCopy [x, y] != 2 && isStoneBelow == true) {   
                isStoneBelow = false;
                fieldCopy [x, y] = 1; //simulate move
                winHuman = false;
                winAI = false;

                //Is there a winner?    
                if (CheckWin (x, y, 1, fieldCopy)) {
                    winHuman = true;
                    winAI = false;
                }

                //No more moves possible?
                if (depth <= 1 || winHuman == true) {  
                    moveValue = evaluationFunction (winAI, winHuman);       //evaluate the move
                } else {
                    moveValue = Max (depth - 1, fieldCopy);
                }

                fieldCopy [x, y] = 0; //Reset simulated move

                if (moveValue < minValue) {
                    minValue = moveValue;
                }
            }
        }
    }
    return minValue;
}


int evaluationFunction (bool winAI, bool winHuman)
{
    if (winAI) { 
        return 1;
    } else if (winHuman) {
        return -1;
    } else {
        return 0;
    }
}

谢谢你的帮助！

4

2 回答 2

3

我相信问题在于您的评估功能。您应该评估他们在游戏中的状态，而不是评估其中一名玩家是否获胜。一个可能的考虑因素是该玩家棋子的最长连续链的长度。这准确地显示了每个玩家距离获胜的距离，而不是在玩家即将获胜但尚未获胜时返回相同的值。

为了清楚起见，这里是伪代码：

int evaluationFunction (int depth)
{
    // max_ai_chain and max_human_chain are global variables that 
    // should be updated at each piece placement

    if (depth % 2 == 0) // assuming AI gets calculated on even depth (you mentioned your depth is 4)
    { 
        return max_ai_chain;
    } else {
        return max_human_chain;
    }
}
于 2013-08-16T22:08:05.150 回答
3

前段时间，我还以 Connect 4 为例进行了一个极小化算法，并尝试了评估函数和搜索深度之间的权衡。我惊讶地发现，几乎不需要搜索，但对评估函数有很强的启发式，你可以实现相当合理的游戏（对于这个游戏）。这似乎比评估函数的弱启发式和深度搜索要好得多。

连续获得 4 个是游戏的获胜条件，因此，您首先必须获得连续 3 个（垂直、水平或对角线）或像 O-OO 或 OO-O（水平或对角线）这样的模式. 这些“潜在的连续 4 分”越多，评估分数就应该越高。通过连续获得 2 分可以为评估函数贡献较小的分数。此外，将计数器放置在棋盘中心也是一个优势，因为更有可能形成 4 线，因此评估功能还应该奖励靠近中心的计数器。根据比赛状态，其他改进也是可能的。

例如，一个重要的考虑因素是，如果您在棋盘的同一列中有两个这样的潜在获胜者，您可以强制获胜。你可以强迫你的对手阻止第一个，然后在同一列中通过在它上面打你的石头来获胜。

如果您的评估函数编码了这些想法，那么当与 mini-maxing 结合使用时，您应该得到一些合理的发挥。

于 2013-08-20T15:25:13.650 回答