How to fix the min max algorithm if it tends to self-destruct?

user_11678228 0
Viewed 59

I am trying to write AI algorithm using MinMax to checkers game. Everything was fine before final test... The computer chooses any piece and after that he is coming to my guys. He really wants to die fast. Here is my code:

public MoveAndPoints MinMax(Dictionary<int, Field> gameBoard, string myColor, Boolean maximizingPlayer, int depth)
    {
        MoveAndPoints bestValue = new MoveAndPoints();
        if (0 == depth)
        {
            return new MoveAndPoints(((myColor == enemyColor) ? 1 : -1) * evaluateGameBoard(gameBoard, myColor), bestValue.move);
        }
            
        MoveAndPoints val = new MoveAndPoints();
        if (maximizingPlayer)
        {
            bestValue.points = int.MinValue;
            foreach (Move move in GetPossibleMoves(gameBoard, myColor))
            {
                gameBoard = ApplyMove(gameBoard, move);
                bestValue.move = move;
                val = MinMax(gameBoard, Extend.GetEnemyPlayerColor(myColor), false, depth - 1);
                bestValue.points = Math.Max(bestValue.points, val.points);
                gameBoard = RevertMove(gameBoard, move);
            }
            return bestValue;
        }
        else
        {
            bestValue.points = int.MaxValue;
            foreach (Move move in GetPossibleMoves(gameBoard, myColor))
            {
                gameBoard = ApplyMove(gameBoard, move);
                val = MinMax(gameBoard, Extend.GetEnemyPlayerColor(myColor), true, depth - 1);
                bestValue.points = Math.Min(bestValue.points, val.points);
                gameBoard = RevertMove(gameBoard, move);
            }
            return bestValue;
        }
    }

This is my heuretic:

public int evaluateGameBoard(Dictionary<int, Field> gameBoard, string color)
{
    return Extend.GetNumberOfPieces(gameBoard, color) - Extend.GetNumberOfPieces(gameBoard, Extend.GetEnemyPlayerColor(color));
}

For example, I have that scenario:

enter image description here

Instead of move any other place he is choosing to die:

enter image description here

If i choose death myself he only kills me because of fact that he must because this is his only move. Can someone help me fix this? I think problem is inside MinMax. I am almost sure this is not very problematic but i really can not find it :(

Here is depth 3 for my tree: enter image description here

minmax artificial-intelligence algorithm c#
1 Answers

I don't have all your code, so I can't verify these completely. But, I believe at least one of your problems is that you are mixing the colors between the players. In your MinMax calls you are passing the same color for both positions:

Here is the call inside the maximizing player:

val = MinMax(gameBoard, Extend.GetEnemyPlayerColor(myColor), false, depth - 1);

Here is the other call:

val = MinMax(gameBoard, Extend.GetEnemyPlayerColor(myColor), true, depth - 1);

You are correctly switching whether you are maximizing or not, but you shouldn't be switching the color between the players.

In practice really want to keep track of who the player is at the root, because all of the evaluations are relative to the player at the root. In that case you'd just pass color through the whole time and never use the enemies color except in the evaluation function.

user_2134890
Related