Теория выборочного поиска в шахматной программе.
Автор: Корнилов Е. 2024г.
Хороша тема, да нету теории или, теории мало. Эта глава в продолжении известной статьи 2004г на эту тему. Там изложение было несколько сумбурное и хотелось бы распрямить и довнести так сказать.
Итак, в любом узле поиска у нас есть в моменте 2 статические оценки, оценка до хода - L_SCORE, и оценка после каждого хода - R_SCORE. Этот тривиальный момент требует однако несколько дополнительных пассов как у фокусника, который отвлекает внимание малозначительными деталями, перед тем как незаметно сделать главное движение. Итак, 2 оценки. Причем для нормальных, невырожденных перемещений R_SCORE > L_SCORE из чего делается вывод, что так как R_SCORE - максимум, то L_SCORE учитывать не нужно.
int alpha_beta(int alpha,int beta, int depth){
if(depth<=0) return Quies(-beta,-alpha);
Generate_and_sort_moves();
L_SCORE = Evaluate_Position(side);
while(NextMove() && alpha<beta){
MakeMove();
R_SCORE = Evaluate_Position(side);
side^=1;
if(!Check() && L_SCORE<=alpha && R_SCORE<=alpha)
{
//skip search
}else
alpha = max(alpha,-alpha_beta(-beta,-alpha,depth-1);
side^=1;
UnMakeMove();
}
return alpha;
}
L_SCORE у нас всегда статическая, а R_SCORE может быть и динамической - вычисляться эвристикой NullMove, когда делаются 2 хода подряд и это засчитывается за максимум оценки. Если максимум не лучше alpha - подрезаем.
Игра на beta пределе.
Не хочу путать читателя, но подобная вещь существует, и необходимо ее упомянуть.
Имеется 2 функции поиска - основной и выборочный или поверхностный. Если оценка выборочного поиска для текущего хода хуже beta, вызывается основной поиск. Для оппонента всегда есть лучший ход, дерево поиска отслеживается корректно, без разрывов, а уточнение дерева игры - лучший способ считать не все и глубоко. Программа будет пытаться выкинуть неперспективные ходы меньше alpha в промежуток между alpha beta и уточнить потенциальное главное изменение. В выборочном поиске может использоваться лмр эвристика, недействительное перемещение, и прочие подрезки. В основном поиске желательно ничего не подрезать. Хотя возможны и другие хитроумные реализации. В целом это прочная схема.
int alpha_beta(int alpha,int beta, int depth){
if(depth<=0) return Quies(-beta,-alpha);
Generate_and_sort_moves();
L_SCORE = Evaluate_Position(side);
while(NextMove() && alpha<beta){
MakeMove();
R_SCORE = Evaluate_Position(side);
side^=1;
if(!InCheck() && L_SCORE>=beta && R_SCORE>=beta &&
-selective_alpha_beta(-beta,-alpha,depth-1) >= beta
// -alpha_beta(-beta,-alpha,depth-2) >= beta
)
{
alpha = beta; //!!??
}else
alpha = max(alpha,-alpha_beta(-beta,-alpha,depth-1);
side^=1;
UnMakeMove();
}
return alpha;
}
Эта фундаментальная вещь, если функцию выборочного поиска правильно подобрать будет стараться выискивать хорошие варианты там где их казалось бы нет. Здесь только основная идея.
Моментум.
Моментум - это скорость изменения оценки или первая производная без учета константы. В некоторой строке игры приращение оценки для белых может выглядеть подобно этому:
+2 -2 +5 -5 +300 -100 +8 -6 +100 -100
А оценка соответственно:
2 0 5 0 300 200 208 202 302 202
Для текущего ply пятый моментум будет (202-200) = 2. То есть берется оценка для текущего ply и для ply-5.
momentum = static_score[side][ply] - static_score[side][max(0,ply-5)];
Почему пятый моментум? Мне так нравится и потом это неплохо для средней глубины поиска. Теперь внимание:
1. Моментум > 0 - ход хороший
2. Ход взятие и моментум больше пол-пешки - хорошее взятие
3. Ход взятие и моментум по модулю меньше пол-пешки - размен
и т. д.
Алгоритм SEE в поиске взятий можно реализовать если на глубине больше 2 рассматривать только размены и хорошие взятия (может исключения когда позиция в шахе)
//поиск только приращений материала
//+ алгоритм SEE
int quies_see(int alpha,int beta, int depth){
Generate_and_sort_captures();
int s;
//здесь стандартно завышаем alpha
//статической оценкой - ожидается что
//реальная оценка будет не хуже
alpha = max(alpha,Evaluate_Position(side));
while(alpha<beta && NextMove()){
MakeMove();
ply++;
// Material(int side){return Mtl(side)-Mtl(side^1);}
s = Material(side);//только ценность фигур
static_score[side][ply] = s;
static_score[side^1][ply] = -s;
int momentum = static_score[side][ply] - static_score[side][max(0,ply-5)];
if(depth>2 && momentum < value_p/2)
{
//skip search
}else{
side^=1;
alpha = max(alpha,-quies_see(-beta,-alpha,depth+1);
side^=1;
}
ply--;
UnMakeMove();
}
return alpha;
}
/////////
//где то в функции поиска
int alpha_beta(int alpha,int beta,int depth){
if(depth<=0)
return quies_see(alpha,beta,0);
...
while(NextMove() && alpha<beta){
MakeMove();
ply++;
int s = Material(side);
static_score[side][ply] = s;
static_score[side^1][ply] = -s;
...
}
return alpha;
}
Экспоненциальное среднее.
Обычное среднее это сумма за период, деленная на размер периода. Коррелирует с определенным интегралом. Экспоненциальное среднее может считаться пошагово и эквивалентно простому среднему с периодом в 2 раза большим. Экспоненциальное среднее c периодом 5 (10) при ходе считается очень просто.
double ema5[2][max_ply] ;
ema5[side][ply] = 0.2*R_SCORE + 0.4*ema5[side][ply-1] ;
ema10[side][ply] = 0.1*R_SCORE(текущая оценка) + 0.9*ema5[side][ply-1] ;
Если после хода (ema5[side][ply] > ema10[side][ply]) то для данной стороны нет сокращений поиска, так как ожидается что ее оценка растет.
Это условие может использоваться как дополнительное при подрезке ветви поиска после итерации на меньшую глубину. Первые 1-3 легальных хода и шахи с ходом пешки на предпоследнюю горизонталь, а также взятие слабых пешек (нет пешки рядом и не защищена пешкой) можно не подрезать.
int alpha_beta(int alpha,int beta, int depth){
if(depth<=0) return Quies(-beta,-alpha);
Generate_and_sort_moves();
L_SCORE = Evaluate_Position(side);
while(NextMove() && alpha<beta){
MakeMove();
R_SCORE = Evaluate_Position(side);
side^=1;
if(!Check() && L_SCORE<=alpha && R_SCORE<=alpha &&
(ema5[side^1][ply] <= ema10[side^1][ply]) &&
-alpha_beta(-beta,-alpha,depth-2) <= alpha
)
{
//skip search
}else
alpha = max(alpha,-alpha_beta(-beta,-alpha,depth-1);
side^=1;
UnMakeMove();
}
return alpha;
}
Программа будет просчитывать далее восходящие последовательности. Можно ограничить приращение, например - если меньшее среднее больше большего и разница между текущей оценкой и большим средним меньше или равна 2 пешки, то ход не подрезается сокращенным поиском.
if(ema5 >ema10 && abs(ema_3 -ema10) < 2*value_pawn)
ema3, ema5, ema10 - это пошагово вычисляемые экспоненциальные средние.
2*value_pawn - это окно от средней, 2% приращения материала от максимального материала. Максимальный материал взят примерно 40 пешек.
В примере выше оценка считалась падающей если меньшая ema пересекла более тяжелую и находится снизу. Этот момент можно уточнить. Добавочное уточнение будет следующим: если эти 2 линии расходятся. То есть , чтобы отследить сей тонкий момент нам подребуется 3 массива, вычисляемых пошагово:
ema5[], ema10[], ema5_minus_ema10[];
if(!Check() && L_SCORE<=alpha && R_SCORE<=alpha &&
//-------- начало блока проверки ------------
(ema5[side^1][ply] <= ema10[side^1][ply]) &&
(abs(ema5_minus_ema10[side^1][ply]) >
abs(ema5_minus_ema10[side^1][ply-1])) &&
//-------- статичемкая оценка падает в среднем
-alpha_beta(-beta,-alpha,depth-2) <= alpha ---
)
{
//skip search
}
Нужно помнить, что это эвристика, то есть алгоритм, который срабатывает не всегда. Но по счастью для шахматной программы нужна просто хорошая вероятность попадания, достаточно 30%. Больше, конечно лучше.
Можно считать стандартную девиацию от среднего, для определения канала вероятной оценки. Это будет экспоненциальное среднее от модуля разницы между текущей статической оценкой после хода и средней оценкой. Уф. Ничего сложного. Если ход - взятие то данное окно от среднего может служить для диагностики разменов. Помните что ema с периодом 10 это обычное среднее с периодом 20. От 20 обычно считается нормальное распределение в статистике и за это даже дали нобелевскую. Дескать чего считать, когда окно от среднего известно - это 2*stdev с вероятностью 66%. Только период неизвестен :))
stdev=ema(abs(R_SCORE-ema10) , 10)
А вот еще простой способ отсечь вероятно бесполезные перемещения. Если оценка после хода больше средней или среднее больше alpha, то перемещение вероятно перспективное. Это, конечно, очень примитивно, но для движка и нужен то небольшой толчок, чтоб он начал считать более разумно.
int alpha_beta(int depth, ...){
int MARGIN = depth<=2? value_pawn/2 :
depth<=4? value_pawn*2 :
depth<=6? value_rook :
value_queen;
...
//нашли очередной ход
if( max(L_SCORE,R_SCORE) <= alpha &&
max(L_SCORE,R_SCORE) <= ema10 &&
ema10+MARGIN<=alpha // ema10 - среднее за 10 перемещений
legal_move_cnt > 1 &&
!Next_Check() &&
!Pawn_Move_In_7_Rank &&
!Capture_Bad_Pawn && //не защищена пешкой и рядом нет пешки
beta < Mate_Value &&
-alpha_beta(depth-2,...) <= alpha)//сокращенный поиск
{
alpha=alpha;
}else
alpha=max(alpha,-search(depth-1,...));
return alpha;
}
Игра на мат.
Какой перворазрядник не любит матовать? Вот пожалуйста, вводим еще одну таблицу истории хороших ходов для найденных матов, траектории Ботвинника, так сказать. Если обнаружен мат или оценка выше матовой грани, то для сортировки перемещения, ведущего к потенциальному мату вводится премия с элементом случайности а также сохраняется средняя история за игру для матовых атак.
int mate_history[2][64][64],history[2][64][64];
//нашл ход улучшающий alpha
if( (history[side][FROM(mv)][TO(mv)] += 1 + rand()%1) > MAX_HIST)
Div_Hist_2(history);
//нашли матовый ход ( оценка более границы мата)
if( (mate_history[side][FROM(mv)][TO(mv)] += 20 + rand()%7) > MAX_HIST)
Div_Hist_2(mate_history);
//Где то в сортировке тихих перемещений:
value_move = history[side][FROM(mv)][TO(mv)] + mate_history[side][FROM(mv)][TO(mv)];
//В функции, вызывающей основной поиск:
int root_search(){
//перед поиском
for(c=WHITE;c<=BLACK;c++)
for(from=0;from<64;from++)
for(to=0;to<64;to++)
{
history[c][from][to]=0;
mate_history[c][from][to] /= 2; // EMA emulation
}
...
}
Жучит короля как только шахматы в руки взяла:))
Самообучение.
Я затрону самый простой вариант. Допустим, в строке игры, не в поиске, обнаружен проигрыш. Мат или среднее растет и больше 2 пешек. Тогда мы должны для всех перемещений, ведущих в данную позицию, без повторений для данной игры, для проигравшей сторона запомнить штраф как часть от статической оценки для фигуры в данной клетке, а для выигравшей - премию.
if(piece==pawn) m=64*3;
else if(piece==queen) m=64*10;
else if(piece==king) m==64*100;
else m==64;
bonus [piece] [to_square(side, sq) ] += (double) (score[piece] [to_square(side, sq) ] + rand(10) )/m;
Величину бонуса можно ограничить +-20% от исходного значения.
int to_square (int side, int sq) {return side==white? 63-sq:sq; }
Исходная таблица для коня может быть похожа на эту:
{1,2,3,4,4,3,2,1,
2,10,10,10,10,10,2,
3,10,20,20,20,20,10,2,
4,10,20,30,30,20,10,2,
... }
и т. д. до 64-х клеток.
Таким образом, таблица корректировочных значений в каждой клетке будет ограничена 20% изменения от значения в клетке исходной таблицы, что не должно быть катастрофичным в случае неправильного самообучения. Ферзя и пешки и короля весьма проблематично обучать таким образом и поэтому приоритеты снижены.
Конечно, это скорее толчок к размышлению, чем готовое решение. Разумеется неплохо иметь дебютный справочник и запоминать приоритеты удачных вариантов, а также позиции с оценками, а также базы данных эндшпилей. Можно сделать подстройку некоторых коэффицентов в оценочной функции вроде ладьи на 7 горизонтали когда там есть пешки. Сложно сказать, премия должна быть 0.7 пешки или 0.1?
Можно регулировать бонус за атаку на слабую пешку. Он должен быть 0.01 пешки или 0.03? Сложно сказать.
Конечно, я не против нейросетевых сверточных технологий. Это может быть удачным решением, но, видимо не для шахмат:))
Успехов.
Отсечка на основе канала средней оценки.
Что есть канал средней оценки. Есть мнение, что вокруг средней существует некоторая область, попав извне в которую, оценка притянется к средней. На этом принципе построен биржевой индикатор CCI. То есть нам нужна средняя, средняя девиация от среднего и некоторый множитель, показывающий максимальные выхлопы от среднего. Сигнал у нас правда не синусоидальный и период точно неизвестен, но, тем не менее. Приведя аналогию с биржевой игрой, не могу не привести аналогию с электротехникой. Там вычисляются 2 величины -
1. Действующее значение
2. Среднее.
В среднем они равны 0.7 и 0.6 а посередине будет 0.65. Вывод достаточно интересен и делается через сопоставление с нагревом постоянным током и переменным током. Я здесь не буду вдаваться в сложности и пугать читателся, но простой аналог вывода следующий: Мы сопоставляем некоторый средний круг (площадь) и сторону квадрата. Что то вроде этого.
L^2 = (Pi*R^2) / 2*Pi*R, площадь квадрата равна площади круга делить на длину круга
Произведя манипуляции на уровне 5 го класса, мы получим.
L = R/ sqrt(2), L - действующее значение синусоидальной величины, R-максимальное.
Просто, не правда ли?
Идея отсечки следующая: если(средняя + девиация от среднего*sqrt(2)) <= alpha, то данный узел кандидат на подрезку. Это всяко лучше чем просто основываться на статическую оценку и поиск сокращенной глубины. Конечно, догадливый читатель понял, что я намекаю на игру на beta пределе: если оценка выборочного поиска после хода >= beta и (средняя - девиация от среднего*sqrt(2)) >= beta, то вернем beta и положим конец жадным алгоритмам.
Далее я привожу просто листок с пояснениями, так как денег мне за сие не платят, а на бумажке даже понятнее:))
Кто не проникся красотой идеи и требует доказательств, привожу текст программы индикаора CCI для платформы tradingview а также скриншот графика актива и реакции индикатора. Биржевые графики создавались видимо по мотивам шахматных партий, оценка туда, оценка сюда :)) Синий канал на графике индикатора это наш канал от средней, красный канал - 2*stdev от средней.(здесь была нобелевская, ах) Средняя это как линия 0.
Когда то предполагалось что пара евродоллар полностью расколота этим индикаторам вместе с аналитическими отделами, рулящими ценой. Если бы Гейтц с Баффетом, когда грузились фьючерсами на евро, знали про этот индикатор, они бы победили подлых маркетмейкеров (шучу)
Далее я привожу еще один график золота уже на таймфрейме 1 час. Видна та же закономерность. Актив стремится в канал. Наиболее интересны точки, когда цена была вне канала и возвращается в канал. Таких точек немного и можно в них расширить глубину поиска если конечно глубина более 2 и канал имеет шанс попасть в диапазон от alpha до beta, то есть в главное изменение. Таких перемещений не должно быть много, особенно взятий.
Проверка восходящих последовательностей и тренда.
Я тут уже начинаю повторятся, потому что из того что изложено, догадливый читатель может вывести и проверку восходящих последовательностей и много что еще. Самую простую проверку может осуществить Моментум.
#define Momentum5 (static_score[side][ply] - static_score[side][max(0,ply-5)])
int search(...){
...
if(Momentum5 < 0 &&
-search(depth-2,...) <= alpha)
{
//skip
}else
alpha=max(alpha,-search(depth-1,...);
...
return alpha;
}
Круто, правда? Это настоящий кандовый Си.
Если же Моментум слишком просто и скучно, можно сделать нечто гораздо ядренее и глубокомысленнее. Если период Ema совпадает с периодом простой средней, то можно написать нечто следующее:
A = ((ema8-ema32) + (ema16-ema32)) / 2;
B = Ema(A,3);
Score_Is_Up = A>B;
Score_Is_Down = B>A;
Линия Ema32 будет как линия 0, а остальные ema будут описывать колебания вокруг нее. Потом мы берем усредненную от всех ema и среднюю от этого. В принципе, это похоже на разложение сигнала в гармонический ряд, только частоты и коэффициенты неизвестны и я просто усредняю. Для практики достаточно.
int search(...){
...
if(Score_Is_Down &&
-search(depth-2,...) <= alpha)
{
//skip
}else
alpha=max(alpha,-search(depth-1,...);
...
return alpha;
}
или
int search(...){
...
if(Score_Is_Up &&
-search(depth-2,...) >= beta)
{
//skip
}else
alpha=max(alpha,-search(depth-1,...);
...
return alpha;
}
Только не нужно в одной функции применять игру сразу и на alpha и на beta пределе, иначе поиск выродится.
Желтая линия на графике – это суммарный показатель текущего тренда. Если линия выше синей, то тренд вверх, ниже – вниз. Глобальный тренд - если линия больше 0, то растет, иначе падает. Так как средняя партия всего 40 ходов, то выше-ниже ema32 можно использовать даже для самообучения, например, если выше на более чем на 20% от суммарной материальной оценки, то глобальный выигрыш и наоборот соответственно.
/*Chess master for commercial users only :))*/
int search(...){
...
if(
-search(depth-2,...) >= beta && !Position_InCheck &&
A > 0 && Score_Is_Up && Legal_Move_Cnt > 1 && Momentum5 > 0 &&
R_SCORE >= beta && L_SCORE>= beta
)
{
//skip
}else
alpha=max(alpha,-search(depth-1,...);
...
return alpha;
}
Еще о окне вероятной оценки.
Мы уже рассматривали динамическое среднее окно вокруг средней, которое называется stdev (стандартное отклонение) и упомянали что 66% возможных оценок содержится в +- 2*stdev, а 95% возможных оценок в +- 3*stdev. Также мы рассмотрели макимальное значение синусоидальной велечины - это среднее +- stdev*sqrt(2).
Все вроде бы верно, только опыт показывает, что окно, эквивалентное 2*stdev заранее известно и считать его не обязательно.
1. локальное среднее +- 2% от велечины всего актива
2. глобальное среднее +- 20%
В шахматах величина актива это 40 пешек примерно и окно плюс погрешность будет легкая фигура и велечина ферзя соответственно. Так же можно в каждом узле считеть только материал и по нему среднее и девиацию от среднего.
int search(...){
const int MARGIN1 = value_knight;
const int MARGIN2 = value_queen;
...
//////// Do Null Move - пропуск хода при высокой оценке
...
if(game_cnt < 30 && //не конец игры
!PositionInCheck()&&
ply > 2 &&
Material - value_pawn > beta &&
MomentumMtl5 - value_pawn/2 > 0)
{
donull();
null_score = -search(depth-3,...);
undonull();
if(null_score >= beta) return beta;
}
...
//цикл по всем перемещениям для данной позиции
while(alpha<beta && NextMove()){
//для каждого найденного хода
//////////////
...
if(EmaMtl10 - MARGIN1 > beta && //окно от среднего более beta
legal_move_cnt > 1 && //не первое легальное перемещение
ply > 2 &&
MomentumMtl - value_pawn/2 > 0 && //растет
!PositionInCheck() &&
!Opponent_Pawn_Has_On_7_Rank() && //пешки противника в ферзи идут
-search(depth-2,...) >= beta) //сокращенный поиск
{
//skip
alpha=beta;
}else if(EmaMtl24 + MARGIN2 < alpha && //окно от среднего
legal_move_cnt > 1 && //не первое легальное перемещение
ply > 2 &&
MomentumMtl + value_pawn/2 < 0 && //падает материал
!NextCheck() &&
!My_Pawn_Has_On_7_Rank() && //пешки в ферзи идут
-search(depth-2,...) <= alpha) //сокращенный поиск
{
//skip
alpha=alpha;
}else
alpha=max(alpha,-search(depth-1,-beta,-alpha,...);
///////////////////////////
}
...
return alpha;
}
///////////
Конечно, можно делать гибкое поле роста от коня до ферзя и назвать это - уровень интеллекта, можно попробовать.
Минимум и максимум за период как окно возможной оценки.
У нас в узле есть L_SCORE и R_SCORE для текущего узла. Можно расшарить тему и смотреть максимум материала за последние 5 полуходов и минимум соответственно. Конечно, можно в каждом узле делать полный EvaluatePosition() и смотреть реальные минимум и макимум.
Если представить себе некоторую точку в которой находится функция поиска, то тот путь слева, которым мы пришли сюда, можно условно назвать левой историей или историей того, что было. Например: e2e4 e7e5 g1f3 g8f6 <точка поиска> <поиск лучшего варианта>. Функция alphabeta вернет лучший по ее мнению вариант из условного будущего, но поиск мы можем скорректировать опираясь на условное прошлое или в нашем случае, на вершины максимума и минимуму за последние 5 полуходов. В нашем случае, если максимальная вершина из прошлого меньше alpha (минимума поиска), можно сделать предположение, что она не будет завышена и сократить глубину поиска при проверке.
.png)
Код может быть примерно следующий:
...
//нашли ход
if(MaxScore(5) + value_pawn/2 < alpha && MomentumMtl + value_pawn/2 < 0 /*падает*/ &&
-search(depth-2,...)<=alpha)
{
score = alpha;
}else
score = -search(depth-1,...);
//////////////////
или
...
//нашли ход
if(MinScore(5) - value_pawn/2 > beta && MomentumMtl + value_pawn/2 > 0 /*растет*/ &&
-search(depth-2,...)>=beta)
{
score = beta;
}else
score = -search(depth-1,...);
//////////////////
Конечно, поле роста здесь приблизительно и максимальное и минимальное за период лучше находить не по материальной а по полной оценке.
Успехов!
Динамический моментум. Индекс относительной силы.
Средняя оценка или пересечение средних подходит для определения тенденции и канала, но не очень хорошо подходит для определения разменов. Для этих целей лучше моментум(скорость изменения оценки за период) или сглаженный моментум. За подобный индикатор в свое время просили 10000$, со временем ажиотаж поулегся, но вещь еще востребована. Я лично использовал моментум 5, но для желающих улучшить привожу пример реализации. Суть в том, что мы отслеживаем 2 средние и только с положительными изменениями - для белых и черных. В итоге мы получим моментум в диапазоне 0..1, но масштабируем его к диапазону 0..100. Несколько много вычислений для быстрой программы, но возможны оптимизации.
Почему моментум лучше для определения разменов, чем средняя:
300 0 300 0 // строка размена и оценка
(300+0+300+0)/4 = 600/4 = 125 //средняя за период 4 (не 0!)
600*100/(600+600) = 50 //динамический моментум
//динамический моментум или RSI
int score[2][MAX_PLY];
//экспоненциальное среднее только положительных приращений - пошагово
void ema(int v[],int i,int a,int b,int len){
int d = a>b?(a-b)*100:0;
v[i]= i==0 ? d : (d/len + v[i-1]*(len-1)/len;
}
int search(...){
L_SCORE = Evaluate(); //оценка до всех перемещений
...
//нашли ход
R_SCORE = Evaluate(); //оценка после хода
ema(score[side],ply,R_SCORE,L_SCORE,5);
ema(score[side^1],ply,L_SCORE,R_SCORE,5);
rsi = (score[side]*100)/(score[side]+score[side^1]);
recapture = (mv&CAPTURE) && ply>5 && abs(rsi-50)<=5; //[-45..55] //размен
up = ply>5 && rsi > 55; //оценка растет
over = ply>5 && rsi>80; // слишком высоко, вероятно ошибочный вариант
...
}
Пробитие статического канала.
Мы уже рассматривали максимум-минимум за период как возможный канал оценки. Средняя оценка будет (min+max)/2. Это конечно не медиана из статистики, но на практике работает. Оценка имеет тенденцию оставаться в канале и даже, выйдя за его пределы, может возвращаться тестировать границу. Конечно это имеет значение для существенных каналов, для взятий и ключевых ходов. Если происходит пробитие канала большим приростом оценки, то это сигнал на вероятное повышение оценки. Отношение сигнал-шум здесь примерно 0.2 - 0.3, но этого достаточно для отсечки за alpha и даже расширение глубины поиска для взятий, пробивающих канал (если глубина поиска более 2 и менее глубины полного перебора без расширений или дробный depth).
Итак, в каких случаях подрезаем найденный ход за alpha предел:
1. Если канал с периодом 5 до хода меньше alpha, и оценка после хода менее alpha
2. Если последний ход не пробивает канал.
int search(int alpha,int beta,int depth,...){
int MAX = MaxValue(score[side][], 5);//максимум за 5 последних
...
//Нашли ход
ply++;
score[side][game_cnt+ply] = evaluate(side);
score[side^1][game_cnt+ply] = -score[side][game_cnt+ply];
tmp = -search(-beta,-alpha,depth-2,...);
if(tmp <= alpha &&
MAX <= alpha &&
score[side][game_cnt+ply] <= alpha &&
score[side][game_cnt+ply] <= MAX &&
!next_check() //не шах
)
{
}else tmp = -search(-beta,-alpha,depth-1,...);
ply--;
if(tmp>alpha){
alpha = tmp;
...
}
return alpha;
}
////////////
//функция основного поиска - вызывает выборочный поиск
int main_search(int alpha,int beta,int depth){
...
//нашли ход
if((tmp = -search(-beta,-alpha,depth-1,...) < beta)
tmp = -main_search(-beta,-alpha,depth-1,...)
if(tmp>alpha){
alpha = tmp;
...
}
...
return alpha;
}
/////////////////////////
Начинающим шахматным программистам.
Бывает так, что построил только первый движок, он считает неглубоко, но программу выборочного поиска построить хочется. Не надо отчаиваться, несколько штрихов и ваша программа заиграет. Сразу хочу предупредить, что главное - это отловить нелегальные ходы, когда король под шахом и не допускать разрастания дерева поиска в терминальных узлах а также, не нужно использовать результат из хеша в терминальных узлах и там запихивать их в хеш. Здесь неисчерпаемое море ошибок. Также если кто то думает, что 64 битный хеш ключ точно определит позицию на глубине больше 5, он сильно заблуждается. Впрочем, это не сильно затрудняет и можно не обращать внимание на мелочи.
Итак мы определили, что по условной шкале времени, текущая позиция находится в настоящем, строка истории, ведущая в позицию - в прошлом, и дерево поиска вариантов - в будущем. Также мы определили, что вокруг средней оценки на истории до данной позиции могут быть некоторые колебания статической оценки, отдаленно похожие на волну.
Например:
e2e4 e7e5 g1f3 g8f6 f1b5 <текущая позиция> дерево поиска (возможные варианты)
Оценка позиции по ходам:
0 +2 0 +3 0 +5
Средняя:
(0+2+0+3+0+5)/6 = 1.66
Отклонение от средней:
1.66-0, 1.66-2, 1.66-0, 1.66-3, 1.66-0, 1.66-5
Среднее отклонение от среднего:
10.0011 / 6 = 1.66685
Два средних отклонения:
1.66685*2 = 3.337
Верхняя вероятная оценка:
3.337 + 1.66 = 4.99
Нижняя вероятная оценка (средняя минус двойное отклонение)
1.66 - 3.337 = -1.67
Моментум 2:
+5 - 3 = 2
Моментум 5:
+5-0 = 5
Минимум за период:
0
Максимум за период:
5
Возможное условие для отсечки за alpha после хода:
Статическая оценка после хода <= alpha
Ход не делает шах
Дополнительные критерии:
1.Верхняя вероятная оценка < alpha
2.Максимум за период < alpha
3.Моментум за период 5 < 0
Два средних отклонения от средней оценки - это окно в которое попадут 66% всех перемещений.
Период средней - 5, 10 или 20. На выбор.
Здесь я подвел черту напоминанию о статистических методах и обратимся к совсем простым приемам.
В текущей позиции мы из прошлого получаем строку перемещений, среднюю оценку за некоторый период и условную волну статической оценки вокруг среднего. Как приблизится к настоящему моменту? Надо уменьшить период (для электромагнитных волн - уменьшить длину волны до светового диапазона)и наконец, элементарный квант - это один ход и оценка до него и после, как статический диапазон минимума и максимума возможой оценки. Это работает не для всех игр и для крупных перемещений - навряд ли тихий ход +1 определит какой то диапазон. Практика показывает, что статический минимум-максимум за период (напр. 5) тоже неплохо определяет диапазон возможной оценки. Можно даже построить стратегию на перемещениях "пробивающих" диапазон. Но вернемся к теме.
Основной статический критерий гласит, что в любой позиции, еще не делая ни одного перемещения можно предположить, что найденная оценка будет не хуже текущей статической. Статическая оценка - это результат функции оценки для неподвижных фигур.
Ниже будет показан пример использования простейшего статического отсечения вмести с проверкой и как результат - beta и alpha отсечения для ускорения поиска.
Также будет использована из "левой" истории экпоненциальная средняя с периодом 10. Некоторым причудливыми образом она апроксимируется в простое среднее с периодом 20. Используется следующая эвристика. В большинстве ситуаций, текущая оценка сделает ретест к средней, что нам, как опытным программистам и надо. Если средняя вышла за пределы alpha beta диапазона и проверка потверждает, то для простой программы, какой нибудь скрипт на java :)) можно пдрезать поиск досрочно.
Некоторым образом среднее похоже на мат. ожидание за период, например:
События(оценки) Вероятность
2 0.2
4 0.2
5 0.2
6 0.2
7 0.2
--------------------------
Мат. ожидание:
2*0.2 + 4*0.2 + 5*0.2 + 6*0.2 + 7*0.2 = 4.8
Среднее:
(2+4+5+6+7)/5 = 4.8
Мы видим, что среднее равно среднему математическому ожиданию за тот же период.
Вернемся к теме. В функции поиска отслеживается статистика Монте-Карло угроз королю и атак на слабые пешки и поддерживается динамическое дерево поиска - первым просматривается лучший ход от предыдущей итерации. Пример служит для пояснения неоднозначных моментов для начинающих. Если отсечку за beta по результатам сокращенного поиска проводить со второй попытки, то мы получим сингулярную эвристику, которая может играть весьма глубокомысленно и рассеяно:))
/*функция поиска - только демонтсрация идей для простой проги*/
int alpha_beta(int alpha, //minimum
int beta, //minimum opponenta
int depth, //glubina
int side, //0..1 - white, black
int in_check, //король в шахе
int in_move, //ход с которого начнется просчет (для скорости)
int &out_move //лучший ход, который функция вернет
){
int old_alpha = alpha, GSR_Point = (rand()&31)+1;//граница хороших:))
static int ema10[2][MAX_GAME+MAX_PLY];
if(depth<=0) //поиск взятий с завышением alpha
//а также превращений пешек в ферзи и возможно
//до некоторой глубина - маты со взятиями :))
//по мотивам Битмапа, Арлазорова, и А-Вельского
//и их загадочной программы
return Search_Captures(alpha,beta,side,out_move);
int hash_move = Hash_Look(side);//ход из хеша - если есть
//////////////////////////////////////
int L_SCORE = Evaluate(alpha,beta,side); //статическая
//оценка
// можно результат NullMove
//оценку больше beta
if(ply+game_cnt==0){
ema10[side][0] = L_SCORE; //средняя оценка - пошагово
ema10[side^1][0] = -L_SCORE;
}
//////////////////////////////////////
if(Generate_And_Sort_Moves(in_move,hash_move)==CAP_KING)
return INF-ply+1;
/*****
генерирует перемещения и расставляет
значения для сортировки
примерный порядок:
in_move
взятия:
наиболее ценная фигура
наименее ценный защитник
взятия последней ходившей фигуры
killer - лучший ход для соседа
остальные взятия
тихие перемещения:
эвристика истории +
эвристика монте карло
матовой истории
***/
int mv,next_check,legal_move_cnt=0,tmp,next_move=0,
next_depth;
while(Pick_Move(mv)){ //подкачивает наверх один лучший ход
if(Check(side) continue;
else legal_move_cnt++;
next_check = Check(side^1);
next_depth = depth-1+next_check;
MakeMove(mv);
ply++;
int N = game_cnt + //полуходов в игре до начала поиска
ply; //глубина поиска от 0
int R_SCORE = Evaluate(alpha,beta,side);
//средняя оценка - пошаговая корректировка
ema10[side][N] = R_SCORE/10 + ema10[side][N-1]*9/10;
ema10[side^1][N] = -ema10[side][N];
/*
поиск на меньшую глубину
если он вернет оценку вне диапазона и
диапазон статической оценки
вне alpha beta, или другими словами -
есть сигнал и есть подтверждение, то не
ищем на полную глубину
*/
//////////////////////////
//сокращенный поиск - может быть отдельная функция
tmp = -alpha_beta(-beta,-alpha,next_depth-1,
side^1,next_check,
next_move,next_move);
if(tmp>=beta && L_SCORE >= beta && depth>2 &&
ema10[side][N] >= beta && //оценка вернется к средней
legal_move_cnt>1 && !in_check
&& ply>2 && legal_move_cnt <=GSR_Point
){
//cutoff
}else if(tmp<=alpha && R_SCORE <= alpha && depth>2 &&
ema10[side][N] <= alpha && //оценка вернется к средней
legal_move_cnt>1 && !next_check
&& ply>2 && legal_move_cnt>GSR_Point //:))
){
//cutoff
}else if(next_depth <= 0){
//уже сосчитали форсированный поиск материала
}else
tmp = -alpha_beta(-beta,-alpha,next_depth,side^1,next_check
next_move,next_move);
//////////////////////////
UnMakeMove(mv);
ply--;
if(time_out())return alpha;
if(tmp>alpha && !time_out()){
alpha = tmp;
out_move = mv;
Hash_Write(mv,depth);
/*******************
поиск от корня идет итеративно от глубина 2 до исчерпания
лимита времени наращивая глубину на 1
таблица истории перед началом поиска обнуляется,
таблица матовой истории - делится на 2
Значение перемещения для сортировки (тихих ходов)
move_sort_val[indexe] =
(8-piece_code) + //пешки вперед
history[side][FROM(mv)][TO(mv)] +
mate_history[side][FROM(mv)][TO(mv)];
Скорректируем таблицы истории
********************/
history[side][FROM(mv)][TO(mv)] += 1;
if(tmp > INF-100) //mate?
mate_history[side][FROM(mv)][TO(mv)]+=2 + rand()&3;
//если сьели слабую пешку (нет соседней и не защищена
//пешкой) или пешка прошла в ферзи то можно
//отследить линию перемещений назад до корня дерева
//и увеличить таблицу истории примерно на (1 + rand()&1)
...
}
if(alpha>beta) break;
}
if(legal_move_cnt==0){
if(in_check) return -INF+ply; //мат
else return 0; //пат
}
return alpha;
}
////////////////////
Это простая программа надеюсь окажется полезной для экспериментов на javascript и python и подобных вещах.
Эмуляция субьектности в функции поиска.
Здесь как просвещенный читатель заметил, речь идет уже не о том как размазать какого нибудь гросса по клетчатой доске так чтобы при одном упоминании о ИИ он нервно закрывался газетой. Речь пойдет о характере игры или о том, как это не меркантильно, за что платят деньги, если человек вообще способен платить сейчас за шахматную прогу. Но, к делу.
Существует две модели поведения или две парадигмы сущностей - автомат и субьект. Автоматы еще любовно называют роботами. Можно ли эмулировать субьекта на языке программирования? Можно и даже легко и даже мы встречаем это сплошь и рядом, просто не знаем как это нназывается.
1. Автомат.
Работает от событий, должно произойти внешнее событие, чтобы автомат отреагировал некоторым задетерминированным образом. Например система Windows, программный цикл:
while(GetMessage(...) && TraslateMessage(...){
DispatchMessage(...);
}
Смысл следующий. Пока есть сообщения в очереди (мышь, клава и т д), обработать их и перенаправить пользователю. Система уже имеет зародыш субьектности - главный программный цикл, но он не развит и кроме того, делегирует обработку сообщений на деревню дедушке, т. е. это автомат.
Субьект:
Какой нибудь игровой цикл:
while(go==true){
если есть сообщения (флаги выставлены) запомнить
их и может быть обработать позже
Основная логика
Ход машины
Ловим реакцию оппонента, желательно не
зависая на этом
}//
Вот этот круг и есть субьектность, если он руководствуется своими интересами а не плывет по течению:))
Замечу, что все процессоры имеют зачатки субьектности, но она может быть не развита, например:
ЦИКЛ внутреннего микрокода процессора
читать команду двоичного кода
найти подпрограмму микрокода, которая его
выполнит
посмотреть флаги прерываний
обработать прерывания, если есть желание, т е
вызвать обработчики по известным адресам
вызвать обработчик операционной системы, если он не
зарвался до того
посчитать чего нибудь, например среднюю загрузку и скорректировать
например тактовую часоту :))
ЕНД.
Это несколько идеальный микропроцессор. Он сочетает в себе признаки субьектности и автомата одновременно.
Но вернемся к функции поиска. Пока он обрабатывает внешние признаки, например левую историю или правый сокращенный поиск, он действует как автомат, у нее нет своего интереса и действия жестко детерминированы, т е не порождают информацию. Такие автоматы играют как правило не интересно. Может сильно, но неинтерсно это точно. Программа должна не смотреть на средние или дисперсии, а должна хотеть порвать оппонента как тузик грелку и это будет прикольно, и может быть примет коммерческий характер (не для шахмат конечно)
Вот пример. Есть 2 функции поиска. Выборочный - использует недействительное перемещение, кучу подрезок и еще чего там. И основной поиск - не использует подрезок вообще. Примерный код.
int Main_search(...){
...
//Нашли ход
if((tmp =-Selective_search(depth-1,...)) <= alpha)
tmp = -Main_search(depth-1,...);
if(tmp>alpha){
alpha=tmp;
...
}
return alpha;
}
//////////////////////
Программа на первый взгляд нелогична. Выборочный поиск вернул alpha и показал что ход неперспективен, но программа запускает элемент внутреннего цикла и пытается выдумать нечто где его казалось бы не должно быть.
Или еще вариант. После каждого хода, программа в цикле, увеличивая глубину поиска, пытается доказать, что alpha не будет улучшен. Играет как человек.
int search(depth,...){
...
//нашли ход
for(d = min(2,depth-1); d <= depth-1; d++)
if((tmp=-search(d,...)) <= alpha)
break;
if(tmp>alpha){
alpha = tmp;
...
}
return alpha;
}
/////////
Вот этот внутренний цикл затыкающий alpha и есть элемент субьектности, который создает очень приятное впечатление у пользователя.
Генетические алгоритмы в шахматных программах.
Встречайте - GSR - genetic search reduction - генетическое сокращение поиска. Сначала, для тех кто забыл, напомним основную канву генетических алгоритмов.
Пример:
Входные данные - популяция случайно инициализованных хромосом.
Ген у нас будет число - x <-- [0,1]
Хромосома - [x,x,x,x,x], одномерный массив генов длиной 5 (5 генов или чисел 0,1)
Популяция - массив хромосом.
[x,x,x,x,x],
[x,x,x,x,x],
[x,x,x,x,x],
[x,x,x,x,x],
[x,x,x,x,x],
Кроссовер - случайная точка от 1..5, точка раздела хромосомы, гены до точки раздела будут меняться местами. Обмен в 2х лучших хромосомах.
[x,x,x,x,x],
| |
[x,x,x,x,x],
|
Селекция - сортировка и выбор сверху 2х лучших.
Мутация - случайный обмен генами в 2х хромосомах, до точки кроссовера.
Цель - получить на выходе хромосому из одних 1 (единиц).
Псевдокод алгоритма может быть следующий:
Создание и инициализация популяции
Оценка
Цикл
Селекция
Кроссовер
Мутация
Оценка
Пока не достигнута цель
Вот в принципе, если это зациклить, то есть ожидание, что цель будет достигнута. Так кстати можно создать несколько наборов коэффициентов для оценочной функции и заняться селекцией. Например - коэф. ладья в обжорном ряду - 7я горизонталь. Предполагаемые значения если там есть пешки - [0.2 - 0.8] (0.2 - это 0.2 от величины пешки - 100*0.2 = 20). Можно просто взять среднее - (0.2 + 0.8)/2 = 0.5, а можно устроить турнир программ с самообучением:))
Теперь внимание. У нас в каждой позиции есть список перемещений, причем он постоянно уточняется и сортируется так чтобы наиболее вероятностно лучшие ходы шли первыми. Если мы случайным образом установим точку кроссоовера и ходы до точки будем считать хорошими и для них создадим привелегированные условия для поиска, а после точки - плохими, и применим к ним поиск на сокращенную глубину, то вероятность угадать с разделом безусловно есть и после множества попыток лучшие ходы будут схвачены и просчитаны глубже. Уф! Это эвристика это не математическая дедукция.
GSR (формальное описание алгоритма сокращения глубина поиска):
int search(depth,alpha,beta,...){
int R,
Cross = (rand()%56) + 1;//случайное от среднего кол-ва ходов (40) * sqrt(2)
...
//find move
if(legalMoves == 1 || nextCheck || PawnMoveRank7 ||
depth - reduction <= 0)
R = 0;
else if(ply > MIN_PLY &&
depth > MIN_DEPTH &&
mv&(CAPTURE|PROMOTE)==0 &&
legalMoves > Cross &&
SpechialCondition(mv)
){
R = RED2;
}else if(ply>MIN_PLY)R = RED1;
else R=0;
if((tmp = -search(depth-reduction-R,-beta,-alpha,...) > alpha){
// if(tmp>alpha&&R > 1)
// tmp = -search(depth-reduction-1,-beta,-alpha,...);
if(tmp>alpha&&R > 0)
tmp = -search(depth-reduction,-beta,-alpha,...);
}
if(tmp>alpha){
...
alpha=tmp;
}
...
return alpha;
}
///////////
MIN_PLY = 2; //первый полуход не
//сокращаем
MIN_DEPTH = 2; //3? Два последних грубо не строгаем
RED2 = 2;
RED1 = 1;
SpechialCondition(mv) = (mv&(CAPTURE|PROMOTE)==0 )&&
... //чего вам нравится
game_cnt+ply>5 &&
(material[side][game_cnt+ply] <= material[side][game_cnt+ply-5]);//например, не растет
///////////////////////////////////
Желательно еще функцию выборочного поиска вызывать из полного широтного поиска, который проверит все начисто.
int main_search(depth,alpha,beta,...){
...
if(tmp = -search(depth-reduction,-beta,-alpha) > alpha)
tmp = -main_search(depth-reduction,-beta,-alpha);
//что то вроде этого
...
return alpha;
}
Хочется добавить, что эти генетические штучки настраиваются очень тонко и желательно иметь движок уже работоспособный без них, прежде чем добавлять. Но дело в принципе. Алгоритм, красивый, лаконичный и понятный.
При том если взять гипотетическую строку поиска от корня дерева, то весьма маловероятно чтобы все сущственные перемещения были обрезаны.Я использовал формулу:
rand()%56+1;
56 = среднее кол-во ходов * 1.41 или максимальное от действующего значения синусоидальной величины:)) См. выше о канале средней величины.
Здесь огромные возможности для эксперементирования.
Вот в принципе и все.В
самом простом случае можно ставить точку раздела случайное число 2..56 и
сокращать на 1 у всех за этой точкой кроме взятий, шахов и угроз
превращения пешек, кроме первых двух полуходов.
Еще пример реализации попроще так сказать.
//функция выборочного поиска
int search(int depth,int alpha,int beta,int pre_null=0,...){
int GSR = 1 + rand()%56;
static int do_null=0;
...
//недействительное перемещение
if(ply>2 && !in_check() && !pre_null){
make_null();
do_null++;
tmp = -search(depth-3,-(beta-1),-beta,1);
do_null--;
un_make_null();
if(tmp>=beta)
if(Proverka())
return beta;
}
...
while(NextMove()){
make_move();
if(king_in_check()){
un_make_move();
continue;
}
legal_cnt++;
...
if(ply<=2 || // первые 2 полухода
next_check || //шах
depth-reduction <= 0 ||
(move & (CAPTURE|PROMOTE)) || //взятие
(material[side][game_cnt + ply] > //скорость оценки по материалу > 0
material[side][game_cnt + ply-5]) &&
legal_cnt <= GSR) //случайный выбор - первый всегда
{
//ход считается потенциально хорошим
tmp = -search(depth-reduction,-beta,-alpha);
}else{
tmp = -search(depth-reduction-1,-(alpha+1),-alpha);
if(tmp>alpha)
tmp = search(depth-reduction,-beta,-alpha);
}
un_make_move();
if(tmp> alpha){
alpha=tmp;
}
}
return alpha;
}
В данном примере велечина дополнительного сокращения всегда 1, что немного. Граница хорошие-плохие ходы выбирается случайным образом. Есть еще идея использовать эту технику только в поиске недействительного перемещения, ускоряя его таким образом еще.
Сейчас в шахматных движках можно встретить реализации LMR алгоритма где велечина сокращения не целое число и выбирается как функция от оставшейся глубины поиска, номера хода в узле, может - велечины окна поиска и много еще чего. Это по сути другой алгоритм. Почему я предпочитаю GSR? Он прост. Просто случайная граница для узла как номер хода но не менее одного. Кроме того, при всей простоте, алгоритм помогает программе хорошо схватывать фигурную активность.
Вариант внутреннего углубления поиска.
Порядок ходов в alpha-beta алгоритме имеет принципиальное значение. Хороший порядок ускоряет поиск а также изменяет стиль игры при нестабильности поиска. Нестабильность - это когда из за сокращений и подрезок поиска результат и ход, как ни парадоксально, в небольшой степени начинает зависеть от того, какой ход просмотрен первым.
Представьте себе двигатель поиска, в котором каким то образом запоминается лучший порядок ходов - это могут быть хеш таблицы, таблица истории ходов, киллеры (лучшие для своей глубины поиска). И если перед поиском перебрать на меньшую глубину и упорядочить таблицы, то в некоторых случаях это может существенно помочь усилить смысловую составляющую того, что программа играет. В некоторых случаях программа при поиске на меньшую глубину может даже вернуть лучший ход, чтобы он был просмотрен первым.
Я тут попробовал вариант предварительного поиска в варианте алгоритма nega-scout. Первый ход в этом алгоитме считается лучшим и просматривается с полным окном, таким образом, в каждом узле у нас гарантированно есть разумный alpha предел. Последующие ходы перебираются с нулевым окном, и если рузультат лучше alpha, выполняется поиск с полным окном. Вот туда то, в нулевое окно я и встроил предварительный поиск. Я обнаружил что это не увеличивает времени поиска, но может помочь от зависаний и в некоторых случаях помогает программе найти существенную игру на мат. Вот пример из реальной программы.
/* Основная идея та, что перед вызовом следующего уровня поиска
найти лучший ход поиском на меньшую глубина и дальше просматривать первый легальный ход, далее по приоритету глубина сокращается для существенных ходов и наиболее агрессивные сокращения - в конце списка ходов
*/
//цикл в функции поиска по всем ходам
nextDepth = depth-1 + ( moveDoCheck || moveDoPawnRank7);
if(legalCnt==1 || nextDepth<=0)
{
if(nextDepth>1) //ищем лучший ход с полным окном
score = -Search( -beta, -alpha, //нам нужна точная alpha в начале поиска
nextDepth-1,...);
score = -Search( -beta, -alpha,
nextDepth,...);
}else{
// поиск на меньшую глубину
//для упорядочивания ходов
// в таблице истории и пр.
score = -Search( -(alpha+1), -alpha,
nextDepth-1,
... );
if(score > alpha || depth<= 2 || nextCheck ||
pawnMoveOnRank7 || moveIsCaptureOrPromote ||
legalCnt < GSR_RANDOM_COUNT)//случайнок число, например (rand()%56)
score = -Search( -(alpha+1), -alpha,
nextDepth, ...);
if(score>alpha){ //поиск с полным окном на полную глубину
score = -Search( -beta, -alpha,
nextDepth, ...);
}
}
//////////////
Тут надо хотя бы строку главного изменения просматривать первой. Впрочем, в хорошем хеше PV узлы (оценка после просмотра узла больше альфа но меньше бета)от предыдущей итерации должны сохраниться.
Данный алгоритм можно совместиь с выборочными сокращениями поиска - LMR, GSR и пр.
Далее, если кому сложно, привожу упрощенную реализация, просматривающую глубже первый легальный ход. Превосходно работает на практике, только конечно итерации с сокращениями глубины поиска не должны пропадать даром а извлекаь по возможности лучший ход для уточнения.
nextDepth = depth-1+(move_do_check | pawn_move_on_7_rank)
if(legalCnt==1 || nextDepth<=0 || move_do_check)
{
if(nextDepth>0){ //поиск лучшего хода для следующего уровня.
score = -Search( -beta, -alpha,
nextDepth-1,...);
}
score = -Search( -beta, -alpha,
nextDepth,...);
}else{
score = -Search( -(alpha+1), -alpha,
nextDepth-1,
... );
if(score > alpha)
score = -Search( -beta, -alpha,
nextDepth, ...);
}
/////
Вот этот скромный фрагмент, похож на развитый negascout и работает практически для всех игр как шахматы, шашки, и пр и пр
Успехов.
Список используемой литературы:
|
Комментариев нет:
Отправить комментарий