Прелюдии: Я понимаю, этот вопрос может быть слишком широким для такого переполнения стека. Хотя, я пытался добавить столько информации, сколько мог придумать.Транспонирование таблицы приводит к движку потерять
Я кодирую шахматный движок в C++ с нуля, и это в основном сделано (за исключением того, что у него слабая функция оценки). Странно, однако, что двигатель теряет каждый раз, когда таблица транспонирования включена, удивительно очевидной ошибкой (отдает королеву, а иногда и королеву и другую часть). Когда зондирование транспозиционного стола отключено, двигатель легко побеждает против Nero и TSCP.
Я использую очень простую реализацию таблицы транспозиций с помощью схемы всегда замены, взятой с сайта Брюса Морланда here.
Вот реализация зонда:
bool probe_table(TranspositionTable& t_table, unsigned int ply,
uint64 hash_key, unsigned int depth, unsigned int& pv_move, int& score,
int alpha, int beta)
{
unsigned int index = hash_key % t_table.num_entries;
assert(index < t_table.num_entries);
if(t_table.t_entry[index].hash_key == hash_key)
{
pv_move = t_table.t_entry[index].move;
if(t_table.t_entry[index].depth >= depth)
{
score = t_table.t_entry[index].score;
if(score > IS_MATE) score -= ply;
else if(score < -IS_MATE) score += ply;
switch(t_table.t_entry[index].flag)
{
case TFALPHA:
{
if(score <= alpha)
{
score = alpha;
return 1;
}
}
case TFBETA:
{
if(score >= beta)
{
score = beta;
return 1;
}
}
case TFEXACT:
{
return 1;
}
default: assert(false); // At least one flag must be set.
}
}
}
return 0;
}
Во время альфа-бета поиска, таблица зондировании (записи хранятся правильно, а также, в зависимости от обрезаний и такие):
if(probe_table(board.t_table, board.ply, board.hash_key, depth, pv_move,
score, alpha, beta))
{
return score;
}
Редактирование: Для полноты здесь приведен фрагмент важных бит кода хранения в поиске:
if(score > alpha) // Alpha cutoff.
{
if(score >= beta) // Beta cutoff.
{
...
store_entry(board.t_table, board.ply, board.hash_key, best_move,
beta, depth, TFBETA);
return beta;
}
alpha = score;
...
}
}
...
assert(alpha >= old_alpha);
if(alpha != old_alpha)
{
store_entry(board.t_table, board.ply, board.hash_key, best_move,
best_score, depth, TFEXACT);
}
else
{
store_entry(board.t_table, board.ply, board.hash_key, best_move,
alpha, depth, TFALPHA);
}
Я рассмотрел и исследовал сбои в любой другой части двигателя, и никто не происходит. Прекрасно отключает тестирование (но все еще использует таблицу для хранения PV-линий).
Я также подумал, влияет ли мое наивное осуществление размышлений на вещи. Чтобы поразмыслить, я просто распечатываю bestmove xxxx ponder xxxx в UCI всякий раз, когда доступно движение размышлений. Если размышление включено, графический интерфейс позволяет движку задуматься (что является обычным поиском, но позже будет использоваться с помощью таблицы транспонирования).
Чтобы проверить, я полностью отключил размышления, что не показало никакого улучшения. После некоторого выигрышного момента двигатель просто отдал свою королеву. Я считаю, что это происходит либо из-за плохой записи в таблице, либо, возможно, из-за какой-то другой нестабильности, которую я не могу понять.
И здесь мне нужен кто-то, кто столкнулся с этим прежде, чем указал мне в общем направлении.
Редактировать: Как спросил grek40, вот пример, который просто проходил (двигатель белый, белый двигаться):
двигатель снова один, потеряли игру на основе глупы движется. Обратите внимание, что двигатель достиг плохого положения, такого как, вероятно, из-за самой таблицы транспонирования.
Анализируя эту позицию с за столом транспозиции заполненных во время игры:
info score cp -425 depth 1 nodes 1 time 0 pv e1d1
info score cp -425 depth 2 nodes 2 time 0 pv e1d1
info score cp -425 depth 3 nodes 3 time 0 pv e1d1
info score cp -425 depth 4 nodes 4 time 0 pv e1d1
info score cp -425 depth 5 nodes 5 time 0 pv e1d1
info score cp -425 depth 6 nodes 6 time 0 pv e1d1
info score cp -425 depth 7 nodes 7 time 0 pv e1d1
info score cp -425 depth 8 nodes 8 time 0 pv e1d1
info score cp -425 depth 9 nodes 9 time 0 pv e1d1
info score cp -425 depth 10 nodes 10 time 0 pv e1d1
info score cp -440 depth 11 nodes 10285162 time 3673 pv f5f8 e7f8 b2b3 b7b5 e1c1 d6d5 a3a4
info score cp -440 depth 12 nodes 29407669 time 10845 pv f5f8 e7f8 e1f1 f8e7 f1f5 d6d5
bestmove f5f8 ponder e7f8
еще раз Анализируя без транспозиции таблицы (на самом деле, с таблицей, но очищается):
info score cp -415 depth 1 nodes 82 time 0 pv f5f8
info score cp -415 depth 2 nodes 200 time 0 pv f5f8 e7f8
info score cp -405 depth 3 nodes 900 time 0 pv f5f8 e7f8 b2b3
info score cp -425 depth 4 nodes 2936 time 1 pv f5f8 e7f8 b2b3 f8e7
info score cp -415 depth 5 nodes 10988 time 4 pv f5f8 e7f8 b2b3 b7b5 e1d1
info score cp -425 depth 6 nodes 65686 time 25 pv f5f8 e7f8 e1f1 d7e7 f1d1 b7b5
info score cp -420 depth 7 nodes 194124 time 76 pv f5f8 e7f8 b2b3 b7b5 e1f1 f8e7 f1f7
info score cp -425 depth 8 nodes 357753 time 141 pv f5f8 e7f8 b2b3 b7b5 e1f1 f8e7 f1f5 d7c7
info score cp -425 depth 9 nodes 779686 time 292 pv f5f8 e7f8 e1f1 f8e7 f1f5 h4h8
info score cp -425 depth 10 nodes 1484178 time 560 pv f5f8 e7f8 e1f1 f8e7 f1f5 h4h8
info score cp -435 depth 11 nodes 29481132 time 11117 pv f5f8 d6d5 e1e5
info score cp -435 depth 12 nodes 106448053 time 41083 pv f5f8 e7f8
bestmove f5f8 ponder e7f8
Следует отметить, что на глубине 10, оценка точна из поиска таблицы транспозиции.
Редактировать: Данная позиция была проанализирована после игры. Во время игры у двигателя не было достаточно времени для завершения поиска на более высокую глубину, в результате чего он играл e1d1, что смешно.
Зачем это произошло? Двигатель обнаруживает лучший ход с глубины 1, но из таблицы транспозиций был найден другой ход. Я также задаюсь вопросом, почему нет линии PV в поиске таблицы транспозиции.
Моя догадка бы поиск Нестабильность цитата из сайта Брюса Морланда здесь: Ключ Зобрист не принимает во внимание тот путь, чтобы добраться до узла. Не каждый путь один и тот же. Возможно, что оценка в элементе хэша может быть основана на пути, который будет содержать повторение, если он встречается в какой-либо другой точке дерева. Повторение может привести к оценке ничьей или, по крайней мере, другому результату.
Редактировать: Я попытался отключить хранение таблицы, когда нет значения TFEXACT. То есть я прекратил хранить и извлекать значения TFALPHA/TFBETA, и он прекрасно работает. Кто-нибудь знает, почему?
Можете ли вы воспроизвести свою проблему с детерминированной последовательностью ходов? – grek40
Вам нужно будет отладить код. Выясните, какие именно пути кода выполняются, что приводит к плохому движению, которое происходит из-за проверки таблицы транспозиции. Добавьте функции для выгрузки таблицы. Добавьте модульные тесты только для таблицы. Распечатайте что-нибудь, когда вы, кажется, определите, что произошло перестановка. –
@ grek40 Добавлен пример, который только что состоялся. –