Я пытаюсь реализовать NegaMax для игры в шашки. Я просто тестирую это с глубиной 0 прямо сейчас, что означает, что текущий игрок просто оценивает все свои ходы, не обращая внимания на то, что другой игрок может сделать дальше. Он отлично работает примерно половину игры (правильно подсчитывает очки), а затем в середине начинает выдавать бессмысленные ответы.
Например, у белых может остаться 1 фигура, а у черных - 5, но ходы белых будут оценены, например, как 7, тогда как все они должны быть отрицательными, потому что он проигрывает. Черные могут выиграть следующим ходом, но они оценят выигрышный ход как -4, хотя он должен быть 1000.
Я могу понять, что он постоянно выводит мусор, но почему он работает первые несколько ходов, а затем начинает глючить?
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));
}
Я выделил состояние доски, которое ему не нравится, на доске 6x6:
. . .
. w B
W . .
. . .
. w .
. . W
w = white, b = black, capital letter = king
Похоже, что это не проблема времени или количества сыгранных ходов, ему просто не нравятся определенные состояния доски. Хотя ничего особенного в этом состоянии я не вижу.
В этом состоянии он оценивает все 4 хода черных как -13. Если вы посмотрите, как я подсчитывал очки, там написано 2 очка за человека, 3 очка за короля, минус, если он принадлежит другому игроку. Похоже, он считает все фигуры белыми... это единственный способ получить 13.
Я нашел еще одну зацепку. В методе оценки доски я заставил его напечатать то, что он видит ... вот что он мне говорит:
2: White
4: White
6: White
13: White
17: White
Где квадраты доски пронумерованы следующим образом:
00 01 02
03 04 05
06 07 08
09 10 11
12 13 14
15 16 17
Я думаю, что это действительно говорит о том, что черная фигура белая...... теперь, чтобы выяснить, что вызывает это.
Итак... теперь я знаю, что цвет неправильный, но только для функции BoardScore
. Моя обычная процедура отображения никогда не замечала этого, иначе я бы понял проблему несколько часов назад. Я думаю, что это может быть в функции ApplyMove
, что цвет переключается..
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;
}
Но это тоже не имеет большого смысла... кусок просто копируется из начальной позиции в конечную позицию. Нужно выяснить, что такое m.Color
... возможно, это даст больше подсказок! Я чувствую себя детективом.
tmpScore = -NegaMax(Board.Opposite(color), boardAfterMove, depth);
. Если предполагается сделать это значение отрицательным, попробуйте-1 * NegaMax(...
- person Jim Schubert   schedule 06.09.2010-(someMethod())
или-1 * someMethod()
иногда приводит к неожиданным результатам. Я не знаю точно, почему, и я всегда предполагал, что-
оптимизируется неправильно. - person Jim Schubert   schedule 07.09.2010