AI в игре Hase und Igel: minimax на троих

Автор: admin от 7-12-2018, 14:45, посмотрело: 230

AI в игре Hase und Igel: minimax на троих


После настоящего бума настольных игр конца 00-х в семье осталась несколько коробок с играми. Одна из них — игра “Заяц и Ёж” в оригинальной немецкой версии. Игра для нескольких игроков, в которой элемент случайности сведен к минимуму, а побеждает трезвый расчет и способность играющего “заглядывать” вперед на несколько шагов.



Мои частые поражения в игре привели меня к мысли написать компьютерный “интеллект” для выбора наилучшего хода. Интеллект, в идеале, способный сразиться с гроссмейстером Зайца и Ежа (а что, чай, не шахматы, игра попроще будет). Далее в статье идет описание процесса разработки, логики AI и ссылка на исходники.

автомат Мура. В серверной логике отсутствуют такие понятия, как “подключенный клиент”, “игровая сессия” и т.д.



Все, что делает сервер — обрабатывает полученную (HTTP POST) команду. На сервере реализован паттерн “команда”. Клиент может запросить выполнение одной из следующих команд:




  • начать новую игру, т.е. “расставить” фишки указанного количества игроков на “чистой” доске

  • сделать ход, указанный в команде



Для второй команды клиент отправляет серверу текущую игровую позицию (объект класса Disposition), т.е., описание следующего вида:




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

  • индекс зайца, совершающего ход.



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



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



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



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



Ход игрока



Ход игрока кодируется целым числом:




  • 0, если игрок вынужден остаться на текущей клетке,

    1, 2, … N для 1, … N шагов вперед,

  • -1, -2, … -M для перемещения на 1 … M клеток назад на ближайшего свободного ежа,

  • 1001, 1002 — специальные коды для игрока, решившего остаться на клетке моркови и получить (1001) или отдать (1002) за это 10 морковок.



  • Программная реализация



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



    Если клиент (игрок) запросил произвести ход с кодом CMD из переданной в команде позиции (POS), сервер производит следующие действия:




    • проверяет, возможен ли такой ход

    • создает новую позицию из текущей, применяя к ней соответствующие модификации,

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





      Реализация с AI



      В список команд, обрабатываемых сервером, добавляется одна команда: выполнить квазиоптимальный, выбранный программой, ход. Эта команда — небольшая модификация команды “ход игрока”, из которой убрано, собственно, поле хода (этом посте (перевод).



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







      Небольшая оптимизация алгоритма альфа-бета отсечения



      С включенной в настройках AI опцией отсечения количество вершин в дереве позиций сократилось в среднем в 3 раза. Этот результат можно несколько улучшить.



      В приведенном выше примере:



      AI в игре Hase und Igel: minimax на троих


      так удачно “совпало”, что, перед поддеревом с вершиной в позиции 3 мы рассмотрели поддерево с вершиной в позиции 2. Если бы очередность была иной, мы могли начать с “худшего” поддерева и не прийти к выводу об отсутствии смысла в рассмотрении очередной позиции.



      Как правило, более “экономным” оказывается отсечение на дереве, вершины-потомки которого на одном уровне (т.е., все возможные ходы из i-позиции) уже отсортированы по текущей (без заглядывания вглубь) оценке позиции. Иначе говоря, мы предполагаем, что от лучшего (с точки зрения эвристики) хода больше вероятность получить лучшую итоговую оценку. Таким образом, мы, с некоторой вероятностью, отсортируем дерево так, что “лучшее” поддерево будет рассмотрено прежде “худшего”, что позволит отсечь больше вариантов.



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





      Дополнительно, раз уж позиции для каждого из возможных в текущей вершине дерева ходов отсортированы по эвристической оценке, напрашивается мысль сразу отбросить несколько худших вариантов. К примеру, шахматист может рассмотреть ход, на котором он подставляет свою ладью под удар пешки. Однако, “раскручивая” ситуацию вглубь на 3, 4 … хода вперед, он сразу отметет варианты, когда, к примеру, противник подставит под удар слона своего ферзя.



      В настройках AI я задаю вектор “отсечения худших вариантов”. К примеру, вектор вида [0, 0, 8, 8, 4] означает, что:




      • заглядывая на один [0] и два [0] шага вперед, программа рассмотрит все возможные ходы, т.к. 0 означает отсутствие отсечения,

      • заглядывая на три [8] и четыре [8] шага вперед, программа рассмотрит до 8 “лучших” ходов, ведущих из очередной позиции, включительно,

      • заглядывая на пять и более шагов вперед [4], программа оценит не более 4 “лучших” ходов.



      Со включенной сортировкой для алгоритма альфа-бета отсечения и похожим вектором в настройках отсечения программа стала затрачивать на выбор квазиоптимального хода порядка 300 миллисекунд, “углубляясь” на 8 шагов вперед.



      Оптимизация эвристики



      Несмотря на приличное количество перебираемых в дереве позиций вершин и “глубокое” заглядывание вперед в поисках квазиоптимального хода, у AI оказалось несколько слабых мест. Одно из них я определил как “заячью ловушку”.





      Поправочные коэффициенты



      Ранее, приводя формулу эвристической оценки текущей позиции

      E = Ks * S + Kc * C + Kp * P,

      я упомянул, но не описал поправочные коэффициенты.



      Дело в том, что, как сама формула, так и наборы функций AI в игре Hase und Igel: minimax на троих, были выведены мной интуитивно, на основании т.н. “здравого смысла”. Хотелось бы, как минимум, подобрать такие коэффициенты Ks, Kc и Kp, чтобы оценка была как можно более адекватна.



      Как оценить “адекватность” оценки? Оценка — величина безразмерная, и сравнивать ее можно лишь с другой оценкой. Я смог придумать единственный один способ уточнения поправочных коэффициентов:



      заложил в программу ряд “этюдов”, хранимых в CSV файле с данными вида



          45;26;2;f;29;19;0;f;2
          ...
      


      Эта строка означает буквально следующее:




      • первый игрок находится на 45 клетке, на руках у него 26 карточек морковки и 2 карточки салата, игрок не пропускает ход (f = false). Право хода всегда за первым игроком.

      • второй игрок на 29 клетке с 19 карточками морковки и без карточек салата, ход не пропускает.

      • цифра два означает, что, “решая” этюд, я предположил, что второй игрок находится в выигрышной ситуации.



      Заложив в программу 20 этюдов, я “загружал” их в игровом web-клиенте, а затем разбирал каждый этюд. Разбирая этюд, я поочередно совершал ходы за каждого из игроков, до тех пор, пока не определялся с “победителем”. Закончив оценку, я отправлял ее в специальной команде на сервер.



      Оценив 20 этюдов (конечно, стоило бы разобрать их побольше), я произвел оценку каждого из этюдов программой. При оценке по очереди перебирались значения каждого из поправочных коэффициентов, от 0.5 до 2 с шагом 0.1 — итого AI в игре Hase und Igel: minimax на троих = 4096 вариантов троек коэффициентов. Если оценка для первого игрока оказывалась выше оценки второго игрока, и аналогичное указание было сохранено в строке записи этюда (последнее значение строки равно 1), засчитывалось “попадание”. Аналогично для зеркальной ситуации. В противном случае засчитывался промах.



      В итоге я выбрал те тройки, для которых процент “попаданий” был максимален (16 из 20). Вышло около 250 из 4096 векторов, из которых я отобрал “лучший”, опять же, “на глазок”, и установил его в настройках AI.



      Итоги



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



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



      Программа вполне работоспособна для варианта с 3-я игроками. Однако есть подозрения, что “качество” ходов AI для игры с 3-я игроками ниже, чем для игры с двумя игроками. Впрочем, в ходе последнего теста я проиграл компьютеру — возможно, по неосторожности, небрежно оценивая количество моркови на руках и придя к финишу с избытком “топлива”.



      Пока что дальнейшее развитие AI тормозит отсутствие человека — “тестировщика”, т.е., живого оппонента компьютерному “гению”. Сам я наигрался в Зайца и Ежа до тошноты и вынужден прерваться на текущем этапе.



      Ссылка на репозиторий с исходниками


    Источник: Хабр / Интересные публикации

    Категория: Веб-разработка

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

    Добавление комментария

    Имя:*
    E-Mail:
    Комментарий:
    • bowtiesmilelaughingblushsmileyrelaxedsmirk
      heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
      winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
      worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
      expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
      disappointedconfoundedfearfulcold_sweatperseverecrysob
      joyastonishedscreamtired_faceangryragetriumph
      sleepyyummasksunglassesdizzy_faceimpsmiling_imp
      neutral_faceno_mouthinnocent