Я познакомлю вас с полным туториалом на HTML5 с демо по алгоритму машинного обучения видеоигре Flappy Bird. Цель этого эксперимента — написать игровой контроллер искусственного интеллекта на основе нейросетей и генетического алгоритма.

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

Прочитав теорию, лежащую в основе этого проекта, можно скачать исходный код в конце этого туториала. Весь код написан на HTML5 с использованием фреймворка Phaser. Кроме того, мы использовали библиотеку Synaptic Neural Network для реализации нейросети, чтобы не создавать её с нуля.

Демо


Для начала посмотрите демо, чтобы оценить алгоритм в действии:



Запустить в полноэкранном режиме

Видеопрезентация


В дополнение к демо вы можете посмотреть короткое видео с простым объяснением алгоритма. Понравится тем, кто любит получать информацию быстро!


Что такое «алгоритм машинного обучения»


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

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

Конкретно в этом проекте, основной подход к машинному обучению (machine learning algorithm, ML) основан на нейроэволюции. В этой форме машинного обучения используются эволюционные алгоритмы, такие как генетический алгоритм (genetic algorithm, GA), для обучения искусственных нейронных сетей (artificial neural networks, ANN).

То есть в нашем случае можно сказать, что ML = GA + ANN.

Искусственная нейронная сеть


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

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

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

В этом проекте каждый объект (птица) имеет собственную нейронную сеть, используемую в качестве ИИ-мозга для прохождения игры. Она состоит из следующих трёх слоёв:

  1. слой входных данных с двумя нейронами представляет то, что видит птица:
    • горизонтальное расстояние до ближайшего промежутка
    • разница высот с ближайшим промежутком
  2. скрытый слой с шестью нейронами
  3. слой выходных данных с одним нейроном, создающий действие:
    • если выходные данные > 0,5, то сделать рывок, в противном случае не делать ничего

На рисунке ниже показана архитектура нейронной сети для этого примера:

Machine Learning Algorithm for Flappy Bird - Neural Network

Генетический алгоритм


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

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

Вот основные этапы реализации нашего генетического алгоритма:

  1. создаём исходную популяцию из 10 объектов (птиц) со случайными нейронными сетями
  2. даём всем объектам играть одновременно с использованием их собственных нейронных сетей
  3. у каждого объекта вычисляем его функцию приспособленности для оценки его качества (подробнее см. в разделе Функция приспособленности)
  4. после смерти всех объектов оцениваем текущее поколение для создания нового с помощью генетических операторов (подробнее см. в разделе Стратегия замены)
  5. возвращаемся к этапу 2

Функция приспособленности


В дополнение к генетическому алгоритму (этап 3), мы рассмотрим здесь подробнее функцию приспособленности — что это такое и как её определить.

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

В общем случае, функция приспособленности — это метрика, измеряющая качество объекта. Если у нас будет метрика качества каждой птицы, мы сможем выбрать самые приспособленные объекты и использовать их для воссоздания следующего поколения.

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

Подведём итог: наша функция приспособленности — это разность между общим расстоянием, проделанным птицей, и текущим расстоянием до ближайшего промежутка.

Machine Learning Algorithm for Flappy Bird - Fitness Function

Стратегия замены


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

  1. сортируем объекты текущего поколения по их уровню приспособленности
  2. выбираем четыре лучших объекта (победителей) и передаём их непосредственно в следующее поколение
  3. создаём одного потомка как результат кроссинговера между двумя наилучшими победителями
  4. создаём трёх потомков как результаты кроссинговера двух случайных победителей
  5. создаём двух потомков как прямые копии двух случайных победителей
  6. применяем к каждому потомку случайные мутации, чтобы добавить вариативности

Исходный код


И вот, наконец, ссылка для скачивания исходного кода:

https://github.com/ssusnic/Machine-Learning-Flappy-Bird

Алгоритм машинного обучения для Flappy Bird — заключение


В этом туториале мы успешно реализовали ИИ-робота для обучения игре во Flappy Bird. В результате нескольких итераций мы можем получить почти неуязвимого игрока. Для достижения этой цели мы использовали два подхода к алгоритмам машинного обучения: искусственные нейронные сети и генетический алгоритм.

Для эксперимента можете попробовать изменить некоторые из параметров в коде и посмотреть, что произойдёт. Например, вы можете изменить количество нейронов в скрытом слое или количество объектов в популяции. Кроме того, можете попробовать изменить функции приспособленности. Более того, попробуйте менять некоторые физические параметры — расстояния между препятствиями, гравитацию и так далее.

Попробуйте также применить тот же подход к эволюции в других играх.

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


  1. Tutanhomon
    30.08.2017 16:11
    +4

    Полный профан в нейронных сетях (я).
    Не пойму, почему в скрытом слое именно шесть нейронов? Из каких соображений выбирается это число? Что за данные идут по каждому из шести синапсов между входным и скрытым слоем? Со входом и выходом все понятно…


    1. Rai220
      30.08.2017 17:14

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


    1. NecroKote
      30.08.2017 18:01

      Сам далеко не спец в теме, но могу предположить, что на скрытый слой попадают те же нормальзованные значения (-1… +1) горизонтального и вертикального расстояния от центра «птицы» до следующего препятствия (т.к ничего не сказано про входные нейроны — считаем их априори «копирующими»)

      Касательно именно 6 нейронов на скрытом слое — предположу что тут замешано «восприятие» сетью положения птички, на основании входных данных (+\-напротив препятствия, +\-напротив перехода от препятствия к пролёту, напротив пролёта, не вижу препятствия).

      Все изложенное — некомпетентное ИМХО и мне тоже хотелось бы услышать «правильный ответ» от разбирающихся товарищей.


    1. Stawros
      30.08.2017 18:01
      +8

      Упрощенно можно рассматривать нейронную (перцептрон) сеть как систему уравнений n-ой степени. Где переменные — это входные значения, количество нейронов в слое = количество коэффициентов, веса нейронов — значения коэффициентов, а количество слоёв — степень уравнений.
      Чтобы понять что мы вообще аппроксимируем нужно построить график — по оси X расстояние до отверстия, а по оси Y — расстояние до центра отверстия. Теперь на пересечении каждого значения, где нужно прыгнуть поставьте точку. Соедините точки и получившаяся фигура и будет то, что мы хотим построить.
      Если вы можете без нейронной сети написать функцию, которая строит такую фигуру — вам нейронные сети не нужны. Если напишите систему уравнений, которые решают ту же задачу — тоже. Если же думать не хочется — можно задать примерную структуру системы уравнений, которая теоретически должна решать задачу (т.е. выбрать структуру нейронной сети) и пусть компьютер подбирает коэффициенты этой системы уравнений (имеется в виду процесс обучения сети).
      Количество слоев выбирается исходя из сложности функции, которую мы хотим решить (аппроксимировать). Логично, что для аппроксимации прямой хватает 2-х слоёв, а вот гиперболу двумя слоями не аппроксимируешь.
      Количество нейронов же обычно подбирается экспериментально. Все упирается во время обучения и итоговую точность, которую нужно получить. В общем данные, которые идут после нейронов скрытого слоя это произведение очередного коэффициента и входящего значения. Для данного случая:
      A1*x + A2*x +… +A6*x = 0.5
      A1*y + A2*y +… +A6*y = 0.5
      где An = вес нейрона, x и y — входящие значения.


      1. Tutanhomon
        30.08.2017 19:13

        Спасибо, что-то начинает вырисовываться.


      1. Zolg
        30.08.2017 19:55
        +1

        Для данного случая:
        A1*x + A2*x +… +A6*x = 0.5
        A1*y + A2*y +… +A6*y = 0.5

        а смысл в 6 нейронах тогда?
        A1*x + A2*x +… +A6*x = (A1+A2+...+A6)*x = As*x


        1. erwins22
          30.08.2017 20:52
          -1

          после вычисления второго слоя применяется функция активации. Последнее время обычно используют просто зануление отрицательной части.


        1. Stawros
          30.08.2017 22:28

          Да, это я как-то очень не удачно пример привёл, а отредактировать из-за премодерации никак. Не столько упростил, сколько запутал. На самом деле весов много (каждая стрелочка на картике — это коэффициент An). Можно давать им трёхзначный коэффициент A111 = вес передачи с 1-ого слоя от 1-ого входа, в 1-й нейрон второго слоя. Количество нейронов в слое влияет не столько на количество коэффициентов в уравнениях, сколько количество самих уравнений в системе. Т.е. допустим наш график — клякса. Каждая выпуклость кляксы — полуокружность. Чем точнее мы хотим её аппорксимировать сетью с двумя слоями, тем больше нам понадобится уравнений полуокружностей — т.е. больше нейронов должно быть в скрытых слоях. Можно, конечно, повышать степень (количество слоев) и описывать уже кусочками N образных кривых уравнений 3-ей степени. Поэтому и получается, что подбор структуры сети процесс творческий.


    1. begemot_sun
      31.08.2017 14:33
      -1

      Это чистая эвристика. Вы можете использовать любое кол-во нейронов в скрытом слое, как и самих слоев. Вся суть НС (с учителем) в том, чтоб она аппроксимирует вход на выход. Т.е. это обычная аппроксимация функцией нескольких переменных.

      > Что за данные идут по каждому из шести синапсов
      это не важно, для вая НС это черный ящык. Никто не в состоянии интерпретировать внутренние данные НС. В общем случае НС внутри обощает паттерны, выделяет среди них общие и использует эти данные для следующих слоев.


      1. erwins22
        31.08.2017 20:48

        Однослойные нейронные сети (с одним скрытым слоем) как в этом случае легко интерпретируются.


        1. begemot_sun
          31.08.2017 21:11

          Где про это почитать?


          1. erwins22
            01.09.2017 07:17
            +1

            habrahabr.ru/post/322438
            просто посмотрите картинки аппроксимацией нейронной сети с одном скрытым слоем.


  1. Mirn
    30.08.2017 22:21

    а что будет с сетью если добавить немножко проблем из реального мира?


    например:
    входа не точные и шумят, порой сильно или работают "на глаз" 100-200 пикс. например
    входа имеют гистерезис т.е. из за малого выходного воздействия могут не измениться.
    датчики имеют задержку по времени которая может изменяться со временем.
    в популяции могут погибать так же и лидирующие особи, например с большим шансом в 20%
    внешнее воздействие может не сработать или иногда сработать в обратную сторону


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


    1. anprs
      31.08.2017 06:55

      Видимо, сеть будет дольше учиться


  1. zigrus
    30.08.2017 22:37
    -5

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


    1. Stawros
      30.08.2017 22:54
      -1

      Нет, если сеть обучилась Flappy Bird, в тетрис она играть не сможет. Теоретически можно построить сеть, которая будет одним входом принимать игру (1 = тетерис / 0 = Flappy Bird), а остальными входами — параметры текущей итерации (хода в игре), но сложность обучения такой сети будет много выше, чем суммарная сложность обучения двух разных сетей (нужно не только научится играть, но и чтобы нейроны, решающие повернуть фигуру в тетрис или нет не реагировали на расстояние до центра отверстия во Flappy Bird). При этом ещё количество входов и выходов различно — строить придется с максимальным количеством входных и выходных нейронов, просто если текущая игра — Flappy Bird, то значение будет только в первом нейроне, остальные должны давать 0.


  1. Kirhgoff
    31.08.2017 07:58

    Жалко не описано, как устроен ген и механизм кроссинговера, это же самое интересное. Пойду читать код


  1. mayorovp
    31.08.2017 08:53
    +3

    Надо упомянуть, что у этой игры есть и строгое математическое решение: https://habrahabr.ru/post/217645/