Главная » Игры, Теория » Правдоподобная генерация перемещений

0

В статическом поиске результат (и лучший ход) зависит от порядка переме­щений. Как это происходит? Допустим, у нас есть два тихих перемещения. Оба дают приращение в узле +8. Оба увеличивают alpha до значения боль­ше статической оценки после хода. Если мы просчитаем первым одно пе­ремещение, второе подрежется статической оценкой. Оба хода ведут к под­резанию. Это явление получило название нестабильности поиска. Обычно нестабильность поиска считается досадной помехой, мешающей осущест­вить грубое усилие более глубоко. Нестабильность поиска возникает в тех случаях, когда отсечка или сокращение глубины основаны на пределах alpha-beta. В качестве примера посмотрим на использование нулевого хода. Мы можем применять нулевой ход без всяких условий:

int Search(int alpha, int beta, int player, int opponent, int depth) {

if(-Search(-beta,-(beta-1),opponent,player,depth-3) >= beta) return beta; (…) //сам поиск

)//function

Предлагается оговорить использование нулевого хода условием: текущая статическая оценка больше или равна beta. Дело в том, что если статическая оценка меньше beta, и мы пропустим ход, то в подавляющем большинстве случаев противник улучшит позицию, и дорогостоящий вызов нулевого хода пропадет напрасно.

Условие применения нулевого хода следующее:

if(L_SCORE >= beta) {

//do null-move {. . . }

)

Очевидно, что даже применение нулевого хода не спасает от нестабильно­сти поиска. Тем более, если мы подрезаем сразу, без проверочных условий. Отсечение статической оценкой может быть двух видов:

int Search(int alpha,int beta,….) {

if(L_SCORE > alpha) alpha = L_SCORE;

if(alpha >= beta) return beta; //можно и alpha

{…} //сам поиск

}

ИЛИ

int Search(int alpha,int beta,…) {

if(L_SCORE >= beta) return beta; //или L_SCORE {…} //сам поиск

}

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

В таком форсированном варианте можно оставить все перемещения на пер­вых двух полуходах, а потом считать только взятия. Тогда ходы, дающие прирост меньше 0 в узле, автоматически подрежутся статической оценкой, а у остальных максимум будет ограничен приростом оценки при ходе

(r_score).

Такой придаток из двух полуходов не сильно задержит поиск, но улучшит понимание программой позиционной оценки. Мне не известен другой спо­соб заставить программу понимать позиционную игру, кроме как повышать alpha текущей оценкой. Это относится к любому виду позиционной оценки. Рассмотренные два полухода часто используются для более глубокого про­смотра шахов, но речь сейчас не об этом, а о чувствительности к порядку ходов, хотим мы этого или нет. Приведу простой пример. Допустим, у нас есть списки фигур, инициализированные перед началом счета. Берем пере­мещения в следующей последовательности: Queen, Rook, Bishop, Knight, King, Pawn. Мы получим один стиль игры. Если мы возьмем перемещения в обратной последовательности: Pawn, King, Knight, Bishop, Rook, Queen, мы получим совершенно другой стиль. В шахматах ход назад считается потен­циально слабым (по крайней мере, в начале партии). Если упорядочить хо­ды так, что ходы назад будут рассмотрены в последнюю очередь, программа будет пытаться решать возникшие задачи, не отступая. Можно менять при­оритет в ходе игры. Мы можем не полагаться на случай, а упорядочить счет:

1.   Борьба за центр (начало партии).

2.   Охота на короля (если ферзей не разменяли).

3.   Проходные пешки (если нет ферзей).

Так как мы не вводим четких позиционных оценок, то стиль игры про­граммы изменяется, но не жестко. Эффект может быть особенно сильным, если у нас более двух полуходов статического отсечения, и мы уточняем главное изменение, оставшееся от предыдущей итерации. Можно попытать­ся сохранить пешечный экран короля (тоже мягко) и т. д. Не прибегая к утомительной настройке коэффициентов вручную, можно научить програм­му пониманию некоторых позиционных факторов. Например, ладейные пешки вперед двигать плохо. Как плохо, насколько? Иногда это выигрывает всю партию, хотя двигать ладейные пешки в начале игры — признак дурно­го стиля. Но как задать эти признаки конкретными значениями? Порядок ходов частично решает эту задачу.

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

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии