Итак, мы добрались до самого сердца шахматной программы Стокфиш. Ее основной функции - search. Именно здесь бьется пульс этого движка.
Сейчас мы произведем разбор этой функции. О ее важности уже не раз говорилось на предыдущих страницах. Теперь нам предстоит понять, как основной поиск выглядит в реальной программе. Еще раз напомню, что функцию search можно найти в файле search.cpp. Обзорному описанию содержания этого файла была посвящена предыдущая часть
Исходные тексты программы Стокфиш можно найти на ее официальной страничке на гитхабе. Все примеры кода ниже приводятся по 18-й версии движка. С этой версией файла search.cpp можно ознакомиться по ссылке:
https://github.com/official-stockfish/Stockfish/blob/cb3d4ee9b47d0c5aae855b12379378ea1439675c/src/search.cpp
Функции pos. вызываемые далее по тексту, вынесены в отдельный файл position.cpp.
Основная функция перебора запускается со строки:
615 Value Search::Worker::search( Position& pos, Stack* ss, Value alpha, Value beta, Depth depth, bool cutNode)
Задаваемыми параметрами функции являются - позиция из которой будет производиться перебор, затем стек предыдущих и последующих ходов из текущей позиции по ветке варианта, далее значения альфы и беты, глубина на которую следует произвести расчет и тип узла.
На старте производится инициализация параметров и вычисление некоторых простейших функций, на которых мы не будем подробно останавливаться. Основное, что следует отметить - здесь происходит выход на QS, к форсированному перебору, если достигнута предельная глубина (depth=0).
Для большей наглядности каждый этап перебора разделен на выделенные "шаги" (Step). Наиболее важные из них начинаются с 7-го, поэтому по первым шагам пробежимся коротко.
Step 1. Initialize node
На первом шаге собственно происходит инициализация параметров для узла (позиции) дерева перебора в которой мы сейчас находимся.
Step 2. Check for aborted search and immediate draw
На втором шаге проверяются условия прерывания поиска и возможность ничейного результата.
Step 3. Mate distance pruning
На третьем шаге производим отсечение по мату. Логика проста - если в какой-либо ветке дерева перебора гарантированно ставится мат, допустим в пять ходов, то в остальных ветках нет смысла смотреть глубже. Лучшим вариантом все равно будет ветвь с наиболее коротким матом. По достижении аналогичной глубины расчетов в любой ветке можно прерывать перебор, поскольку он нам больше ничего не даст.
Step 4. Transposition table
На четвертом шаге проверяем, нет ли позиции в таблице перестановок (хеш-таблицах). То есть, не просматривалась ли данная позиция ранее на требуемую или большую глубину. Проверка осуществляется по хеш-ключу. Если позиция присутствует, то перебор из нее проводить не обязательно, используем данные из таблиц.
Step 5. Tablebases probe
На пятом шаге производится проверка эндшпильных баз, если они подключены. Нет смысла проводить перебор, если позиция уже есть в базах.
Step 6. Static evaluation of the position
На шестом шаге производится оценка позиции. Здесь через функцию evaluate(pos) и далее файл evaluate.cpp, происходит обращение к нейросети NNUE.
Это будет так называемая статическая оценка позиции, то есть оценка выполненная нейросетью на основе количества и взаимного расположения фигур, без их перемещения (а не та оценка, которую мы получаем после форсированного перебора qsearch).
Оценка целочисленная и рассчитывается в сантипешках. Это не значит, что цена пешки строго равна 100 единицам, но она достаточно близка к этому значению. Оценка возвращается с точки зрения той стороны, чей ход в данной позиции.
734 else 735 { 736 unadjustedStaticEval = evaluate(pos); 737 ss->staticEval = eval = to_corrected_static_eval(unadjustedStaticEval, correctionValue); 739 // Static evaluation is saved as it was before adjustment by correction history 740 ttWriter.write(posKey, VALUE_NONE, ss->ttPv, BOUND_NONE, DEPTH_UNSEARCHED, Move::none(), 741 unadjustedStaticEval, tt.generation()); 742 }
Надо сказать, что оценка нейросети не используется в переборе в чистом виде. Она предварительно корректируется с помощью некоторой статистики предыдущего перебора, называемой correctionHistory. Таким образом, на данном шаге сначала производится оценка позиции нейросетью, а затем ее корректировка.
Корректировка оценки основана на разнице между чистой оценкой нейросети и оценкой полученной после полноценного перебора из той же позиции. После каждого прохода поиска данные заносятся в специальные таблицы. Со временем correctionHistory накапливает статистику о разнице оценок. Вычисляемая на основании табличных значений величина поправки оперативно вносится на этом шаге. Для пополнения таблиц, позиция совсем не обязательно должна быть идентична предыдущим, достаточно лишь совпадения отдельных ключевых элементов. Для быстрого распознавания одинаковых структур используются хеш-ключи.
Общую структуру системы корректировки оценок можно посмотреть в файле history.h, там же где находятся сортировки по истории.
*****
После того как мы на предыдущих шагах попытались (и не нашли) позицию среди известных нам, и произвели её оценку, мы наконец-то можем заняться собственно самой позицией.
Всего в основном поиске 21 шаг и наиболее важные среди них шаги с 7-го по 20-й. Именно в них прописаны основное методы производящие сокращения/продления дерева перебора.
Нетрудно заметить, что каждый шаг выглядит достаточно типовым образом. Обычно его предваряют входные условия (if). Если они не выполняются, то шаг пропускается и происходит переход далее, к следующему шагу, где будет предпринята очередная попытка произвести отсечение.
if (...) { value = -search(...); }
Если условия выполняются, то могут быть проведены некоторые дополнительные процедуры. Далее, либо сразу производится отсечение, либо выполняется перебор (search) ходов из данной позиции на определенных условиях и на определенную глубину. Из него мы получаем динамическую оценку позиции (value), на основании которой принимается решение об отсечении данной ветки, переходе к следующему шагу или выбору другого направления перебора. Но обычно происходит переход к следующему шагу.
Сначала пробуем методы, которые могут привести к немедленному отсечению, без излишнего перебора.
Step 7. Razoring
Step 8. Futility pruning
На седьмом и восьмом шагах производятся отсечения, если перебор приблизился к предельной/заданной глубине (низкой depth).
870 // Step 7. Razoring 873 if (!PvNode && eval < alpha - 485 - 281 * depth * depth) 874 return qsearch<NonPV>(pos, ss, alpha, beta); 876 // Step 8. Futility pruning: child node 878 { 879 auto futility_margin = [&](Depth d) { ... ... 885 }; 887 if (!ss->ttPv && depth < 14 && eval - futility_margin(depth) >= beta && eval >= beta 888 && (!ttData.move || ttCapture) && !is_loss(beta) && !is_win(eval)) 889 return (2 * beta + eval) / 3; 890 }
Основной принцип следующий. Если по мере углубления по дереву перебора остался всего один полуход до достижения заданной глубины, а оценка позиции при этом уже настолько плоха, что последним полуходом ее никак не исправить, тогда этот ход можно не генерировать и не рассматривать и прервать перебор уже сейчас. Под плохой оценкой здесь подразумевается оценка ниже оценки основного варианта, обязательно с приличным запасом (futility_margin).
Если последний полуход "за соперника", то он никак не сможет повысить нам оценку, поэтому можно сразу отсекать. Такой метод называется Futility Pruning.
Если последний полуход "за нас", то переходим к qsearch. Обязательно нужно посмотреть форсированные ходы, поскольку хорошее взятие все еще может резко поднять нашу оценку. Тихие ходы можно пропустить. Такой метод называется Razoring.
Правило можно расширить на позиции за два, три и более полуходов до заданной глубины. Но с увеличением дистанции нужно увеличивать и запас по оценке. За расчет величины запаса отвечает отдельная функция.
Step 9. Null move search
На девятом шаге выполняются отсечения уже известным нам нулевым ходом (Null Move Pruning). Он подробно рассматривался во II и III частях настоящей статьи.
892 // Step 9. Null move search with verification search 893 if (cutNode && ss->staticEval >= beta - 18 * depth + 350 && !excludedMove 894 && pos.non_pawn_material(us) && ss->ply >= nmpMinPly && !is_loss(beta)) 895 { ... ... 898 // Null move dynamic reduction based on depth 899 Depth R = 7 + depth / 3; 900 do_null_move(pos, st, ss); 902 Value nullValue = -search<NonPV>(pos, ss + 1, -beta, -beta + 1, depth - R, false); 904 undo_null_move(pos); 906 // Do not return unproven mate or TB scores 907 if (nullValue >= beta && !is_win(nullValue)) 908 { ... ... 914 // Do verification search at high depths, with null move pruning disabled 915 // until ply exceeds nmpMinPly. 916 nmpMinPly = ss->ply + 3 * (depth - R) / 4; 918 Value v = search<NonPV>(pos, ss, beta - 1, beta, depth - R, false); 920 nmpMinPly = 0; 922 if (v >= beta) 923 return nullValue; 924 } 925 }
Аналогично, здесь сначала производится проверка условий допустимости нулевого хода, потом собственно пропуск хода (do_null) и пробный рекурсивный перебор за ту же сторону. Величина сокращения пробного перебора (R) рассчитывается в зависимости от глубины. При положительном исходе пробного перебора выполняется верификационный перебор, который окончательно решает, производить отсечение или нет.
Step 10. Internal iterative reductions (IIR)
На десятом шаге производится сокращение глубины, если позиции нет в хеш-таблице.
929 // Step 10. Internal iterative reductions 932 if (!allNode && depth >= 6 && !ttData.move && priorReduction <= 3) 933 depth--;
Для таких позиций оказалось выгоднее выполнять перебор с сокращенной глубиной. IIR очень похож на применявшийся ранее метод IID (Internal Iterative Deepening), но подходит к вопросу несколько иначе.
Step 11. ProbCut
Step 12. A small Probcut idea
На одиннадцатом и двенадцатом шаге выполняется отсечение методом ProbCut.
935 // Step 11. ProbCut 936 // If we have a good enough capture (or queen promotion) and a reduced search 937 // returns a value much above beta, we can (almost) safely prune the previous move. 938 probCutBeta = beta + 235 - 63 * improving; 939 if (depth >= 3 940 && !is_decisive(beta) 941 // If value from transposition table is lower than probCutBeta, don't attempt probCut there 943 && !(is_valid(ttData.value) && ttData.value < probCutBeta)) 944 { ... ... 947 MovePicker mp(pos, ttData.move, probCutBeta - ss->staticEval, &captureHistory); 948 Depth probCutDepth = std::clamp(depth - 5 - (ss->staticEval - beta) / 315, 0, depth); 950 while ((move = mp.next_move()) != Move::none()) 951 { ... ... 959 do_move(pos, move, st, ss); 961 // Perform a preliminary qsearch to verify that the move holds 962 value = -qsearch<NonPV>(pos, ss + 1, -probCutBeta, -probCutBeta + 1); 964 // If the qsearch held, perform the regular search 965 if (value >= probCutBeta && probCutDepth > 0) 966 value = -search<NonPV>(pos, ss + 1, -probCutBeta, -probCutBeta + 1, probCutDepth, 967 !cutNode); 969 undo_move(pos, move); 971 if (value >= probCutBeta) 972 { 973 // Save ProbCut data into transposition table 974 ttWriter.write(posKey, value_to_tt(value, ss->ply), ss->ttPv, BOUND_LOWER, 975 probCutDepth + 1, move, unadjustedStaticEval, tt.generation()); 977 if (!is_decisive(value)) 978 return value - (probCutBeta - beta); 979 } 980 } 981 }
Как мы уже знаем, альфа-бета рассматривает как минимум одно продолжение из позиции на заданную глубину, и если его оценка превышает бету, то производится отсечение. При этом не учитывается, насколько превышена бета. Но ведь можно учитывать величину превышения. Идея метода ProbCut заключается в том, что если оценка намного превышает бету, то перебор этого продолжения можно выполнить и на глубину меньше заданной.
Таким образом сначала выполняется перебор и проверяется оценка позиции на меньшей глубине, и если она окажется гораздо больше беты, то отсечение производится сразу. Можно предположить, что если ветка имеет большой запас по превышению беты на несколько сокращенной глубине, то с немалой долей вероятности она отсечется и на полной глубине, а расчетов можно будет выполнить гораздо меньше.
Величину уменьшенной глубины можно подбирать опытным путем. Специальным тестированием можно определить такой порог и глубину предварительного перебора, что отсечение будет наиболее эффективным и надежным. Если по итогам сокращенного перебора бета будет превышена на достаточную величину, то произойдет отсечение, результаты отправятся в хеш-таблицу и могут быть использованы позже.
ProbCut производит отсечения примерно в той же области дерева перебора что и нулевой ход. При этом он сравнительно менее эффективен. Поэтому как правило он применяется после нулевого хода и как бы "вдовесок" к нему. Работая на уже расчищенном нулевым ходом "поле", он приносит немного пользы, а потому применяется обычно только в ведущих программах.
В Стокфише ProbCut применяется для взятий с высокой оценкой. Код во многом напоминает основной перебор в миниатюре.
*****
Перед тринадцатым шагом производится инициализация некоторых параметров, в том числе параметров для сортировки.
996 MovePicker mp(pos, ttData.move, depth, &mainHistory, &lowPlyHistory, &captureHistory, contHist, 997 &sharedHistory, ss->ply); 999 value = bestValue; 1001 int moveCount = 0;
Step 13. Loop through all pseudo-legal moves until no moves remain or a beta cutoff occurs
На тринадцатом шаге запускается цикл генерации ходов (move = mp.next_move) из рассматриваемой позиции. По мере его выполнения будут рассмотрены все возможные ходы из позиции, если конечно в какой-то момент не произойдет отсечение и выход из цикла.
Ходы выдаются по одному за раз. Но пока они только определяются, а не выполняются на "внутренней доске" программы - эта операция будет произведена на 16 шаге. Выполнять ходы не нужно, поскольку программа сначала попытается их отсечь максимально быстро, используя только информацию о ходе. Перебор начнется позже.
Класс MovePicker, в том числе генератор ходов mp.next_move можно найти в файлах movepick. Как уже упоминалось ранее, для экономии ресурсов ходы генерируются "порционно", по стадиям сортировки.
1003 // Step 13. Loop through all pseudo-legal moves until no moves remain 1004 // or a beta cutoff occurs. 1005 while ((move = mp.next_move()) != Move::none()) 1006 { ... ... 1009 if (move == excludedMove) 1010 continue; 1012 // Check for legality 1013 if (!pos.legal(move)) 1014 continue; ... ... 1022 ss->moveCount = ++moveCount; ... ... 1029 if (PvNode) 1030 (ss + 1)->pv = nullptr; 1032 extension = 0; 1033 capture = pos.capture_stage(move); 1034 movedPiece = pos.moved_piece(move); 1035 givesCheck = pos.gives_check(move); 1037 // Calculate new depth for this move 1038 newDepth = depth - 1;
Одновременно с генерацией производится сортировка ходов. Методы сортировки разобраны нами во II части. Стокфиш в основном использует те же самые методы, кроме киллеров. Многочисленные таблицы сортировки по истории вполне заменили их, и необходимость в киллерах просто отпала.
Таблицы истории вынесены в отдельный файл history.h. Сам процесс сортировки можно посмотреть в файле movepick.cpp.
Таблицы ButterflyHistory и PieceToHistory в принципе одинаковы и отражают классическое представление таблиц истории. Различия между ними только в характере записи ходов. Аналогично как в записи шахматной партии, в одном случае используется запись хода координатами начального и конечного полей, а в другом запись фигура - конечное поле.
Конечно сейчас система сортировок стала более разнообразной, чем в старых программах. Кроме обычных таблиц истории здесь накапливается статистика отдельно для пешечных структур PawnHistory, для перебора вблизи корня LowPlyHistory, для взятий CapturePieceToHistory и таблицы отражающие связь предшествующих и последующих ходов ContinuationHistory. PawnHistory определяет пешечные формации с помощью хеш-ключей, аналогично тому как поступают таблицы корректировки оценки (см. Step 6).
После определения хода, который будет рассматриваться далее, проверяется его корректность с помощью функции pos.legal(move). Дело в том, что генератор не всегда выдает корректные ходы с точки зрения правил. Поэтому ходы выходящие из под генератора ходов называют псевдолегальными.
Некоторые ходы слишком трудоемко полноценно вычислять на этапе генерации ходов. Например взятия на проходе или рокировки. Можно проверить их на корректность позже, когда они уже будут "заиграны". Проще сделать такой ход и проверить, подвергается ли король атаке. Аналогичным образом функция pos.legal(move) проверяет также ходы королем под шах и связки.
Таким образом сначала генерируются так называемые псевдолегальные ходы, а недопустимые среди них отсеиваются уже после генерации, по ходу цикла. Еще раз напомню, что функции начинающиеся с pos. можно найти в файле position.cpp
Step 14. Pruning at shallow depth
На четырнадцатом шаге снова выполняются отсечения на предельных глубинах (низких depth). Но на этот раз для их выполнения требуется знать ход в позиции. Генерация хода производилась на предыдущем шаге.
1049 // Step 14. Pruning at shallow depths. 1051 if (!rootNode && pos.non_pawn_material(us) && !is_loss(bestValue)) 1052 { 1053 // Skip quiet moves if movecount exceeds our FutilityMoveCount threshold 1054 if (moveCount >= (3 + depth * depth) / (2 - improving)) 1055 mp.skip_quiet_moves(); 1057 // Reduced depth of the next LMR search 1058 int lmrDepth = newDepth - r / 1024; 1060 if (capture || givesCheck) 1061 { ... ... 1081 } 1082 else 1083 { 1084 int history = (*contHist[0])[movedPiece][move.to_sq()] 1085 + (*contHist[1])[movedPiece][move.to_sq()] 1086 + sharedHistory.pawn_entry(pos)[movedPiece][move.to_sq()]; 1088 // Continuation history based pruning 1089 if (history < -4083 * depth) 1090 continue; 1092 history += 69 * mainHistory[us][move.raw()] / 32; 1095 lmrDepth += history / 3208; 1097 Value futilityValue = ss->staticEval + 42 + 161 * !bestMove + 127 * lmrDepth 1098 + 85 * (ss->staticEval > alpha); 1100 // Futility pruning: parent node 1103 if (!ss->inCheck && lmrDepth < 13 && futilityValue <= alpha) 1104 { 1105 if (bestValue <= futilityValue && !is_decisive(bestValue) 1106 && !is_win(futilityValue)) 1107 bestValue = futilityValue; 1108 continue; 1109 } 1111 lmrDepth = std::max(lmrDepth, 0); 1113 // Prune moves with negative SEE 1114 if (!pos.see_ge(move, -25 * lmrDepth * lmrDepth)) 1115 continue; 1116 } 1117 }
Вблизи предельной/заданной глубины не обязательно отсекать только по оценке, как это делали Razoring и Futility Pruning ранее. Можно сформулировать правила отсечения и на основании иных принципов. Поэтому помимо Futility pruning здесь производятся отсечения поздних ходов по сортировке, ходов с плохой историей, отсечения по SEE.
Отсечения производятся раздельно для взятий и тихих ходов.
Step 15. Extensions
На пятнадцатом шаге мы обратимся к методам продления вариантов.
1119 // Step 15. Extensions 1120 // Singular extension search 1129 if (!rootNode && move == ttData.move && !excludedMove && depth >= 6 + ss->ttPv 1130 && is_valid(ttData.value) && !is_decisive(ttData.value) && (ttData.bound & BOUND_LOWER) 1131 && ttData.depth >= depth - 3 && !is_shuffling(move, ss, pos)) 1132 { 1133 Value singularBeta = ttData.value - (53 + 75 * (ss->ttPv && !PvNode)) * depth / 60; 1134 Depth singularDepth = newDepth / 2; 1136 ss->excludedMove = move; 1137 value = search<NonPV>(pos, ss, singularBeta - 1, singularBeta, singularDepth, cutNode); 1138 ss->excludedMove = Move::none(); 1140 if (value < singularBeta) 1141 { 1142 int corrValAdj = std::abs(correctionValue) / 230673; 1143 int doubleMargin = -4 + 199 * PvNode - 201 * !ttCapture - corrValAdj 1144 - 897 * ttMoveHistory / 127649 - (ss->ply > rootDepth) * 42; 1145 int tripleMargin = 73 + 302 * PvNode - 248 * !ttCapture + 90 * ss->ttPv - corrValAdj 1146 - (ss->ply * 2 > rootDepth * 3) * 50; 1148 extension = 1149 1 + (value < singularBeta - doubleMargin) + (value < singularBeta - tripleMargin); 1151 depth++; 1152 } 1154 // Multi-cut pruning 1160 else if (value >= beta && !is_decisive(value)) 1161 { 1162 ttMoveHistory << std::max(-400 - 100 * depth, -4000); 1163 return value; 1164 } 1166 // Negative extensions 1173 // If the ttMove is assumed to fail high over current beta 1174 else if (ttData.value >= beta) 1175 extension = -3; 1177 // If we are on a cutNode but the ttMove is not assumed to fail high over current beta 1179 else if (cutNode) 1180 extension = -2; 1181 }
При изложении различных методов отсечений и сокращений (reductions) в предыдущих частях не раз упоминались и продления (extensions). Но за исключением QS, который традиционно не принято к ним относить, ни одного примера продлений так и не было приведено. Тем не менее, хотя в программах продления и не играют решающей роли, они очень важны. Всегда полезно продлить определенную ветку, досчитаться до конкретных последствий некоторых ходов и тем самым уточнить ее оценку.
По тексту программы можно заметить, что небольшие продления вариантов периодически происходят то здесь, то там. Но единственным "глобальным" методом продлений, выделенным отдельным пунктом, являются Singular Extensions - продления единственных ходов.
Те, кому приходилось играть против обычных шахматных программ, знают что они могут быть чрезвычайно изворотливы, особенно если попадают в сложную ситуацию. Раз за разом они отыскивают неочевидные ходы, которые только на время отодвигают материальные потери. Иногда даже чрезмерно отодвигают (так называемый "эффект горизонта"). Но против человека такой подход иногда срабатывает.
Если программа считает на фиксированную глубину, то она может неадекватно высоко оценивать такие варианты, тогда как это всего лишь отсрочка неизбежного. Поэтому логично их немного продлить, чтобы получить истинную оценку. Идея Singular Extensions заключается в продлении одного из ходов, если его оценка намного выше, чем у других из данной позиции. Тем более, что если такой ход единственный, то продлить его будет не слишком затратно.
Чтобы не производить лишнего перебора посмотрим в хеш-таблице, не отсекался ли по бете (BOUND_LOWER) данный ход из данной позиции ранее, с приличной глубиной. Если так, то его оценка должна быть высока. Исключаем его из рассмотрения (excludedMove) и проводим перебор с сокращенной глубиной и с понижением альфа-бета границ на определенную величину. Если отсечения не произошло, то наш исключенный ход был единственным с высокой оценкой и его можно продлить.
Напротив, если отсечение на предварительном переборе все же случилось, то значит мы имеем уже минимум два хода с высокой оценкой. В таком случае никаких продлений выполнять нельзя.
Здесь вступает в действие метод MultiCut, который наоборот, производит отсечение узла. Его основной принцип заключается в том, что мы по сути уже дважды отсекли этот узел на сокращенной глубине, сначала исключенным ходом из хеш-таблиц, затем вторым ходом на предварительном переборе. Если позиция отсекалась уже несколькими ходами на сокращенной глубине, то почти наверняка хотя бы один из таких ходов отсечет ее и на полной (заданной) глубине. Производим отсечение.
В этом отношении MultiCut очень похож на ProbCut и нулевой ход. Точно так же он отсекает по бете с перебором на сокращенную глубину, но с некоторым условием. Это условие у каждого метода разное - пропуск хода у Null Move, большой запас в превышении беты у ProbCut, и многократные отсечения у MultiCut.
Так как методы похожи, то и отсекают они примерно одни и те же узлы. Нулевой ход наиболее эффективен в шахматах, поэтому он выполняется раньше. Два других метода вынуждены отсекать уже на "очищенном" дереве и соответственно дают не слишком большую прибавку к силе игры, а потому имеют вспомогательный характер.
Если же и MultiCut не сработает, то продолжим далее. Теперь мы можем если не отсечь, то хотя бы сократить глубину перебора.
Таким образом, на самом деле 15-й шаг представляет собой очень гибкую систему, как продлений, так и сокращений. Действительно, если в позиции единственный ход с высокой оценкой, то его надо продлить. Но если таких ходов два или больше, то напротив, весь вариант надо отсекать, а если отсечение не проходит, то можно хотя бы подсократить перебор по ветке хода.
Step 16. Make the move
Здесь собственно делается ход. Позиция на "внутренней доске" программы меняется. Производится углубление по дереву вариантов. Попутно обновляется счетчик позиций.
1183 // Step 16. Make the move 1184 do_move(pos, move, st, givesCheck, ss);
Между 16 и 17 шагом, в зависимости от некоторых условий вводятся различные поправки (r) к глубине на основании типа и статистики узлов. Это дополнительные величины сокращений и продлений для хода из нашей позиции. Они потребуются в основном на следующем шаге, для LMR.
1037 // Calculate new depth for this move 1038 newDepth = depth - 1; 1040 int delta = beta - alpha; 1042 Depth r = reduction(improving, depth, moveCount, delta); ... ... 1186 // Add extension to new depth 1187 newDepth += extension; ... ... 1199 // Increase reduction for cut nodes 1200 if (cutNode) 1201 r += 3372 + 997 * !ttData.move; 1203 // Increase reduction if ttMove is a capture 1204 if (ttCapture) 1205 r += 1119; ... ... 1226 // Scale up reductions for expected ALL nodes 1227 if (allNode) 1228 r += r / (depth + 1);
Step 17. Late moves reduction (LMR)
Метод LMR описан во II и III частях. Согласно нему, на ходах после первого по сортировке (moveCount > 1) производится перебор на сокращенную глубину. При этом используется минимальное окно по методу PVS. Если альфа превышена, то для проверки корректности оценки перебор повторяется, уже на полную глубину.
Сокращения (r, reduction) для LMR вычисляются выше, отдельной функцией в строке 1042. В Стокфише при вычислении сокращений учитываются уже четыре параметра, а не один лишь номер хода (moveCount), как практиковалось в старых программах.
1230 // Step 17. Late moves reduction / extension (LMR) 1231 if (depth >= 2 && moveCount > 1) 1232 { 1238 Depth d = std::max(1, std::min(newDepth - r / 1024, newDepth + 2)) + PvNode; 1240 ss->reduction = newDepth - d; 1241 value = -search<NonPV>(pos, ss + 1, -(alpha + 1), -alpha, d, true); 1242 ss->reduction = 0; 1244 // Do a full-depth search when reduced LMR search fails high 1246 if (value > alpha) 1247 { 1248 // Adjust full-depth search based on LMR results - if the result was 1249 // good enough search deeper, if it was bad enough search shallower. 1250 const bool doDeeperSearch = d < newDepth && value > bestValue + 50; 1251 const bool doShallowerSearch = value < bestValue + 9; 1253 newDepth += doDeeperSearch - doShallowerSearch; 1255 if (newDepth > d) 1256 value = -search<NonPV>(pos, ss + 1, -(alpha + 1), -alpha, newDepth, !cutNode); 1258 // Post LMR continuation history updates 1259 update_continuation_histories(ss, movedPiece, move.to_sq(), 1365); 1260 } 1261 }
Step 18. Full-depth search
Когда все предыдущие способы прекратить или сократить перебор исчерпаны, то выполняется основной перебор на заданную глубину. Если ход первый по сортировке (moveCount = 1) и является PV-node, он выполняется с полным альфа-бета окном. Для ходов после первого по сортировке выполняется перебор с минимальным окном. Аналогично предыдущему шагу, при превышении минимального окна, перебор может быть проведен повторно, с полным окном (см. PVS). При запуске задается тип узла <PV> или <NonPV> , Cut или All.
1263 // Step 18. Full-depth search when LMR is skipped 1264 else if (!PvNode || moveCount > 1) 1265 { ... ... 1270 // Note that if expected reduction is high, we reduce search depth here 1271 value = -search<NonPV>(pos, ss + 1, -(alpha + 1), -alpha, 1272 newDepth - (r > 3957) - (r > 5654 && newDepth > 2), !cutNode); 1273 } 1275 // For PV nodes only, do a full PV search on the first move or after a fail high, 1276 // otherwise let the parent node fail low with value <= alpha and try another move. 1277 if (PvNode && (moveCount == 1 || value > alpha)) 1278 { 1279 (ss + 1)->pv = pv; 1280 (ss + 1)->pv[0] = Move::none(); 1282 // Extend move from transposition table if we are about to dive into qsearch. 1283 // decisive score handling improves mate finding and retrograde analysis. 1284 if (move == ttData.move 1285 && ((is_valid(ttData.value) && is_decisive(ttData.value) && ttData.depth > 0) 1286 || ttData.depth > 1)) 1287 newDepth = std::max(newDepth, 1); 1289 value = -search<PV>(pos, ss + 1, -beta, -alpha, newDepth, false); 1290 }
Step 19. Undo move
После того как ветка на предыдущем шаге исследована на заданную глубину, возвращаем ход назад. Поднимаемся выше по дереву вариантов.
1292 // Step 19. Undo move 1293 undo_move(pos, move);
Step 20. Check for a new best move
Здесь подводятся итоги основного перебора выполненного ранее, конечно если уже не произошло отсечения на одном из предыдущих шагов. Полученная оценка позиции последовательно сравнивается с оценкой текущего лучшего хода из позиции bestValue, альфой и бетой, по нарастающей.
Если оценка текущего рассматриваемого хода из позиции выше лучшей оценки, то значение лучшей оценки для позиции обновляется. Если выше альфы, то повышается альфа (кроме случая, когда превышена бета). Если выше беты, то происходит отсечение и выход из цикла - оставшиеся возможные ходы из позиции не рассматриваются.
1297 // Step 20. Check for a new best move 1298 // Finished searching the move. If a stop occurred, the return value of 1299 // the search cannot be trusted, and we return immediately without updating 1300 // best move, principal variation nor transposition table. 1301 if (threads.stop.load(std::memory_order_relaxed)) 1302 return VALUE_ZERO; 1304 if (rootNode) 1305 { ... ... 1353 } 1355 // In case we have an alternative move equal in eval to the current bestmove, 1356 // promote it to bestmove by pretending it just exceeds alpha (but not beta). 1357 int inc = (value == bestValue && ss->ply + 2 >= rootDepth && (int(nodes) & 14) == 0 1358 && !is_win(std::abs(value) + 1)); 1360 if (value + inc > bestValue) 1361 { 1362 bestValue = value; 1364 if (value + inc > alpha) 1365 { 1366 bestMove = move; 1368 if (PvNode && !rootNode) // Update pv even in fail-high case 1369 update_pv(ss->pv, move, (ss + 1)->pv); 1371 if (value >= beta) 1372 { 1374 ss->cutoffCnt += (extension < 2) || PvNode; 1375 assert(value >= beta); // Fail high 1376 break; 1377 } 1379 // Reduce other moves if we have found at least one score improvement 1380 if (depth > 2 && depth < 14 && !is_decisive(value)) 1381 depth -= 2; ... ... 1384 alpha = value; // Update alpha! Always alpha < beta 1385 } 1386 }
После 20 шага цикл генерации и просмотра ходов из позиции, который начинался с 13 шага, заканчивается. Далее следует подведение итогов.
После 21 шага в основном обновляются хеш-таблицы и различная статистика по результатам прошедшего перебора. На этом основной перебор в данной позиции заканчивается. Функция search возвращает в дерево перебора оценку bestValue рассматриваемой позиции, предполагая некий лучший ход из нее, с перебором выполненным на заданную глубину.
Окончание следует…