0
\$\begingroup\$

it's my first time posting so apologies in advance if the format is weird. I'm developing a board game that's very similar to checkers/chess and I've faced some problems implementing the minimax/negamax algorithms with alpha-beta pruning for my AI. This is how far I've got:

public IEnumerator MoveAI()
{
    if (Preserve.againstAI)
    {
        if (!CheckMat() && !CheckNull())
        {
            yield return new WaitUntil(() => BasePiece.mandatoryCheckFinished);
            minimaxChecking = true; //Changing the movement of pieces so it doesn't appear physically in the board
            Tuple<BasePiece, Cell, int> minimaxTuple = MiniMax(originalDepth, -10000, 10000, false);
            minimaxChecking = false;
            minimaxTuple.Item1.targetCell = minimaxTuple.Item2;
            minimaxTuple.Item1.Move(); //Applying the move found by MiniMax
            StartCoroutine(minimaxTuple.Item1.MandatoryCheck());
            SwitchSides(Color.black);
        }                                                                 
    }
}

public Tuple<BasePiece, Cell, int> MiniMax(int depth, int alpha, int beta, bool maximizingPlayer)
{
    if (depth == 0)
    {
        return new Tuple<BasePiece, Cell, int>(null, null, BasePiece.numberOfWhitePieces - BasePiece.numberOfBlackPieces);
    }
    if (maximizingPlayer)
    {
        BasePiece actualPiece = null;
        Cell actualCell = null;
        bool found = false;
        int maxEval = -10000;
        for (int j = 0; j < allWhites.Count; j++) //Going through all possible whites movement
        {
            actualPiece = allWhites[j];
            actualPiece.CheckPathing();
            if (actualPiece.highlightedCells.Count > 0)
            {
                for (int i = 0; i < actualPiece.highlightedCells.Count; i++)
                {
                    actualCell = actualPiece.highlightedCells[i];
                    actualPiece.targetCell = actualCell;
                    actualPiece.Move();
                    int eval = MiniMax(depth - 1, alpha, beta, false).Item3;
                    UIElement.Undo(); //Undoing the previous move
                    maxEval = eval > maxEval ? eval : maxEval;
                    alpha = eval > alpha ? eval : alpha;
                    if (beta <= alpha)
                    {
                        found = true;
                        break;
                    }
                }
                if (found)
                {
                    break;
                }
            }
        }
        return new Tuple<BasePiece, Cell, int>(actualPiece, actualCell, maxEval);
    }
    else
    {
        BasePiece actualPiece = null;
        Cell actualCell = null;
        bool found = false;
        int minEval = 10000;
        for (int j = 0; j < allBlacks.Count; j++)
        {
            actualPiece = allBlacks[j];
            actualPiece.CheckPathing();
            if (actualPiece.highlightedCells.Count > 0)
            {
                for (int i = 0; i < actualPiece.highlightedCells.Count; i++)
                {
                    actualCell = actualPiece.highlightedCells[i];
                    actualPiece.targetCell = actualCell;
                    actualPiece.Move();
                    int eval = MiniMax(depth - 1, alpha, beta, true).Item3;
                    UIElement.Undo();
                    minEval = eval < minEval ? eval : minEval;
                    beta = eval < beta ? eval : beta;
                    if (beta <= alpha)
                    {
                        found = true;
                        break;
                    }
                }
                if (found)
                {
                    break;
                }
            }
        }
        return new Tuple<BasePiece, Cell, int>(actualPiece, actualCell, minEval);
    }
}

The result is quite weird for any initial depth. For an originalDepth = 1, The player's first move gets undone, plus the move that I get is not a valid one. (the negamax gives a similar result although with a different move)

The problem could very well be in my undo function (Which I doubt as the undo method works very well in a human vs human mode) and I can edit it's code in if there is no actual error within the algorithm.

I'm also wondering if it's necessary to make a deep copy of the board state before the MiniMax call (right now I'm exploring the moves without physically moving the pieces in the board but rather changing their cells and then I undo each move, all in the original board).

Any help or suggestions would be greatly appreciated as I have been stuck with this for quite a few days now.

EDIT: I'm aware of the lack of a proper evaluation function but I don't think it explains why I'm getting an invalid move. (I could be wrong)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.