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

0

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

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

1)   Простой ход фигуры из одной позиции в другую. Фигура при этом стира­ется в старой клетке доски и записывается в новой. Вся необходимая ин­формация об этом перемещении содержится в индексе стартовой клетки и индексе конечной клетки. Можно назвать их N1 и N2. Это самый простой ход, и с ним не будет путаницы.

2)   Простой ход с взятием. Фигура при этом покидает стартовую клетку и становится в другую. При этом она съедает фигуру противника в конечной клетке. Для данного перемещения нужно тоже две переменных N1 и N2.

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

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

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

5)   Рокировки. Существуют правая и левая рокировки. Король и ладья дела­ют нестандартное перемещение. Рокировку можно делать, только если ко­роль и ладья до этого ни разу не ходили, и король не под шахом. Король, так как он перепрыгивает через клетку, не должен пересекать битое поле. Эту особенность можно и не учитывать для простой программы, но что ко­роль не делает рокировки под шахом, надо учитывать обязательно. Для ге­нерации перемещения нужно много информации: перемещалась ли фигура до этого, детектор шахов, стартовая и конечная координаты короля, старто­вая и конечная координаты ладьи, кроме того, флаг перемещения, характе­ризующий вид данного хода. Попробуем сформировать тип описателя пере­мещения. Он нужен для того, чтобы функция MakeMove, которая выполнит данное перемещение, могла его сделать, а функция UnMakeMove — восстано­вить позицию. Шахматную позицию, хотя она и имеет два измерения, мы представим в виде одномерного массива:

const pos:array!0..7,0..7] of byte =

(

(0,0,0,0,0,0,0,0), (6,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0) , (0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0)

);

В шахматах доска имеет размер 8×8 клеток. В нашем случае массив проин­дексирован 0..7, что одно и то же. Данный двумерный массив можно пред­ставить одномерным:

const pos: array [0. ..63] of byte = (

0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0

);

Что мы выигрываем, представляя двумерный массив одномерным? Раньше профессионалы бы заметили, что двумерный массив при компиляции под­разумевает дополнительную операцию умножения (или битового сдвига для хорошего компилятора). Компилятор, чтобы определить конкретный адрес в массиве, делает следующее:

N := у*8 + х;

Хороший компилятор сделал бы следующее:

N := (у shl 3) + х;

Битовый сдвиг влево на 3 — это то же, что умножить число на 8.

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

увидим впоследствии, а пока представим наш целевой массив как сле­дующий:

const pos:array[0..16*16-1]   of integer = (

F,F,F,F, F, F, F, F, F, F, F, F,     F, F, F, F,

F,F,F,F, F, F, F, F, F, F, F, F,     F, F, F, F,

F,F,F,F, F, F, F, F, F, F, F, F,     F, F, F, F,

F, F, F, F, F, F, F, F, F, F, F, F,  F, F, F, F,

F, F, F, F, 0,0,0,0,0,0,0,0, F,F,F,F,

F, F, F, F, 0,0,0,0,0,0,0,0, F, F, F, F,

F,F,F,F, 0,0,0,0,0,0,0,0, F, F, F, F,

F,F,F,F, 0,0,0,0,0,0,0,0, F, F, F, F,

F, F, F, F, 0,0,0,0,0,0,0,0, F, F, F, F,

F, F, F, F, 0,0,0,0,0,0,0,0, F, F, F, F,

F,F,F,F, 0,0,0,0,0,0,0,0, F, F, F, F,

F,F,F,F, 0,0,0,0,0,0,0,0, F, F, F, F,

F, F, F, F, F, F, F, F, F, F, F, F,  F, F, F, F,

F, F, F, F, F, F, F, F, F, F, F, F,  F, F, F, F,

F, F, F, F, F, F, F, F, F, F, F, F,  F, F, F, F,

F, F, F, F, F, F, F, F, F, F, F, F,  F, F, F, F

} ;

Само игровое поле находится  в центре и помечено 0. Клетки за пределами поля помечены константой F. Чтобы преобразовать координату N данного массива в координаты массива 8 х 8, нужно сделать следующее:

X := N mod 16 – 4;

Y     := N div 16 – 4;

Данную тонкость можно представить в более профессиональном виде:

X : = (N and 15) – 4;

Y     := (N shr 4) – 4;

Или на языке С:

х = (п & 15) – 4; у = (п » 4) – 4;

Обратное преобразование несколько избыточно по коду, можно просто вос­пользоваться массивом перекодировки, где для каждой клетки с координа­той N записана координата этой клетки в массиве 16 х 16. Это просто и бы­стро выполняется.

const hlatl6:array[0..63] of integer = (

68,69,70,71,72,73,74,75 ,

84,85,86,87,88,89,90,91,

100,101,102,103,104,105,106,107,

116,117,118,119,120,121,122,123,

132,133,134,135,136,137,138,139,

148,149,150,151,152,153,154,155,

164,165,166,167,168,169,170,171,

180,181,182,183,184,185,186,187,

) ;

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

CONST

{типы перемещений}

kNormal   = 1; {простой ход}

kCapture = 2; {простое взятие}

kFIrstPawn = 4; {первый ход пешкой через клетку}

kEnPassant = 8; {взятие пешкой через битое поле}

kLeftCastling = 16; {левая рокировка}

kRightCastling = 32; {правая рокировка}

kPromote = 64; {превращение пешки}

kNotMove = 0; {нет перемещений}

{примерный описатель хода} Type TMove = record

N1,N2:integer; { откуда и куда пошла фигура }

F:integer;     {сама фигура}

eatFN:integer; {координата взятой фигуры}

eatF:integer; {взятая фигура}

desc:integer; {тип хода}

rNl,rN2:integer; {откуда и куда пошла ладья при рокировке}

end;

Потребуются еще значения фигур в новой позиции. Например, ходил ферзь с dl на d2. Ячейка в массиве позиции должна отражать, что ферзь переме­щался. При сканировании массива позиции мы должны четко знать, какая фигура перемещалась хоть раз, а какая — нет. Это нужно для генерации первых ходов пешки и рокировок. Позиция у нас представлена одномерным массивом чисел. Давайте разберемся с этим. Если в клетке доски 0, фигуры нет. Введем коды фигур:

{фигуры} CONST

KING = 1 ; QUEEN = 2; ROOK = 3; BISHOP = 4; KNIGHT = 5;

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

Наши коды фигур представлены числами от 1 до 6 включительно. Это зна­чит, они поместятся в первых 3 битах числа. Остальные биты числа мы мо­жем использовать по своему усмотрению. Определим необходимые кон­станты:

{цвет}

CBLACK = 64; CWHITE = 128;

Эти десятичные числа займут биты с номерами 6 и 7. У нас еще остаются свободными биты с номерами 5, 4, 3. Один из них используем под флаг пе­ремещения. Если он установлен, фигура перемещалась до этого хоть один раз.

CMOVE = 16; {флаг, что фигура перемещалась}

Позиция находится в центре массива 16 х 16, а по краям находятся поля, которые нужно заполнить флагом переполнения, чтобы было видно, когда мы вышли за пределы доски. Для этого можно использовать оставшийся свободным бит с номером 3.

COUT = 8;

У нас еще остался свободным бит с номером 5. Его мы используем позже. Проверить, какая фигура стоит в клетке доски, легко можно с помощью поразрядной логической операции AND. Она в результате оставит только те биты, которые установлены в 1 у обоих операндов. Чтобы из клетки доски выделить код фигуры (без цвета), мы должны сделать следующее:

F : = S and 7;

где s — клетка доски.

Чтобы выделить цвет фигуры:

COLOR := S and (CBLACK + CWHITE);

Введем некоторые дополнительные константы для удобства:

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

Для того чтобы выделить фигуру, мы можем написать:

F := S and CFIGURE;

Цвет:

COLOR :+ S and CCOLOR;

Намного понятнее в реальной программе. В языке С подобные операции удобно делать с помощью макросов с параметрами.

Чтобы проиллюстрировать все изложенное, возьмем все перемещения фер­зя. Наша позиция, как вы помните, представлена массивом 16 х 16. Игро­вое поле 8×8 находится в центре, а лишние поля заполнены флагом пере­полнения.

procedure GetMovesQueen( Nf:integer {координаты фигуры};

opColor:integer {цвет фигур противника}

) ;

const

addNQueen:array[0..8] of integer = (1§,-16,1,-1,17,-17,15,-15,0); var

N, j:integer; begin

j := 0;

while addNQueen[j] <> 0 do begin

N := Nf + addNQueen[j]; while pos[N] = 0 do begin

{здесь простое перемещение ферзя в пустую клетку (не взятие)

}

N := N + addNQueen[j]); end;

{ не пустая клетка доски,

если на ней стоит фигура противника, это взятие

}

if (pos[N] and CCOLOR) = opColor then

begin

{нашли взятие} end; j := j + 1;

end;

end;

Как видите, все предельно просто, и объем кода минимален. Если бы мы использовали двумерный массив или не имели по краям полей с флагом переполнения, объем кода значительно возрос бы.

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

if (pos[N] and CCOLOR) = opColor then …

Так как цвета фигур имеют значения 64 и 128, а флаг переполнения 8, то при операции AND они никогда не пересекутся, так как это различные би­ты.

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

TMove = record N1,N2:byte; end;

Или может выглядеть так:

TMove = record

N1, N2:byte;    {откуда и куда}

moveType:byte;   {тип перемещения}

next:byte; {номер следующего описателя в буфере} end;

Это несколько отвлеченный пример, но он демонстрирует основные прин­ципы. Когда мы находим очередное перемещение, мы добавляем его в свой список. Списки потом соединяются, и функция Generate (генератор пере­мещений) возвращает указатель на первый элемент общего списка переме­щений. Типичный описатель списка:

PList = /vTList;

TList = record {…}

PList next; end;

Поле next указывает на следующий элемент списка. Это обычный указа­тель, и его размер, как правило, составляет 4 байта. В нашем случае функ­ция Generate для описателей перемещения использует буфер, откуда берутся свободные описатели. Буфер может располагаться где угодно, обычно в сте­ке вызывающей функции. Размер буфера ограничен некоторым реальным числом, представляющим максимально возможное количество ходов в дан­ной позиции. Для шахмат это может быть 200. Таким образом, буфер состо­ит из 200 элементов, и для адресации следующего элемента можно исполь­зовать не указатель, а просто номер элемента в буфере. Например:

const MAX_MOVES = 200;

EMPTY = 255; {такого номера не может быть} buf:array[0.,MAX_MOVES-l] of TMove; list:byte; {индекс первого элемента списка} count:byte; {номер первого свободного описателя в буфере} list := EMPTY;

count := 0; {. . . }

{нашли перемещение} with buf[count] do begin

{заполнили все необходимые поля} {…}

{вставим в список} next := list; end;

list := count; count := count + 1;

Здесь не показано, каким образом мы нашли перемещение. Это в данном случае не важно. Чтобы просмотреть весь список, нужно сделать примерно следующее:

while list о EMPTY do begin with buf[list] do begin

{необходимые действия с данным ходом} {…}

{номер следующего хода} list := next; end;

end;

Я думаю, эти операции не сложнее, чем с указателями. Можно использо­вать и указатели, это совершенно не принципиально. Просто повысится размер описателя перемещения, а у нас задача ограничить его 4 байтами.

В приведенном ранее примере мы осуществляли вставку в начало списка. Если есть необходимость вставлять в конец списка, можно сделать следую­щее:

type PByte = ~byte; const MAX_MOVES = 200;

EMPTY = 255; {такого номера не может быть} buf:array[0..MAX_MOVES-l] of TMove; listrbyte; {индекс первого элемента списка} lastltem:PByte;{указатель на адрес конца списка} count:byte; {номер первого свободного описателя в буфере} list := EMPTY; lastltem := @list;

count := 0; {- . .}

{нашли перемещение} with buf[count] do begin

{заполнили все необходимые поля} {. . . }

{вставим в список} next := EMPTY; lastltem’4 := count; lastltem := @next; end;

count := count + 1;

В конец списка удобнее, потому что мы при генерации перемещений будем отслеживать несколько подсписков, которые нужно потом соединить в один.

Рассмотрим еще один важный момент. При генерации перемещений нам нужно найти наши фигуры. Сканировать массив доски в поисках своих фи­гур неэффективно. Генератор перемещений должен работать максимально быстро. Для определения места расположения фигур можно ввести списки фигур. Они инициализируются один раз перед началом просчета и потом только корректируются. Каждый элемент списка фигур должен содержать координату фигуры и собственно фигуру. Описатель элемента списка фигур может выглядеть как

PPiece = ЛТР1есе; TPiece = record

_ N:integer; {номер клетки фигуры}

_ F:integer; {фигура}

_ index:integer; {номер описателя в буфере}

_ next:PPiece; {следующий элемент списка}

end;

К каждому элементу списка фигур можно обратиться по указателю и по номеру данного элемента в буфере, откуда берутся описатели. Списки фи­гур инициализируются следующим образом. Сначала идет король, потом ферзь и так все фигуры по убыванию. Выглядит это примерно так: King, Queen, Rook, Rook, Bishop, Bishop, Knight, Knight, Pawn. Вот пример функ­ции, инициализующей списки фигур перед просчетом:

{глобальные переменные} var

glFigBuf:array[0..32] of TPiece; {буфер описателей фигур}

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

glUpFList:PPiece;{список фигур верхних}

glBotFList:PPiece;{список фигур нижних}

{инициализирует списки фигур}

PROCEDURE InitFList;

VAR

р:PPiece;

count,К,N,f:intege г; BEGIN

count := 0;

glUpFList := NIL;

glBotFList := NIL;

for K := PAWN downto KING do

for N := 0 to 16*16-1 do

begin

f := glPos[N];

if (f = 0) or (f = COUT) or ((f and СFIGURE) о K)

then continue; p := @glFigBuf[count];

рл.    F := f;

рл.    N := N;

рл.    index := count;

inc(count >;

if (f and CCOLOR) = glUpFColor then begin

рл.    next := glUpFList;

glUpFList := p; end else begin

рл.    next := glBotFList;

glBotFList := p; end;

end;

glFigBufCount := count; {количество фигур}

END;

К любому элементу списка фигур можно обратиться по его указателю и но­меру в буфере giFigBuf. Окончательный вариант описателя перемещения, который будет однозначно определять ход:

PMove = ATMove; TMove = record case byte of 1: (

____ Figlndex:byte; {индекс описателя перемещения в giFigBuf}

____ N2:byte;    {куда пошла}

____ desc:byte;  {тип перемещения}

____ next:byte;  {индекс следующего перемещения}

) ; 2: (

____ data:LongInt;

) ;

end;

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

with giFigBuf[ Figlndex] do

begin

{все поля}

end;

Почему такая сложность и запутанность? Дело в том, что перемещения должны браться максимально быстро. В нашем случае нам нужно всего 4 байта. Это совсем немного и по размеру, и по объему заполнения. Боль­шинство ходов не потребуется, и нет смысла создавать для каждого хода развернутый описатель перемещения. Функция Generate — самая критичная по времени функция выполнения программы. Были многочисленные по­пытки реализовать ее аппаратно, чтобы повысить производительность при вычислении. Если у нас будет генератор перемещений и функции MakeMove и UnMakeMove, делающие перемещение и восстанавливающие позицию, на это можно будет не обращать внимания, а заниматься более интересными вещами.

В поле описателя перемещения есть еще элемент    data. Он занимает то же

пространство в памяти, что и 4 байта основного описания. Это так назы­ваемое объединение (union). Если нужно скопировать один описатель пере­мещения в другой, совершенно не обязательно копировать все поля по оче­реди. Можно написать

movel. data := move2. data;

Все поля при этом будут корректно перенесены, так как поле        data зани­мает в памяти машины то же место, что и 4 байта основного описания.

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

Чтобы alpha-beta процедура нормально считала, ходы, дающие наибольшие приращения в узле, должны быть рассмотрены первыми. Это верно и для материальной, и для стратегической оценки. Мы должны наиболее ценные взятия рассматривать первыми, а наименее ценные последними, по прин­ципу MW/LVA (наиболее ценная жертва — наименее ценный нападаю­щий). Итак, определим порядок сортировки взятий:

1.   Взяли короля.

2.   Взятия, бьющие последнюю ходившую фигуру противника.

3.   Взятия по убыванию веса захваченной фигуры.

Как видите, все достаточно непросто. Взятия можно и не сортировать, но скорость просчета при этом резко снизится, и рассматривать форсирован­ные варианты до конца мы просто не сможем.

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

TYPE

TMoveArray = array[0..1] of TMove; PMoveArray = /4TMoveArray; {типы перемещений} CONST

{типы перемещений}

kNormal        = 1; {простой ход}

kCapture       = 2; {простое взятие}

kFIrstPawn     = 4; {первый ход пешкой через клетку}

kEnPassant = 8; {взятие пешкой через битое поле} kLeftCastling = 16; {левая рокировка} kRightCastling = 32; {правая рокировка} kProraote = 64; {превращение пешки} kNotMove = 0; {нет перемещений} CONST

M_EMPTY = 255; { указатель NIL} {приращения при движении фигур ло коду фигуры

если приращение 0, конец строки приращений }

type tagArray = array[0..8] of integer; const

_addEmpty:tagArray = (0,0,0,0,0,0,0,0,0); {пустая строка для кода 0}

_addKing:tagArray = (16,-16,1,-1,17,-17,15,-15,0); {для короля} _addQueen:tagArray = (16,-16,1,-1,17,-17,15,-15,0); {для ферзя} _addRook:tagArray = (16,-16,1,-1,0,0,0,0,0);  {для ладьи}

_addBishop:tagArray = (17,-17,15,-15,0,0,0,0,0);    {для слона}

_addKnight:tagArray =

(32+1, 32-1,16+2,16-2,-(32+1),-(32-1),-(16+2),-(16-2),0);{для коня}

{адреса строк приращений по коду фигуры} const glAdd: array [ 0. . 6 ] of PIntArjcay = (

@_addEmpty,@_addKing,@_addQueen,@_addRook,@_addBishop,@_addKnight, @_addEmpty ) ;

{получает взятия в отсортированном порядке}

PROCEDURE GenerateAndSortAllCaptures( color:integer; {цвет фигур}

node:PMove; {ход в эту позицию} buf:PMoveArray; {стековый буфер } size-.integer; {сколько TMove в буфере} {номер первого элемента списка в буфере } var firstMove:integer; var countMoves:integer {сколько перемещений} ) ;

{единица соответствует коду фигуры, чье перемещение не требует линии: король и конь} const simpleF:array[0..6] of byte = (0,1,0,0,0,1,0); const pawnlnQueen:array[0..15] of byte = (0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0); VAR

list:PPiece;   {список наших фигур}

count:integer; {сколько описателей перемещений использовано} {список взятий, бьющих последнюю ходившую фигуру} la-stEatList:byte; {начало списка}

pLastEatList:PByte; {всегда указывает на конец списка} {списки остальных взятий}

eatList:array[0..б] of byte; {по коду взятой фигуры} pEatList:array[0..6] of PByte; {на концы списков} n:integer;

f:integer; {фигура, чьи перемещения берем} pAdd:PIntArray; {строка перемещений} index:integer; {куда фигура переместилась} delPawn:integer; {приращение при движении пешки} tmp:integer; eatF:integer;

procedure AddEatMove( codeEatF:integer; {код взятой фигуры} flag:integer     {тип хода}

) ;

var

listNumber:integer; begin

if count < size then begin

with bufл[count] do begin

Figlndex := listA. index; N2 := index;

      desc := flag;

      next := M_EMPTY;

if (node".______ desc <> kNotMove) and

(node*. N2 = index) then begin

{ взяли только ходившую фигуру)

      next := lastEatList;

lastEatList := count;

if    next = M_EMPTY then

pLastEatList := @________ next;

end else begin

[остальные взятия} listNumber := codeEatF;

      next := eatList[listNumber];

eatList[listNumber] := count; if next = M_EMPTY then

pEatList[listNumber] := @________ ^next;

end; end;[with}

inc(count); end;

end;

{/////////////////////////////////////} VAR

opColor,del:integer; BEGIN

(инициализируем списки} lastEatList := M_EMPTY; pLastEatList := @lastEatList; for n := 0 to 6 do begin

eatList[n] := M_EMPTY; pEatList[n] := @eatList[n]; end;

firstMove := M_EMPTY; {нет пока перемещений} countMoves := 0; count := 0;

{инициализируем переменные в зависимости от того, верхние ли наши фигуры или нижние} if(color = glUpFColor) then begin

list := glUpFList; delPawn := 16; end else begin

list := glBotFList; delPawn := -16; end;

if color = CBLACK then opColor := CWHITE else opColor := CBLACK; while (list <> NIL) do begin

f := glPos [list*4.  N] ;

if f <> listA. F then

begin

list := list74.__ next;

continue;

end;

{ /////case//// } case (f and CFIGURE) of PAWN: begin

{/////////PAWN/////////////////////} {на клетку вперед}

index := list*4.____ N + delPawn;

if(glPos[index] = 0) then begin

{добавим в список}

if pawnlnQueen[index shr 4] <> 0 then {пешка в ферзи}

AddEatMove(QUEEN,kPromote);

end;

{взятия}

index := lisf4._____ N + delPawn + 1;

tmp := glPos[index];

if (tmp and CCOLOR) = opColor then

begin

if pawnlnQueen[ index shr 4 ] <> 0 then {пешка в ферзи}

AddEatMove(QUEEN,kPromote+kCapture)

else

AddEatMove(tmp and CFIGURE, kCapture);

end;

index := listA._ N + delPawn – 1;

tmp := glPos[index];

if (tmp and CCOLOR) = opColor then

begin

if pawnlnQueen[ index shr 4 ] <> 0 then {пешка в ферзи}

AddEatMove(QUEEN,kPromote+kCapture) else

AddEatMove(tmp and CFIGURE, kCapture);

end;

{взятие через битое поле}

if(node*.__ desc and kFIrstPawn) <> 0 then

begin

if (node’4.___ N2+1) = list*4.  N then begin

index := listA._____ N + delPawn – 1;

AddEatMove(PAWN,kEnPassant);

end;

if (nodeA.__ N2-1) = listA.     N then begin

index := listA._____ N + delPawn + 1;

AddEatMove(PAWN,kEnPassant);

end; end;

{/////////PAWN/////////////////////} end; {PAWN}

else begin {все фигуры, кроме пешек} {получим строку приращений при движении} п := 0; {индекс приращения} pAdd := glAdd [ f and CFIGURE ]; del := pAddA[n]; while del <> 0 do begin

index := list*. N + del;

{линия}

if siitpleF[ f and CFIGURE ] = 0 then

while glPos[index] = 0 do inc(index,del); {здесь, возможно, не взятие в любом случае, ненулевая клетка

}

eatF := glPos[index];

if (eatF and CCOLOR) = opColor then

begin

(добавим взятие}

AddEatMove(eatF and CFIGURE, kCapture);

end;

inc(n);

del := pAdd’4 [n] ; end; (while} end;{все фигуры} end; {case}

{ /////case//// }

list := listA.__ next;

end;{while}

{собираем подсписки} for n := PAWN-1 downto KING do

pEatList[n]л := eatList[n+1]; pLastEatList" := eatList[KING]; firstMove := lastEatList; countMoves := count; END;{function}

Данный код требует некоторого пояснения. Перемещения пешек берутся отдельно, так как это нестандартные ходы. Перемещения всех других фигур берутся сразу для всех фигур. По коду фигуры вычисляется адрес начала строки приращений. Массив simpieF содержит 1 в ячейке, соответствующей коду фигуры, для которой не нужно строить линию: конь или король. Обра­тите внимание, что объем кода для такой нетривиальной задачи, как взятие и сортировка перемещений, совсем небольшой. Найденные взятия вносятся в свой подсписок по коду съеденной фигуры. Вносятся в начало списка. Так как списки фигур идут по убыванию веса фигуры, а внесение в начало списка инвертирует порядок, происходит правильная сортировка. Фигуры в списке фигур расположены: King, Queen, Rook. Взятия в подсписке ферзя: Pawn, Bishop, Rook. Взятия, бьющие последнюю сходившую фигуру про­тивника, имеют высший приоритет. Они вносятся в особый список, списки можно потом соединить. Сортировка взятий выполняется практически без накладных расходов.

Рассмотрим в качестве примера еще функцию, генерирующую простые пе­ремещения. Она еще более компактна. В ней не выполняются никакие сор­тировки, так как это учебный пример. В реальной программе можно вести три подсписка по приращению стратегической оценки:

1.    Приращение меньше 0.

2.    Небольшое приращение (разумное значение).

3.    Лучшие ходы.

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

(только ходы без приращения материальной оценки}

PROCEDURE GenerteNotCaptures( color:integer; {цвет фигур}

node:PMove; {ход в эту позицию} buf:PMoveArray; {стековый буфер } size:integer; {сколько TMove в буфере} {номер первого элемента списка в буфере} var firstMove:integer; var countMoves:integer {сколько перемещений} ) ;

const simpleF:array[0..6] of byte = (0,1,0,0,0,1,0); const pawnlnQueen:array[0..15] of byte = (0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0);

{стартовые горизонтали пешек} const pawnStartY:array[0..15] of byte = (0,0,0,0, 0,1,0,0,0,0,1,0, 0,0,0,0); LABEL done ; VAR

list:PPiece;    {список наших фигур}

count:integer; {сколько описателей перемещений использовано}

{список взятий, бьющих последнюю ходившую фигуру}

{списки остальных ходов}

noEat:byte;

pNoEat:PByte;

n:integer;

f:integer; {фигура, чьи перемещения берем} pAdd:PIntArray; {строка перемещений} index:integer; {куда фигура переместилась} delPawn:integer; {приращение при движении пешки} tmp:integer;

canBeLeftCastl,canBeRightCastl:boolean; fN:integer;

VAR

noEatMove:TMove; (шаблон описателя перемещения} del:integer; isSimpleFig:boolean; BEGIN

(указатель на начало списка – вставка в конец} noEat := M_EMPTY; pNoEat := @noEat;

(шаблон наиболее распространенного хода}

noEatMove._ desc := kNormal;

noEatMove._ next := M_EMPTY;

firstMove := M_EMPTY; {нет пока перемещений} countMoves := 0; count : = 0 ;

{инициализируем переменные в зависимости от того, верхние ли наши фигуры или нижние} if(color = glUpFColor) then begin

list := glUpFList; delPawn := 16; end else begin

list := glBotFList; delPawn := -16; end;

while (list <> NIL) do begin

fN := list".__ N;

f := glPos[fN];

if f <> list"._ F then

begin

list := listA._____ next;

continue;

end;

noEatMove._ Figlndex := listA.  index;

{ /////case//// } case (f and CFIGURE) of PAWN: begin

{/////////PAWN/////////////////////} {на клетку вперед} index := fN + delPawn; if(glPos[index] = 0) then

begin

{добавим в список}

if pawnlnQueen[index shr 4 ] =0 then begin {пешка не в ферзи}

{////// добавим в конец списка ////} with buf"[count] do begin

      data := noEatMove. data;

      N2 := index;

pNoEatA := count;

pNoEat := @________ next;

end;

inc(count); {/////// end ///////////////////} end;

if pawnStartY[fN shr 4] <> 0 then begin

{если первый ход пешки} inc(index,delPawn); if(glPos[ index ] = 0) then begin {ход пешки через клетку} {////// добавим в конец списка ////} with buf4 [count] do begin

      data := noEatMove._ data;

      N2 := index;

      desc := kFIrstPawn;

pNoEat* := count;

pNoEat := @________ next;

end;

inc(count); {/////// end ///////////////////} end;

end;

end;

[/////////РРШ/////////////////////} end; {PAWN} else begin {все фигуры, кроме пешек}

isSimpleFig := simpleF[ f and CFIGURE ] <> 0; {получим строку приращений при движении} п := 0; {индекс приращения} pAdd := glAdd [ f and CFIGURE ]; del := pAdd’4 [n];

while del <> 0 do begin

index := fN + del; {линия}

while glPos[index] = 0 do begin

{свободная клетка – добавляем не взятие} {…}

{////// добавим в список ////} with bufA[count] do begin

      data := noEatMove._____ data;

      N2 := index;

pNoEaf4 := count;

pNoEat := @____________ next;

end;

inc(count); {/////// end ///////////////////} {///// end add no eat ///////} {если король или конь – линию не строим} if (isSimpleFig) then break; inc(index,del); {следующая клетка доски} end; inc(n);

del := pAddA[n];

if count > size-10 then goto done; end; {while} end;{все фигуры} end; {case}

{ /////case//// }

{если перемещения короля, и он не перемещался ранее} if ( (f and CFIGURE) = KING ) and

( (f and CMOVE) = 0 ) then begin

{рокировки} {левая рокировка} canBeLeftCastl := false; canBeRightCastl := false; n := fN;

if (glPos[n-1] = 0) and (glPos[n-2] = 0) and (glPos[n-3] = 0) and

((glPos[n-4] and CFIGURE) = ROOK) and ((glPos[n-4] and CMOVE) = 0) then canBeLeftCastl := true; {правая рокировка} if (glPos[n+1] = 0) and (glPos[n+2] = 0) and

((glPos[n+3] and CFIGURE) = ROOK) and ((glPos[n+3] and CMOVE) = 0) then canBeRightCastl := true; if canBeLeftCastl or canBeRightCastl then begin

if (node*4. desc = kNotMove) or

not InCheck(glPos[nodeA.  N2],

node’4._________ N2,

fN) then

begin

if canBeLeftCastl then begin index := fN – 2;

{////// добавим в конец списка ////} with bufл[count] do begin

I

      data := noEatMove.__ data;

      N2 := index;

      desc := kLeftCastling;

pNoEat^ := count;

pNoEat := @_________ next;

end;

inc(count); {/////// end ///////////////////}

end;

if canBeRightCastl then begin index := fN + 2;

{////// добавим в конец списка ////} with bufл[count] do begin

      data := noEatMove.__ data;

      N2 := index;

      desc := kRightCastling;

pNoEat^ := count;

pNoEat := @_________ next;

end;

inc(count);

{/////// end ///////////////////}

end; end; end;

end; {рокировки}

if count > size-10 then break;

list := list74. next;

end;{while} done:

firstMove := noEat; countMoves := count; END;{function}

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

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

Рассмотрим для данной схемы функции, делающие ход и восстанавливаю­щие позицию. Нужно учесть, что они должны выполняться только перед переходом в следующую позицию (MakeMove), поэтому страшного ничего нет. Если мы будем создавать развернутый описатель перемещения в гене­раторе ходов, будет значительно хуже, так как большая часть перемещений, как правило, не используется. Функция MakeMove при выполнении заполняет поля структуры tagMove. Они содержат всю информацию, необходимую для восстановления позиции функцией UnMakeMove. Вот эти функции и сама структура tagMove:

PTagMove = ^TagMove; TTagMove = record

N1,N2, {откуда и куда пошла}

F,    {фигура}

newF, {значение на новом месте}

eatF, {взятая фигура}

NEatF, {координата взятой фигуры}

desc: {описатель перемещения}

integer;

Figl,Fig2:PPiece; {элементы списка фигур: первый основной,

второй вспомогательный для рокировки} Nll,N12,Fll,newFll:integer; {откудаи куда пошла ладья при рокировке}

end;

PROCEDURE MakeMove(move: PMove; {описатель перемещения}

tag: PTagMove{вспомогательная структура} ) ;

VAR

p:PPiece;

BEGIN

with tagA do begin

Figl := @glFigBuf[ move~. Figlndex ]; {элемент списка фигур}

N1 := Figl".____ N;        {стартовая координата}

N2 := move".____ N2;      {куда пошла}

F := glPos[Nl];           {фигура на старом месте}

newF := glPos[Nl] or CMOVE; {фигура на новом месте} NEatF := N2;    {координаты фигуры}

eatF := glPos[NEatF];     {взятая фигура}

desc : = move’4._ desc;    {тип перемещения}

{если превращение пешки} if (desc and kPromote) о 0 then

newF := ( glNewF or (newF and (not CFIGURE)) ) or C_NEW_F; {если пешка взяла через битое поле} if (desc and kEnPassant) <> 0 then begin

{координата фигуры не совпадает} if (F and CCOLOR) = glUpFColor then

dec(NEatF, 16) else inc(NEatF, 16); eatF := glPos[NEatF]; end;

{выполним перемещение} glPos[Nl] := 0; glPos[NEatF] := 0; glPos[N2] := newF; {изменение в списке фигур}

FiglA .___ N := N2;

ГСд1Л. F := newF;

{если рокировка – перемещаем ладью}

if (desc and (kLeftCastling+kRightCastling)) о 0 then begin

{находим координату ладьи}

if (desc and kLeftCastling) <> 0 then

begin

N11 := N1-4; {коор. ладьи}

N12 := N11+3; end else begin

N11 := N1+3; {коор. ладьи}

N12 : = N11-2; end;

{находим элемент списка фигур ладьи} if (F and CCOLOR) = glUpFColor then

p := glUpFList else

p := glBotFList; while (p <> NIL)  and

Л.   N О N11) do

begin

p := рл.________ next;

end;

Fig2 := p;{если p – 0 то !!!} Fll := glPos[Nil]; newFll := Fll or CMOVE; glPos[Nil] := 0; glPos[N12] := newFll;

Fig2A. N := N12;

Fig2A. F := newFll;

end; end; END;

{восстанавливает перемещение} PROCEDURE UnMakeMove(tag:PTagMove); BEGIN

with tag’4 do begin glPos[N2] := 0;

glPos[NEatF] := eatF; glPos [Nl]     := F;

Figl^. N__ := N1;

Figl". F__ := F;

if (desc and (kLeftCastling+kRightCastling)) <> 0 then begin

glPos[N12] := 0; glPos[Nil] := Fll;

Fig2~. N := N11;

Е1д2Л. F := Fll;

end; end;

END;

Позиция 16 x 16 во всех функциях содержится в glPos. Данный пример яв­ляется учебным, но код вполне работоспособен. Основная польза его мне видится в том, что при написании своей программы желательно отталки­ваться от каких-то идей, а не начинать с нуля. Эффективная генерация пе­ремещений в шахматах — сложная задача и не имеет одного решения.

В реальной программе потребуется еще функция, генерирующая сразу все перемещения: и взятия, и не взятия. Ее можно написать, просто объединив эти две функции. Все зависит от конкретной реализации. Хочется обратить внимание на один тонкий момент, связанный с использованием списков фигур. Если фигуры нет на доске (например, коня), то пустой элемент спи­ска фигур может случайно указать на другого коня, и перемещения для ос­тавшегося коня будут сгенерированы два раза. Чтобы это избежать, можно при инициализации позиции для парных фигур использовать дополнитель­ный бит флага. У нас остался свободным бит 5, который и можно использо­вать для этой цели. Вот пример стартовой позиции в игре с учетом бита флага парности фигур:

const glStartPos:array[0..7][0..7] of byte = (

(ROOK+CBLACK+32,KNIGHT+CBLACK+32,BISHOP+CBLACK+32,QUEEN+CBLACK+32,KING+CB LACK,BISHOP+CBLACK,KNIGHT+CBLACK,ROOK+CBLACK),

(PAWN+CBLACK+32,PAWN+CBLACK+32,PAWN+CBLACK+32,PAWN+CBLACK+32,PAWN+CBLACK, PAWN+CBLACK,PAWN+CBLACK,PAWN+CBLACK),

(0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0), (0,0,0,0,0,0,0,0),

(PAWN+CWHITE+32,PAWN+CWHITE+32,PAWN+CWHITE+32,PAWN+CWHITE+32,PAWN+CWHITE, PAWN+CWHITE,PAWN+CWHITE,PAWN+CWHITE),

(ROOK+CWHITE+32,KNIGHT+CWHITE+32,BISHOP+CWHITE+32,QUEEN+CWHITE+32,KING+CW HITE,BISHOP+CWHITE,KNIGHT+CWHITE,ROOK+CWHITE)

) ;

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

Литература:

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

По теме:

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