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

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

Источник

2 ответа

Решение

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

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

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

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

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

Снова отредактируйте: есть два вызова - правильно ли клонируется?

Источник

Нашел проблему.

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

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

Источник
Другие вопросы по тегам