"YSS 7.0": Структуры данных и алгоритм

Японский исходник: 1997 5/29
Впервые эта статья была опубликована под названием "Computer Shogi no Shinpo2" в Японии, 20 мая 1998 г. (Редактор и автор - Хитоси Мацубара, ISBN4-320-02892-9\2300)
Хироси Ямасита (программист сёги)
E-mail: cxj00674@nifty.ne.jp

В 1987 году я заинтересовался программированием сёги (японских шахмат). Я нашёл "ESS" в букинистическом магазине. "ESS" (Система Сёги с Электронным мозгом, "Electro-brains Shogi System") была напечатана в журнале "MICRO" за 1984 год. В это же время я начал создавать программу сёги "YSS" (Система Сёги Ямасита)". И я (YSS 2.0) принимал участие во втором чемпионате компьютерных сёги в 1991 году, а также, непрерывно, во всех последующих чемпионатах. Места, которые я занимал: 5, 4, 4, 3 и 4, начиная со второго чемпионата. Наконец, "YSS 7.0" победила в 7-м чемпионате в феврале 1997 года. А "Канадзава Сёги", непрерывно побеждавшая до этого четыре раза, - проиграла.

Я объясняю алгоритм поиска и вычислительные функции "YSS 7.0". Эта программа продавалась под названием "AI Shogi 2" в Японии через компанию "Ascii Something Good" в апреле 1997 г.



1. Структуры данных

2. Генератор хода
2.1 Классификация ходов
2.2 Вычисление промежуточного хода
2.3 Последовательности генерации ходов
2.4 Генерация пустого хода и "хода сожаления"
2.5 Ход-убийца

3. Оценочная функция
3.1 Суждение о дебюте, миттельшпиле и эндшпиле
3.2 Стоимость фигур
3.3 Построение замка в дебюте
3.4 Миттельшпиль и эндшпиль
3.5 Вычисление конечного узла

4. Алгоритм поиска
4.1 Расширение на полшага
4.2 Таблица подстановок
4.3 Два типа Эффекта горизонта
4.4 Повторение ходов прорыва (последовательные шахи)

5. Матовые задачи (Цумэ-сёги)
5.1 Матовые задачи
5.2 Хисси

6. Приложение: запись игры

7. Решение уравнений сёги

8. Эпилог

1. Структуры данных.

Чтобы научить компьютер играть в сёги, необходимо по меньшей мере выучить правила сёги. Первый уровень структур данных важен потому, что его влияние на дальнейшее программирование доминирующе. Я изменял основную структуру данных трижды. Наконец, я стал использовать Номер Фигуры. Все программы написаны на языке Си, с ходами для Windows NT. Основная структура данных в YSS такова. Все 40 фигур пронумерованы числами от 1 до 40. Чёрный король - 1. Белый король - 2. Ладьи 3-4, слоны 5-6, золотые 7-10, серебряные 11-14, кони 15-18, стрелки 19-22, и пешки 23-40. Позиция и статус (чёрная или белая, перевёрнута или нет) поддерживаются для каждой фигуры. На реальной доске сёги, правый верхний угол имеет координаты (1,1), а левый нижний - (9,9). Но эта координатная система для компьютера плоха. Поэтому я использую такие координаты: левый верхний угол - (1,1), а правый нижний - (9,9). Настоящие пешки 77-76 превращаются в пешки 37-36, координата X - обращается. Размер доски сёги - 9*9. Поэтому легко использовать двумерный массив 9*9. Но я, для быстродействия, использую одномерный массив board[256]. Позиция, соответствующая координатам (x,y) при этом равна y*16+x. Пример: пешка 76 - это пешка 36; x=3, y=6, и поэтому z = y*16+x = 0x63 (на языке Си). Элемент Board[0x63] содержит номер фигуры, стоящей на этом квадрате. Для описания границы доски я использую рамку, окружающую доску. Поэтому в программе размер доски равен 11*11. Когда создаётся таблица Кики (показывающая места, на которые каждая из фигур может походить), в дополнительных суждениях необходимости нет.

Примечание. Кики () - область действия (яп.)

Таблица 1 - Тип чёрных фигур с их номером.

P L N S G B R K +P +L +N +S +G +B +R
1 2 3 4 5 6 7 8  9 10 11 12  - 14 15
Когда чёрная фигура переворачивается, к её номеру прибавляется 8. К номеру белой фигуры вдобавок прибавляется 0x80(=128). К примеру, белый дракон имеет номер 0x8f(= 128+7+8). Не думали ли Вы, что фигуры сёги удобно обозначать в гексадецимальной нотации?
Начальные данные доски таковы: 0xff - это код рамки, окружающей доску.

int board[256]= {
0xff, 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, 0xff,0,0,0,0,0,

0xff, 0x82,0x83,0x84,0x85,0x88,0x85,0x84,0x83,0x82, 0xff,0,0,0,0,0,
0xff, 0x00,0x87,0x00,0x00,0x00,0x00,0x00,0x86,0x00, 0xff,0,0,0,0,0,
0xff, 0x81,0x81,0x81,0x81,0x81,0x81,0x81,0x81,0x81, 0xff,0,0,0,0,0,
0xff, 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, 0xff,0,0,0,0,0,
0xff, 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, 0xff,0,0,0,0,0,
0xff, 0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00, 0xff,0,0,0,0,0,
0xff, 0x01,0x01,0x01,0x01,0x01,0x01,0x01,0x01,0x01, 0xff,0,0,0,0,0,
0xff, 0x00,0x06,0x00,0x00,0x00,0x00,0x00,0x07,0x00, 0xff,0,0,0,0,0,
0xff, 0x02,0x03,0x04,0x05,0x08,0x05,0x04,0x03,0x02, 0xff,0,0,0,0,0,

0xff, 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff, 0xff,0,0,0,0,0};

Номер фигуры (1-40), которая уходит с доски, укладывается в стек, в соответствии с её типом. Когда сбрасывается фигура из руки, программа достаёт её номер из стека. К примеру, когда чёрные на (1) сбрасывают пешку на поле 47, то всего на доске нет пешек: 4 шт. (всего пешек 18)

/* Содержимое стека */

PN_stack[1][0] = 0 /* не используется */
PN_stack[1][1] = 25
PN_stack[1][2] = 33
PN_stack[1][3] = 36
PN_stack[1][4] = 27; количество не задействованных пешек = 4.

PN_stack_number[1] = *PN_stack[1][4] (указатель)
PN[27][0] = 0x01 фигура номер 27 - чёрная пешка.
PN[27][1] = 0x76 Её позиция - 0x76 (пешка номер 47)
PN_stack_number[1] - уменьшение стека, [1] - пешка,[2] - стрелка.

Таблица 2. Главный массив данных в YSS (всё - в int.)

board[256] содержит номера фигур.
init_board[256] Типы фигур (пусто - 0, граничная рамка - 0xff, чёрные - 0x01-0x0f, белые - 0x81-0x8f)
Hand_Black[8] Номера в руке чёрных
Hand_White[8] "-" белых
Kiki_Black[256] Число Кики у чёрных
Kiki_White[256] "-" у белых
KikiC_B[256][32] Содержимое Кики чёрных (какой тип фигуры?). Максимальное число Кики = 18.
KikiC_W[256][32] "-" белых
PN[41][2] номер фигуры ([][0] - тип фигуры, [][1] - позиция фигуры.)
PN_stack[8][32] Номера отсутствующих фигур.
*PN_stack_numbe[8] Указатель на номера отсутствующих фигур.
move[64][64][8] Ход каждого уровня. (глубина - 64 уровня, 64 хода в одну глубину, 8 - содержимое хода, и т.д.)
best[64][64][4] лучшая последовательность. Максимальная глубина = 64.
(4 - содержимое хода. "До", "После", "Переворот", "Флаг Переворота".)
ret_depth[64] глубина вызова вычисляющей функции.
depth_add Десятичная часть максимальной глубины.
depth_max максимальная глубина.
*MoveP[64] Указатель хода в каждую глубину. (Он указывает на move[64][64][8].)

В языке Си внутренние вычисления осуществляются битовыми сдвигами, когда Вы используете массив размера 2^n ( к примеру, [53][64], или [3][16][256]). Поэтому, ради скорости, следует использовать массивы размером 2^n .
(1): объяснение Кики.

Есть два типа Кики: косвенное Кики и прямое Кики. Прямое Кики - это место, на которое фигура может реально походить. В непрямом Кики фигура не может походить реально. Но, когда продолжаются размены, непрямое Кики становится эффективно. К примеру, на (1) у поля 86 есть непрямое Кики ладьи 82. В виде исключения, Кики для дальнобойщиков проходит сквозь короля противника на один шаг. Это полезно для суждений о матовании короля. На (1) Кики чёрного слона на 44 проходит сквозь короля противника (33) и достигает поля 22. Вдобавок, на (1), когда серебро (62) ходит на 71, Кики слона (44) эффективно на 71.Это называется теневым Кики. Но в YSS теневого Кики нет.

KikiC_B[256][32] содержит номера чёрных фигур, которые могут пойти на данное поле (прямое или непрямое). К примеру, на (1) у белых поле 86 имеет Кики пешки (85) (её номер - 26), стрелки (83) (её номер - 19) и ладьи (82) (её номер - 3).

Kiki_White[0x62] = 3; номер Кики белых.
KikiC_W[0x62][0] = 26; пешка номер 26 работает.
KikiC_W[0x62][1] = 3 + 0x80; ладья номер 3 работает
(0x80 добавлено потому, что это косвенное Кики).
KikiC_W[0x62][2] = 19 + 0x80; стрелка номер 19 работает (0x80 добавлено потому, что это косвенное Кики).


Когда фигура ходит, эти структуры данных обновляются лишь частично, лишь в местах изменений. Когда серебро (39) ходит на 38, все Кики серебра (39) удаляются. А все для серебра (38) - записываются. В данном случае, правое Кики ладьи (88) останавливается серебром (38). Поэтому удаляется и записывается лишь правое Кики ладьи. Кроме этого, одновременно обновляются данные хэш-кода (перестановок) и основная ценность фигур. В таблице (2) показаны основные структуры данных в YSS. Из-за того, что я делю все данные между белыми и чёрными, в программу встроены особые процедуры "генератор хода" для чёрных и для белых. К примеру, есть две процедуры, которые ищут вилки слоном. Это, по сути, бесполезно, но когда речь идёт о скорости, то так проще.

2. Генератор хода.


2.1 Классификация ходов.


Сперва YSS делит все ходы на "атакующие" и "защитные".
"Атакующие" - это 3 следующих типа:
Взятие фигуры противника - Переворот - Угроза взятия (включая вилки).
"Защитные" - следующие 6:
- Взятие фигуры, которая угрожает моей фигуре
- Сброс моей фигуры туда, куда хочет сбросить противник (когда его сброс хорош)
- Угроза полю, на которое хочет походить его фигура
- Убегание фигуры, которой угрожают
- Вставка, когда ход дальнобойщика (ладьи, слона или стрелки) противника хорош
- Вставка, когда угрожает вражеский дальнобойщик.


Из этих шести, лишь при убегании я реально хожу фигурой на доске с вычислением стоимости фигуры, и выбираю лучшие 3 или 5 ходов (R,B - 5; G,S - 4), когда (depth_max - depth) >= 3 . Во всех других случаях я вычисляю ходы без реальных ходов на доске (производя лишь временные вычисления). При вилке ход, которым атакуемая фигура убегает, защищая другую фигуру, может быть найден реальным ходом за один шаг.

2.2 Вычисление промежуточного хода.


Вычисление промежуточного хода происходит методом минимакса, с учётом числа своих угроз и угроз противника на предполагаемое поле хода.
(1): объяснение взятия пешки (85) (показывается ещё раз)

Для примера, я объясню ценность взятия пешки 85 на (1). Первоначальная ценность фигур присваивается таблицей 3. Далее, размен фигур производится последовательно, от фигуры наименьшей стоимости к наибольшей. На (1) чёрные фигуры, "глядящие" на поле 85 - это конь, серебро, слон и ладья в такой последовательности. У белых - стрелка, золото и ладья. (На (2), когда в размене участвуют белые ладья и стрелка, стрелка не может идти на поле 85 первой. Но моя программа это не рассматривает.) Здесь у чёрных есть выбор - брать или нет пешку (85) первыми. Если чёрные возьмут её конём, то у белых тоже будет выбор: брать или нет чёрного коня стрелкой.

(2)

Так создаётся дерево (2). В нём у чёрных - max, у белых - min, взятие ведёт влево, не взятие - вправо. Сначала, если чёрные не берут пешку на 85, то их очки, конечно же, равны 0. Когда чёрные берут, то (если белые не берут) их очки равны +200 (стоимость пешки взята из таблицы 3). Если же белые тоже берут, а чёрные далее не берут, то очки белых равны +700. (конь за пешку) Так создаётся дерево минимакса, после которого ценность взятия пешки на (85) получается равной +100. Я использую эту ценность для добавления фиксированных ценностей доске и т.д.

Таблица 3: ценность фигур.
                       P    L    K    S    G    B    R  K 
Основная ценность     100  430  450  640  690  890 1040 -
Ценность переворота   320  200  190   30    -  260  260
Добавление в руку (1)  15   50   60   80   90  220  230
Ценность размена;     200  860  900 1280 1380 1780 2080
Размена с переворотом 520 1060 1090 1310   -  2040 2340 

Примечания: Ценность размена = Основная ценность * 2;
Ценность размена с переворотом = Основная ценность * 2 + Ценность переворота.

2.3 Последовательности генерации ходов.


При глубине поиска N, генерация последовательности ходов такова:

Если (depth_max - depth) = 1, то генерируются следующие ходы:
- Взятие фигуры противника, ходившей только что.
- Взятие фигур противника (если оно эффективно)
- Переворот
- "Ход сожаления" (объясняется в п.2.4)
- Эффективный шах (когда размен фигур эффективен)
- Убегание самой ценной из фигур под угрозой, если такие есть (убегание другими не рассматривается)

Если (depth_max - depth) = 2, то генерируются следующие ходы:
- Создание угрозы (включая вилки)
- Открытый шах.
- Сброс золота и серебра прямо перед королём противника.
- Ход, открывающий угрозу.
- Угроза прикалыванием (приколотая фигура не может ходить. Если она походит, король (или другая фигура) будет взят дальнобойщиком. )
- Сброс ладьи и слона в лагерь противника

Если (depth_max - depth) = 3, то генерируются следующие ходы:
- Дикие сбросы вокруг короля противника (сбросы на поля, у которых много своих и чужих Кики)
- Отгоняющие ходы (шахи с жертвой. Если король возьмёт, то будет взят его защитник)
- Взятие S, G, B и R, даже если оно неэффективно)

Если depth = 2, то генерируются следующие ходы:
- Ход пешкой перед ладьёй или стрелкой
- Жертвы и сбросы. (Если, в случае взятия, появятся эффективные взятие или вилка)
- Висячая пешка (сброс пешки за поле до цели с угрозой переворота)
- Удар (сброс пешки прямо перед вражеской фигурой)
- Жертва пешки с переворотом
- Вставка (против вражеских R и B)
- Движение токина или любой перевёрнутой фигуры во вражеском лагере вбок, в сторону короля противника
- Сброс пешки перед только что походившей фигурой
- Угроза только что походившей фигуре. Или ход генералом перед только что походившей фигурой
- Ход королём.

Если depth = 2 в дебюте, то генерируются следующие ходы:
- Угрожающая пешка
- Авангардная пешка
- Случайный ход (исключая сбросы)

Если depth = 1, то генерируются следующие ходы:
- Случайный ход (исключая сбросы)
- Шах (без рассмотрения получаемой выгоды)
- Случайный сброс пешки (до 15)

У всех подпроцедур, генерирующих ходы, есть верхняя граница числа ходов. Ходы выбираются из тех, которые важны. Верхняя же граница их числа зависит от остающейся глубины поиска (глубина = число ходов в японской нотации: каждый ход каждого игрока считается за один - Д.К.). Программа не рассматривает вилки, если остаётся лишь один уровень глубины поиска. Вилки рассматриваются лишь от двух уровней. К примеру, вилка на короля и ладью ("Оотэ-хися-тори") слоном требует 2 уровня. Это: сброс слона и убегание короля. Вы можете подумать, что ход, когда слон берёт ладью, требует третьего уровня? Да. Но практически, вместо него это делает процедура вычисления размена в конечном узле. (Конечно же, уверенности в этом нет.)

Вкратце, ход следует рассматривать, лишь если остаётся достаточно глубины поиска для рассмотрения того, достигнет ли этот ход цели Подпроцедура ходов-угроз особо тщательна в генерации всех ходов. В YSS, когда остающаяся глубина поиска более трёх уровней, создаются лишь 5 сильнейших ходов-угроз. Однако иногда ходы-угрозы могут производиться 10-20 ходов подряд. Поэтому важна последовательность рассмотрения. В YSS она такова:
- Вилка, создаваемая фигурой L, N, S, G, B и R. Ходу на доске отдаётся приоритет перед сбросом.
- Ход-угроза (от R до L). Приоритет хода на доске также выше, чем у сброса.
Исключения: сброс генералов для угрозы ладье или слону по приоритету ниже. А сброс пешки - выше.

YSS не сортирует ходы. Последовательность ходов и последовательность генераций идентичны. После генерации YSS лишь уничтожает некоторые ходы. (Однако, последний наилучший ход ставится первым.) В миттельшпиле и эндшпиле среднее число генерирующихся ходов - 80 (глубина = 1), 40 (глубина = 2),
20 (глубина = 3), 6-13 (глубина >= 4). Верхней границы в целом нет. При итеративном углублении, если оно занимает в 6 раз больше времени, YSS может рассматривать на один уровень поиска больше.

2.4 Генерация нулевого хода и "хода сожаления".


Генерация "хода сожаления" происходит в целях генерации защиты. Если, при выборе защитного хода, серебро будет захвачено даром, то Вы легко можете найти, как его защитить. К примеру, создав бой поля, на котором это серебро стоит, или же убежав этим серебром. Но, если при этом эффективна жертва ладьи противника (если ладья будет взята - то королю мат!), то Вам нелегко найти защиту. Одноуровневый поиск не может найти жертву ладьи. Другими словами, если Вы видите лишь позицию (но не поиск), то не можете найти защитных ходов.
Один из методов решения этой задачи - "ход сожаления". Сначала программа делает пас (то есть, нулевой ход) и смотрит на лучший (наиболее эффективный) ход противника. Далее программа генерирует ходы, защищающие от него. В действительности, программа делает пас и смотрит на лучшую последовательность. И, из этой последовательности генерируются свои ходы, а также ходы, защищающие от ходов противника из неё. На (3) показан пример. Ход чёрных.

(3)

Если в этой позиции чёрные пасуют, то белые ходят пешкой (54), чёрный слон убегает, и ладья (76) берёт коня (77). Если в этой позиции слон (55) отсутствует, то Вы найдёте, что конь (77) будет следующим ходом взят. Поэтому Вы можете легко найти угрозу полю 77: к примеру, S-78 или G-68. Здесь я предполагаю, что чёрные пасуют. В данном случае, лучшие ходы противника - P-54 ... Rx77+. Лучшей последовательностью будет: Пас, P-54, B-46, Rx77+, K-69. Из этой последовательности в генерируемый список добавляются ходы чёрных, а также их ходы, защищающие от ходов белых. В данном случае это ходы B-46 и K-69, а также - ход, защищающий от P-54 (в данном случае такого нет), и ход, защищающий от Rx77+: к примеру, S-78, G-68. Далее программа может найти защитные ходы, которые не обнаруживаются при одноуровневом поиске.

Замечание! Эти ходы могут оказаться невозможными на доске, если это не ходы, защищающие непосредственно от следующего хода. Поэтому все их необходимо жёстко проверять на нарушение правил. В реальном поиске YSS пасует во всех узлах кроме конечного, и получает лучшую последовательность. Из этой последовательности YSS не генерирует защиту от ходов противника глубины более 3. (в корневом узле генерируется всё.) Причина этого в том, что защитных ходов может оказаться слишком много, когда лучшая последовательность длинна (более 10 ходов). В этом у генерации хода сожаления тоже недостаток.<Сначала необходимо получить лучший ход противника, когда происходит пас. Значения альфа-бета следует установить на -бесконечность и +бесконечность. Поэтому достаточность поиска ухудшается (невозможно использовать идею Окна) Кроме того, лучший ход противника всегда может оказаться реально не лучшим, поскольку YSS использует значения альфа-бета, берущиеся из родительского узла без корневого узла. К примеру, обрыв альфа-бета модет произойти взятием ладьи (но в реальности существует одноходовый мат!). Поэтому программа сгенерирует ходы, защищающие от взятия ладьи - но не одноходовый мат. При использовании итеративного углубления, я думаю, эта ошибка уменьшается, но не полностью..

2.5 Ход-убийца.


Лучший ход противника, получающийся в результате пасования, становится идеальным ходом-убийцей. Однако сейчас я не использую ход-убийцу, поскольку необходимость в нём не столь велика чтобы запоминать все лучшие ходы позиций в большой хэш-таблице.

3. Оценочная функция.


3.1 Суждение о дебюте, миттельшпиле и эндшпиле.


Оценочная функция разделена в YSS на две (дебютная и миттельшпиль-эндшпильная) Перед началом поиска программа выносит суждение: является ли данная позиция дебютом, или же это миттельшпиль-эндшпиль (и во время поиска это суждение не изменяется). Стандарты суждения таковы:

- Сумма рук чёрных и белых (старше стрелки) более трёх фигур.
- Фигура, которая старше серебра (или перевёрнутая фигура) вторглась в лагерь противника (или в свой лагерь).
- Есть угроза (у себя или у противника) фигуре, старше стрелки.

Если три этих условия выполнены, выносится суждение, чтоэто миттельшпиль-эндшпиль. Однако, если с начала игры прошло менее 10 ходов, то это дебют.

Ценность фигур в YSS всегда постоянна. Однако в миттельшпиле-эндшпиле она может сильно расти и уменьшаться из-за позиции.

3.2 Ценность фигур.


Ценность фигур задаётся таблицей 3.
Таблица 3: ценность фигур (повторение).
                       P    L    K    S    G    B    R  K 
Основная ценность     100  430  450  640  690  890 1040 -
Ценность переворота   320  200  190   30    -  260  260
Добавление в руку (1)  15   50   60   80   90  220  230
Ценность размена;     200  860  900 1280 1380 1780 2080
Размена с переворотом 520 1060 1090 1310   -  2040 2340 

Примечания: Ценность размена = Основная ценность * 2;
Ценность размена с переворотом = Основная ценность * 2 + Ценность переворота.

Ценность размена используется при размене фигур. Она вдвое больше Основной ценности.
(ибо если фигура захватывается, то исчезает её ценность на доске, а у противника прибавляется её ценность в руке - отсюда и удвоение.)

Ценность размена с переворотом - это дважды основная ценность плюс ценность переворота (Почему - поймите сами!) "Добавление в руку" в таблице 3 показано для одной фигуры в руке. Если у Вас есть одно золото, добавляется 90. Если два золота, добавляется 90+40. Поэтому 1,2,3,4 - это 90,40,10,0. Захват фигур одного и того же типа менее ценен.

3.3 Построение замка в дебюте.


В дебюте ценность фигур постоянна. Добавочная ценность (чем ближе к центру доски или к королю противника, тем она выше) мала (менее 10% от ценности пешки). Основной стандарт её увеличения и уменьшения зависит от "Таблицы увеличения и уменьшения для построения замка" и "Авангардной пешки (курай)". В целом, YSS не использует дебютных книг. Поэтому дебюты YSS слабы. Но я думаю, что компьютеру не следует использовать сложные дебюты, которые он не в состоянии понять. Он не сможет играть по их завершении. YSS в дебютном построении замка использует "метод Западни" (так я его называю). YSS создаёт таблицу, в которой, если золото с серебром находятся в определённой позиции, то за это даётся +n очков. Если YSS хочет, чтобы фигуры ходили быстро, то разница в очках у полей увеличивается (???). Поэтому каждая фигура стремится ходить в порядке наибольшего увеличения ценности. И, в результате, получаются замки Ягура и Мино. YSS создаёт эту таблицу для всех фигур. Реально у YSS есть эти таблицы для дебютов "Ягура", "Статическая ладья с Анагумой", "Левое Мино", "Система Ямада (быстрая атака S-57)", "Воздушный Бой", "Смещённая ладья", "Смещённая ладья с Анагумой", "Замок для форы в 2 (или 4, или 6) фигур)", "нерешённый замок". То, какую таблицу YSS использует, определяется с помощью случая и по положению вражеской ладьи. Увеличение и уменьшение, по которому определяется значение реальной битвы, добавляется в эту таблицу "Западни". К примеру, чем ниже позиция стрелки, тем выше её ценность. Ценность коня, прыгнувшего на край доски, ниже. Ценность генералов в углу сильно ниже. Ценность ладьи на седьмой вертикали немного ниже. И т.д.

Курай. Дальнейшее говорится для чёрных. Курай - это пешка чёрных на 3, 4 и 5 горизонтали.
- Если пешка на 5-й горизонтали, а пешка противника - на 3-й, то очков +1. Если пешки противника нет, но моя пешка не защищена, то очков +2. Если защищена, то +15.
- Если пешка на 4-й горизонтали и далее может перевернуться (поле перед нею не бьётся противником), то у неё +100 очков. Если есть пешка противника на 2-й горизонтали, то +20. Если нет, то +40. Если пешка на 4-й горизонтали защищена, то ей добавляется +10 очков.
- Ценность пешки на 3-й горизонтали ниже, чем на 4-й.

Вкратце, если пешка на 3-й, 4-й или 5-й горизонтали, и нет пешки противника на 1-й, 2-й или 3-й горизонтали, то ценность пешки выше. Ценности других пешек таковы: если нет пешек на той же аертикали, на которой есть ладья, то +35. А если противник не защищает свою вертикаль пешкой, то +30. Если нет пешки перед королём, то -15, поскольку размен пешки перед королём при ягуре ухудшает положение.

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

3.4 Миттельшпиль и эндшпиль.


Оценочная функция в миттельшпиле и эндшпиле делится на три части: ценность фигур, безопасность короля, и увеличение / уменьшение ценности позиций фигур. Ценность фигур всегда постоянна. Элементы, подверженные большим изменениям - это безопасность короля и ценность позиции фигуры. Я не забочусь о том, чей ход - белых или чёрных. Позиции королей определяют рост и убывание позиций фигур. Если фигура ближе к чьему-либо королю, то её ценность выше. Если фигура удалена от обоих королей, то её ценность ниже. На таблице 4 показана ценность положения фигур белых по отношению к чёрному королю. Предполагается, что ценность фигуры равна 100. Если фигура будет стоить 50 то все ценности делятся пополам. Зона отрицательных значений X не приводится из-за симметрии. К примеру, если чёрный король сидит на поле 69, а белое золото на 37, то ценность его позиции равна 114 (X=3, Y=2). Поскольку ценность золота равна 690, ему добавляется (114-100)*(690/100)=+96 очков. Если же золото на поле 19, то X=5, Y=0, и ему добавляется (75-100)*(690/100)=-172 очка.

Таблица 4: ценность позиций чёрных фигур по отношению к белому королю (симметрична по оси X).

         0   1   2   3   4   5   6   7   8  (расстояние по оси X)
   +8   50  50  50  50  50  50  50  50  50
   +7   50  50  50  50  50  50  50  50  50
   +6   62  60  58  52  50  50  50  50  50
   +5   80  78  72  67  55  51  50  50  50
   +4  100  99  95  87  78  69  50  50  50
   +3  140 130 110 100  95  75  54  50  50
   +2  170 160 142 114  98  80  62  55  50:  Максимум - на две вертикали выше короля.
   +1  170 165 150 121  94  78  58  52  50
    0  170 145 137 115  91  75  57  50  50:  Это центр (чёрный король - на поле (0,0)).
   -1  132 132 129 102  84  71  51  50  50
   -2  100  97  95  85  70  62  50  50  50
   -3   90  85  80  68  60  53  50  50  50
   -4   70  66  62  55  52  50  50  50  50
   -5   54  53  51  50  50  50  50  50  50
   -6   50  50  50  50  50  50  50  50  50
   -7   50  50  50  50  50  50  50  50  50
   -8   50  50  50  50  50  50  50  50  50
(смещение по оси Y)


На таблице 5 показана ценность позиций чёрных фигур по отношению к ЧЁРНОМУ королю. Исключение: позиции пешек, коней и стрелок ниже, чем по таблице 5. Ценности коней и стрелок вычисляются с предположением, что они находятся на одну горизонталь выше (максимальная ценность позиций стрелок и коней - на три вертикали выше короля.) Окончательная ценность фигуры определяется, как максимальная из её ценностей по отношению к каждому из королей.

Таблица 5: ценность позиций чёрных фигур по отношению к чёрному королю (симметрична по оси X).

         0   1   2   3   4   5   6   7   8  (расстояние по оси X)
   +8   50  50  50  50  50  50  50  50  50
   +7   56  53  50  50  50  50  50  50  50
   +6   64  61  55  50  50  50  50  50  50
   +5   79  77  70  65  54  51  50  50  50
   +4  100  99  95  87  74  58  50  50  50
   +3  116 117 101  95  88  67  54  50  50
   +2  131 129 124 114  90  71  59  51  50
   +1  137 138 132 116  96  76  61  53  50
    0  142 142 136 118  98  79  64  52  50:  Это центр.
   -1  132 132 129 109  95  75  60  51  50
   -2  121 120 105  97  84  66  54  50  50
   -3   95  93  89  75  68  58  51  50  50
   -4   79  76  69  60  53  50  50  50  50
   -5   64  61  55  51  50  50  50  50  50
   -6   56  52  50  50  50  50  50  50  50
   -7   50  50  50  50  50  50  50  50  50
   -8   50  50  50  50  50  50  50  50  50
(смещение по оси Y)


В результате получается такая диаграмма 5.

Диаграмма 5: добавочная позиционная ценность золота.

Эта диаграмма показывает ценность позиций чёрного золота. Она добавляется радом с королями, и особенно сильно растёт в верхней части, рядом с белым королём. (Это создаёт ощущение сдерживания короля противника.) При одноуровневом поиске программа выберет атаку сбросом золота на два поля выше короля противника, вместо защитного сброса рядом со своим королём. В отношении драконов: если их позиция выше, то ценность возрастает. Но если их позиция ниже, то ценность позиции не добавляется. У старших фигур (R и B) возможности движения велики. Поэтому если они далеки от поля боя, они работают хорошо. Если ладья или дракон - в лагере противника, то добавочная ценность сильно влияет на её позицию (препятствия между королём и ладьёй). Если между своей ладьёй и королём противника есть пешка-якорь, то ценность ладьи ниже. Таблицы изменений ценности для пешки, стрелки и коня вычисляются исходя из позиции короля, перед началом поиска. Поэтому, если король ходит во время поиска, таблица ценностей будет ошибочной. Ценность других фигур (S, G, R, B и перевёрнутых фигур) вычисляется верно. Делается это для ускорения.

Элементы безопасности короля таковы:
- Серебряная (золотая) стена - это минус: если король на 3-й или 4-й вертикали, и не может уйти на 3-ю или 2-ую вертикаль, то это минус.
- Если на поле из восьми, окружающих короля, есть угроза противника, то это минус:
-- Если на этом поле есть своя фигура, а перед нею - угроза противника, то это минус в 1/4 ценности этой фигуры.
-- Если же, при этом, поле перед нею защищено своей фигурой, то минус - лишь в 1/8 от ценности этой фигуры.
-- Если на поле, соседнем с королём, нет фигуры, а на поле перед ним - угроза противника, то это -250.
-Если сумма угроз и защит равна, и у противника есть фигура, которую он может сбросить на это поле, то -200. Если же у него такой фигуры нет, то -130. Каждая дополнительная фигура, которую он может сбросить, даёт -50.
Это ценности полей перед королём. Они исчезают при уходе ниже короля.
- Фигура, приколотая вражеским дальнобойщиком, это минус.
- У входящего короля ценность растёт с приближением к вражескому лагерю. К примеру, добавочная ценность от 1 шага до 9 шага по 1-й вертикали такова:

Шаг:       1   2   3    4    5    6     7    8    9 
Добавка:   0,  0,  0, 150, 450, 900, 1300,1550,1600 (1 or 9 File)

3.5 Вычисление конечного узла

Вычисление конечного узла таково: сначала, если шах, программа безусловно ищет на один уровень больше. В других же позициях программа находит максимальную из ценностей взятия фигур следующим ходом, и добавляет её к функции, вычисляющей статическую ценность. Добавочная ценность - это ценность размена фигуры. Если следующим ходом берётся пешка, то добавляется +200. Также добавляется ценность добавления в руку. Я не рассматриваю чётность глубины поиска. Если глубина поиска достигает предела, то поиск останавливается и вызывается оценочная функция. Я не использую сингулярных выражений (которые используются в Deep Blue).

4. Алгоритмы поиска.

4.1 Расширение на полшага.

Вплоть до YSS 6.0 я использовал фиксированный альфа-бета поиск в глубину. Но начиная с YSS 7.0, я стал использовать итеративное углубление. Причина этому в том, что я захотел попробовать, эффективен ли алгоритм расширения на полшага. Итеративное углубление (возможно, Вы знаете его из шахматных программ) - это поиск без фиксированной глубины, увеличивающий глубину шаг за шагом. Сначала программа запускает поиск на глубину в один шаг, и находит лучший ход. Далее программа запускает поиск на глубину в два шага. На этот раз программа производит поиск, начиная с лучшего хода, найденного при поиске с глубиной в один шаг. Аналогично программа устраивает поиск с глубиной в 3,4,5, ... ,n-1,n шагов. Программа может эффективно искать по альфа-бета алгоритму, поскольку ведёт поиск от лучшего хода, найденного поиском на глубину в n-1 шаг. Этот метод эффективен при игре с ограничением времени. Когда лимит времени исчерпывается во время поиска на n шагов в глубину, то, если программа нашла первый ход (лучший при поиске на глубину в n-1 шаг), выбирается этот ход. Если происходит поиск второго хода, то выбирается всё равно первый, поскольку программа не знает правильно ценность второго хода. Если ищется третий или далее, и лучший ход изменился, то программа выбирает тот ход, который теперь стал лучшим. Алгоритм расширения на полшага - это вариант итеративного углубления. Когда используется расширение на полшага, программа сначала ищет лучший ход и, только для него, прибавляет к максимальной глубине поиска 0.5 шага. Два расширения на 0.5 шага дают расширение на один (реальный) шаг. Поэтому ход, считающийся хорошим, исследуется глубже. Пример показан на диаграмме 6.

Диаграмма 6: Дерево алгоритма расширения на полшага, глубина=3.

На диаграмме 6 показано основное дерево алгоритма расширения на полшага с глубиной поиска, равной 3. У каждого узла здесь две ветви. Левая (жирная) ветвь показывает лучший ход. Числа (слева от узлов) показывают максимальную глубину поиска. Если программа выбирает левый (лучший) узел, то к максимальной глубине прибавляется 0.5 шага. Если же программа выбирает правый узел, максимальная глубина не увеличивается. Если программа уже трижды выбирала лучший ход, считая от корневого узла (когда глубина = 3), то трижды прибавлялось 0.5, поэтому максимальная глубина = 4.5. При обычном поиске на этом шаге поиск заканчивается. Но в данном случае, из-за того, что максимальная глубина равна 4.5, поиск продолжится. Если программа выберет лучший ход в этом узле глубины 3, то максимальная глубина станет равной 5.0, и программа проведёт поиск ещё на один шаг. Если она выберет лучший ход в этом узле глубины 4, то максимальная глубина станет равной 5.5. Текущая глубина станет равной 5, а максимальная 5.5, то есть меньше, чем 6. Поэтому программа завершит поиск на этой глубине (5). И, напротив, ести программа трижды выбирает правую ветвь, то максимальная глубина, не увеличиваясь, остаётся равной 3, и поэтому, по достижении её, программа останавливается. В результате, когда основная глубина равна n (=3), программа может вести поиск до глубины 2n-1 (=5). Сила этого алгоритма в том, что времени (числа конечных позиций) он занимает лишь вдвое больше по сравнению с обычным поиском. К приеру, время поиска возрастает лишь в 2.35 раза, когда основная глубина равна 8 (а максимальная, следовательно, 15), и коэффициент ветвления равен 20.Это показано в таблице 6.

Таблица 6: время и максимальная глубина. Коэффициент ветвления = 20.
A=основная глубина; B=кратность требуемого времени; C=максимальная глубина.
A   B   C  
3   1.14   5
4   1.28   7
5   1.46   9
6   1.70  11
7   2.00  13
8   2.35  15
9   2.79  17
10   3.32  19

При реальном поиске коэффициент ветвления примерно равен 6-80, а продлевающийся ход - единственный (лучший) из всех. Программа проверяет хэш-таблицу, ища лучший ход поиска уровня n-1. Если его нет в хэш-таблице, у программы есть два пути. Первый: расширение останавливается. В этом случае узел становится конечным. Второй: программа запускает итеративное углубление из этого узла, и ищет лучший ход (мульти-итеративное углубление) Если depth_max = 7, и depth = 3, то программа изменяет depth_max = 4, 5, 6, 7. Если программа находит новый лучший ход, то к depth_max прибавляется 0.5, и программа ищет этот новый лучший ход снова. Почему?: да потому, что старый лучший ход был найден при (depth_max + 0.5), а новый лучший ищется лишь при (depth_max) (??? а не наоборот? - Д.К.). Самая сложная задача при этом - тестирование усиления при использовании этого метода расширения на полшага. В моём эксперименте (1998-03-25), программа с расширением победила 249 раз, проиграла 150, и сыграла вничью 1, сражаясь с алгоритмом без расширения. Уровень побед 0.62. Как по-Вашему, много это, или мало? Если же моя программа использует вдвое больше времени, уровень побед около 0.6. Втрое больше - он становится равен 0.75, вчетверо - 0.88, вдесятеро - 0.88 (практически без изменений).

Замечание от 2003-02-19.
Теперь YSS использует отличное расширение в полшага. "Отличное" означает, что если программа находит, что бывший-лучший ход из хэш-таблицы не "лучший", то она ищет этот новый лучший ход, вновь добавляя к ограничению глубины +0.5. Также, YSS использует "Внутреннее Итеративное углубление". Если YSS находит, что хэш-хода в поиске глубины 5 нет, она исследует этот узел последовательными поисками с глубины 1 до глубины 5. Это делается для каждого узла. Лишь узел PV (???) при "внутреннем итеративном углублении" был для YSS плох. Оно требует втрое больше времени для обдумывания, но становится сильнее. Я думаю, что тут важно то, сколь глубоко он может искать, когда лучший ход изменяется.

В таблице 7 показаны уровни глубины, из которых вызывалась оценочная функция. Это было сделано при игре YSS с самой собой. Все уровни для чёрных и для белых суммировались вместе. В дебюте поиск останавливается на малой глубине, поэтому основной уровень глубины взят из миттельшпиля и эндшпиля. 60 и более процентов превосходят основную глубину, равную 8. Максимальная глубина равна20. Причина этого в расширении при шахах и двухходовых расширениях для эффекта горизонта.

Таблица 7: уровни глубины, из которых вызывалась оценочная функция.

depth: %
1: 0.0:
2: 0.0:
3: 0.2:
4: 0.5:
5: 1.2: **
6: 3.3: ******
7: 10.7: *********************
8: 21.0: *****************************************
9: 25.7: ***************************************************
10: 20.3: ****************************************
11: 10.1: ********************
12: 3.9: *******
13: 1.7: ***
14: 0.9: *
15: 0.4:
16: 0.1:
17: 0.0:
18: 0.0:
19: 0.0:
20: 0.0:

Игра закончилась за 140 ходов.
Основная максимальная глубина = 8.
На поиск хода отводилось по 40 секунд.
Всего узлов поиска: 78.436.893.
Всего времени на обдумывание: 2250 минут(??? м.б. секунд?). (процессор Alpha, 500MHz).

Я не знаю, является ли уровень расширения 0.5 лучшим. Другая идея - поварьировать его в пределах 0.1 - 0.9, и прибавлять расширение не только к лучшему ходу, а также применять укорачивание.

В кодах 7 и 8 показаны функция максимума при простом альфа-бета поиске и функция минимума YSS, использующей расширение в полшага.

Код7: функция максимума простого альфа-бета поиска.

int f_max( int alpha, int beta )
{
if ( depth >= depth_max ) return(evaluation value);

making moves

for ( i=0 ; i < number of moves ; i++ ) {

go ahead a move
depth++;

k = f_min( alpha, beta );

go back a move
depth--;

if ( k > alpha ) alpha = k;
if ( alpha >= beta ) return(alpha);
}

return(alpha);
}

Код 8: функция минимума YSS, использующей расширение в полшага.

int f_min( int alpha, int beta )
{
Проверить хэш-таблицу (глубина уровня слева)
If already searched or high limit = alpha, return value , best move,
and search depth of value.

if ( depth >= depth_max && King is not check ) {
Set of search depth of value.
Call evaluation function. And add next capturable piece value.
}

IF (шах) генерируется защитный ход.
ELSE {
Проверить мат в 1 ход
Вызвать матующую программу, зависящую от глубины поиска слева
Генерировать ход, захватывающий фигуру противника, которая только что походила
Генерировать ход, захватывающий фигуры
Ход сожаления (объяснено в 2.4)
Генерировать другие ходы
}

Вырезать аналогичные ходы
Установить n-1-й лучший ход первым лучшим
Проверить расширение на 2 шага в этой позиции на эффект горизонта

for ( i=0 ; i < number of moves ; i++ ) {
Go ahead a move.
depth++;
if ( i==0 ) depth_max += 0.5;
k = f_max( alpha, beta );
if ( k < beta && 2 ply extension flag ) {
depth_max += 2;
k = f_max( alpha, beta );
depth_max -= 2;
}

Go back a move.
depth--;
if ( k < beta ) {
beta = k;
Copy search depth of value.
Copy best sequence.
}

if ( i==0 ) depth_max -= 0.5;
if ( alpha >= beta ) {
Set hash table.
return(beta);
}
}

Если нет ходов, защищающих короля от шаха, проверить, не учифудзумэ (мат сбросом пешки) это ли.
if ( Is beta value is renewal once? ) Set beta value to hash table.
return(beta);
}

4.2 Таблица перестановок (хэш-таблица).


YSS использует хэш-таблицу в поиске при решении цумэ-сёги и в реальном поиске. Конечный узел в обоих этих поисках не регистрируется. Я использую метод Открытого Аддреса. Рехэш-коэффициент равен 16. Рехэш-последовательность - это фиксированная случайная последовательность. (Она эффективна в методе Открытого Аддреса)

Если YSS использует 75% хэш-таблицы, YSS выносит решение, что хэш-таблица полна, поэтому регистрация останавливается на 75%. В хэш-коде я использую 64-битные значения. Сначала я использовал 32-битные значения, но при них часто случалось 2-3 ошибочных совпадения при поиске по 300,000 позиций. Это было очень ненадёжно. Поэтому я перешёл на 64 бита. по моим грубым оценкам, если использовать 64 бита, вероятность того, что произойдёт одно совпадение, равна 1% на один день поиска.
(скорость поиска = 10,000 узлов/с. За день поиск проходит примерно по 2^32 позициям.) Случайное число генерируется множительно-комбинационным методом. ( a=16807, m=2^32-1 ) В основной обдумывающей процедуре YSS производит в первую очередь поиск цумэ (матовых позиций). И только позиции, являющиеся матовыми (в оригинале - TUMI - Д.К.) регистрируются в основной хэш-таблице поиска. Я разделил основную хэш-таблицу поиска и хэш-таблицу поиска цумэ. А при поиске цумэ, я разделяю цумэ чёрных и цумэ белых. Почему?: из-за позиций обратного шаха (когда чёрные шахуют белого короля, но следующий защитный ход белых одновременно является шахом чёрному королю! Происходит смущение.) Чей сейчас ход - чёрных или белых - показано в обратном хэш-коде. Если происходит два паса, хэш-коду возвращается исходное значение (0x01-0xfe-0x01).

Таблица 8. Значения, регистрируемые в хэш-таблице.

1. Хэш-код в 64 бит
2. "Код руки" в 32 бит (учитывает лишь все числа руки белых, но не чёрных)
3. Значение вычислений для главного поиска (верхняя граница, или нижняя граница, или точное значение)
4. Флаг, показывающий, что именно содержится в (3.): верхнее, нижнее или точное значение.
5. Глубина поиска (На какую глубину вести поиск из данной позиции?)
Это число показывает (настоящую глубину * 256). Если поиск ведётся на глубину 3.5, значение = 3*256 + 128 = 0x0380.
6. Относительная глубина поиска для цумэ чёрных.
7. Значение цумэ чёрных. (TUMI (мат), UTI-FU-TUME (мат сбросом пешки), FUMEI(неизвестно), KIRE(не заматовать) )
8. Относительная глубина поиска для цумэ белых.
9. Значение цумэ белых. (TUMI, UTI-FU-TUME, FUMEI, KIRE)
10. Лучший ход

4.3 Два типа эффекта горизонта.


В компьютерных сёги (и, конечно же, в компьютерных шахматах) программа часто делает бессмысленный удар пешкой или странные ходы, приводящие лишь к потере темпа или к потере фигур. Это называется "эффект горизонта".

Диаграмма 9. Возможен эффект горизонта.

На диаграмме 9 показана игра YSS - Kiwame, на 4-м Чемпионате Компьютерных Сёги 1993 года. Ход чёрных. Чёрный король (король YSS) будет заматован грядущим сбросом G'58. Лучшим ходом было бы взятие пешки Sx57. Но если так походить, то последует +Bx87 (шах), K-58, и взятие коня +Bx65. Поэтому чёрные не cмогут сыграть Nx53+! Будь тут человек, он подумал бы: "У меня нет иного выбора, кроме как играть Sx57." Это хорошо. Но компьютер так не подумает. Следующим ходом YSS был сброс G'62. Почему?

В это время глубина поиска YSS была фиксирована 6-ю шагами. И, на глубине 6, YSS не могла найти шаха моему королю со стороны врага. Мыслью YSS было: G'62, K-82; Gx72, Gx72; Nx53+. последний из этих ходов имел глубину 5, поэтому YSS не нашла следующий за ним сброс G'58, и подумала, что в этом варианте я выигрывал ладью! Таким образом, продолжая шахи, компьютер отдаляет эффективный ход противника за свои пределы поиска.

В реальной игре было сыграно: G'62, K-82; S'71, Gx71; Gx72, Gx72; Sx57. Самым фатальным ходом этой последовательности был сброс S'71. Ходы G'62 (шах) и Gx72 (шах) не приносили выгоды, и были тоже фатальными. (если G'62, Gx62; то Nx62+ Kx62 Nx53+, и это было хорошо для чёрных.) Но ход S'71 был слепым. Это была просто потеря серебра. И всего лишь из-за одного этого хода позиция изменилась с немного хорошей на очень плохую. Причина того, почему был сыгран ход S'71, та же, что и у хода G'62. Проблема в этом. Когда эффект горизонта происходит с неприбыльным ходом (шахом и т.д.), это не фатально. Но если с ним происходит потеря фигуры, защищающей от мата в один ход, то это фатально. Если эффект Горихонта проявляется без потери фигуры (к примеру, эффективный шах, или ход-угроза без потери фигуры), я называю его "Слабо вредящий эффект горизонта", и не пытаюсь с ним справиться. (Говоря по-правде, я и не знаю, как с ним справиться...) Важная проблема - это "Сильно вредящий эффект горизонта". Это - ходы с реальной потерей фигуры.

Я хотел разрешить "Сильно вредящий эффект горизонта". В результате, я пришёл к следующим двум выводам.

1. Не искать такой неистовый ход!
2. Необходимо научить компьютер пониманию бесполезности попыток в результате, когда неистовый ход кажется эффективным.

Первый метод применяется к более глубокому узлу. Важно, чтобы программа не искала неистовый ход в более глубоком узле. В нём она должна производить поиск лишь среди небольшого количества ходов, которые очевидно эффективны (убегание или взятие). Чтобы решить вторую задачу, YSS использует расширение на +2 шага. Сначала программа ищет с обычным ограничением глубины. Если программа делает ход с жертвой, и ценность изменяется после взятия жертвуемой фигуры (подозрение на эффект горизонта?), то к ограничению глубины прибавляется 2 шага для этого жертвующего хода и взятия. К примеру, на диаграмме 9 программа рассматривала вариант S-79, Gx79. Произошёл эффект горизонта, и ценность была обновлена. Итак, программа "копает" с ограничением глубины поиска в 6 шагов после этих ходов S-79, Gx79 (ограничение поиска на глубину в 8 шагов, считая от корневого узла). Пространство поиска просто удваивается. Поэтому время обдумывания тоже удваивается. Если жертва со взятием - не единственный ход, программа исследует все ходы со взятием. Лучший ход после расширения на 2 шага кажется лучшим ходом корневого узла. Сначала я брал лучший ход корня из хэш-таблицы, и искал только этот лучший ход после расширения на 2 шага, для ускорения. Но это оказалось нестабильным. Почему? Потому, что на этот лучший ход тоже влиял эффект горизонта. Зачастую это была "ударяющая пешка".Теперь YSS использует это расширение на 2 шага лишь для глубины 3 и 4. Поэтому YSS делает бессмысленные (жертвенные) ходы лишь глубины 1 и 2. С использованием этого метода YSS не играет "эффект горизонта" слишком много в проигрышных позициях.

4.4 Прорыв повторяющихся ходов (последовательных шахов).

Я слежу за повторяющимися ходами, сохраняя хэш-код всех позиций игры. Если позиция повторяется, а моя рука меньше, то ценность -= 5000. (поскольку этот ход - просто потеря фигуры). Если позиция повторяется, моя рука не изменилась, а вражескому королю - шах, то ценность -= 1000. (Возможно, это повторяющиеся шахи.) Если позиция повторяется и моя рука не изменилась, то ценность -= 200. (Я хочу разорвать петлю.)

5. Матовые задачи (цумэ-сёги).

5.1 Матовые задачи.

Для решения матовых задач YSS использует итеративное углубление и хэш-таблицу. Однако её процедура крайне упрощена. Я считаю, что YSS может заматовать лишь в позициях, в которых мат можно увидеть и в реальной игре. Искусство матовых задач вне моего поля зрения. Поэтому большое количество неистовых шахов не рассматривается.

1. Если сумма потерь фигур превосходит 2 ладьи, считая от стартовой позиции, то поиск останавливается.
2. Не рассматриваются вставки-жертвы (включая сбросы).
3. Если ранее данный ход был отвергнут, [и противник захватил его (???),] не рассматривать отвергнутый ход. (Не рассматривать непрерывно отвергаемые ходы!)
4. Не рассматриваются сбросы дальнобойщиков, если их расстояние от вражеского короля превосходит 4 поля.
5. Если R, B и P могут перевернуться, то они переворачиваются..

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

Для ускорения, я сделал последним мат в один ход. Сначала YSS просматривает окружающие короля 8 полей. И, если вражеские угрозы есть не на всех них, выставляется битовый флаг подвижности. Далее, если есть сброс с шахом (YSS делает так, чтобы её сброс с шахом мог заполнить окружающие короля клетки), YSS проверяет битовый флаг заполнения И битовый флаг подвижности. (Про это "И": конечно же, я верю, что Вы понимаете :-) ) Этим методом YSS может быстро найти мат в один ход сбросом. Но в реальности, эта идея была с "жучком":

Диаграмма 10. Ошибка одношагового мата сбросом.

На диаграмме 10 показана ошибка в матовании за один ход сбросом. В данном случае YSS думала, что ход S'22 - это мат! ...Нет, это не так. Король может уйти на поле 12. (Линия дракона заслоняется!) Поэтому теперь YSS тестирует ход сбросом фигуры на реальную доску после битового теста. Шахи усложняют позицию на доске. Поэтому YSS тестирует эти ходы тоже на реальной доске. Из-за этих крайностей YSS может решить цумэ-сёги длиннее 20 ходов лишь поиском по 10000 узлам. Конечно же, найденный мат может оказаться некорректным, поскольку YSS не рассматривает некоторые ходы-вставки.

5.2 Хисси

... В процессе перевода jap -> eng.

6. Приложение: запись игры.

Чёрные: Kanazawa Shogi 2
Белые: YSS 7.0

1.S-4h P-3d 2.P-2f G-3b 3.P-7f Bx8h+ 4.Sx8h S-2b
5.S-7g S-3c 6.P-6f S-6b 7.G-7h G-5b 8.K-6i K-4a
9.G-5h K-3a 10.K-7i G5b-4b 11.P-5f P-6d 12.S-5g P-8d
13.P-2e K-2b 14.S-4f P-4d 15.S-5e S-6c 16.K-8h P-7d
17.G5h-6g N-7c 18.P-3f P-4e 19.N-3g P-3e 20.Px3e P-5d
21.S-4d N-8e 22.Sx3c+ G4bx3c 23.S-8f S*3f 24.S*4h R-9b
25.B*1h Sx3g+ 26.Sx3g N*4b 27.S-2f G-4d 28.S*5c G4d-4c
29.Sx4b= Rx4b 30.N*3d Gx3d 31.Px3d S-5b 32.P-7e Px7e
33.Sx7e P*7d 34.Sx7d N*7e 35.G-7f S*6g 36.Gx7e B*3i
37.Gx6g Bx2h+ 38.S*5a R-4c 39.N*3e R-4d 40.P-2d Px2d
41.P*2c Gx2c 42.Nx2c+ Kx2c 43.G*3e R-4a 44.G*4b +Bx1i
45.Gx5b R*2h 46.S*7h Rx2f+ 47.Gx4a +Rx3e 48.B-2g +B-2h
49.B-1f K-1d 50.P-3c+ S*2e 51.P*2f +Bx1g 52.Bx2e Px2e
53.R*3d +Rx3d 54.+Px3d K-1e 55.Sx8e Px8e 56.N*2i +B-2g
57.R*2b Kx2f 58.Rx2a+ R*3i 59.N*1i +B-1h 60.S*3g K-1e
61.+R-2d K-1f 62.P*1g +Bx1g 63.+Rx2e Kx2e 64.Nx1g K-1f
65.S-2h R-2i+ 66.B*2e K-1e 67.S-2g S*7i 68.K-7g B*5i
69.G-6h Bx6h+ 70.K-7f G*8f 71.Px8f +Bx8f 72.K-6g S-6h+
73.K-5g +R-5i 74.G*5h +Rx5h 75.сдалась.

7. Решение уравнений сёги.

8. Эпилог.

P.S.
Спасибо Вам за советы и всё остальное :-).
Нобухира Ёсимуре
Джеффу Роллансону
Паули Мискангас
Райеру Хримберхену и "Основному словарю сёги" на его домашней странице
И всем фанатам сёги и компьютерных сёги.
eng->rus: shogi.ru, Д.К., 2005