I'm trying to implement NegaMax for a game of checkers. I'm just testing it with a depth of 0 right now, meaning the current player just evaluates all his moves without regard to what the other player might do next. It works perfectly for about half the game (computes the scores correctly), and then part way through it starts spitting out non-sense answers.
For example, White might have 1 piece left, and Black will have 5, but it will evaluate White's moves as a score of 7 for example, when they should all be negative because he's losing. Black might about to win on his next move, but it will evaluate the winning move as a -4 even though it should be 1000.
I can understand it consistently outputting garbage, but why would it work for the first few turns and then start messing up?
private static Move GetBestMove(Color color, Board board, int depth)
{
var bestMoves = new List<Move>();
IEnumerable<Move> validMoves = board.GetValidMoves(color);
int highestScore = int.MinValue;
Board boardAfterMove;
int tmpScore;
var rand = new Random();
Debug.WriteLine("{0}'s Moves:", color);
foreach (Move move in validMoves)
{
boardAfterMove = board.Clone().ApplyMove(move);
if (move.IsJump && !move.IsCrowned && boardAfterMove.GetJumps(color).Any())
tmpScore = NegaMax(color, boardAfterMove, depth);
else
tmpScore = -NegaMax(Board.Opposite(color), boardAfterMove, depth);
Debug.WriteLine("{0}: {1}", move, tmpScore);
if (tmpScore > highestScore)
{
bestMoves.Clear();
bestMoves.Add(move);
highestScore = tmpScore;
}
else if (tmpScore == highestScore)
{
bestMoves.Add(move);
}
}
return bestMoves[rand.Next(bestMoves.Count)];
}
private static int NegaMax(Color color, Board board, int depth)
{
return BoardScore(color, board);
}
private static int BoardScore(Color color, Board board)
{
if (!board.GetValidMoves(color).Any()) return -1000;
return board.OfType<Checker>().Sum(c => (c.Color == color ? 1 : -1) * (c.Class == Class.Man ? 2 : 3));
}
I've isolated a board state that it doesn't like, on a 6x6 board:
. . .
. w B
W . .
. . .
. w .
. . W
w = white, b = black, capital letter = king
It appears that this is not a time or number-of-moves played issue, it just doesn't like particular board states. I don't see anything peculiar about this state though.
In this state, it evaluates all 4 of Black's moves as -13. If you look at how I did the scoring, it says 2 pts per man, 3 pts per king, negative if owned by the other player. It looks as though it is treating all the pieces as white...that's the only way to get 13.
I found another clue. In the board score method I got it to print what it's seeing.. this is what it's telling me:
2: White
4: White
6: White
13: White
17: White
Where the board squares are numbered like this:
00 01 02
03 04 05
06 07 08
09 10 11
12 13 14
15 16 17
I think it is indeed saying the black piece is white...... now to figure out what's causing this.
So... now I know that the color is wrong, but only to the BoardScore function. My normal display routine never picked up on this otherwise I would have figured out the problem hours ago. I'm thinking it might be in the ApplyMove function that the color gets switched..
public Board ApplyMove(Move m)
{
if (m.IsJump)
{
bool indented = m.Start % Width < _rowWidth;
int offset = indented ? 1 : 0;
int enemy = (m.Start + m.End) / 2 + offset;
this[m.Color, enemy] = Tile.Empty;
}
this[m.Color, m.End] = this[m.Color, m.Start];
this[m.Color, m.Start] = Tile.Empty;
var checker = this[m.Color, m.End] as Checker;
if (m.IsCrowned) checker.Class = Class.King;
return this;
}
But that doesn't make a lot of sense either... the piece is just copied from the start position to the end position. Need to investigate what m.Color is... perhaps it'll provide more clues! I feel like a detective.