Пусть компьютер сам принимает решение или пишем ИИ для игры вместе
Вы когда-нибудь задумывались о том, насколько просто написать свой искусственный интеллект, который сам будет принимать решения в игре? А ведь это действительно просто. Пусть для начала он принимает случайные решение, но позже вы можете его воспитать, научить анализировать ситуацию, и тогда он станет принимать осознанные решения. В этой статье я расскажу, как я писал своего бота, а также покажу, как вы за несколько минут можете написать своего. Наш компьютер будет играть в клон игры Трон, а точнее в ту часть, где нужно на мотоцикле победить врагов.
Под катом gif-файлов мегабайт на 10.
Об игре
В игре вы управляете мотоциклом, который оставляет за собой стену из света. Игровое поле ограничено, а у соперников такие же мотоциклы. Мотоцикл едет постоянно, вы лишь можете поворачивать. Свободное место на поле кончается, и избегать препятствия становится сложнее. Побеждает тот, кто дольше всех продержится. Клон игры я сделал браузерным многопользовательским с использованием node.js и socket.io. Управление из двух кнопок – поворот влево и поворот вправо.
Интерфейс бота
При поступлении от сервера команды обновления данных мотоциклов (было совершено их передвижение) я проверяю, есть ли у меня вообще подконтрольный мотоцикл, не столкнулся ли он еще и был ли он перемещён, и, в случае успеха, я вызываю основной метод для работы ИИ — update().
Интерфейс готов, теперь можно добавить сам ИИ.
Искусственный интеллект
Когда я решил написать бота, я понятия не имел, как это можно сделать. Я попробовал очень простой код:
Поведение было примерно таким:
Я смотрел на него и испытывал большую радость, мне казалось, что он теперь самостоятельный. Казалось, что он сам ищет попытки выжить, бьётся там, как живой. Трогательное зрелище.
Но хотелось, чтобы он жил как можно больше. Я стал искать информацию о том, как пишут ИИ к играм. Нашел статьи, которые описывали разные подходы. Но я искал что-то чрезвычайно простое. Я нашел на хабре в одной из статей про бота для игры вроде Zuma упоминание волнового метода. Он же алгоритм Ли. Мне он показался очень простым и подходящим. Это алгоритм поиска кратчайшего пути из одной точки в другую по полю, где клетки могут быть либо свободными, либо занятыми. Суть простая. Мы начинаем из точки назначения, присваиваем ей значение 1 и помечаем все соседние свободные клетки цифрой на единицу больше. Затем берём все соседние свободные помеченных и снова помечаем на единицу больше. Так расширяемся на всё поле, пока не дойдем до точки назначения. А путь строим поиском из соседних по уменьшению числа, пока не дойдем до 1. Я смотрел алгоритмы поиска кратчайших путей в графах, но этот мне показался наиболее подходящим.
Я перенёс алгоритм копипастой из страницы в вики, дал ему имя BotSocket.prototype.algorithmLee. Для поля я создал сначала объект battleground, в котором при каждом обновлении помечал занятые точки с их координатами. А в алгоритме Ли сводил это поле к такому же, но с шагом 1.
Нужно было как-то определять точку назначения. Я решил выбирать её случайно через определенные интервалы времени. Сделал метод для поиска случайной свободной точки на поле:
Теперь я мог переписать update:
Здесь упоминается метод moveToPoint, который поворачивает, если нужно, чтобы достигнуть первую точку из кратчайшего пути с учётом текущего направления.
Позже я решил сделать ботов более агрессивными и вместо случайной желаемой точки, я искал точку впереди врагов, чтобы перекрыть им путь. Или чтобы они не играли так долго сами с собой.
Бот на стороне клиента
Я решил попробовать перенести бота на клиентскую часть. Так как проект на node.js, я могу использовать написанный код для бота и на стороне клиента. Для этого я расширил BotSocket отдельным клиентским файлом, который переопределял методы emit() и control(), чтобы правильно взаимодействовать с сервером без ссылки на объект game.
Локально всё работало отлично, а после деплоя на удалённый сервер была какая-то странная картина:
Долго думая, я понял, что дело в задержке. Бот отправлял команду поворота, но она доходила после обновления его позиции на сервере, отчего он часто не мог попасть на прямой путь к желаемой точке. Но я хотел нормального бота на клиентской стороне. Поэтому решил учитывать задержку. Для этого написал снова расширение BotSocket. Статья получается длинной, так что опишу основные решения. Перед вызовом алгоритма Ли вместо текущей точки я подставлял прогнозируемое положение с учетом текущего положения и направления, а так же множителя задержки. Множитель задержки – это число, во сколько раз превосходит задержка частоту обновления положения на сервере. Предсказание будущей точки мне еще понадобилось в методе moveToPoint().
Предсказание работало, если играл один. Но если были другие участники, то бот не учитывал это и направлял туда, где через некоторое время уже проехал другой игрок. Для решения этой проблемы я изменил метод, который помечает клетки поля занятыми. Я стал их помечать занятыми в некотором радиусе движения мотоциклов. Радиус зависит от множителя задержки.
Предварительно я снабдил бота функциями отладки, который рисовали на поле желаемую точку и занятые точки. Моя версия клиентского бота с учетом задержки теперь двигается так:
Мой красненький, остальные серверные.
Самое важное – попробуйте сделать бота сами
Основная цель этой статьи – пробудить интерес к написанию бота. Я сделал много, чтобы победить вашу лень. Для этого я добавил возможность подгружать свой собственный скрипт с ботом, который будет расширять мой базовый клиентский класс. Зайдите на проект и нажмите на текст «Show options for room with your own bot», а затем на кнопку «Create room for test your own bot». Будет создана комната, где можно легко применять ботов, по умолчанию вашим ботом будет бот без учета задержки. Теперь настало время для вашего кода.
Два простых варианта для использования вашего кода в деле, используйте любой:
Если вы определились с методом ввода вашего кода, попробуйте переопределить методы класса BotSocket. Для начала самое простое:
После этого пересоздайте объект botSocket, введя
При этом код на странице сам пересоздаст и заполнит объект. Этим вы измените стандартное поведение бота на случайное. А дальше уже дело для вашей фантазии или глубоких знаний.
Вы так же можете подключить скрипт моего улучшенного бота с учетом задержки, вставив в url для бота https://raw.github.com/rnixik/tronode-js/master/public/javascripts/MyBotSocketClient.js
Заключение
Я рассказал, как я создавал своего ИИ на сервере, затем как перенес его на клиент и как пытался научить его играть с учетом высокого пинга. Я очень надеюсь, что смог заинтересовать вас, и вы попробовали написать свой ИИ, если еще ни разу этого не делали раньше. Конечно, в играх высокого класса используются совсем другие подходы, но начинать стоит с малого.
Если у вас нет под рукой node.js, вы можете воспользоваться развернутыми мной приложениями:
1) tronode.livelevel.net — самая дешевая VPS на DigitalOcean,
2) tronode-js.herokuapp.com — бесплатная виртуальная единица на Heroku.
Первый, скорее всего, первым может не справиться с нагрузкой, а второй на некоторых компьютерах сбрасывает socket.io-транспорт в xhr-polling, из-за этого игра очень сильно лагает.
Если вы хотите узнать больше, о том, как я программировал игровую логику, то можете прочитать здесь. Там же о развертке node.js и немного о графической части.
Если у вас нет аккаунта на хабре, то задать вопросы или прислать свои интересные предложения можете мне на почту dev@1i1.be.
Как создать искусственный интеллект?
А ведь действительно, именно желание создать совершенный искусственный интеллект, будь то игровая модель или мобильная программа, сподвигла на путь программиста многих из нас. Проблема в том, что за тоннами учебного материала и суровой действительностью заказчиков, это самое желание было заменено простым стремлением к саморазвитию. Для тех, кто так и не приступил к исполнению детской мечты, далее краткий путеводитель по созданию настоящего искусственного разума.
Стадия 1. Разочарование
Когда мы говорим о создании хотя бы простых ботов, глаза наполняются блеском, а в голове мелькают сотни идей, что он должен уметь делать. Однако, когда дело доходит до реализации, оказывается, что ключом к разгадке реальной модели поведения является. математика. Если быть немного конкретнее, то вот список её разделов, которые необходимо проштудировать хотя бы в формате университетского образования:
Теория вероятностей и математическая статистика.
Это тот научный плацдарм, на котором будут строится ваше дальнейшее программирование. Без знания и понимания этой теории все задумки быстро разобьются о взаимодействие с человеком, ведь искусственный разум на самом деле не больше, чем набор формул.
Стадия 2. Принятие
Когда спесь немного сбита студенческой литературой, можно приступать к изучению языков. Бросаться на LISP или другие функциональные языки пока не стоит, для начала надо научиться работать с переменными и однозначными состояниями. Как для быстрого изучения, так и дальнейшего развития прекрасно подойдёт Python, но в целом можно взять за основу любой язык, имеющий соответствующие библиотеки.
Стадия 3. Развитие
Теперь переходим непосредственно к теории ИИ. Их условно можно разделить на 3 категории:
Слабый ИИ – боты, которых мы видим в компьютерных играх, или простые подручные помощники, вроде Siri. Они или выполняют узкоспециализированные задачи или являются незначительным комплексом таковых, а любая непредсказуемость взаимодействия ставит их в тупик.
Сильный ИИ – это машины, интеллект которых сопоставим с человеческим мозгом. На сегодняшний день нет реальных представителей этого класса, но компьютеры, вроде Watson очень близки к достижению этой цели.
Совершенные ИИ – будущее, машинный мозг, который превзойдёт наши возможности. Именно об опасности таких разработок предупреждают Стивен Хоккинг, Элон Маск и кинофраншиза «Терминатор».
Естественно, начинать следует с самых простых ботов. Для этого вспомните старую-добрую игру «Крестики-нолики» при использовании поля 3х3 и постарайтесь выяснить для себя основные алгоритмы действий: вероятность победы при безошибочных действиях, наиболее удачные места на поле для расположения фигуры, необходимость сводить игру к ничьей и так далее.
Сыграв несколько десятков партий и анализируя собственные действия, вы наверняка сможете выделить все важные аспекты и переписать их в машинный код. Если нет, то продолжайте думать, а эта ссылка здесь полежит на всякий случай.
К слову, если вы всё-таки взялись за язык Python, то создать довольно простого бота можно обратившись к этому подробному мануалу. Для других языков, таких как C++ или Java, вам также не составит труда найти пошаговые материалы. Почувствовав, что за созданием ИИ нет ничего сверхъестественного, вы сможете смело закрыть браузер и приступить к личным экспериментам.
Стадия 4. Азарт
Теперь, когда дело сдвинулось с мёртвой точки, вам наверняка хочется создать что-то более серьёзное. В этом вам поможет ряд следующих ресурсов:
Как вы поняли даже из названий, это API, которые позволят без лишних затрат времени создать некоторое подобие серьёзного ИИ.
Стадия 5. Работа
Теперь же, когда вы уже вполне ясно представляете, как ИИ создавать и чем при этом пользоваться, пора выводить свои знания на новый уровень. Во-первых, для этого потребуется изучение дисциплины, которое носит название «Машинное обучение». Во-вторых, необходимо научиться работать с соответствующими библиотеками выбранного языка программирования. Для рассматриваемого нами Python это Scikit-learn, NLTK, SciPy, PyBrain и Nump. В-третьих, в развитии никуда не обойтись от функционального программирования. Ну и самое главное, вы теперь сможете читать литературу о ИИ с полным пониманием дела:
И да, вся или почти вся литература по данной тематике представлена на иностранном языке, поэтому если хотите заниматься созданием ИИ профессионально необходимо подтянуть свой английский до технического уровня. Если вы только начинаете путь к мечте, советуем записаться на бесплатный двухчасовой интенсив по основам программирования.
В остальном, ваше дальнейшее развитие будет зависеть лишь от практики и желания усложнять алгоритмы. Но будьте осторожны: возможно совершенный искусственный разум опасен для человечества?
Освоить востребованную профессию в Data Science можно всего за полтора года на курсах GeekBrains. После учёбы вы сможете работать по специальностям Data Scientist, Data Analyst, Machine Learning, Engineer Computer Vision-специалист или NLP-специалист.
На этой неделе вы могли прочитать крайне мотивирующей кейс от Валерия Турова, где он рассказал об одной из своих целей, которая привела в профессию – желанию познать принцип работы и научиться создавать самому игровых ботов.
А ведь действительно, именно желание создать совершенный искусственный интеллект, будь то игровая модель или мобильная программа, сподвигла на путь программиста многих из нас. Проблема в том, что за тоннами учебного материала и суровой действительностью заказчиков, это самое желание было заменено простым стремлением к саморазвитию. Для тех, кто так и не приступил к исполнению детской мечты, далее краткий путеводитель по созданию настоящего искусственного разума.
Стадия 1. Разочарование
Когда мы говорим о создании хотя бы простых ботов, глаза наполняются блеском, а в голове мелькают сотни идей, что он должен уметь делать. Однако, когда дело доходит до реализации, оказывается, что ключом к разгадке реальной модели поведения является. математика. Если быть немного конкретнее, то вот список её разделов, которые необходимо проштудировать хотя бы в формате университетского образования:
Теория вероятностей и математическая статистика.
Это тот научный плацдарм, на котором будут строится ваше дальнейшее программирование. Без знания и понимания этой теории все задумки быстро разобьются о взаимодействие с человеком, ведь искусственный разум на самом деле не больше, чем набор формул.
Стадия 2. Принятие
Когда спесь немного сбита студенческой литературой, можно приступать к изучению языков. Бросаться на LISP или другие функциональные языки пока не стоит, для начала надо научиться работать с переменными и однозначными состояниями. Как для быстрого изучения, так и дальнейшего развития прекрасно подойдёт Python, но в целом можно взять за основу любой язык, имеющий соответствующие библиотеки.
Стадия 3. Развитие
Теперь переходим непосредственно к теории ИИ. Их условно можно разделить на 3 категории:
Слабый ИИ – боты, которых мы видим в компьютерных играх, или простые подручные помощники, вроде Siri. Они или выполняют узкоспециализированные задачи или являются незначительным комплексом таковых, а любая непредсказуемость взаимодействия ставит их в тупик.
Сильный ИИ – это машины, интеллект которых сопоставим с человеческим мозгом. На сегодняшний день нет реальных представителей этого класса, но компьютеры, вроде Watson очень близки к достижению этой цели.
Совершенные ИИ – будущее, машинный мозг, который превзойдёт наши возможности. Именно об опасности таких разработок предупреждают Стивен Хоккинг, Элон Маск и кинофраншиза «Терминатор».
Естественно, начинать следует с самых простых ботов. Для этого вспомните старую-добрую игру «Крестики-нолики» при использовании поля 3х3 и постарайтесь выяснить для себя основные алгоритмы действий: вероятность победы при безошибочных действиях, наиболее удачные места на поле для расположения фигуры, необходимость сводить игру к ничьей и так далее.
Сыграв несколько десятков партий и анализируя собственные действия, вы наверняка сможете выделить все важные аспекты и переписать их в машинный код. Если нет, то продолжайте думать, а эта ссылка здесь полежит на всякий случай.
К слову, если вы всё-таки взялись за язык Python, то создать довольно простого бота можно обратившись к этому подробному мануалу. Для других языков, таких как C++ или Java, вам также не составит труда найти пошаговые материалы. Почувствовав, что за созданием ИИ нет ничего сверхъестественного, вы сможете смело закрыть браузер и приступить к личным экспериментам.
Стадия 4. Азарт
Теперь, когда дело сдвинулось с мёртвой точки, вам наверняка хочется создать что-то более серьёзное. В этом вам поможет ряд следующих ресурсов:
Как вы поняли даже из названий, это API, которые позволят без лишних затрат времени создать некоторое подобие серьёзного ИИ.
Стадия 5. Работа
Теперь же, когда вы уже вполне ясно представляете, как ИИ создавать и чем при этом пользоваться, пора выводить свои знания на новый уровень. Во-первых, для этого потребуется изучение дисциплины, которое носит название «Машинное обучение». Во-вторых, необходимо научиться работать с соответствующими библиотеками выбранного языка программирования. Для рассматриваемого нами Python это Scikit-learn, NLTK, SciPy, PyBrain и Nump. В-третьих, в развитии никуда не обойтись от функционального программирования. Ну и самое главное, вы теперь сможете читать литературу о ИИ с полным пониманием дела:
И да, вся или почти вся литература по данной тематике представлена на иностранном языке, поэтому если хотите заниматься созданием ИИ профессионально необходимо подтянуть свой английский до технического уровня. Если вы только начинаете путь к мечте, советуем записаться на бесплатный двухчасовой интенсив по основам программирования.
В остальном, ваше дальнейшее развитие будет зависеть лишь от практики и желания усложнять алгоритмы. Но будьте осторожны: возможно совершенный искусственный разум опасен для человечества?
Освоить востребованную профессию в Data Science можно всего за полтора года на курсах GeekBrains. После учёбы вы сможете работать по специальностям Data Scientist, Data Analyst, Machine Learning, Engineer Computer Vision-специалист или NLP-специалист.
Выращивание искусственного интеллекта на примере простой игры
В этой статье я поделюсь опытом выращивания простейшего искусственного интеллекта (ИИ) с использованием генетического алгоритма, а также расскажу про минимальный набор команд, необходимый для формирования любого поведения.
Результатом работы стало то, что ИИ, не зная правил, самостоятельно освоил игру крестики-нолики и нашел слабости ботов, которые играли против него. Но начал я с еще более простой задачи.
Набор команд
Все началось с подготовки набора команд, которым мог располагать ИИ. Языки высокого уровня содержат сотни различных операторов. Чтобы выделить необходимый минимум, я решил обратиться к языку Ассемблер. Однако, оказалось, что и он содержит множество команд.
Мне требовалось, чтобы ИИ мог читать и выводить данные, работать с памятью, выполнять вычисления и логические операции, делать переходы и циклы. Я наткнулся на язык Brainfuck, который содержит всего 8 команд и может выполнять любые вычисления (т.е. полон по Тьюрингу). В принципе, он подходит для генетического программирования, но я пошел дальше.
Я задался вопросом: какое минимальное количество команд необходимо для реализации любого алгоритма? Как оказалось — одна!
Процессор URISC содержит всего одну команду: вычесть и пропустить следующую инструкцию, если вычитаемое было больше уменьшаемого. Этого достаточно для построения любого алгоритма.
Олег Мазонка пошел еще дальше, он разработал команду BitBitJump и доказал, что она полна по Тьюрингу. Команда содержит три адреса, копирует один бит из первого по второму адресу памяти и передает управление на третий адрес.
Позаимствовав идеи Олега, для упрощения работы, я разработал команду SumIfJump. Команда содержит четыре операнда: A, B, C, D и выполняет следующее: к ячейке по адресу B прибавляет данные из ячейки по адресу A, если значение получилось больше заданного*, то переходит по адресу C, иначе переходит по адресу D.
Когда операнд A обращается к ячейке памяти N0, происходит ввод данных, а когда к ячейке N1, то вывод.
Ниже представлен код SumIfJump на FreePascal (бесплатный аналог Delphi).
SumIfJump реализует самомодифицируемый код. Может выполнять любые алгоритмы, доступные на обычном языке программирования. Код легко изменяется и выдерживает любые манипуляции.
Простая задача
Итак, у нашего ИИ всего одна команда. Пока крестики-нолики для него очень сложная игра, и я начал с более простой.
Бот выдает случайное число, а ИИ должен считать данные и дать ответ. Если число больше среднего (от диапазона случайных чисел), ИИ должен выдать число меньше среднего и наоборот.
Геном нашего ИИ состоит из 256 ячеек со значениями от 0 до 255. Каждое значение — это и память, и код, и адрес. Количество шагов выполнения кода ограничено 256. Операнды читаются друг за другом.
Первоначально геном формируется набором случайных чисел, поэтому ИИ не знает, во что ему нужно играть. Более того, он не знает, что нужно последовательно вводить и выводить данные, отвечая боту.
Популяция и отбор
Первая популяция состоит из 256 ИИ, которые начинают играть с ботом. Если ИИ совершает правильные действия, например, запросил данные на ввод, а потом что-то вывел, то ИИ получает очки. Чем больше правильных действий, тем больше очков.
16 ИИ, которые набрали больше всего очков, дают по 15 потомков и продолжают участвовать в игре. Потомок — это мутант. Мутация происходит заменой у копии родителя одной случайной ячейки на случайное значение.
Если в первой популяции ни один ИИ не набрал очков, формируется следующая популяция. И так до тех пор, пока какой-нибудь из ИИ не начнет совершать правильные действия и давать «правильное» потомство.
Эволюция
| N | Вехи |
|---|---|
| 1 | ИИ ничего не делает. Программа совершает 256 шагов и завершается. |
| 2 | Начал запрашивать данные. |
| 3 | Начал запрашивать данные и что-то выводить. Последовательность запросов и ответов хаотичная. |
| 4 | Ввод и вывод данных происходит последовательно, иногда возникают ошибки. В половине случаев ИИ дает правильный ответ. |
| 5 | Регулярно дает правильные ответы, но иногда возникают ошибки. |
| 6 | Дал правильный ответ в 30 тыс. итерациях. Отбор закочен. |
Между значимыми событиями проходили тысячи смен поколений. Программа была запущена в несколько потоков на Core i7. Вычисления заняли около 15 минут.
Интересные моменты
Заключение
В заключение я проделал то же с игрой крестики-нолики. Размер генома использовал тот, что и в первом случае. Количество шагов было увеличено до 1024, а размер популяции до 64 (для более быстрого расчета). Расчет занял несколько больше времени. Все происходило примерно по тому же сценарию.
Сначала ИИ играл против «рандомайзера». Я так назвал бота, который ходит случайным образом. Довольно быстро ИИ начал его обыгрывать, заполняя какую-либо строчку. Далее я усложнил задачу, добавив рандомайзеру немного разума: занимать линию, если есть возможность, либо защищаться. Однако, и в этом случае ИИ нашел слабости бота и стал обыгрывать его. Пожалуй, рассказ об этом — это тема для отдельной статьи.
Сын просил написать программу, чтоб ИИ играли между собой, а не с ботом. Были идеи сделать то же для игры шашки или го, однако, для этого у меня уже не хватило времени.
Единственный метод, который я применял для получения новых особей, — это мутация. Можно также использовать кроссовер и инверсию. Возможно, эти методы ускорят получение требуемого результата.
В конце родилась идея: дать ИИ возможность управлять всеми процессами на ПК и бороться за ресурсы компьютера. Подключить ПК к интернету, а в качестве вычислительных мощностей использовать пул старых биткойн ферм…
Как сказал, проводя аналогичный эксперимент, блогер Михаил Царьков:
Может, они мир захватят, а вдруг?