Шахматы: ошибка в альфа-бета

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

Функция оценки использует кусочно-квадратные таблицы, например, для пешек:

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. В частности, если вам интересно, поиск происходит таким образом, когда столбцы A-H отображаются в 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 (или любой другой UII-совместимый графический интерфейс) и играя против сильного движка. При запросе manlio я загрузил код:

Вот репозиторий GitHub (ссылка удалена, проблема была в фрагменте выше). Он будет строить с использованием "make" в OS X или любой системе * nix.

Ответ 1

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

Я был бы рад взглянуть на фактическое репо, но я испытал эту точную проблему много раз, внедряя аналогичные игровые алгоритмы. Я расскажу вам, что вызвало проблемы для меня, и вы можете проверить, допустите ли вы те же ошибки. Они перечислены в том порядке, в котором, я думаю, наиболее вероятно, чтобы решить вашу проблему.

Plys не перемещаются, ходы должны увеличиваться на 2 каждой итерации (это то, что слой)

Эта ошибка почти всегда указывается, делая неудовлетворительные выборы почти для каждого хода для первого игрока, потому что они никогда не видят последствий плохого движения. То, как вы избегаете этого, - это увеличение на 2 (или более общее число игроков в игре, но вы используете minmax, так что это 2). Это гарантирует, что каждый игрок всегда будет искать последствия до следующего хода.

Оценка всегда должна выполняться с точки зрения текущего игрока

Это звучит очевидно, но я клянусь, что каждый раз, когда я реализую функцию оценки, я вставляю ее. При разработке оценки мы всегда разрабатываем его таким образом с точки зрения первого игрока, чтобы играть, когда мы должны его разрабатывать, чтобы вернуть оценку текущего игрока. Мы можем сказать, какой игрок его поворачивает, потому что у нас есть полное состояние платы, поэтому нет необходимости передавать его.

Это особенно сложно отладить, если ваш вызов оценки не является первым вызовом в вашей функции minmax, но вы внедрили его таким образом, так что это не проблема.

Функция оценки должна быть симметричной

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

Возьмите, к примеру, в шахматы, где, как победитель, вы хотите выиграть наименьшее количество ходов, но если вы проиграете, вы хотите проиграть в самом длинном числе ходов. Типичным решением для этого является то, что если вы собираетесь выиграть, добавьте бонус на выигрыш в меньшем количестве ходов, но если вы проиграете, добавьте бонус для более длинных последовательностей. Это приводит к добавлению бонуса по разным причинам в зависимости от ситуации и удалению симметрии из оценки, так что игрок A не равен -Player B. Когда вы теряете эту симметрию, вы уже не можете просто передавать значения обратно в дерево игры, вы должны переоценить их на каждом шагу.

Но трюк заключается в том, что такие корректировки всегда ошибочны. С глубокой статической оценкой он будет просто отрезан раньше, если найдет гарантированный выигрыш. С итерационными углубляющимися решениями он все равно найдет первую победу. Помощник в 5 никогда не бывает помощником в 4, если противник не промахивается, поэтому корректировки, подобные этому, никогда не нужны.

Дважды проверьте, что у вас нет столкновений с таблицей транспонирования

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

`mtd_f` не следует обращаться к таблице транспонирования

mtd_f - это транзитная функция, которая правильно обрабатывает таблицу транспонирования при первом вызове negamax. Вы неправильно используете значение из него, поскольку оно реализовано сейчас, но просто удаление этого кода очистит реализацию и обработает ее правильно. Кроме того, вы должны передать оценку функции mtd_f на каждой итерации, а не пытаться загружать ее каждый раз.