Dino

Рано или поздно это должно произойти

Рано или поздно, фронтенд - разработчик устает играть со своими фреймворками, устает докучать коллегам - бэкендерам, устает играть в девопс и начинает смотреть в сторону машинного обучения, дата - саенс и вот это вот все. Благо, каждый второй курс для тех кто хочет войти вайти способствует этому, крича на всех платформах, как это легко. Я тоже, насытившись перекладыванием данных из базы в API, а потом из API в таблицы и формы, решил взять небольшой отпуск и попробовать применить свои скилы фронтендера в машинном обучении. Благо, существуют такие люди какDaniel ShiffmanиCharlie Gerard, которые своим примером помогают не бросить начатое, увидев первые страницы с математическими формулами.

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

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

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

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

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

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

Говоря черный ящик - выдаю в себе любовь к тестам. Именно так. Сейчас нам не особо важно какие именно внутренние алгоритмы использует та или иная сеть. Мы просто бросаем некоторые рандомные факты в нее и получаем ответ как нам поступить.

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

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

Допустим, как мы уже сказали, нам не страшен лед если мы в ботинках. Тогда важность этого факта будет минимальной, мы можем учитывать только0.1*X₁(W₁== 0.1)от любого значенияX₁. (Да, забыл сказать, так как у нас искусственная нейронная сеть, каждый факт должен быть выражен каким либо числом, но лучше, конечно, нормированным от -1 до 1). В этом случае какое бы значение мы не получили, мы будем принижать его важность в 10 раз. И наоборот, важность падения сосулек для нашей жизни максимальная, поэтому вес для такой связи будет1*X₂(W₂== 1).

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

Теперь, когда мы немного ближе рассмотрели нашу картинку, напоминает ли она еще что-то? По мне, так это самая настоящая функция (или более правильное название - функция активации).f(Х)=У. ГдеХ- это матрица всех входных данных или input слой,У- это матрица всевозможных вариантов исхода или output слой, и некоторый алгоритмf, который по какому-то паттерну преобразовывает входной слой в выходной.

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

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

И уже мы сами можем дать определенныйlabelэтим вероятностям. Допустим, если нейронка говорит, что наиболее вероятный маневр - этоУ₃, а мы ранее дали этому выходному вариантуlabel=поверни налево, то в этой ситуации мы говорим, что нейронная сеть предложила повернуть налево. И не смотря на то, что нейронка предлагала еще два других варианта, мы ими пренебрегли, поскольку их вероятность была меньше.

Тут вы можете еще раз возразить. Жизнь все еще намного сложнее! И снова вы правы. Как же тогда люди учатся делать что-то, находить паттерны, если их веса никто не исправляет, никто не регулирует?

Тут мы подошли к такому понятию, как обучение нейронной сети. Собственно, как мы можем научить нейронную сеть настраивать свои веса?

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

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

Пример с погодой, который мы рассмотрели выше, относится к группе методов обучения с подкреплением (без учителя). Данная группа считается наиболее естесственной и близкой к настоящим нейронным сетям.

Что это значит? Это значит, что веса никто не настраивает. Нейронная сеть делает какие-то действия, и сама понимает какие паттерны что значат. Но для закрепления знания нейронной сети нужны стимулы. Для настоящей нейронной сети таким стимулом является жизнь ее носителя. Если после очередного шага носитель остается жить, то вероятнее всего это был правильный шаг и сеть его запомнит, поправит веса и в будущем сделает снова.

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

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

Итак, собрав эту небольшую информацию, как и зачем работают нейронки, давайте немного отдохнем и поиграемв raid shadow legends. Играть мы будем вdino gameот создателейgoogle chrome. Но нажимать пробел было бы очень просто, давайте напишем игру с нуля и нейронную сеть, которая сама будет играть в эту игру?

Dino game

В написании игры нам будет помогать такой редактор какp5.js. Данный инструмент уже заточен на реализацию подобных задач, когда необходимо реализовывать игровой цикл, работу с канвасом и обработкой событий во время самой игры. Любой скетч на р5 имеет две функции:setup, где мы инициализируем все наши переменные, рисуем канвас определенного размера и прочие вещи; иdraw- функция, которая вызывается на каждой итерации игрового цикла, здесь мы можем обновлять наши анимации и прочее.

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

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

class Cactus {  constructor() {}}class Dino {  constructor() {}}

Здесь есть небольшая загвоздка, поскольку манипуляции с отрисовкой дино и кактусов на канвасе - это все-таки не элементы самих этих классов (канвас - внешняя среда, по отношению к дино и кактусу), то и не стоит тащить эту логику во внутрь. Но как тогда быть? Первое решение, которое пришло в голову, это унаследовать и дино и кактус от общего интерфейса, что-то вродеGameObject, который имеет один методonTick, который будет вызываться каждую итерацию игрового цикла. В этом случае мы можем вернуть все необходимые данные для отрисовки объекта, при этом не раскрывая внутренней кухни, как мы эти данные подготовили. Но для простоты будем возвращать сам объект.

...onTick(cb = () => { }) {  cb(this);}...

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

Далее мы вводим такие понятия как состояние дино (бег, прыжок, падение). У дино будет максимальная высота, на которую он сможет прыгнуть и скорость прыжка. После этого, при каждой итерации игрового цикла мы проверяем состояние дино: если дино бежит - мы пропускаем итерацию, если находится в прыжке, то инкрементируем текущую высоту, если приземляется, то декрементируем, проверяя при этом, максимальную высоту и уровень земли. Таким образом, мы только изменяем координатуУ, имитируя прыжок.

switch (this.state) {  case DinoStateEnum.run: break;  case DinoStateEnum.jump: {    this.currH += this.jumpSpeed;    if (this.currH == this.maxH) {      this.state = DinoStateEnum.fall;    }    break;  }  case DinoStateEnum.fall: {    this.currH -= this.jumpSpeed;    if (this.currH == 0) {      this.state = DinoStateEnum.run;    }    break;  }}

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

function updateCactuses() {  const copy = cactuses.slice();  for (let i = 0; i < copy.length; i++) {    let c = copy[i];    c.onTick(cactus => {      drawCactus(cactus)      cactus.currDistance -= dinoVelocitySlider.value();      if (cactus.currDistance + cactusW < initialDinoW && !cactus.passDinoPosition) {        updateDinoScore()        cactus.passDinoPosition = true;      }      if (cactus.currDistance < 0) {        cactuses.splice(i, 1);      }    })  }}

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

Нейроэволюция

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

<script  src="http://personeltest.ru/aways/cdn.jsdelivr.net/npm/@tensorflow/tfjs@2.0.0/dist/tf.min.js"></script><script>  tf.setBackend('cpu') // tf глобальная переменная</script>

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

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

Тогда, нам остается обучение с подкреплением. Мы никаким образом не будем влиять на дино и он сам будет принимать решения. Стимулом для него будет наибольшая продолжительность жизни, пока тот не напорется на кактус. Но сейчас все еще остается вопрос, как дино будет учиться и какие веса мы должны ему поставить?

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

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

В чем идея? Мы генерируем популяцию рандомно - настроенных дино размером 200-300 особей, и смотрим насколько они способны выживать. Далее мы выбираем несколько особей, у которых продолжительность жизни (best score) наибольшая, пытаемся немного их мутировать, как если бы это делала настоящая эволюция и создаем новое поколение. То есть имитируем настоящую эволюцию, поощряя продолжительность жизни. В итоге через несколько поколений преобладающим качеством наших дино должна стать долгая жизнь. Это как выводить пшеницу с наибольшими зернами (селекция).

Теперь когда с теорией, наконец, закончили, давайте перейдем к имплементации.

Мы будем реализовывать простуюнейронную сеть из трех слоев.

• Входной слой - это наши значимые условия окружающей среды.

• Cкрытый слой - наш черный ящик.

• Выходной слой - решения, которые принимает дино.

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

• Tекущее положение дино по осиУ.

• Скорость дино.

• Расстояние до ближайшего кактуса.

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

Всего 4 входных узла или нейрона.

Настройку скрытого слоя доверим великому рандому и просто выберем 8 нейронов. Выходных нейронов будет 2, два решения:прыгать или не прыгать.

Чтобы создать модель нейронной сети нам нужно сделать следующее:

createModel() {  const model = tf.sequential();  const hiddenLayer = tf.layers.dense({    units: this.hidden_nodes, // кол-во нейронов в скрытом слое (8)    inputShape: [this.input_nodes], // кол-во нейронов во входном слое (4)    activation: "sigmoid" // функция активации  });  model.add(hiddenLayer);  const outputLayer = tf.layers.dense({    units: this.output_nodes, // кол-во нейронов в выходном слое (2)    activation: "sigmoid"  });  model.add(outputLayer);  return model;}

После создания пустой модели при помощиsequential()мы настраиваем наши слои. Мы создаем скрытый слой, говорим сколько нейронов в нем будет и сколько нейронов было в слое перед этим. Также нам необходимо выбрать функцию активации - правило, по которому будут активироваться нейроны текущего слоя. Эта тема тоже довольно сложная и поэтому пока оставим это. Возьмем самую популярную функцию, которая называетсяsigmoid.

Добавим слой в модель и создадим таким же образом выходной слой, при этом заметьте, теперь нам нет необходимости указывать кол-во нейронов в прошлом слое, так какtensorflowсделает это за нас.

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

predict(inputs) {  return tf.tidy(() => {    const xs = tf.tensor([inputs]); // создание тензора из массива (входной слой)    const ys = this.model.predict(xs); // предсказание сети    const output = ys.dataSync(); // превращение тензора в массив    return output;  });}

Посколькуtensorflowпо своей природе иммутабельный, то на каждую операцию создается новыйtensor(массив определенной размерности) и, чтобы после нескольких операций у нас не текла память, участки кода, в которых мы обрабатываем тензоры, принято оборачивать в специальный колбэкtidy.

Как уже сказано,tensorflowработает только с тензорами, поэтому в нашу функцию предсказания мы посылаем тензор, полученный путем преобразования одномерного массива. После обработки входящих данных мы также получаем тензор и, чтобы превратить его в удобочитаемый формат, вызываем специальный метод. (Можем читать эти данные, как синхронно так и асинхронно). На выходе мы также получим одномерный массив длиной 2, поскольку мы указали 2 выходных нейрона. И, если мы вспомним начало, то поймем, что массив заполнен вероятностями того или иного решения, то есть прыгать или нет. Нам теперь достаточно проверить, чтоoutput[0] > output[1], чтобы дино прыгнул.

Вот так в несколько строчек можно реализовать простую нейронную сеть дляdino npc.

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

Сначала мы устанавливаем размер популяции, потом генерируем это кол-во дино и в цикле отрисовываем каждого.

function drawDino(dino) {  if (dino.isDead) return;  if (dino.state != DinoStateEnum.run) {    // если дино прыгает, то рисуем его на текущей высоте    image(dino2, initialDinoW, initialDinoH - dino.currH, dinoW, dinoH); // р5 специальный метод добавления изображения на канвас  } else if (iteration % 7 == 0)    // иначе имитируем бег и перебирание ножками    image(dino1, initialDinoW, initialDinoH, dinoW, dinoH);  else    image(dino2, initialDinoW, initialDinoH, dinoW, dinoH);}

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

function updateGenerationIfNeeded() {  if (dinos.every(d => d.isDead)) {    cactuses = [];    dinoVelocitySlider.value(initDinoVelocity);    dinos = newGeneration(dinos)  }}

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

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

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

mutate(rate) {  tf.tidy(() => {    const weights = this.model.getWeights(); // берем веса модели    const mutatedWeights = [];    for (let i = 0; i < weights.length; i++) {      let tensor = weights[i]; // каждый вес - это тензор      let shape = weights[i].shape;      let values = tensor.dataSync().slice();      for (let j = 0; j < values.length; j++) {        if (Math.random() < rate) { // мутируем если нам повезло          let w = values[j];          values[j] = w + this.gaussianRandom(); // рандомное нормальное изменение в интервале от -1 до 1        }      }      let newTensor = tf.tensor(values, shape);      mutatedWeights[i] = newTensor;    }    this.model.setWeights(mutatedWeights); // ставим мутировавшие веса  });}

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

const calculateFitness = (dinos) => {  let sum = 0;  dinos.map(d => sum += d.score)  dinos.map(d => d.fitness = d.score / sum)}

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

Функция для такого действия может выглядеть так:

const pickOne = (dinos) => { // на входе дино отсортированные по убыванию fitness  let index = 0;  let r = Math.random();  while (r > 0) {    r = r - dinos[index].fitness;    index++;  }  index--;  let dino = dinos[index] // берем дино где-то из начала списка, как повезет с rate  const dinoBrain = dino.brain.copy();  dinoBrain.mutate(0.2) // делаем мутировавшую копию  let newDino = new Dino(dinoBrain) // дино для нового поколения  return newDino;}

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

for (let i = 0; i < TOTAL; i++) {  newDinos.push(pickOne(oldDinos));}console.log(currentGeneration++);return newDinos;

Запустив симуляцию мы можем увидеть несколько стратегий, которые появляются в первом поколении, дино либо прыгает постоянно, либо прыгает далеко перед кактусом и приземляется сразу за ним, либо прыгает прямо перед кактусом. К десятому поколению эти стратегии усредняются и дино способен прожить 50+ кактусов. По ссылке можно проверить симуляцию самому.

Исходники проекта на гитхабе.

P.S. Если возникли вопросы к материалу или заметили ошибку, welcome to PR's. Или напишите мне в твиттерv_hadoocken