Главная » Игры, Теория » Детекторы шахов

0

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

Без детектора шахов не обходится ни одна шахматная программа. Причина в том, что программа должна находить наиболее сильные перемещения, стремиться поставить мат противнику и усилить давление на его короля, а шах — это потенциально наиболее сильное перемещение. Шахи очень ска­зываются на эффекте горизонта. Если программа считает, например, на 6 полуходов, то из-за шаха в конце строки она может выдать неверный ре­зультат: ей может показаться, что она теряет ферзя, а нужно только укло­ниться от шаха. Если мы используем выборочные продления и не сокращаем глубину перебора при шахе, то программа может находить очень глубокие форсированные маты, и в этих ситуациях сказывается все преимущество машины перед человеком. Продление статической оценкой — это примерно то же самое, оно используется для сглаживания эффекта горизонта или на­хождения в глубине очень длинных тактических выпадов, построенных на шахах.

Так или иначе, детектор шахов — это одна из основных частей шахматной программы, и имеет смысл рассмотреть его подробнее.

Какие основные требования предъявляются к детектору шахов?

?    Он должен работать максимально быстро. Отсутствие шаха должно опре­деляться практически сразу, чтобы не иметь непроизводительных рас­ходов.

?    Он должен определять шах, объявленный последней ходившей фигурой противника. Если в строке игры шах уже был объявлен другой фигурой, то короля уже съели в предыдущем узле.

Примечание

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

Как видим, детектор шахов — довольно условная вещь и даже не определя­ет всех шахов. Тем не менее на практике он необходим.

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

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

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

00000000

Мы можем определить ненулевой бит для ферзя:

00000001

Сложнее, если две фигуры могут объявить шах из одного места, например слон и ферзь. Для слона мы используем следующий бит:

00000010

Тогда в ячейке массива, откуда и слон, и ферзь могут объявить шах, будет изображено:

00000011

Если представить это на языке программирования, то это будет подобно следующему:

CONST

check_queen = 1; check bishop = 2;

Чтобы определить возможность шаха только для ферзя, мы должны приме­нить к ячейке массива операцию AND с кодом ферзя:

(value AND CHECK_BISHOP)

if (value AND CHECK_BISHOP) о 0 then …

Поразрядная логическая операция AND оставит только те биты, которые установлены в 1 у обоих операндов, остальные сбросит в 0.

Для ладьи:

00000100

После того как мы определили возможность вероятного шаха, нужно по­строить линию для дальнобойных фигур, чтобы убедиться, что на ней ниче­го нет. Для коня линию строить не нужно. Для него вероятный шах совпа­дает с действительным. Для пешки необходимо просто проверить, по ходу ли пешки клетка короля. Черные пешки двигаются вниз, а белые вверх. Для черных нужно проверить, что координата Y пешки меньше координаты ко­роля, для белых — наоборот.

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

Игровое поле у нас представлено массивом 16 х 16 с массивом игры 8^8 в центре и флагом выхода за пределы по краям. Вот пример детектора шахов:

{/////////// некоторые предшествующие определения ///////} TYPE

TPosl6 = array[0..16*16-1] of integer; {позиция} CONST (фигуры) KING = 1 ; QUEEN = 2; ROOK = 3; BISHOP = 4; KNIGHT = 5;

PAWN = 6; (итого первые 3 бита}

{цыета}

CBLACK = 64;

CWHITE = 128;

CCOLOR = CBLACK + CWHITE; {маска для выделения цвета} CFIGURE = 7;  {маска для выделения фигуры}

COUT = (1 shl 9);     {выход за пределы доски}

var glUpFColor; {цвет верхних фигур}

{//////////////////////// детектор шахов //////////}

{вероятный шах}

CONST

{коды фигур для вероятного шаха)

N_QUEEN = 1;

N_ROOK = 2;

N_BISHOP= 4;

N_KNIGHT= 8;

N_PAWN = 16;

N_NO = 32;

{массив, где по основному коду фигуры (1..6) записан код

фигуры для детектора шахов }

_codeF:array[0..6] of integer = (N_NO,N_NO,N_QUEEN,N_ROOK,N_BISHOP,N_KNIGHT,N_PAWN);

{массив вероятного шаха, в каждой ячейке сумма кодов фигур, которые могут объявить шах из этой ячейки}

BASE = (16*7)+8-1;   {координата виртуального короля} X = 0;

_check:TPosl6 = (

5, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0,  0, 0,   5, 0,

0, 5, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0,  0, 5,   0, 0,

0, 0, 5, 0, 0, 0, 0, 3, 0, 0, 0, 0,  5, 0,   0, 0,

0, 0, 0, 5, 0, 0, 0, 3, 0, 0, 0, 5,  О, О,   О, О,

О, 0, 0, 0, 5, 0, 0, 3, 0, 0, 5, О,  О, О,   О, О,

О, О, О, 0, 0, 5, 8, 3, 8, 5, О, О,  О, О,   О, О,

О, 0, 0, 0, 0, 8,21, 3,21, 8, О, О,  О, О,   О, О,

О, О, О, О, О, 8,21, 3,21, 8, О, О,  О, О,   О, О,

О, О, 0, 0, О, 5, 8, 3, 8, 5, О, О,  О, О,   О, О,

О, 0, 0, 0, 5, 0, 0, 3, 0, 0, 5, О,  О, О,   О, О,

О, 0, 0, 5, 0, 0, 0, 3, 0, 0, 0, 5,  О, О,   О, О,

О, 0, 5, О, О, О, 0, 3, О, О,  О,  0, 5,   О,   О, О,

О, 5, О, О, О, О, 0, 3, О, О,  О,  О, 0,   5,   О, О,

5, О, О, О, О, О, 0, 3, О, О,  О, О, О,     0,   5, О,

О, О, О, О, О, О, О, 3, О, О,  О, О, О,     0,   0, 5 ) ;

{приращения при построении линии} _del:TPosl6 =

(

-17,  О, О, О, О, 0, 0,-16, 0, 0, 0, 0, 0, 0,-15, 0,

0,-17, 0, 0, 0, 0, 0,-16, 0, 0, 0, 0, 0,-15, 0, 0,

0, 0,-17,  0, 0, 0, 0,-16, 0, 0, 0, 0,-15, 0, 0, 0,

0,  0, 0,-17, 0, 0, 0,-16, 0, 0, 0,-15, 0, 0, 0, 0,

0,  0, 0, 0,-17, 0, 0,-16, 0, 0,-15, 0, 0, 0, 0, 0,

0,  0, 0, 0, 0,-17, 0,-16, 0,-15, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 8,-17,-16,-15, 8, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 8, 15, 16, 17, 8, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 15, 0, 16, 0, 17, 0, 0, 0, 0, 0, 0,

0, 0, 0, 0, 15, 0, 0, 16, 0, 0, 17, 0, 0, 0, 0, 0,

0, 0, 0, 15, 0, 0, 0, 16, 0, 0, 0, 17, 0, 0, 0, 0,

0, 0, 15, 0, 0, 0, 0, 16, 0, 0, 0, 0, 17, 0, 0, 0,

0, 15, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 17, 0, 0,

15,   0, 0, 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 17, 0,

0,  0, 0, 0, 0, 0, 0, 16,    О, 0, О, О, О, О, 0, 17 ) ;

{возвращает true, если фигура f с    индексом NFigure объявляет

шах королю с индексом NKing

счет ведется для позиции 16*16 glPos

}

FUNCTION InCheck(F,NFigure,NKing:integer) :boolean;

VAR

del,N:integer;

BEGIN

InCheck := false; {вероятный шах}

if (_check[ NKing-NFigure+BASE ] and _codeF[F and CFIGURE]) о

(_codeF[F and CFIGURE]) then exit ;

{для пешки и коня – своя проверка} case (f and CFIGURE) of KNIGHT: begin

InCheck := true; exit; end; PAWN:begin

if (F and CCOLOR) = glUpFColor then begin

if NFigure < NKing then InCheck := true;

end else begin

if NFigure > NKing then InCheck := true;

end;

exit; end; end; {case}

(строим линию между двумя точками} del := _del[NFigure – NKing + BASE]; if del = 0 then exit; N := NKing + del; (если вышли за пределы поля игры, флаг выхода} while (N о NFigure) and (glPos[N] = 0) do inc(N,del);

InCheck := (N = NFigure);

END;

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

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

Литература:

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

По теме:

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