Что может заставить это начать просчет через некоторое время?

Question

Я пытаюсь реализовать 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 ... возможно, это даст больше подсказок! Я чувствую себя детективом.

Answer 1

С учетом вашего описания я нахожу, что подозреваю данные цвета куска. Если бы он каким-то образом ошибся, он бы оценил все как отрицательные.

Я не слишком доволен своей функцией BoardScore - сложные формулы, подобные этому, хороши для скрытия ошибок и их трудно отлаживать.

Я бы добавил функцию Checker.Value (Color), чтобы упростить BoardScore и позволить вам более легко просматривать то, что происходит.

Вы не указали тип данных Цвет, если он допускает более чем черно-белое поврежденное значение, это приведет к поведению, которое вы наблюдаете.

Учитывая ваше последнее обновление, я бы посмотрел на boardAfterMove и удостоверился, что он сгенерирован правильно.

Изменить еще раз: есть два звонка - он клонирует правильно?

Answer 2

Обнаружили проблему.

 foreach (char ch in checkers) 
     { 
      switch (ch) 
      { 
       case 'w': 
        Add(new Checker(Color.White, Class.Man)); 
        break; 
       case 'W': 
        Add(new Checker(Color.White, Class.King)); 
        break; 
       case 'b': 
        Add(new Checker(Color.Black, Class.Man)); 
        break; 
       case 'B': 
        Add(new Checker(Color.White, Class.King)); 
        break; 
       default: 
        Add(Tile.Empty); 
        break; 
      } 
     } 

Только с черными королями. Глупое клонирование !! Почему невозможно было сделать глубокое копирование?