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

Правила игры

Давайте договоримся, что начиная с этого момента и далее я буду писать «сёги», но подразумевать упрощенную версию игры на поле 5 на 5.

Фигуры

Первое с чем надо разобраться при изучении новой игры - это ходы. В сёги есть 10 различных фигур. Обозначения фигур, их названия и возможные ходы представлены в таблице ниже:

Перевороты

Наверняка вы заметили, что среди есть фигур есть «перевёрнутые дубли», которые чаще всего сильнее оригинала. Принцип усиления в сёги похож на шахматный, но, если в шахматах, превращается только пешка, и превращается она в произвольную фигуру, то в сёги переворачиваются все фигуры, кроме золота и короля. Чтобы добиться переворота необходимо начать или закончить ход на последней горизонтали противника. В общем случае переворот является произвольным: т.е. вы можете дойти ладьёй до последней горизонтали, но не перевернуть её, а следующим ходом вернуться в свой лагерь уже с переворотом (т.к. ход вы начали на последней диагонали). Естественно, пешка обязана перевернуться, если она достигла зоны переворота.

Сбросы

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

Любую съеденную у противника фигуру вы можете выставить на любое свободное поле как свою. Такое действие называется сбросом (хотя лично мне больше нравится слово «космодесант», которое впервые в данном контексте применил Андрей Васнецов).

Правда при сбросе есть несколько ограничений, но они довольно просты:

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

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

Очерёдность ходов и начальная расстановка

Игра проходит на квадратном поле со стороной в 5 клеток. В начале игры на поле выглядит следующим образом:

По неизвестным мне причинам, в сёги первыми начинают чёрные, а белые защищаются. Чтобы не путаться с терминами, давайте договоримся, что сторона, начинающая партию называется сенте, а защищающаяся сторона готэ.

Прежде чем переходить к собственно программированию, необходимо отметить ещё одну важную вещь. В сёги нет понятия шаха, т.е. вашему королю угрожают, вы не обязаны защищаться или убегать. Вы вполне можете начать свою атаку. Правда следующим ходом скорее всего съедят вашего короля, и игра закончится.

Программирование игры

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

Перебор игровых деревьев

Полный перебор игровых деревьев

Пусть мы играем в сёги и в какой-то момент на доске возникла интересная позиция, в которой нам необходимо найти лучший ход за сенте. Т.к. компьютер по сути своей - глупый исполнитель, мы можем приказать ему перебрать все возможные ходы и оценить их. Тогда лучшим ходом будет ход с наибольшей оценкой. Но нам по-прежнему неизвестно, как оценивать ходы.

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

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

Перебор игровых деревьев с ограничением глубины рекурсии

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

function SearchBestMove(Depth: byte ; color: TColor) : real ;
var
r, tmpr: real ;
i, N: word ;
Moves: TAMoves;
begin
if Depth= 0 then
r: = EstimatePos
else
begin
real : =- 100000 ;
N: = GenerateAllMoves(Moves) ;
for i: = 1 to N do
begin
Делаем ход Moves[ i] ;
tmpr: =- SearchBestMove(Depth- 1 , opcolor(color) ) ;
Отменяем ход Moves[ i] ;
if tmpr>r then
r: = tmpr;
end ;
end ;
SearchBestMove: = r;
end ;

Понятно, что данный алгоритм выдаёт не полную оценку позиции, а только оценку той позиции, которая возникнет через Depth ходов. Поэтому, если необходимо усилить игру программы, в первую очередь надо увеличивать глубину рекурсии, а это в свою очередь приводит к увеличению дерева, а значит и увеличению времени счёта.

Альфа-бета отсечение

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

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

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

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

Сортировка ходов

Основная проблема в том, что заранее невозможно определить, какие ходы на самом деле хорошими, а какие окажутся плохими. В этом случае приходится прибегать к эвристикам. Если при оценки позиции в расчёт берётся только материальный перевес, то имеет смысл первыми рассматривать ходы-взятия. Причём, есть смысл в первую очередь рассматривать те ходы, где лёгкой фигурой берётся тяжёлая. Кроме того в сёги огромную роль играют перевёрнутые фигуры, поэтому для ходов-переворотов тоже можно увеличивать предварительную эвристическую оценку.

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

В итоге после того, как все ходы были сгенерированы и проведена их эвристическая оценка, необходимо их отсортировать по этой оценке, и подать на вход альфа-бета алгоритма, который выглядит примерно так:

function AB(POS : TRPosition; color: TColor; Depth: byte ; A, B: real ) : real ;
var
Moves: TAMoves;
i, MovesCount: byte ;
OLDPos: TRPosition;
begin
MovesCount: = 0 ;
if (Depth= 0 ) or Mate(POS . HandSente , POS . HandGote , color) then
A: = EstimatePos
else
begin
if color= sente then
MovesCount: = GenerateMoves(POS . Board , color, POS . HandSente , Moves)
else
MovesCount: = GenerateMoves(POS . Board , color, POS . HandGote , Moves) ;

for i: = 1 to MovesCount do
begin
if A>= B then
Break ;
OLDPOS: = POS ;
MakeMove(POS , Color, Moves[ i] ) ;
Moves[ i] . r : =- AB(POS , opcolor(color) , Depth- 1 , - B, - A) ;
POS : = OLDPos;
if Moves[ i] . r >A then
A: = Moves[ i] . r ;
end ;
end ;
AB: = A;
end ;

Доска сёги - 9x9 клеток, нумерующихся сверху вниз и справа налево. Клетки имеют прямоугольную форму, никак не обозначены и не имеют цвета. «Сверху» расставляются в три ряда белые фигуры - пятиугольные дощечки с иероглифическими надписями, названиями фигур, «снизу» - в идентичном порядке, фигуры черных. Играют два игрока. «Белые» и «черные» - это обозначение играющих, фигуры в сёги одного цвета, принадлежность последних определяется направлением острого угла дощечки. Фигура всегда устанавливается острой стороной к противнику. У каждого игрока по 20 фигур 8 наименований, отличающихся друг от друга своей ценностью, силой и рисунком ходов.

У каждой стороны есть один король, одна ладья, один слон, два золотых генерала, два серебряных генерала, два коня, два копья и девять пешек. В крайнем ряду, рядом с копьями располагаются кони. Рядом с конями - серебряные генералы. Рядом с серебряными генералами - золотые генералы. В центре, между двумя золотыми генералами находится король. На втором ряду - только две фигуры. Перед конем с левой стороны находится слон. Перед конем с правой стороны - ладья. В третьем ряду расположены девять пешек.

Порядок игры

Игроки делают ходы поочередно. Первые ходят чёрные. Ход представляет собой перемещение одной из фигур своего цвета, имеющихся на доске на любое разрешенное поле согласно правилам передвижения фигур или (сброс) фигуры находящейся в резерве. Фигуры «в резерве» (или по-другому «в руке») - это фигуры, взятые (сбитые) у противника.

В сёги при достижении фигурами (лагерь противника) они могут быть усилены (превращены). При превращении фигура переворачивается. В сёги усилиться может любая фигура кроме короля и золотого генерала.

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

Ходы фигур

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

Фигура		Рисунок хода
	- японское обозначение K - латинское обозначение	Ходы короля
Как и в шахматах, король ходит на одно поле в любом направлении, за исключением поля под шахом противника (восемь различных ходов). Шах - это положение, когда король оказывается под ударом вражеской фигуры, т.е. находится в поле, куда может походить вражеская фигура.
	Золотой генерал (Кин) - японское обозначение G - латинское обозначение	Ходы золотого генерала
Золотой генерал может передвигаться на одно поле по горизонтали или по вертикали в любую сторону, а также по диагонали вперёд (шесть различных ходов).
	- японское обозначение S - латинское обозначение	Ходы серебрянного генерала
	- японское обозначение +S - латинское обозначение
Серебряный генерал может передвигаться на одно поле по диагонали в любом направлении или на одно поле по вертикали вперёд (пять различных ходов). Достигнув вражеского лагеря, может быть превращен в золотого генерала.
	- японское обозначение N - латинское обозначение	Ходы коня
	- японское обозначение +N - латинское обозначение
Как и его шахматный аналог, конь ходит буквой Г, но только вперед и без возможности отступления. Т.е. ход коня составляет одно поле по вертикали вперёд, затем одно поле по диагонали вправо или влево (два возможных хода). Это единственная фигура, которая может перепрыгивать через стоящие на пути фигуры. Достигнув вражеского лагеря, может быть превращен в золотого генерала.
	- японское обозначение L - латинское обозначение	Ходы копья
	- японское обозначение +L - латинское обозначение
Копьё ходит только вперёд по вертикали на любое количество полей, не занятых другими фигурами. Назад ходить не может. Достигнув вражеского лагеря, может быть превращено в золотого генерала.
	- японское обозначение P - латинское обозначение	Ходы пешки
	- японское обозначение +P - латинское обозначение
Пешка ходит на одно поле вперёд по вертикали. Бьет вражеские фигуры не наискосок, как в шахматах, а прямо перед собой. Достигнув вражеского лагеря, может быть превращена в золотого генерала.
	- японское обозначение R - латинское обозначение	Ходы ладьи
	- японское обозначение +R - латинское обозначение
Ладья ходит по горизонтали и по вертикали на любое число полей, не занятых другими фигурами (аналогично шахматной Ладье). Достигнув вражеского лагеря, может быть превращена в короля-дракона - фигуру, которая, сохраняя возможности Ладьи, дополнительно может ходить на одно поле по диагонали в любом направлении.
	- японское обозначение B - латинское обозначение	Ходы cлона
	- японское обозначение +B - латинское обозначение
Слон ходит по диагонали в любом направлении на любое число полей, не занятых другими фигурами (аналогично шахматному cлону). Достигнув вражеского лагеря, может быть превращен в коня-дракона - фигуру, которая, сохраняя возможности cлона, дополнительно может ходить на одно поле по вертикали или горизонтали в любом направлении.

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

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

Производя размены, всегда следует учитывать конкретную ситуацию на доске. В зависимости от степени укрепленности королевских крепостей, тактических возможностей и общего стратегического рисунка игры сила фигур в сёги может изменяться. Неоднозначность шкалы ценностей иллюстрируют и некоторые пословицы, сложенные об игре. Например: «Одна пешка ценнее тысячи золотых генералов» , «Превращенный слон стоит трех генералов» или «В конце игры скорость важнее материала» .

Тем не менее, несмотря на неоднозначность, материальный баланс является одним из важнейших критериев оценки позиции. Кодзи Танигава, 17-й Пожизненный Мейдзин, в книге «Как мыслить, чтобы выигрывать в сёги» предлагает следующую шкалу ценностей фигур:
Пешка - 1 балл;
Копье - 5;
Конь - 6;
Серебрянный генерал - 8;
Золотой генерал - 9;
Превращенный серебр. генерал - 9;
Превращенное копье - 10;
Превращенный конь - 10;
Превращенная пешка - 12;
Слон - 13;
Ладья - 15;
Превращенный слон - 15;
Превращенная ладья - 17.

Взятие фигур

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

Превращение

Когда фигура достигает лагеря противника (зоны превращения) (см. у неё возникает возможность стать превращенной (исключение составляют лишь король и золотой генерал, которые превращаться не могут). Но превращение не является обязательным, оно может быть осуществлено при любом очередном ходе (сначала передвижение, затем превращение), но только если эта фигура по-прежнему находится в лагере противника. Фигура может быть также превращена за пределами зоны превращения - в момент выхода из нее. При превращении фигура переворачивается сразу после хода и приобретает свойства превращенной фигуры. Для большинства фигур это способности золотого генерала, ладья и слон превращаются соответственно в короля-дракона и коня-дракона (см. ). Обратное превращение не допускается.

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

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

Выставление

Фигура, находящаяся «в руке», может быть выставлена (сброшена) на любое свободное поле доски, что считается очередным ходом. Фигура сбрасывается только в непревращённом виде (даже если она была превращенной до взятия). Нельзя выставляться на поле занятое фигурой противника. После выставления фигура приобретает те же права, что и находящиеся на доске. Если фигура сброшена в лагерь противника, она может превратиться, только сделав следующий ход, даже если он сделан на поле за пределами зоны превращения.

Запрещенные ходы

Следующие ходы запрещены:

1. Сдваивание пешек (нифу). Когда на одной из вертикалей имеется не превращённая пешка, не разрешается выставлять другую пешку на ту же вертикаль.
2. Выставление пешки с матом (учи-фу-тсумэ). Не разрешается выставлять пешку с матом королю противника. Однако объявлять мат очередным ходом пешки, находящейся на доске, разрешено.

   К запрещенным ходам также относятся:

3. Неправильные ходы (кинтэ).
   
   
   1. Выставленная фигура заперта. Запрещается сбрасывать фигуры таким образом, что у них будет отсутствовать возможность хода в дальнейшем. Такая ситуация возникает при выставлении пешки, копья либо коня на последнюю горизонталь, а для коня - также при сбросе на предпоследнюю горизонталь.
   2. Выставленная фигура сразу перевернута.
   3. Ход фигурой сделан не по правилам.

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

Ничья

Большинство партий в сёги оканчиваются либо матом, либо признанием поражения одним из игроков, однако ничья также возможна.

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

Ничья объявляется при четырёхкратном повторении одновременно следующих трёх условий:

• позиция на доске;
• фигуры «в руке»;
• очередность хода;

В турнирной практике такие партии, как правило, переигрываются (на оставшееся время с переменой цвета).

Безвыходное положение. Такая ситуация возникает крайне редко, при варианте, когда оба короля зашли в лагерь противника и нет возможности поставить мат.

В таком случае производится подсчёт фигур. ладья и слон считаются за 5 очков, остальные - за одно. Если оба игрока имеют в сумме более 24 очков, то присуждается ничья. Если у одного из игроков менее 24 очков - ему засчитывается проигрыш.

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

Компанией лучше всего играть в квесты комнаты от "In Game" в Днепре по доступным ценам.

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

Первые попытки создать машины для игры в интеллектуальные игры (в первую очередь в шахматы) появились задолго до появления компьютеров. Около 1769 года появился известный шахматный аппарат «механический турок». Машина играла весьма неплохо, но весь её секрет заключался в спрятанном внутри сильном шахматисте.

В XX веке механические машины уступили свои позиции цифровым компьютерам. Первопроходцем в этой области (как и во многих других) можно назвать известного математика Алана Тьюринга. По современным меркам разработанный им алгоритм был весьма примитивным, а ввиду отсутствия доступа к реальным вычислительным машинам, выполнять алгоритм приходилось вручную.

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

Со времён Шеннона задача программирования интеллектуальных игр переместилась из области развлечений в область серьёзных исследований. За последние годы на основе исследований Шеннона были построены реализуемые на практике алгоритмы, с помощью которых компьютеры научились безошибочно играть в шашки и достигли выдающихся успехов в шахматах и го.

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

Правила игры

Прежде чем говорить о построении алгоритмов для игры в сёги, необходимо описать правила этой игры.

Фигуры

В сёги есть 8 различных фигур (если учитывать перевёрнутые фигуры, то 14). Правила ходов для различных фигур представлены в таблице:

Если проанализировать таблицу, можно сделать следующие наблюдения:

1. Дальнобойных фигур в сёги всего две: ладья и слон;
2. Возможности отступления многих фигур ограничены или совсем отсутствуют.

Эти наблюдения позволяют разбить все фигуры на четыре группы:

1. Король, обладающий абсолютной ценностью;
2. Старшие фигуры (ладья и слон), способные к дальнобойным атакам и быстрому отступлению;
3. Генералы (золотой и серебряный), чьи возможности наступления значительно превышают возможности отступления;
4. Младшие фигуры (конь, стрела, пешка), не способные отступать.

Начальная расстановка и очерёдность хода

В сёги играют два игрока, которых принято называть сэнтэ (ходящие первыми) и готэ (ходящие вторыми), на квадратной доске 9x9 клеток. Начальная расстановка фигур показана на рисунке:

Также у каждого игрока есть специальная подставка (комадай), куда помещаются взятые у противника фигуры. Также принято говорить, что взятые фигуры оказываются «в руке».

Перевороты

Три последние горизонтали (относительно каждого игрока) являются зоной переворота. Любая неперевёрнутая фигура (кроме золота и короля), начинающая или заканчивающая свой ход внутри этой зоны, может перевернуться и превратиться в другую фигуру. Правила превращения фиксированы и показаны в таблице:

Важно отметить, что решение о том переворачивать фигуру или нет, принимает игрок. Случаи, когда переворот необходим, описаны в разделе запрещённые ходы.

Сбросы

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

В правиле сброса есть несколько ограничений, но они довольно просты:

1. Все фигуры сбрасываются не перевёрнутыми (даже если они сбрасываются в зону переворота);
2. Нельзя сбрасывать пешку на ту вертикаль, где уже есть пешка (токин не считается пешкой);
3. Нельзя сбрасывать пешку с матом.

Запрещённые ходы

Если противник сделал запрещённый ход, ему немедленно засчитывается поражение, поэтому крайне важно знать список запрещённых ходов:

1. Ходы, нарушающие правила (например, отсутпление золотом по диагонали);
2. Нарушение правил сброса (например, сброс второй пешки на вертикаль);
3. Ход, после которого фигура не сможет сделать ни одного хода. Это правило требует пояснения. Нельзя ходить пешкой на последнюю горизонталь без переворота или конём на последнюю или предпоследнюю горизонталь без переворота. Очевидно, что и сбрасывать фигуры таким образом нельзя.

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

Завершение игры

Игра заканчивается, когда один из игроков поставил мат или сделал запрещённый ход. Но в сёги существуют дополнительные правила окончания игры:

1. Если позиция повторилась трижды в результате непрерывной серии шахов (т.н. «вечный шах»), то на четвёртый раз атакующий игрок должен сделать другой ход, иначе ему будет засчитано поражение.
2. Если же позиция повторилась 4 раза без объявления шаха, то игроки переигрывают партию без объявления результатов, но с переменой цвета на оставшееся время.

Вышеописанные правила делают ничейный результат крайне редким для сёги (не более 3% от всех сыгранных игр). Но тем не менее, ничья возможна в одном случае: если оба короля вошли в лагерь противника и укрепились там. Если оба игрока согласны с тем, что возникшая ситуация тупиковая, то происходит подсчёт очков. Все фигуры (в т.ч. и в руке) кроме короля, слона и ладьи оцениваются в 1 очко, слон и ладья - в 5 очков, король в подсчёте не участвует.

В профессиональных партиях проигрывает игрок, у которого меньше 24 очков, если у обоих игроков не меньше 24 очков, то объявляется ничья. В любительских партиях побеждает тот, у кого не менее 27 очков, если у обоих игроков по 27 очков, то победа присуждает готэ.

Алгоритм нахождения лучшего хода

Алгоритм MiniMax

Впервые стратегия поиска лучшего хода для любой заданной позиции была описана ещё Клодом Шенноном. Если немного подумать, то можно заметить, что эта стратегия довольно проста и применима к любой игре.

Пусть у нас есть некоторая позиция, в которой нам необходимо сделать оптимальный ход. Вначале необходимо сгенерировать все разрешённые правилами ходы. Потом каждый из корректных ходов необходимо оценить. Ходы, ведущие к победе, будут оцениваться как +1, ведущие к поражению, - как -1, и ходы, ведущие к ничейным позициям, получат оценку 0.

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

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

Функция поиска лучшего хода будет рекурсивно вызывать сама себя до тех пор пока не возникнет матовая или ничейная ситуация.

При этом оценка итоговой позиции не представляет сложности, а при оценке родительских узлов пользуются следующими правилами:

1. Оценка хода для первого игрока вычисляется как максимум оценок дочерних узлов;
2. Оценка хода для второго игрока вычисляется как минимум оценок дочерних узлов.

Такой алгоритм называют MiniMax. Если графически изобразить цепочку вызовов, то получится т.н. игровое дерево:


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


Alpha-Beta отсечение

В рассмотренном выше примере для получения итоговой оценки узла У0, пришлось получить оценки для всех остальных узлов У1-У16, но на самом деле в этом не было необходимости: как только мы узнали, что узел У1 приводит к победе, необходимость в анализе узлов У7-У16 отпадает, т.к. любые оценки, полученные для тех узлов, не превысят оценку узла У1 (т.к. она максимальна), а это значит, что хода лучше чем У1 просто нет. Если учесть это, то анализируемое дерево будет выглядеть следующим образом:

Очевидно, что такой сокращённый анализ не ухудшает точность решения, но значительно сокращает время поиска лучшего хода. Именно идея «обрезки» неперспективных ветвей дерева лежит в основе алгоритма Alpha-Beta отсечений.

При использовании отсечений дополнительно вводятся две переменные: минимум для сэнтэ (A) и максимум для готэ (B). Сам алгоритм Alpha-Beta отсечений похож на алгоритм MiniMax, за исключением следующих пунктов:

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

1. Если в какой-либо момент оценка первого игрока становится больше A, то значение A обновляется;
2. Аналогично поступают и с оценкой B для второго игрока.

Важным моментом при использовании этого алгоритма является порядок просмотра ходов. Если сначала рассматривать те ходы, которые сильнее всего сужают диапазон , то количество отсечённых ветвей будет достаточно большим. Возвращаясь к рассмотренному выше дереву, легко заметить, что порядок просмотра У7, У12, У1 даст гораздо меньший выигрыш в производительности. Поэтому перед использованием алгоритмов с отсечениями производят предварительную сортировку ходов по ожидаемой эффективности.

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

Функция оценки позиции

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

Материальная оценка

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

Все фигуры в руке оцениваются на 30% дороже, т.к. их мобильность за счёт возможности сброса значительно возрастает.

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

Стратегическая оценка

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

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

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

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

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

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

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

Алгоритм выборочных продлений

Уже рассмотренные алгоритмы MiniMax и Alpha-Beta отсечения всегда находят лучший ход на заданной глубине, но проблема в том, что глубина анализа (8-10 ходов) недостаточна для сильной игры. Профессионалы просчитывают позиции на 12-14 ходов, а некоторые позиции более чем на 20 ходов. Такая глубина для компьютеров пока недостижима.
Некоторым компромиссным вариантом является просмотр на значительную глубину только некоторых ветвей дерева, в то время как остальные ветви будут просматриваться на уменьшенную глубину. Такой подход называется методом выборочных продлений.

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

Изначально глубина просмотра каждого хода равна 0, а оценка хода равна -INF (т.е. проигрыш). На первой итерации выполняется анализ позиции на глубину 1 для всех ходов, при этом каждый ход получает свою оценку эффективности, а глубина его просмотра увеличивается на 1. Затем все ходы упорядочиваются по эффективности, и лучшие ходы анализируются на глубину 2. Если во время очередного продления выяснилось, что ход с максимальной оценкой уже проанализирован на максимальную глубину, то этот ход исключается из дальнейшего рассмотрения. Процесс углубления продолжается до тех пор, пока все ходы не будут просмотрены на минимальную глубину. На рисунке ниже показан примерный порядок построения дерева при использовании выборочных продлений (максимальная глубина - 4, минимальная глубина - 2, в узлах показана оценка позиция на текущей глубине просмотра):


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

Кеширование

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

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

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

Для использования кеширования результатов в алгоритм поиска лучшего хода необходимо внести следующие изменения:

1. Перед началом просчёта проверять наличие позиции в кеш;
2. Если позиция содержится в кеш, то прекратить расчёт и вернуть полученное ранее значение;
3. При завершении просчёта записывать результат в кеш;

Есть ещё один довольно тонкий момент. Если в кеш уже содержится искомая позиция, просчитанная на малую глубину, этот результат тоже можно использовать. Вспомним, что алгоритм Alpha-Beta отсечений очень чувствителен к порядку ходов. Практика показывает, что оценка, полученная с малой глубиной просчёта, является довольно качественной эвристической оценкой качества хода. Т.е. значения, хранящиеся в кеш, могут быть использованы для сортировки ходов перед вызовом Alpha-Beta отсечений.

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

По графику видно, что использование кеш значительно повышает глубину просчёта для повторяющихся позиций. Например, при ограничении времени в 5 секунд на ход использование кеш позволяет добиться такой же глубины анализа, как и 100-секундный анализ без использования кеш.

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

И в качестве заключения небольшой пример игры разработанной программы против программы Shogi Lvl. 100:

Доска сёги - 9x9 клеток, нумерующихся сверху вниз и справа налево. Клетки имеют прямоугольную форму, никак не обозначены и не имеют цвета. «Сверху» расставляются в три ряда белые фигуры - пятиугольные дощечки с иероглифическими надписями, названиями фигур, «снизу» - в идентичном порядке, фигуры черных. Играют два игрока. «Белые» и «черные» - это обозначение играющих, фигуры в сёги одного цвета, принадлежность последних определяется направлением острого угла дощечки. Фигура всегда устанавливается острой стороной к противнику. У каждого игрока по 20 фигур 8 наименований, отличающихся друг от друга своей ценностью, силой и рисунком ходов.

У каждой стороны есть один король, одна ладья, один слон, два золотых генерала, два серебряных генерала, два коня, два копья и девять пешек. В крайнем ряду, рядом с копьями располагаются кони. Рядом с конями - серебряные генералы. Рядом с серебряными генералами - золотые генералы. В центре, между двумя золотыми генералами находится король. На втором ряду - только две фигуры. Перед конем с левой стороны находится слон. Перед конем с правой стороны - ладья. В третьем ряду расположены девять пешек.

Порядок игры

Игроки делают ходы поочередно. Первые ходят чёрные. Ход представляет собой перемещение одной из фигур своего цвета, имеющихся на доске на любое разрешенное поле согласно правилам передвижения фигур или (сброс) фигуры находящейся в резерве. Фигуры «в резерве» (или по-другому «в руке») - это фигуры, взятые (сбитые) у противника.

В сёги при достижении фигурами (лагерь противника) они могут быть усилены (превращены). При превращении фигура переворачивается. В сёги усилиться может любая фигура кроме короля и золотого генерала.

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

Ходы фигур

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

Фигура		Рисунок хода
	- японское обозначение K - латинское обозначение	Ходы короля
Как и в шахматах, король ходит на одно поле в любом направлении, за исключением поля под шахом противника (восемь различных ходов). Шах - это положение, когда король оказывается под ударом вражеской фигуры, т.е. находится в поле, куда может походить вражеская фигура.
	Золотой генерал (Кин) - японское обозначение G - латинское обозначение	Ходы золотого генерала
Золотой генерал может передвигаться на одно поле по горизонтали или по вертикали в любую сторону, а также по диагонали вперёд (шесть различных ходов).
	- японское обозначение S - латинское обозначение	Ходы серебрянного генерала
	- японское обозначение +S - латинское обозначение
Серебряный генерал может передвигаться на одно поле по диагонали в любом направлении или на одно поле по вертикали вперёд (пять различных ходов). Достигнув вражеского лагеря, может быть превращен в золотого генерала.
	- японское обозначение N - латинское обозначение	Ходы коня
	- японское обозначение +N - латинское обозначение
Как и его шахматный аналог, конь ходит буквой Г, но только вперед и без возможности отступления. Т.е. ход коня составляет одно поле по вертикали вперёд, затем одно поле по диагонали вправо или влево (два возможных хода). Это единственная фигура, которая может перепрыгивать через стоящие на пути фигуры. Достигнув вражеского лагеря, может быть превращен в золотого генерала.
	- японское обозначение L - латинское обозначение	Ходы копья
	- японское обозначение +L - латинское обозначение
Копьё ходит только вперёд по вертикали на любое количество полей, не занятых другими фигурами. Назад ходить не может. Достигнув вражеского лагеря, может быть превращено в золотого генерала.
	- японское обозначение P - латинское обозначение	Ходы пешки
	- японское обозначение +P - латинское обозначение
Пешка ходит на одно поле вперёд по вертикали. Бьет вражеские фигуры не наискосок, как в шахматах, а прямо перед собой. Достигнув вражеского лагеря, может быть превращена в золотого генерала.
	- японское обозначение R - латинское обозначение	Ходы ладьи
	- японское обозначение +R - латинское обозначение
Ладья ходит по горизонтали и по вертикали на любое число полей, не занятых другими фигурами (аналогично шахматной Ладье). Достигнув вражеского лагеря, может быть превращена в короля-дракона - фигуру, которая, сохраняя возможности Ладьи, дополнительно может ходить на одно поле по диагонали в любом направлении.
	- японское обозначение B - латинское обозначение	Ходы cлона
	- японское обозначение +B - латинское обозначение
Слон ходит по диагонали в любом направлении на любое число полей, не занятых другими фигурами (аналогично шахматному cлону). Достигнув вражеского лагеря, может быть превращен в коня-дракона - фигуру, которая, сохраняя возможности cлона, дополнительно может ходить на одно поле по вертикали или горизонтали в любом направлении.

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

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

Производя размены, всегда следует учитывать конкретную ситуацию на доске. В зависимости от степени укрепленности королевских крепостей, тактических возможностей и общего стратегического рисунка игры сила фигур в сёги может изменяться. Неоднозначность шкалы ценностей иллюстрируют и некоторые пословицы, сложенные об игре. Например: «Одна пешка ценнее тысячи золотых генералов» , «Превращенный слон стоит трех генералов» или «В конце игры скорость важнее материала» .

Тем не менее, несмотря на неоднозначность, материальный баланс является одним из важнейших критериев оценки позиции. Кодзи Танигава, 17-й Пожизненный Мейдзин, в книге «Как мыслить, чтобы выигрывать в сёги» предлагает следующую шкалу ценностей фигур:

Пешка - 1 балл;
Копье - 5;
Конь - 6;
Серебрянный генерал - 8;
Золотой генерал - 9;
Превращенный серебр. генерал - 9;
Превращенное копье - 10;
Превращенный конь - 10;
Превращенная пешка - 12;
Слон - 13;
Ладья - 15;
Превращенный слон - 15;
Превращенная ладья - 17.

Взятие фигур

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

Превращение

Когда фигура достигает лагеря противника (зоны превращения) (см. у неё возникает возможность стать превращенной (исключение составляют лишь король и золотой генерал, которые превращаться не могут). Но превращение не является обязательным, оно может быть осуществлено при любом очередном ходе (сначала передвижение, затем превращение), но только если эта фигура по-прежнему находится в лагере противника. Фигура может быть также превращена за пределами зоны превращения - в момент выхода из нее. При превращении фигура переворачивается сразу после хода и приобретает свойства превращенной фигуры. Для большинства фигур это способности золотого генерала, ладья и слон превращаются соответственно в короля-дракона и коня-дракона (см. ). Обратное превращение не допускается.

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

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

Выставление

Фигура, находящаяся «в руке», может быть выставлена (сброшена) на любое свободное поле доски, что считается очередным ходом. Фигура сбрасывается только в непревращённом виде (даже если она была превращенной до взятия). Нельзя выставляться на поле занятое фигурой противника. После выставления фигура приобретает те же права, что и находящиеся на доске. Если фигура сброшена в лагерь противника, она может превратиться, только сделав следующий ход, даже если он сделан на поле за пределами зоны превращения.

Запрещенные ходы

Следующие ходы запрещены:

1. Сдваивание пешек (нифу). Когда на одной из вертикалей имеется не превращённая пешка, не разрешается выставлять другую пешку на ту же вертикаль.
2. Выставление пешки с матом (учи-фу-тсумэ). Не разрешается выставлять пешку с матом королю противника. Однако объявлять мат очередным ходом пешки, находящейся на доске, разрешено.

   К запрещенным ходам также относятся:

3. Неправильные ходы (кинтэ).
   
   
   1. Выставленная фигура заперта. Запрещается сбрасывать фигуры таким образом, что у них будет отсутствовать возможность хода в дальнейшем. Такая ситуация возникает при выставлении пешки, копья либо коня на последнюю горизонталь, а для коня - также при сбросе на предпоследнюю горизонталь.
   2. Выставленная фигура сразу перевернута.
   3. Ход фигурой сделан не по правилам.

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

Ничья

Большинство партий в сёги оканчиваются либо матом, либо признанием поражения одним из игроков, однако ничья также возможна.

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

Ничья объявляется при четырёхкратном повторении одновременно следующих трёх условий:

• позиция на доске;
• фигуры «в руке»;
• очередность хода;

1. Безвыходное положение. Такая ситуация возникает крайне редко, при варианте, когда оба короля зашли в лагерь противника и нет возможности поставить мат.

   В таком случае производится подсчёт фигур. ладья и слон считаются за 5 очков, остальные - за одно. Если оба игрока имеют в сумме более 24 очков, то присуждается ничья. Если у одного из игроков менее 24 очков - ему засчитывается проигрыш.

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