Шахматы: ошибка в альфа-бете
Я использую шахматный движок и написал довольно сложную процедуру альфа-бета поиска с таблицами поиска покоя и транспозиции. Однако я наблюдаю странную ошибку.
Функция оценки использует таблицы с квадратными фигурами, как эта для пешек:
static int ptable_pawn[64] = {
0, 0, 0, 0, 0, 0, 0, 0,
30, 35, 35, 40, 40, 35, 35, 30,
20, 25, 25, 30, 30, 25, 25, 20,
10, 20, 20, 20, 20, 20, 20, 10,
3, 0, 14, 15, 15, 14, 0, 3,
0, 5, 3, 10, 10, 3, 5, 0,
5, 5, 5, 5, 5, 5, 5, 5,
0, 0, 0, 0, 0, 0, 0, 0
};
Когда наступает чёрный ход, таблица отражается по оси X. В частности, если вам интересно, поиск происходит следующим образом: столбцы AH отображаются на 0-7, а строки на 0-7 со стороны белых:
int ptable_index_for_white(int col, int row) {
return col+56-(row*8);
}
int ptable_index_for_black(int col, int row) {
return col+(row*8);
}
Таким образом, пешка на h4 (координаты 7, 3) стоит 3 очка (сантипавны) для белых, а пешка на f6 (координаты 5, 5) стоит 3 сантипавона для черных.
Вся функция оценки в настоящее время представляет собой квадратные таблицы и материал.
На больших глубинах поиска мой движок выбирает действительно ужасные движения. Рассмотрим этот вывод, сгенерированный из начальной позиции:
Iterative Deepening Analysis Results (including cached analysis)
Searching at depth 1... d1 [+0.10]: 1.b1c3
(4 new nodes, 39 new qnodes, 0 qnode aborts, 0ms), 162kN/s
Searching at depth 2... d2 [+0.00]: 1.e2e4 d7d5
(34 new nodes, 78 new qnodes, 0 qnode aborts, 1ms), 135kN/s
Searching at depth 3... d3 [+0.30]: 1.d2d4 d7d5 2.c1f4
(179 new nodes, 1310 new qnodes, 0 qnode aborts, 4ms), 337kN/s
Searching at depth 4... d4 [+0.00]: 1.g1f3 b8c6 2.e2e4 d7d5
(728 new nodes, 2222 new qnodes, 0 qnode aborts, 14ms), 213kN/s
Searching at depth 5... d5 [+0.20]: 1.b1a3 g8f6 2.d2d4 h8g8 3.c1f4
(3508 new nodes, 27635 new qnodes, 0 qnode aborts, 103ms), 302kN/s
Searching at depth 6... d6 [-0.08]: 1.d2d4 a7a5 2.c1f4 b7b6 3.f4c1 c8b7
(21033 new nodes, 112915 new qnodes, 0 qnode aborts, 654ms), 205kN/s
Searching at depth 7... d7 [+0.20]: 1.b1a3 g8f6 2.a1b1 h8g8 3.d2d4 g8h8 4.c1f4
(39763 new nodes, 330837 new qnodes, 0 qnode aborts, 1438ms), 258kN/s
Searching at depth 8... d8 [-0.05]: 1.e2e4 a7a6 2.e4e5 a6a5 3.h2h4 d7d6 4.e5d6 c7d6
(251338 new nodes, 2054526 new qnodes, 0 qnode aborts, 12098ms), 191kN/s
На глубине 8 обратите внимание, что черные открываются ходами "... a7a6 ... a6a5", которые ужасны в соответствии с таблицей фигурных квадратов. Кроме того, "h2h4" - ужасный ход для белых. Почему моя функция поиска выбирает такие причудливые ходы? Примечательно, что это начинает происходить только на больших глубинах (ходы на глубине 3 выглядят хорошо).
Более того, поиски часто приводят к ошибкам! Рассмотрим следующую позицию:
Движок рекомендует ужасную ошибку (3... f5h3), почему-то упускает очевидный ответ (4. g2h3):
Searching at depth 7... d7 [+0.17]: 3...f5h3 4.e3e4 h3g4 5.f2f3 g8f6 6.e4d5 f6d5
(156240 new nodes, 3473795 new qnodes, 0 qnode aborts, 17715ms), 205kN/s
Поиск покоя не задействован, так как ошибка происходит на уровне 1 (!!).
Вот код для моих функций поиска. Я извиняюсь, что это так долго: я упростил, как мог, но я не могу знать, какие части не имеют отношения к ошибке. Я предполагаю, что мой алгоритм как-то немного не так.
Реализация основана на этом из Википедии, почти точно. (Обновление: я значительно упростил поиск, и моя ошибка все еще присутствует.)
// Unified alpha-beta and quiescence search
int abq(board *b, int alpha, int beta, int ply) {
pthread_testcancel(); // To allow search worker thread termination
bool quiescence = (ply <= 0);
// Generate all possible moves for the quiscence search or normal search, and compute the
// static evaluation if applicable.
move *moves = NULL;
int num_available_moves = 0;
if (quiescence) moves = board_moves(b, &num_available_moves, true); // Generate only captures
else moves = board_moves(b, &num_available_moves, false); // Generate all moves
if (quiescence && !useqsearch) return relative_evaluation(b); // If qsearch is turned off
// Abort if the quiescence search is too deep (currently 45 plies)
if (ply < -quiesce_ply_cutoff) {
sstats.qnode_aborts++;
return relative_evaluation(b);
}
// Allow the quiescence search to generate cutoffs
if (quiescence) {
int score = relative_evaluation(b);
alpha = max(alpha, score);
if (alpha >= beta) return score;
}
// Update search stats
if (quiescence) sstats.qnodes_searched++;
else sstats.nodes_searched++;
// Search hueristic: sort exchanges using MVV-LVA
if (quiescence && mvvlva) nlopt_qsort_r(moves, num_available_moves, sizeof(move), b, &capture_move_comparator);
move best_move_yet = no_move;
int best_score_yet = NEG_INFINITY;
int num_moves_actually_examined = 0; // We might end up in checkmate
for (int i = num_available_moves - 1; i >= 0; i--) { // Iterate backwards to match MVV-LVA sort order
apply(b, moves[i]);
// never move into check
coord king_loc = b->black_to_move ? b->white_king : b->black_king; // for side that just moved
if (in_check(b, king_loc.col, king_loc.row, !(b->black_to_move))) {
unapply(b, moves[i]);
continue;
}
int score = -abq(b, -beta, -alpha, ply - 1);
num_moves_actually_examined++;
unapply(b, moves[i]);
if (score >= best_score_yet) {
best_score_yet = score;
best_move_yet = moves[i];
}
alpha = max(alpha, best_score_yet);
if (alpha >= beta) break;
}
// We have no available moves (or captures) that don't leave us in check
// This means checkmate or stalemate in normal search
// It might mean no captures are available in quiescence search
if (num_moves_actually_examined == 0) {
if (quiescence) return relative_evaluation(b); // TODO: qsearch doesn't understand stalemate or checkmate
coord king_loc = b->black_to_move ? b->black_king : b->white_king;
if (in_check(b, king_loc.col, king_loc.row, b->black_to_move)) return NEG_INFINITY; // checkmate
else return 0; // stalemate
}
// record the selected move in the transposition table
evaltype type = (quiescence) ? qexact : exact;
evaluation eval = {.best = best_move_yet, .score = best_score_yet, .type = type, .depth = ply};
tt_put(b, eval);
return best_score_yet;
}
/*
* Returns a relative evaluation of the board position from the perspective of the side about to move.
*/
int relative_evaluation(board *b) {
int evaluation = evaluate(b);
if (b->black_to_move) evaluation = -evaluation;
return evaluation;
}
Я вызываю поиск следующим образом:
int result = abq(b, NEG_INFINITY, POS_INFINITY, ply);
Редактировать: ошибка сохраняется, даже когда я упростил процедуру поиска. Двигатель просто расшвыривает куски. Вы можете легко увидеть это, загрузив его в XBoard (или любой другой UCI-совместимый графический интерфейс) и сыграв на сильном движке. По просьбе Манлио я загрузил код:
Вот репозиторий GitHub (ссылка удалена; проблема была во фрагменте выше). Он будет собираться с использованием "make" в OS X или любой *nix системе.
2 ответа
if (score >= best_score_yet) {
должно быть:
if (score > best_score_yet) {
или вы собираетесь рассматривать плохие ходы. Первый best_move_yet будет правильно (так как best_score_yet = NEG_INFINITY) но другие ходы с score == best_score_yet не обязательно лучше.
Изменение этой строки:
Начальная позиция
Iterative Deepening Analysis Results (including cached analysis)
Searching at depth 1... d1 [+0.10]: 1.e2e4
(1 new nodes, 4 new qnodes, 0 qnode aborts, 0ms, 65kN/s)
(ttable: 1/27777778 = 0.00% load, 0 hits, 0 misses, 1 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 2... d2 [+0.00]: 1.e2e4 g8f6
(21 new nodes, 41 new qnodes, 0 qnode aborts, 0ms, 132kN/s)
(ttable: 26/27777778 = 0.00% load, 0 hits, 0 misses, 25 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 3... d3 [+0.30]: 1.d2d4 g8f6 2.c1f4
(118 new nodes, 247 new qnodes, 0 qnode aborts, 5ms, 73kN/s)
(ttable: 187/27777778 = 0.00% load, 0 hits, 0 misses, 161 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 4... d4 [+0.00]: 1.e2e4 g8f6 2.f1d3 b8c6
(1519 new nodes, 3044 new qnodes, 0 qnode aborts, 38ms, 119kN/s)
(ttable: 2622/27777778 = 0.01% load, 0 hits, 0 misses, 2435 inserts (with 0 overwrites), 1 insert failures)
Searching at depth 5... d5 [+0.10]: 1.g2g3 g8f6 2.f1g2 b8c6 3.g2f3
(10895 new nodes, 35137 new qnodes, 0 qnode aborts, 251ms, 184kN/s)
(ttable: 30441/27777778 = 0.11% load, 0 hits, 0 misses, 27819 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 6... d6 [-0.08]: 1.d2d4 g8f6 2.c1g5 b8c6 3.g5f6 g7f6
(88027 new nodes, 249718 new qnodes, 0 qnode aborts, 1281ms, 264kN/s)
(ttable: 252536/27777778 = 0.91% load, 0 hits, 0 misses, 222095 inserts (with 0 overwrites), 27 insert failures)
Searching at depth 7... d7 [+0.15]: 1.e2e4 g8f6 2.d2d4 b8c6 3.d4d5 c6b4 4.g1f3
(417896 new nodes, 1966379 new qnodes, 0 qnode aborts, 8485ms, 281kN/s)
(ttable: 1957490/27777778 = 7.05% load, 0 hits, 0 misses, 1704954 inserts (with 0 overwrites), 817 insert failures)
Находясь в тестовом положении:
Calculating...
Iterative Deepening Analysis Results (including cached analysis)
Searching at depth 1... d1 [+2.25]: 3...g8h6 4.(q)c3d5 (q)d8d5
(1 new nodes, 3 new qnodes, 0 qnode aborts, 0ms, 23kN/s)
(ttable: 3/27777778 = 0.00% load, 0 hits, 0 misses, 3 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 2... d2 [-0.13]: 3...f5e4 4.c3e4 (q)d5e4
(32 new nodes, 443 new qnodes, 0 qnode aborts, 3ms, 144kN/s)
(ttable: 369/27777778 = 0.00% load, 0 hits, 0 misses, 366 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 3... d3 [+0.25]: 3...g8h6 4.c3e2 h6g4
(230 new nodes, 2664 new qnodes, 0 qnode aborts, 24ms, 122kN/s)
(ttable: 2526/27777778 = 0.01% load, 0 hits, 0 misses, 2157 inserts (with 0 overwrites), 0 insert failures)
Searching at depth 4... d4 [-0.10]: 3...g8f6 4.e3e4 f5e6 5.f1b5
(2084 new nodes, 13998 new qnodes, 0 qnode aborts, 100ms, 162kN/s)
(ttable: 15663/27777778 = 0.06% load, 0 hits, 0 misses, 13137 inserts (with 0 overwrites), 2 insert failures)
Searching at depth 5... d5 [+0.15]: 3...g8f6 4.f1e2 h8g8 5.g2g4 f5e4 6.(q)c3e4 (q)f6e4
(38987 new nodes, 1004867 new qnodes, 0 qnode aborts, 2765ms, 378kN/s)
(ttable: 855045/27777778 = 3.08% load, 0 hits, 0 misses, 839382 inserts (with 0 overwrites), 302 insert failures)
Я был бы рад взглянуть на реальный репозиторий, но я сталкивался с этой проблемой много раз при реализации подобных игровых алгоритмов. Я скажу вам, что вызвало проблемы для меня, и вы можете проверить, если вы делаете те же ошибки. Они перечислены в том порядке, в котором, как я полагаю, скорее всего, решится ваша проблема.
Слои - это не ходы, ходы должны увеличиваться на 2 на каждую итерацию (это и есть слой)
На эту ошибку почти всегда указывает плохой выбор почти каждого хода для первого игрока, потому что они никогда не видят последствий неудачного хода. Чтобы избежать этого, увеличьте количество ходов на 2 (или, в более общем случае, на количество игроков в игре, но вы используете minmax, так что это 2). Это гарантирует, что каждый игрок всегда ищет последствия вплоть до следующего хода.
Оценка всегда должна быть сделана с точки зрения текущего игрока
Это звучит очевидным, но я клянусь, я вверты это каждый раз, когда я реализую функцию оценки. При разработке оценки мы всегда проектируем ее таким образом, с точки зрения первого игрока, который будет играть, когда мы должны разработать ее так, чтобы она возвращала оценку текущего игрока. Мы можем сказать, чей ход игрока, потому что у нас полное состояние доски, поэтому нет необходимости передавать его.
Это особенно сложно отладить, если ваш вызов вычисления не является первым вызовом в вашей функции minmax, но вы реализовали его таким образом, так что это не проблема.
Функция оценки должна быть симметричной
Это особенно неприятная ошибка, когда это происходит. Идея состоит в том, что один и тот же игрок будет по-разному оценивать одну и ту же позицию в зависимости от того, выигрывал он или проигрывал.
Возьмем, к примеру, шахматы, где, как выигравший игрок, вы хотите выиграть наименьшее количество ходов, но если вы собираетесь проиграть, вы хотите проиграть за самое длинное количество ходов. Типичное решение для этого - сказать, что если вы собираетесь выиграть, добавьте бонус за победу за меньшее количество ходов, но если вы собираетесь проиграть, добавьте бонус за более длинные последовательности. Это приводит к добавлению бонуса по противоположным причинам в зависимости от ситуации и удаляет симметрию из оценки так, что Игрок A не равен -Player B. Когда вы теряете эту симметрию, вы больше не можете просто передавать значения обратно в дерево игры, Вы должны переоценивать их на каждом этапе.
Но хитрость в том, что делать такие корректировки всегда неправильно. При глубокой статической оценке он просто рано отключится, если найдет гарантированный выигрыш. С итеративными решениями углубления это все еще найдет более раннюю победу сначала. Мат в 5 никогда не будет матом в 4, если оппонент не ошибается, поэтому такие корректировки не нужны.
Дважды проверьте, что у вас нет столкновений с таблицей транспозиции
Я не вижу реализации вашей таблицы транспонирования, но если вы имеете дело с большим количеством состояний, чем выделено для хранения, то вы должны убедиться, что это одна и та же позиция, прежде чем доверять значению. Я сомневаюсь, что это проблема, поскольку похоже, что вы просматриваете только несколько миллионов узлов, но всегда полезно перепроверить. Кроме того, убедитесь, что ваша хеш-функция достаточно случайна, чтобы избежать регулярных коллизий.
mtd_f не следует обращаться к таблице транспонирования
mtd_f является сквозной функцией, которая будет правильно обрабатывать таблицу транспонирования при первом вызове negamax, Вы неправильно используете значение из него, как оно реализовано сейчас, но простое удаление этого кода очистит реализацию и правильно обработает ее. Кроме того, вы должны передать оценку mtd_f Функция на каждой итерации, а не пытаться загрузить его каждый раз.