Пусть компьютер сам принимает решение или пишем ИИ для игры вместе

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

image
Под катом gif-файлов мегабайт на 10.


Об игре


В игре вы управляете мотоциклом, который оставляет за собой стену из света. Игровое поле ограничено, а у соперников такие же мотоциклы. Мотоцикл едет постоянно, вы лишь можете поворачивать. Свободное место на поле кончается, и избегать препятствия становится сложнее. Побеждает тот, кто дольше всех продержится. Клон игры я сделал браузерным многопользовательским с использованием node.js и socket.io. Управление из двух кнопок – поворот влево и поворот вправо.

Интерфейс бота


Так как я использую socket.io, то обработка игроков на сервере у меня была в виде работы над массивом специальных объектов socket, которые создаёт socket.io. Из этих объектов я использовал только id, функции emit и broadcast. А значит безболезненно для самой игры можно реализовать интерфейс socket и использовать его в обработке, будто играет ещё один пользователь. Я назвал класс BotSocket.
Метод emit(event, data) у бота выполняет почти такие же действия что и у клиента при входящих данных от сервера, а именно:
  1. Сохраняет данные обо всех играющих мотоциклах при их добавлении
  2. Сохраняет ссылку на свой мотоцикл при его добавлении
  3. Обновляет данные обо всех играющих мотоциклах
  4. Сбрасывает состояния при перезапуске игры

Для передачи команд управления своим мотоциклом на сервер потребовалось сохранить ссылку на объект игры, который обрабатывает такие команды от обычных пользователей. Метод класса Game у меня назван onControl(socket, data), поэтому я добавил метод в BotSocket
BotSocket.prototype.control = function(data) {
  this.game.onControl(this, data);
};

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

Искусственный интеллект


Как бы громко это не звучало, но в играх игроков, за которых играет компьютер, принято называть именно ИИ, либо ботами. Объект BotSocket обладает необходимыми данными об игре, чтобы принять решение. Вариантов решения может быть всего три:
  1. Ничего делать, ехать прямо
  2. Повернуть направо
  3. Повернуть налево


Когда я решил написать бота, я понятия не имел, как это можно сделать. Я попробовал очень простой код:
BotSocket.prototype.update = function()  {
    var r = Math.random();
    if (r > 0.95) {
        this.control({'button': 'right'});
    } else if (r > 0.90) {
        this.control({'button': 'left'});
    }
}

Поведение было примерно таким:
image

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

Но хотелось, чтобы он жил как можно больше. Я стал искать информацию о том, как пишут ИИ к играм. Нашел статьи, которые описывали разные подходы. Но я искал что-то чрезвычайно простое. Я нашел на хабре в одной из статей про бота для игры вроде Zuma упоминание волнового метода. Он же алгоритм Ли. Мне он показался очень простым и подходящим. Это алгоритм поиска кратчайшего пути из одной точки в другую по полю, где клетки могут быть либо свободными, либо занятыми. Суть простая. Мы начинаем из точки назначения, присваиваем ей значение 1 и помечаем все соседние свободные клетки цифрой на единицу больше. Затем берём все соседние свободные помеченных и снова помечаем на единицу больше. Так расширяемся на всё поле, пока не дойдем до точки назначения. А путь строим поиском из соседних по уменьшению числа, пока не дойдем до 1. Я смотрел алгоритмы поиска кратчайших путей в графах, но этот мне показался наиболее подходящим.

Я перенёс алгоритм копипастой из страницы в вики, дал ему имя BotSocket.prototype.algorithmLee. Для поля я создал сначала объект battleground, в котором при каждом обновлении помечал занятые точки с их координатами. А в алгоритме Ли сводил это поле к такому же, но с шагом 1.

Нужно было как-то определять точку назначения. Я решил выбирать её случайно через определенные интервалы времени. Сделал метод для поиска случайной свободной точки на поле:
BotSocket.prototype.getDesiredPoint = function() {
  var point = [];
  var H = Object.keys(this.battleground[0]).length - 1;
  var W = Object.keys(this.battleground).length - 1;
  var x, y, i, j;
  var found = false;
  var iter = 0;
  do {
    i = this.getRandomInt(1, W);
    j = this.getRandomInt(1, H);
    x = i * this.moveStepSize;
    y = j * this.moveStepSize;
    if (this.battleground[x][y] === this.BG_EMPTY) {
      found = true;
    }
    iter++;
  } while (!found && iter < 100);

  point = [x, y];
  return point;
};


Теперь я мог переписать update:
BotSocket.prototype.update = function() {
  if (!this.desiredPoint || this.movements % this.updDestinationInterval === 0) {
    this.desiredPoint = this.getDesiredPoint();
  }

  if (!this.desiredPoint) {
    return;
  }

  var currentPoint = [this.myBike.x, this.myBike.y];
  var path = this.algorithmLee(currentPoint, this.desiredPoint);

  if (path && typeof path[1] !== 'undefined') {
    this.moveToPoint(path[1]);
  } else {
    this.desiredPoint = this.getDesiredPoint();
  }
};

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

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

Бот на стороне клиента


Я решил попробовать перенести бота на клиентскую часть. Так как проект на node.js, я могу использовать написанный код для бота и на стороне клиента. Для этого я расширил BotSocket отдельным клиентским файлом, который переопределял методы emit() и control(), чтобы правильно взаимодействовать с сервером без ссылки на объект game.
Локально всё работало отлично, а после деплоя на удалённый сервер была какая-то странная картина:
image

Долго думая, я понял, что дело в задержке. Бот отправлял команду поворота, но она доходила после обновления его позиции на сервере, отчего он часто не мог попасть на прямой путь к желаемой точке. Но я хотел нормального бота на клиентской стороне. Поэтому решил учитывать задержку. Для этого написал снова расширение BotSocket. Статья получается длинной, так что опишу основные решения. Перед вызовом алгоритма Ли вместо текущей точки я подставлял прогнозируемое положение с учетом текущего положения и направления, а так же множителя задержки. Множитель задержки – это число, во сколько раз превосходит задержка частоту обновления положения на сервере. Предсказание будущей точки мне еще понадобилось в методе moveToPoint().

Предсказание работало, если играл один. Но если были другие участники, то бот не учитывал это и направлял туда, где через некоторое время уже проехал другой игрок. Для решения этой проблемы я изменил метод, который помечает клетки поля занятыми. Я стал их помечать занятыми в некотором радиусе движения мотоциклов. Радиус зависит от множителя задержки.
Предварительно я снабдил бота функциями отладки, который рисовали на поле желаемую точку и занятые точки. Моя версия клиентского бота с учетом задержки теперь двигается так:
image
Мой красненький, остальные серверные.

Самое важное – попробуйте сделать бота сами


Основная цель этой статьи – пробудить интерес к написанию бота. Я сделал много, чтобы победить вашу лень. Для этого я добавил возможность подгружать свой собственный скрипт с ботом, который будет расширять мой базовый клиентский класс. Зайдите на проект и нажмите на текст «Show options for room with your own bot», а затем на кнопку «Create room for test your own bot». Будет создана комната, где можно легко применять ботов, по умолчанию вашим ботом будет бот без учета задержки. Теперь настало время для вашего кода.
Два простых варианта для использования вашего кода в деле, используйте любой:

  1. Выкладывайте js-файл на любой сервер, который будет доступен вашему браузеру. Url к вашему скрипту вставляйте в игре рядом с кнопкой “Load your AI script”. После нажатия на эту кнопку будет создан и заполнен новый объект botSocket, у которого будет вызван метод start().
  2. Используйте консоль браузера (Firebug – F12, Firefox — Ctrl+Shift+K, Chrome – Ctrl+Shift+J, другие – здесь).


Если вы определились с методом ввода вашего кода, попробуйте переопределить методы класса BotSocket. Для начала самое простое:
BotSocket.prototype.update = function()  {
    var r = Math.random();
    if (r > 0.95) {
        this.control({'button': 'right'});
    } else if (r > 0.90) {
        this.control({'button': 'left'});
    }
}


После этого пересоздайте объект botSocket, введя
botSocket = null;

При этом код на странице сам пересоздаст и заполнит объект. Этим вы измените стандартное поведение бота на случайное. А дальше уже дело для вашей фантазии или глубоких знаний.
Вы так же можете подключить скрипт моего улучшенного бота с учетом задержки, вставив в url для бота https://raw.github.com/rnixik/tronode-js/master/public/javascripts/MyBotSocketClient.js

Заключение


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

Исходный код на Github: github.com/rnixik/tronode-js

Если у вас нет под рукой node.js, вы можете воспользоваться развернутыми мной приложениями:

1) tronode.livelevel.net — самая дешевая VPS на DigitalOcean,
2) tronode-js.herokuapp.com — бесплатная виртуальная единица на Heroku.

Первый, скорее всего, первым может не справиться с нагрузкой, а второй на некоторых компьютерах сбрасывает socket.io-транспорт в xhr-polling, из-за этого игра очень сильно лагает.
Если вы хотите узнать больше, о том, как я программировал игровую логику, то можете прочитать здесь. Там же о развертке node.js и немного о графической части.

Если у вас нет аккаунта на хабре, то задать вопросы или прислать свои интересные предложения можете мне на почту dev@1i1.be.
Поделиться публикацией
Ой, у вас баннер убежал!

Ну. И что?
Реклама
Комментарии 36
  • +1
    Очень понравились размышления, поиск ответов да и вообще, реализация задумки. Для тех, кто не имеет опыта в разработке игр — самое то!
    • 0
      Спасибо большое, приятно.
    • +7
      просто необходим игровой чат)
      • 0
        Почти во все предыдущие проекты с вебсокетами добавлял чат, а тут что-то не стал. А еще у меня проблема с размещением элементов на странице. Я просто не знаю куда его поместить.
        • 0
          а у меня проблема с пингом. наверное, хватит с рабочего компа играть
          • 0
            Ну вот прямо сейчас сервер решил призадуматься, хотя ЦП и память на VDS ещё есть.
            • 0
              Уже минут 15 в моих браузерах рисование мотоциклов очень сильно лагает, но судя по траекториям, кто-то вполне хорошо себя там чувствует. Ноду ребутал, ничего не изменилось. Топовый bandwidth на VPS был 15 Mpbs, но недолго. Обычно около 1 Mpbs. htop говорит, что с ресурсами всё хорошо. Что-то я запутался.
        • 0
          Желательно с «voteban-ом», иначе весь чат забьют попрошайки инвайтов и флудеры.
          • +3
            Да, не нашёл, куда писать «Лошары! :)» :)
          • 0
            На недавней конференции nips (машинное обучение и статистика) меня сильно впечатлила демка, где модель выучилась нескольким играм на Атари считывая только экран игры. Причем «без учителя», через reinforced learning.

            Вот статья, правда там немногословно и слегка мутновато.
            • 0
              Отличная статья, как раз пишу AI для своей мини игры по захвату клеток, ваша статья оказалась к стати (: Спасибо!
              • +1
                Этот рад услужить всем :)
              • +1
                Тоже когда-то баловался подобным, когда играть одному было скучно, но хотелось. Тогда ещё не знал, что данная игра называет Tron, а впервые её увидел на спектруме.

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

                • 0
                  На Heroku синий бот просто убивается с разбегу об стенку в каждой гонке.
                  • 0
                    Значит это не серверный бот. Просто кто-то либо тестирует, либо взял себе имя, как у бота, и оставил игру.
                  • НЛО прилетело и опубликовало эту надпись здесь
                    • 0
                      Какой такой Флинн?
                      • НЛО прилетело и опубликовало эту надпись здесь
                    • 0
                      Snake Battle вспомнился.
                      • 0
                        О, не я один в это играл оказывается О_о
                        • 0
                          думаю что нет. на самом деле, было бы интересно увидеть что-то подобное в режиме онлайн.
                          • 0
                            Руководство к действию? =D
                            • 0
                              ну я в программировании вообще ноль. но если вы готовы взять техническую часть на себя, то жду сообщения в личку)
                      • 0
                        Ещё бы постоянное управление (A или стрелка влево — всегда влево, если возможно, остальные — аналогично), а не как сейчас: A — повернуть на 90 градусов. А так игра отличная получилась.
                        • 0
                          Интересный заголовок

                          Пусть компьютер сам принимает решение


                          Причем РЕШЕНИЕ [decision, model solution] — это
                          1. Выбор одной или нескольких альтернатив из множества возможных.
                          2. Процесс (алгоритм) осуществления такого выбора.

                          а в реализации

                          Math.random(); и «вместо случайной желаемой точки, я искал точку впереди врагов, чтобы перекрыть им путь»


                          Простите, но это не решение, а имитация (подражание) принятия решения.

                          Здесь же не нужно разговаривать на языке и анализировать речь, управлять конечностями в 3D чтобы ловить предметы и сохранять равновесие, распознавать образы при разном освещении, удаленности и наклоне.
                          Неужели даже для такой простой игры нельзя реализовать «сильный» ИИ?
                          Вопрос, наверное, не к автору, а вообще к разработчикам игр. Дайте нам умного соперника!
                          • 0
                            А Вы просите умного соперника именно к этой игре или вообще к любой? Если к этой, то можете попробовать поиграть в другие клоны Трона, например, Armagetron. Насколько я помню, там можно играть со сложным соперником. А если вы вообще про ИИ в играх, то уже давно есть боты для шашек и шахмат, которые делают неслучайные действия.
                            • +1
                              Разумные существа были бы кстати везде — и в стрелялках, и в гонках, и в настольных играх.
                              Опять же, придираясь к заголовку, я ожидал в этой статье увидеть цель ИИ, ее обоснованный выбор и способ достижения цели.
                              Например: «не врезаться самому», «подрезать противника». В текущий момент времени одна из целей будет активной. Могут даже образовываться подцели. Например, ИИ про себя думает «я сейчас догоняю противника, чтобы на повороте его подрезать». Но способ выбора не должен быть рандомный. Вы же, когда играете в эту игру, принимаете решения пусть и быстро, но обоснованно? В идеале — на основе опыта. То есть если в прошлой игре ИИ принял решение «подрезать» и врезался сам, он должен извлечь опыт и в аналогичной ситуации остаться на цели «не врезаться». Можно ли как-то реализовать такое принятие решений?
                              • 0
                                А если вы вообще про ИИ в играх, то уже давно есть боты для шашек и шахмат, которые делают неслучайные действия.

                                Это Вы выражаетесь очень мыслекорректно к ботам для шашек и шахмат. А можно ли эти действия назвать разумными? У каждого хода, если он делается разумным существом, должна быть цель. А сейчас мы имеем соперника в виде ИИ, который делает оптимизированный перебор ходов + имеет базу данных позиций, заложенную разработчиком. Это не цель, это способ имитации что у ИИ есть цель в его действиях.
                                • +1
                                  что бы у ИИ была цель, необходимо, что бы оно понимал зачем т.е ИИ должно обладать сознанием- осознанием происходящего, чего пока невозможно реализовать, можно только имитировать, как замечено выше. К примеру НС без учителя(очень правдоподобно будет), но тут уже извините совсем не игровой уровень :D
                                  • 0
                                    Как мы можем узнать, что используя свой рандом, ИИ не следует своей цели? Может он просто притворяется и не показывает всю мощь своего интеллекта и тайно строит Скайнет в /dev/null?
                                    • 0
                                      Как мы можем различить одну инерциальную систему отсчёта (к примеру подвижную) от другой (к примеру неподвижную)?
                                      Ответ — никак, в ИСО все законы выполняются одинаково.
                                      Все принципы строятся на фундаментальных основах… Любой генератор случайных чисел (на ЭВМ) это ПГСЧ т.е. псевдоГСЧ, в который зашиты обычный и понятный математический аппарат. Таким образом мы можем утверждать, что кофеварка не задушит нас ночью, а ИИ в играх никогда не будет жить своей жизнью, по крайне мере, пока не будет известен алгоритм эволюции и формирования человека на земле. ИМХО
                                      • 0
                                        Вот поэтому я и люблю смайлы, они хотя бы намекают, что я шучу :)
                                        • 0
                                          ах вы проказник ;D выкрутились, правда я не вижу ни одного смайла :PP
                                          • 0
                                            В правилах Хабра рекомендуют не использовать, вот и не стал.
                              • 0
                                Не сочтите за рекламу, www.nitrous.io бесплатное облачко для экспериментов над node.js
                                • 0
                                  С той же идеей в прошлом феврале сидел — делал Tron-a под Node.js и хотел AI реализацию написать и использовал A* алгоритм тогда. Хочу вашу потестить сейчас очень)

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

                                  Самое читаемое