Make Minimax return Move and Number

Question

I am working on a chess AI. To calculate the best Move I am using the MiniMax algorithm with alpha beta pruning. My problem is that the Minimax only returns a evaluation of the Positin I.e. who is currently most likely to win. But I want not only the evaluation of the Position but also the "Path" to the best possible outcome for the maximazing player. As an example I want the algorithm to return the best move in the Position like e4 or something and not only a number which represents wo is better right now.

This is my main branch. The Object Model is holds an 2d double array which represents the board. Futhermore the Object holds double XCoordinateStart, double YCoordinateStart,double XCoordinateEnd, double YCoordinateEnd which represent the last move, that led to that Position. I am not sure if the the algorithm is implemented correctly since I dont see what move are being made. double Max(double MaxEval, double Eval) { if (MaxEval < Eval) return Eval;else return MaxEval; } double Min(double MaxEval, double Eval) { if (MaxEval < Eval) return MaxEval; else return Eval; }

    double Minimax(Model model_, int depth, double alpha, double beta, bool MaximazingPlayer)
    {
        if (depth == 0)
        {
            return BoardEvaluation(model_);
        }

        if (MaximazingPlayer)
        {
            double maxEval = -10000;
            for(int i = 0; i < model_.PossiblePositions.Count; i++)
            {
          double eval = Minimax(model_.PossiblePositions[i], depth - 1, alpha, beta,false);         
                maxEval = Max(maxEval, eval);
                alpha = Max(alpha, eval);
                if (beta <= alpha) break;
            }
            return maxEval;

        }
        else
        {
            double minEval = 10000;
            for(int i = 0; i < model_.PossiblePositions.Count; i++)
            {
                double eval = Minimax(model_.PossiblePositions[i], depth - 1, alpha, beta,true);
                minEval = Min(minEval, eval);
                alpha = Min(beta, eval);
                if (beta <= alpha) break;

            }
            return minEval;

        }
    }

I tried somethin like this with a global variable:

       public string BestMove;
       double Max(double MaxEval, double Eval)
        {
            if (MaxEval < Eval) return Eval;else return MaxEval;
        }
        double Min(double MaxEval, double Eval)
        {
            if (MaxEval < Eval) return MaxEval; else return Eval;
        }

        string MoveAsStr(Model model_)
        {
        return model_.XCoordinateStart.ToString() + ";" + model_.YCoordinateStart.ToString() +";" +     model_.XCoordinateEnd.ToString() + ";" + model_.YCoordinateEnd.ToString() + "-";
        }
        double Minimax(Model model_, int depth, double alpha, double beta, bool MaximazingPlayer)
        {
            if (depth == 0)
            {
                return BoardEvaluation(model_);
            }

            if (MaximazingPlayer)
            {
                double maxEval = -10000;
                for(int i = 0; i < model_.PossiblePositions.Count; i++)
                {
                    double eval = Minimax(model_.PossiblePositions[i], depth - 1, alpha, beta, `false);`
                    maxEval = Max(maxEval, eval);
                    if (maxEval == eval) BestMove = MoveAsStr(model_);
                    alpha = Max(alpha, eval);
                    if (beta <= alpha) break;
                }
                return maxEval;

            }
            else
            {
                double minEval = 10000;
                for(int i = 0; i < model_.PossiblePositions.Count; i++)
                {
                    double eval = Minimax(model_.PossiblePositions[i], depth - 1, alpha, beta, `true);`
                    minEval = Min(minEval, eval);
                    alpha = Min(beta, eval);
                    if (beta <= alpha) break;

                }
                return minEval;

            }

But I just get the Move 0,7 to 0,7 as a result which doesnt make sense because this move does not exist in any child of the Position because Pieces cannot stand still. Is there something terribly wrong with my Implementation or am I grabbing the Move at the wrong spot in the algortithm? Thank you!

I don't see how this is language-dependent. I understand you are trying to use c# for your solution but this seems very language-neutral. I'd suggest dropping the c# tag here. — julealgon
– julealgon, Commented Mar 29, 2023 at 21:01
Changed it, thanks for the feedback its my first question ever... — ImNotARobot
– ImNotARobot, Commented Mar 29, 2023 at 21:03

trincot · Accepted Answer · 2023-03-30 08:22:25Z

1

Using a global variable for the best move will in general not work, because that variable will be set by deeper recursive executions of Minimax, and one of those assignments could be the last assignment. Thus you get a move back that has not been played as a first move (i.e. a move in the current position).

You could have the Minimax function return a pair: the value and the corresponding move. Only the top level caller will be interested in the move part, while the recursive callers will only be interested in the value part, but that's fine.

In C# you would use a Tuple for this purpose. Then make Bestmove a local variable and return (maxEval, BestMove). On the caller side you can extract Item1 from that tuple:

var eval = Minimax(model_.PossiblePositions[i], depth - 1, alpha, beta, false).Item1;

And the top-level caller can take Item2 for getting the best move (adapt the arguments to what you have):

var bestmove = Minimax(model_, depth, -double.PositiveInfinity, double.PositiveInfinity, true).Item2;

answered Mar 30, 2023 at 8:22

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

ImNotARobot Over a year ago

Thank you! My only Question left is: where should I set the bestmove variable in the algorithm?

trincot Over a year ago

You would define it where you make the initial call to Minimax (so where you need to know what move to play). I provided the code idea for that at the end of my answer. That is where you define that variable -- it doesn't need a large scope as you only need it to actually play that move right after that, and then you no longer need it.

trincot Over a year ago

In the Minimax function you can do like you already did with the if (maxEval == eval) statement, but obviously you need to do a similar thing for the minimizing user (in the else block).

Collectives™ on Stack Overflow

Make Minimax return Move and Number

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related