26 октября 2012 в 12:35

ИИ для игры в сёги (японские шахматы)

Есть одна старинная японская игра сёги. Иногда её называют японскими шахматами. Не буду спорить, что-то общее у этих игр есть, но сёги намного сложнее. Впервые я узнал об этой игре из комментария на Хабре, где утверждалось, что это одна из сложнейших игр, и лучшие компьютерные программы по-прежнему не могут победить сильнейших игроков-людей. Конечно, я заинтересовался и начал играть. За год я достиг некоторых успехов и даже занял второе место среди новичков на официальном турнире. Учитывая мою любовь к программированию, следующий шаг был очевиден — написать свой ИИ. Об этом и пойдёт рассказ ниже.
Сразу писать ИИ для настоящих сёги на поле 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>=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;
 

Итоговая реализация


В результате я написал небольшую программу (скачать), которая на мой взгляд, весьма неплохо играет в сёги. Конечно, она далека от совершенства, и в ней есть много вещей, требующих исправления и доработки. Неплохо было бы добавить ходы — угрозы королю в эвристическую оценку, совсем здорово было бы доработать программу и научить её играть в полноценные сёги, но всё это планы на будущее, а пока вы можете попробовать свои силы в этой интереснейшей игре.
+37
12795
112
GORKOFF 95,5

Комментарии (18)

+7
ozonar, #
Чтобы не путаться с терминами, давайте договоримся, что сторона, начинающая партию называется сенте, а защищающаяся сторона готэ.


Ну да, с такими терминами стало значительно проще. =)

По теме:
1. Выйгранной партия считается когда съёли короля?
2. У фигур есть какие-то графические обозначения? По себе почувствовал, если досконально не знаешь правил — начать играть будет невозможно.
+1
GORKOFF, #
1. Да партия заканчивается, когда съедают короля, но т.к. игра японская, то существуют определённые традиции. Крайне редко игру доводят до такого момента, чаще всего игрок сдаётся за несколько ходов до мата.
2. В игре фигуры обозначаются иероглифами, в которых разобраться ещё сложнее, чем в буквенных обозначениях.
0
Hellenko, #
2. В таких случаях удобно подсвечивать поля, на которые выбранная фигура может пойти.
0
VMAtm, #
В шахматах сейчас тоже часто не доходят до конца, и сдаются.
0
alexzzam, #
В последнем предложении всплывают некие «полноценные сёги». А это, стало быть, какой-то упрощённый вариант игры? В чём отличие?
+1
GORKOFF, #
Да. Я ещё в самом начале поста написал, что пишу программу для игры в упрощённый вариант. В полноценных сёги сражение идёт на доске 9 на 9, и у каждой стороны по 9 пешек, по 2 золота и серебра, и, помимо описанных фигур, есть ещё стрелы и кони.
+1
pleax, #
это одна из сложнейших игр, и лучшие компьютерные программы по-прежнему не могут победить сильнейших игроков-людей

Таким комментарием обычно сопровождают описание Го.
+1
GORKOFF, #
Го и правда невероятно сложная игра, но это не делает сёги менее простыми. Да и для го не так давно появились интересные и очень эффективные методы компьютерной игры с использованием метода Монте-Карло.
+3
pleax, #
Ну на счет «очень эффективных» методов можно говорить только в отношении к предыдущему поколению играющих программ. Речь до сих пор идет о нескольких камнях форы перед профессионалами.

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

PS: Я это все не к тому, чтобы выяснять кто же сложнее там и круче. Просто такое вот дежа-вю. Даже цитата с википедии какбэ намекает.
Среди множества настольных игр, го выделяется ещё и тем, что она оказалась наиболее сложной для компьютера.
0
Halt, #
Го сложна в первую очередь масштабами. Доска имеет размер 19х19; при игре камни снимаются очень редко, так что конфигурация постоянно усложняется: «Если в шахматах в начальной позиции существует 20 разных ходов, то в го — 361. Дерево вариантов с каждым ходом растет стремительно: так, если в шахматах после четвертого хода может возникнуть около 100 тысяч позиций, то в го — более 16 миллиардов»

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

+1
GORKOFF, #
Я ещё раз скажу, что не отрицаю сложность го. Но судите сами, после каждого сделанного хода, количество возможных ответных ходов в го уменьшается, а в сёги наоборот увеличивается (за счёт сбросов).
Нет особого смысла мерятся сложностью. Каждая игра сложна по своему.
0
Halt, #
Дак я не меряюсь. Я просто хотел сказать, что это разные игры и в общем-то напрямую сравнивать нельзя.

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

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

Максимум, что можно сделать в го за один ход, это съесть группу противника (если она и так осталась с одним дамэ), но это задача тривиальная и противник никогда такого не допустит (если не совсем нуб). Более сложный вариант с жизнью и смертью групп, но там тоже все не очевидно.

Собственно зачем я тут распинаюсь? Мне хотелось бы услышать от вас, в чем именно заключается ключевое отличие рассчета в сёги от шахмат. Я понимаю, что в статье вы затронули вопросы переворота, но хотелось бы услышать что-то большее :)

P.S.: За статью спасибо, вопросы игрового ИИ всегда интересны.
0
GORKOFF, #
Наверное, я так и не сформулировал основную мысль поста. Вся суть просчёта игровых деревьев в том, что этот метод может применяться к любой игре: и к сёги, и к шахматам, и к го. Более того, если глубину просчёта искусственно не ограничивать, этот метод всегда найдёт лучший ход.
Все отличия заключаются в функции оценки позиции и в алгоритме сортировки ходов.
0
KvanTTT, #
Спасибо за статью.

Но реализовали хотя бы технику хеширования Зобриста, а то статья коротковатой получилась. По идее она здесь себя будет хорошо проявлять, потому что поле небольшое. Если что не понятно — обращайтесь ко мне :)
0
limon_spb, #
что-то со ссылкой :-) или там просто на вики?
0
KvanTTT, #
Да, на вики и что-то неправильно вставилась.
Вот правильная.
0
GORKOFF, #
Вы, наверное, и списки ходов быстрой сортировкой упорядочиваете?
А если серьёзно, меня всегда немного удивляли люди, которые в простенькие по сути задачи пытаются впихнуть все известные алгоритмы.
0
KvanTTT, #
О способе сортировки ходов рассказывать не нужно — сортировка итак хорошо известная вещь, к тому же простая.

Простенькая задача? А может тогда и альфа-бета отсечение делать не нужно и сортировку?

Может для доски 5*5 она и простенькая, но для большей доски уже нужно будет изобретать что-то новое.

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

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