c# - 井字游戏的 Minimax 算法进入无限递归循环

Question

问题： 我编写的 Minimax 函数完成了第一棵树，它填满了井字游戏板的所有可能槽，但随后分数开始返回我设置的无限值。

提示： 一旦板子第一次完全填满，递归就开始变坏，然后它试图清空板子跟踪，但在清空最后三个插槽后卡住，进入无限循环。返回值是无穷大，包括负数和正数。不知何故，板子没有被清空，因此值没有改变。

一些信息： 我正在用 Unity C# 构建项目，我使用的数组数据结构是用于存储板信息的结构类型。

//The initial function that returns the optimal move for AI to execute.
    public int[] GetMove()
    {
        int aBestScore = -mInfinity;
        int[] aMoveInfo = new int[2];

        SyncValues();
        int aLength = mAIPosInfo.GetLength(0);
        mBreakPoint = mBreakLimit;
        int aTest = -1;

        //Initial loop that tests the first move and gets into the recursion
        for (int i = 0; i < aLength; i++)
        {
            for (int j = 0; j < aLength; j++)
            {
                aTest++;
                if (mAIPosInfo[i, j].mFilledPiece == PieceId.Empty)
                { 
                    mAIPosInfo[i, j].mFilledPiece = mAIPiece;

                    int aScore = MiniMax(mAIPosInfo, 0, 0, 0, false, i, j);
                    mAIPosInfo[i, j].mFilledPiece = PieceId.Empty;

                    if (aScore > aBestScore)
                    {
                        aBestScore = aScore;
                        aMoveInfo[0] = i;
                        aMoveInfo[1] = j;
                    }

                }
            }
        }

        return aMoveInfo;
    }

//The MINI MAX ALGORITHM
    private int MiniMax(AIPosInfo[,] pPosInfo, int pDepth, bool pMaximizingPlayer, int pRowId, int pColId)
    {

        int aScore = CheckScore(pMaximizingPlayer, pPosInfo, pRowId, pColId);

        if (pDepth >= mDepthLimit || aScore != -5) //-5 is value returned for still playing
        {
            return aScore;
        }

    //Maximizing player turn..the AI Turn!!!
        if (pMaximizingPlayer)
        {
            int aMaxEval = -mInfinity;
            int aLength = pPosInfo.GetLength(0);

            for (int i = 0; i < aLength; i++)
            {
                for (int j = 0; j < aLength; j++)
                {
                    if (pPosInfo[i, j].mFilledPiece == PieceId.Empty)
                    {                        
                        pPosInfo[i, j].mFilledPiece = mAIPiece;

                        int aEvalve = MiniMax(pPosInfo, pDepth + 1, false, i, j);

                        pPosInfo[i, j].mFilledPiece = PieceId.Empty;

                        aMaxEval = Mathf.Max(aEvalve, aMaxEval);


                    }
                }
            }            
                return aMaxEval;           
        }
        else   //THE HUMAN PLAYER'S TURN
        {
            int aLength = pPosInfo.GetLength(0);
            int aMinEval = mInfinity;

            for (int i = 0; i < aLength; i++)
            {
                for (int j = 0; j < aLength; j++)
                {
                    if (pPosInfo[i, j].mFilledPiece == PieceId.Empty)
                    {


                        pPosInfo[i, j].mFilledPiece = mHumanPiece;


                        int aEval = MiniMax(pPosInfo, pDepth + 1, true, i, j);

                        pPosInfo[i, j].mFilledPiece = PieceId.Empty;

                        aMinEval = Mathf.Min(aEval, aMinEval);


                    }

                }
            }          
            return aMinEval;

            }
}

CheckScore 和 CheckWin 功能，字典有这个信息

    mScoreInfo.Add(PieceId.Cross, 1); //AI
    mScoreInfo.Add(PieceId.Zero, -1); //Human
    mScoreInfo.Add(PieceId.Draw, 0);
    mScoreInfo.Add(PieceId.Playing, -5);



private int CheckScore(bool pMaximizing, AIPosInfo[,] pPosInfo, int pRowId, int pColId)
    {
        PieceId aPieceId;
        int aValue;
        if (pMaximizing)
        {
            aPieceId = mAIPiece;
        }
        else
        {
            aPieceId = mHumanPiece;
        }

        PieceId aResult = CheckWin(pRowId, pColId, aPieceId, pPosInfo, true);

        if (mScoreInfo.TryGetValue(aResult, out aValue))
        {

            return aValue;
        }
        else
        {
            Debug.LogError("Undefined Variable in PieceId enum");
            return 0;
        }

    }

public PieceId CheckWin(int pRowId, int pColId, PieceId pPieceId, AIPosInfo[,] pPosArray, bool pAI)//The functionalities for the last parameter was removed because it wasn't needed. 
    {

        var aPosArray = pPosArray;

        bool aHorMatch = true;
        bool aVerMatch = true;
        bool aDiag1Match = true;
        bool aDiag2Match = true;

        for (int i = 0; i < BoardSetup.mInstance.mDegree; i++)
        {

            if (aPosArray[pRowId, i].mFilledPiece != pPieceId)
            {
                aHorMatch = false;
                //Debug.LogError("Not Horizontal");
            }

            if (aPosArray[i, pColId].mFilledPiece != pPieceId)
            {
                aVerMatch = false;
                //Debug.LogError("Not Vertical");
            }

            if (aPosArray[i, i].mFilledPiece != pPieceId)
            {
                aDiag1Match = false;
                //  Debug.LogError("Not Diagonal 1");
            }

            if (aPosArray[i, (BoardSetup.mInstance.mDegree - 1) - i].mFilledPiece != pPieceId)
            {
                aDiag2Match = false;
                //Debug.LogError("Not Diagonal 2");
            }
        }

        if (aHorMatch ||
           aVerMatch ||
           aDiag1Match ||
           aDiag2Match)
        {

            return pPieceId;
        }
        else
        {
            var aBoardInfo = BoardSetup.mInstance.mPosInfo;
            bool aCheckFill = true;
            for (int i = 0; i < aBoardInfo.Count; i++)
            {
                if (aBoardInfo[i].mFilledPiece == PieceId.Empty)
                {
                    aCheckFill = false;
                }
            }

            if (aCheckFill)
            {

                Debug.Log("Game Tied");

                return PieceId.Draw;
            }
        }

        return PieceId.Playing;

    }

标签： c#unity3dartificial-intelligencetic-tac-toeminimax