Главная » Игры, Теория » Безопасность короля

0

В шахматах безопасность короля занимает особое место. Цель игры — по­ставить мат королю. Чем больше программа обращает внимание на без­опасность короля, тем лучше она играет. Нужно учесть, что оценка позиции инвертированная, и если мы разрабатываем безопасность короля, то про­грамма лучше чувствует потенциальные угрозы королю и успешнее строит атаки на короля противника. — это ключевая тема шахматной программы. Шахи, безусловно, отражают безопасность короля, но не в полной мере. Очень глубокого полного перебора и продления шахов может оказаться достаточно для приемлемой игры, но варианты, потенци­ально опасные для короля, лучше просчитывать глубже. Эти ходы сложно как-то характеризовать. Они увеличивают давление на короля противника, и все. Представим себе на поле игры некоторые воображаемые квадраты: квадрат, равный полю игры, отображает все поле, некоторый квадрат вокруг короля — поле короля. Любые передвижения в квадрате короля могут иметь повышенную опасность для него. Можно еще представить себе квадрат цен­тра поля, отражающий борьбу за центр в начале игры, некоторый квадрат для проходных пешек на половине противника и т. д. Главная идея исполь­зования таких квадратов, или мини-полей, заключается в том, что на всем поле перебрать глубже ходы мы не в состоянии, но можно продлевать ходы в некоторых выбранных квадратах. Деление на квадраты довольно условно, но нужно не забывать, что мы не вносим дополнительной погрешности, а только ищем критерии для более углубленного просчета некоторых ходов. Ситуация в форсированных вариантах все равно будет просчитана до конца, мы только можем расширить полный перебор для некоторых строк игры.

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

Выборочные продления — хорошая техника, но их не должно быть много. Каким же образом можно ограничить неуправляемый рост дерева перебора при выборочных продлениях? Можно задать дробное значение Depth, можно расширять потенциально опасные для короля ходы. И потом, этих расши­рений все равно не должно быть много.

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

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

//////////////// расстояние до фигуры ///////// static unsigned char _taxi[20*32]= f

9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9, 8,7, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 8, 9, 0, 0, 0,0, 0, 0, 0, 0,0, 0, 0, 0, 0, 9,8,7,6,5,5,5,5,5,5,5,5,5,5,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,5,4,4,4,4,4,4,4,4,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,5,4,3,3,3,3,3,3,3,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,5,4,3,2,2,2,2,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,5,4,3,2,1,1,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9,3,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,5,4,3,2,1,1,1,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,5,4,3,2,2,2,2,2,3,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,5,4,3,3,3,3,3,3,3,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,5,4,4,4,4,4,4,4,4,4,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,5,5,5,5,5,5,5,5,5,5,5,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,6,6,6,6,6,6,6,6,6,6,6,6,6,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,0,0,0,0,0,0,0 } ;

////////////// возвращает расстояние от фигуры до фигуры /////////////// #define TAXI(х,у,kingX,kingY)\ ( _taxi[ ((9 + ((int)у – (int)kingY)) « 5)\ + 9 + ((int)x – (int)kingX) ])

Воображаемый король стоит в ячейке [9,9]. Ширина массива больше его высоты. Это сделано для того, чтобы можно было вычислить индекс ячейки без умножения простым битовым сдвигом. Умножение на 32 эквивалентно сдвигу влево на 5. Современные процессоры очень быстро перемножают небольшие числа, но злоупотреблять этим не следует. Функция taxi перево­дит координаты ферзя (х, y) и короля (kingx, kingY) в координаты массива taxi и возвращает расстояние от ферзя до короля. Этот пример только де­монстрирует один из способов решения данной задачи. Далее приводится схематичный пример расширения узла при потенциальной угрозе ферзя ко­ролю:

if(ply <= _maxPly+2 && PIECE(_pos[fy][fx]) = QUEEN) {

int oldTaxi = TAXI(oldX,oldY,kingX,kingY); int newTaxi = TAXI(fx,fy,kingX,kingY); bool isTaxi = false;

if(newTaxi < 4) {

if(newTaxi < oldTaxi) isTaxi = true;

if(newTaxi == oldTaxi && fx+fy < oldX+oldY) isTaxi = true;

}

if(isTaxi) isAddDepth = true;

}

if(isAddDepth) Depth++; Depth—;

Обозначения в программе:

?    oldTaxi — расстояние от ферзя до короля в старой позиции ферзя; П newTaxi — расстояние от ферзя до короля в новой позиции ферзя;

?    fy, fx — новые координаты ферзя;

?    oldY, oldx — старые координаты ферзя;

D kingY, kingx — координаты нашего короля;

?    isAddDepth — флаг расширения узла;

?    ply — абсолютная глубина узла в строке от 0;

?    depth — остаток глубины просчета (регулируется);

D maxPly — гарантированная глубина просчета при данной итерации без выборочных продлений.

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

не ограничивается угрозами ферзя. Она может отра­жаться и в оценочной функции, и в выборочных продлениях. Возможен и силовой вариант: перебор на 8 (лучше — 10) полуходов с продлением ша­хов. Стандартный подход учитывает безопасность короля только в позици­онной оценке и продлевает только шахи. Но с таким подходом не написать программу, играющую выше среднего уровня (если у вас, конечно, нет зна­комого гроссмейстера, который потратит на написание и отладку оценоч­ной функции лет тридцать).

Стандартными, с точки зрения теории игр, являются расширения, значи­тельно увеличивающие прирост в узле после хода. Для шахмат — еще шахи и авансы пешек. Перебор для сильной игры при силовом решении должен быть не менее 8 полуходов, кроме того, форсированные варианты с взятия­ми. Все остальное находится в области экспериментирования. Расширяя узлы, критичные для безопасности короля, но не имеющие четкой фор­мальной характеристики, мы рискуем, и подобный подход требует тонкой настройки. Тем не менее на практике это может работать очень хорошо. Желательно добиться, чтобы программа в дереве перебора всегда дотягива­лась до короля, каким бы пешечным и другим экраном он ни был закрыт. Для этого можно расширить другие ходы в квадрате короля (простые пере­мещения — совсем немного, взятия — значительно больше). В самом нача­ле игры такое расширение использовать не целесообразно. В качестве при­мера могу сказать, что расширение только угроз ферзя придавало програм­ме, считающей на 6 полуходов, способность видеть острые ситуации, которые могла развить только программа, считающая на 8 или даже 10 по­луходов. Просчитывать глубоко самые интересные ситуации — это признак уровня программы и совершенно преобразует ее игру, даже когда подобные ситуации не подпадают под формальные признаки.

Литература:

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

По теме:

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