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!
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;