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

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

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


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

    Подробнее
    Реклама
    Комментарии 18
    • +7
      Чтобы не путаться с терминами, давайте договоримся, что сторона, начинающая партию называется сенте, а защищающаяся сторона готэ.


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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