I have been trying to implement a good AI for a checkers game made in Unity3D, by searching online I've found the best choice to be MiniMax/Negamax, so I have created this class:
public static class NegaMax
{
public static IMiniMaxNode FindBestChoice(IEnumerable<IMiniMaxNode> choices, int depth, int sign)
{
// if I simply use -Calculate(...) I'm obtaining different results based on whether the depth is even or odd
// I suspect this is wrong nonetheless
int inverter = (depth % 2 == 0) ? 1 : -1;
IMiniMaxNode bestNode = null;
float alpha = float.NegativeInfinity;
foreach (var choice in choices)
{
var score = inverter * Calculate(choice, depth - 1, float.NegativeInfinity, -alpha, -sign);
if (score > alpha)
{
alpha = score;
bestNode = choice;
}
}
return bestNode;
}
private static float Calculate(IMiniMaxNode node, int depth, float alpha, float beta, int sign)
{
if (depth == 0)
{
return node.CalculateValue() * sign;
}
node.CreateChildren();
if (node.Children.Length == 0) // if the opponent has no possible move
{
return sign / 0f; // (sign == 1) ? positive infinity : negative infinity
}
// standard negamax
var bestValue = float.NegativeInfinity;
for (int i = 0; i < node.Children.Length; i++)
{
var value = -Calculate(node.Children[i], depth - 1, -beta, -alpha, -sign);
bestValue = Math.Max(bestValue, value);
alpha = Math.Max(alpha, bestValue);
if (alpha >= beta)
{
return bestValue;
}
}
return bestValue;
}
}
where IMiniMaxNode is the following interface:
public interface IMiniMaxNode
{
IMiniMaxNode Parent { get; }
IMiniMaxNode[] Children { get; }
float CalculateValue();
void CreateChildren();
}
and the actual implementation is this one:
public class CheckersMove : IMiniMaxNode
{
public int Team { get; private set; }
public IMiniMaxNode Parent { get; private set; }
public IMiniMaxNode[] Children { get; private set; }
public float CalculateValue()
{
// data.state is the current board array after this move has been applied
// the board array is an int[8,8]:
// empty = 0, black pawn = -1, black king = -2, white pawn = 1, white king = 2
//
// and GetAbsoluteValue() simply returns a Sum of each element
return data.state.GetAbsoluteValue() * Team;
}
public void CreateChildren()
{
// calculate every possible move for the opponent and assign them to the Children array
// every child has Team = -Parent.Team
// also, if a move has multiple jumps, they all get included in the same node
}
// ... other methods and properties to calculate the possible moves,
// and to store movement data (starting position, movement deltas, jump[s], promotion)
}
I then use it inside of my CheckersAI class:
private static MovementData CalculateMoveInternal(State state)
{
// - state.team represents the team that has to make a move:
// black = -1, white = +1
// - state.input is the current board state, represented an int[8,8] array:
// empty = 0, black pawn = -1, black king = -2, white pawn = 1, white king = 2
// - state.depth is simply the depth argument for the negamax function
// create an empty root node, corresponding to the opponent's last move (hence -state.team)
var move = CheckersMove.CreateRoot(state.input, -state.team);
// calculate all possible moves for the current team
move.CreateChildren();
// find the best node amongst all of the root node children (shuffled to obtain different results if the best moves have the same value)
var result = NegaMax.FindBestChoice(move.Children.Shuffle(), state.depth, state.team) as CheckersMove;
// cache some values for debugging
_lastRootMove = move;
_lastChosenMove = result;
// convert the result node into a valid move for the engine
return CreateMovementData(result);
}
The AI seems to work alright for most of the match, but sometimes makes plain wrong decisions (e.g. sacrifices 2 pawns for no apparent reason), and sometimes it inverts the value of the "No Possible Moves" case, in that it assigns it positive infinity (victory) while it should have been negative infinity (lost).
I am 90% sure that the problem lies in a wrong sign somewhere, but I have been trying every possible combination of signs in each method, and the AI always makes unexpected decisions, I am testing it both as black team (-1) and white team (+1).
Could anyone help me, by pointing out what I could be doing wrong? I have tried to include all the relevant code and to comment every important passage. Thank You!