Выращивание искусственного интеллекта на примере простой игры



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

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

Набор команд


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

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

Я задался вопросом: какое минимальное количество команд необходимо для реализации любого алгоритма? Как оказалось — одна!

Процессор URISC содержит всего одну команду: вычесть и пропустить следующую инструкцию, если вычитаемое было больше уменьшаемого. Этого достаточно для построения любого алгоритма.

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

Позаимствовав идеи Олега, для упрощения работы, я разработал команду SumIfJump. Команда содержит четыре операнда: A, B, C, D и выполняет следующее: к ячейке по адресу B прибавляет данные из ячейки по адресу A, если значение получилось больше заданного*, то переходит по адресу C, иначе переходит по адресу D.

Примечание
*В данном случае использовалось 128 — половина от длинны генома.

Когда операнд A обращается к ячейке памяти N0, происходит ввод данных, а когда к ячейке N1, то вывод.

Ниже представлен код SumIfJump на FreePascal (бесплатный аналог Delphi).

procedure RunProg(s: TData);
var
  a, b, c, d: TData;

begin
  Inc(NStep);
  if NStep > MaxStep then
  begin
    ProgResult := 'MaxStep';
    Exit;
  end;

  a := s;
  b := s + 1;
  c := s + 2;
  d := s + 3;

  a := Prog[a];
  b := Prog[b];
  c := Prog[c];
  d := Prog[d];

  if a = 0 then
  begin
    ProgResult := 'Input';
    Exit;
  end;

  if a = 1 then
  begin
    ProgResult := 'Output';
    Exit;
  end;

  Prog[b] := Prog[b] + Prog[a];

  if Prog[b] < ProgLength div 2 then
    RunProg(c)
  else
    RunProg(d);
end;

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

Простая задача


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



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

Геном нашего ИИ состоит из 256 ячеек со значениями от 0 до 255. Каждое значение — это и память, и код, и адрес. Количество шагов выполнения кода ограничено 256. Операнды читаются друг за другом.

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

Популяция и отбор


Первая популяция состоит из 256 ИИ, которые начинают играть с ботом. Если ИИ совершает правильные действия, например, запросил данные на ввод, а потом что-то вывел, то ИИ получает очки. Чем больше правильных действий, тем больше очков.

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



Если в первой популяции ни один ИИ не набрал очков, формируется следующая популяция. И так до тех пор, пока какой-нибудь из ИИ не начнет совершать правильные действия и давать «правильное» потомство.

Эволюция


N Вехи
1 ИИ ничего не делает. Программа совершает 256 шагов и завершается.
2 Начал запрашивать данные.
3 Начал запрашивать данные и что-то выводить. Последовательность запросов и ответов хаотичная.
4 Ввод и вывод данных происходит последовательно, иногда возникают ошибки. В половине случаев ИИ дает правильный ответ.
5 Регулярно дает правильные ответы, но иногда возникают ошибки.
6 Дал правильный ответ в 30 тыс. итерациях. Отбор закочен.

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



Интересные моменты


  1. Когда ИИ «лидер» совершал случайную ошибку и не набирал достаточное количество очков, популяция начинала деградировать, т.к. потомство формировалось из «второстепенных» родителей.
  2. Бывало так, что в потоке с аутсайдерами, которые топтались на месте, происходила удачная мутация, обеспечивающая взрывной рост набираемых очков. После чего этот поток становился лидером.
  3. Иногда в течение долгого времени не происходило никаких удачных мутаций, и даже 500 тыс. поколений не хватало, чтобы завершить отбор.


Заключение


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

Сначала ИИ играл против «рандомайзера». Я так назвал бота, который ходит случайным образом. Довольно быстро ИИ начал его обыгрывать, заполняя какую-либо строчку. Далее я усложнил задачу, добавив рандомайзеру немного разума: занимать линию, если есть возможность, либо защищаться. Однако, и в этом случае ИИ нашел слабости бота и стал обыгрывать его. Пожалуй, рассказ об этом — это тема для отдельной статьи.

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

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

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

Как сказал, проводя аналогичный эксперимент, блогер Михаил Царьков:
Может, они мир захватят, а вдруг?

Ссылки


  1. Генетические алгоритмы
  2. Копирование Бита — Простейшая Вычислительная Машина / Олег Мазонка
  3. URISC — Википедия
  4. Полнота по Тьюрингу — Википедия
Поделиться публикацией
Никаких подозрительных скриптов, только релевантные баннеры. Не релевантные? Пиши на: adv@tmtm.ru с темой «Полундра»

Зачем оно вам?
Реклама
Комментарии 29
  • +4

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

    • +1
      Эти мощности умеют только считать SHA-1 хеши. В отрыве от биткоина довольно бесполезная задача.
      • 0
        Вдруг SHA-1 полон по Тьюрингу?
    • +1
      > Были идеи сделать то же для игры шашки или го, однако, для этого у меня уже не хватило времени.

      Как писал Норберт Винер, человека вполне можно передать по телеграфу, но в настоящий момент технические сложности представляются непреодолимыми.
      • +1
        С го вполне можно попробовать для начала на доске с небольшим количеством клеток.
        • 0
          Сложность была не столько техническая, сколько личная — мало свободного времени для программирования.
          • 0
            Да не, вы клёвую штуку сделали, и я понимаю, что, в принципе, это дело должно масштабироваться и под более сложные задачи. Ирония была про то, что в более сложных задачах частенько вылезают досадные мелочи, масштаб которых (и затраты времени, соответственно) бывает очень сложно оценить заранее :)
        • 0
          непонятно конечно, где же тут ИИ, если все четко алгоритмировано, и по факту состояние всегда зависит только от внешних сигналов, но никакой накопленной памяти нет
          • 0
            никакой накопленной памяти нет

            Память есть. ИИ берет данные из нулевого адреса (ячейка ввода) и может складывать их внутрь себя, далее обрабатывать их и выводить с учетом этого какой-либо результат.
            • 0
              то есть вся память это значение одной ячейки? но тогда будет очень мало вариантов развития событий, если бы была комбинация из 10 ячеек, тут уже можно было бы говорить о сложной памяти
              • 0
                Вся память — это весь геном: 256 ячеек.
            • 0
              Все, что ИИ положил «в себя», т.е. запомнил, так в нем и остается до тех пор, пока он играет с ботом.
            • +2
              Обратите внимание на этот интересный проект


              (ссылка на скачивание в описании к видео)

              Neural Guppies
              В этой симуляции автор реализовал простой самообучающийся ИИ с использованием генетического алгоритма.

              Из пояснений к видео:
              Goopies — это двумерные существа, которые живут в виртуальной среде.
              Каждое существо оснащено нейронной сетью и набором датчиков, которые позволяют
              «видеть» и «чувствовать» окружающую их среду.
              Там так же есть запперы, гранулы и трупы.
              запперы (синего цвета) при контакте с Гуппи забирают их энергию.
              Гранулы (зеленый) и трупы (красный) напротив, восстанавливают энергию Гуппи.
              Энергия также может переходить между Гуппи в зависимости от их текущего цвета (красного, зеленого и синего) как в «камень-бумага-ножницы» (красный бьет зеленый, зеленый бьет синий, синий бьет красный). Гуппи могут менять свой цвет, используя свои нейронные сети.
              Когда Гуппи умирают, выбираются наиболее подходящие особи для производства нового поколения. Их гены смешиваются с применением случайной мутации. Те особи, которые выживают дольше всех, имеют более высокую вероятность на передачу своих генов следующему поколению.
              Этот алгоритм имитирует «естественный отбор». На протяжении многих поколений можно ожидать что Гуппи будут становиться все более «умными», т.к. их нейронные сети станут более адаптированными к среде обитания.
              • 0
                По вашей наводке я обратил внимание на данный проект и… испытал горечь от того, что исходниками автор не делится. Не делится видимо из скромности, хотя графическое отображение происходящего очень и очень интересное. Больше всего в этом плане мне понравилась первая часть.
              • 0
                Тема очень интересная, и у меня возник ряд вопросов. Если найдете время ответить, буду очень признателен!

                1. Почему геном содержит именно 256 генов? Чем обусловлена эта цифра?
                2. Допустим ген содержит цифру 42 (или любую другую из возможных). И что это значит на практике? Как соотносится значения генов и действия, выполняемые Вашим ИИ?
                3. Как происходит процесс «обдумывания» очередного хода (крестики-нолики)? Или обученный таким образом ИИ на основе уже сделанных ходов просто «знает» какой ход ему нужно сделать. Значит ли это, что каждый раз на одни и те же действия бота будет один и тот же ответ ИИ?
                • 0
                  1. В зависимости от сложности задачи, можно сделать геном больше, но вычисления будут больше времени занимать. В моем случае этой длинны оказалось достаточно. Поскольку геном — это и код, и адреса памяти. Удобно использовать значения типа Byte — от 0 до 255, чтобы любые значения могли ссылаться на полный диапазон ячеек генома. Для более сложной задачи можно использовать тип данных Word от 0 до 65 535, тогда размер генома целесообразно делать 65 536 ячеек.
                  2. Допустим, ячейка N15 содержит цифру 42. При запуске с этого места операнд A будет обращаться к 42 ячейке памяти: возьмет от туда данные для добавления к адресу B. Адрес B будет взят из 16-ой ячейки (15 + 1).
                  3. Процесс обдумывания хода у ИИ достаточно сложный. Я пытался анализировать то, что он делает, но понять это достаточно трудно. Видно только, что он что-то «усиленно» считает перед тем, как дать ответ.
                    Здесь можно сделать по-разному. Я перезагружал ИИ после каждого боя с ботом, поэтому он начинал всякий раз одинаково и действовал однотипно. Можно между боями перегрузу не делать, тогда ИИ будет модифицироваться в процессе боя и вести себя всякий раз по-разному.
                  • 0
                    Спасибо, буду разбираться, т.к. подход достаточно необычный и заслуживает внимания.
                    • 0
                      Да забавная статья! И что еще более забавно, что ИИ превзошел создателя, если опираться на п3. :)
                      А можно посмотреть все исходники проекта? Может выложите на github?
                      • 0
                        Нельзя сказать, что ИИ превзошел создателя. Дело в том, что код из одной инструкции — это просто набор чисел. Поэтому, глядя на числа, очень трудно понять суть того, что происходит. Это только Нео из Матрицы умел делать :)

                        Код выложить могу, но позже, т.к. желательно провести рефакторинг и сделать минимальные инструкции, а на это нужно время.
                        • 0
                          Да было бы очень интересно посмотреть на завершенный проект, а то в общих словах как-то не очень понятно.
                          Понял только что буфер 256байт, есть набор примитивных инструкций 2или 3 работающих с этим буфером. То что «это» как-то работает это понятно и то что «ОНО» что-то вычисляет тоже понятно, непонятно другое: как оно взаимодействует и вообще хотелось бы отдельную более подробную статью про то как ОНО играет в крестики нолики…
                  • 0
                    Вовремя, кстати, статья подоспела, так как на этих выходных я решил-таки разобраться с генетическим алгоритмом в играх nes. Попробовал два разных подхода, первый — lua-скрипт в эмуляторе, работает почти идеально, за сутки решает уровень, но только для двух версий марио, а второй — самообучающаяся программа, которая может проходить довольно много игр. Очень интересно сделана, нужно сначала записать небольшой реплей с прогрессом, скормить обучалке, она сама проанализирует и решит, какой цели нужно добиваться. Процесс, правда, долгий, за сутки в 6 потоков набирается минута-две геймплея, но в любом случае, наблюдать за этим интересно.

                    В принципе, если кому-нибудь интересно, могу попробовать написать гайд по запуску, так как в процессе нарвался на несколько неочевидных вещей.
                    • 0
                      Как присваивались баллы в разных вехах?
                      • +1
                        В первой (простой) игре во всех вехах система баллов была одинаковая:
                        — один балл за запрос ввода;
                        — один балл за вывод чего-либо после ввода;
                        — один балл за правильный ответ.
                        И так по кругу, до тех пор пока ИИ не совершит ошибку.

                        В крестиках-ноликах система баллов была другой:
                        — по одному очку за правильный ввод и вывод;
                        — 100 очков за победу;
                        — 50 за ничью;
                        — 0 за поражение.
                        • 0
                          Запрос ввода и вывода был один раз в такт?
                          Что запрашивало и что выводило, поконкретнее? Например, в крестиках-ноликах опрашивалось содержание каждого поля и ставился крестик (нолик)?
                          • +1
                            В крестиках-ноликах бот ждал, когда ИИ начнет запрашивать данные на ввод. ИИ мог совершить некоторое количество вычислений перед тем, как запросить данные. То же и с выводом. Т.е. процесс ввода и вывода занимал у ИИ не по одному такту.

                            На ввод и вывод подавалось значение от 0 до 255. Занимаемая ячейка была той, что соответствовала остатку от целочисленного деления на 9. Например вводится «142»: 142 mod 9 = 7. Значит заполняется ячейка номер 7. Если она занята, то заполняется следующая свободная.

                            Ячейки нумеровались так:
                            0 1 2
                            3 4 5
                            6 7 8
                      • 0
                        Вы генетическим алгоритмом сделали автоматический аппроксиматор дерева решений крестиков-ноликов в код «одноинструкторного» процессора. Методы ИИ тут условно присутствует, конечно, но ИИ — не выращенный код, а сам генетический алгоритм, ищущий «дерево решений крестиков-ноликов в виде кода одноинструкторного процессора». (Возможно, моя критика не очень понятна и кажется лишь претензией к терминологии.)

                        Для применения генетического алгоритма необходима модель искомого «фенотипа решателя» (выращиваемого ИИ) такая, чтобы малые изменения генотипа приводили с высокой степенью вероятности либо к «летальному исходу», либо к малому изменению адаптивного успеха особи (т.е., чтобы случайными мутациями «нащупывался» неслучайный градиент приспособленности на условном ландшафте «репродуктивного успеха»). И в случае проекции «алгоритм игры в крестики-нолики ⇔ код одноинструкторного процессора» это не так (по сути, для «голого» одноиструкторного процессора вообще трудно придумать полезную задачу, в которой бы малые изменения кода приводили к малым изменениям успеха в решении задачи). Да, вы вручную ввели дополнительные условия (ваша таблица «вех эволюции»), чтобы как-то создать «градиент репродуктивного успеха», однако на этапе уже непосредственно отбора на успех в игре в крестики-нолики ваш генетический алгоритм, по-сути, вырождается в что-то типа метода Монте-Карло (вариант полного перебора, в котором все варианты просто перемешиваются в случайно порядке). Дерево решений крестиков-ноликов просто очень маленькое, и потому с высокой вероятностью умещается в ваши параметры размера генотипа и размера поколения, но успех отбираемой особи в игре, по сути, уже не зависит от успеха своих родителей (им важно лишь дожить до этапа 3). Для любой другой мало-мальски сложной задачи ваш метод не сработает.

                        Чтобы таки вырастить универсальный ИИ, необходимо обеспечить возможность эволюционной организации фенотипа (чтобы особи могли обособлять и развивать отдельные «органы», которые и будут являться суб-моделями происходящего в окружающей среде, и «органы» управления ими, которые могли бы уже и выражаться одноинструкторным процессорами, и всё это с возможностью наращивать бесконечные иерархии). Бесструктрный код одноинструкторного процессора, выращиваемый генетически, сам внутри себя к такой организации фенотипа тоже мог бы прийти (т.е., чтобы все эти «органные абстракции» сами родились внутри него, не требуя от программиста сложного описания «иерархичного фенотипа», чтобы этот код сам разбивался на подпрограммы), но тогда нужно обеспечить в генетическом механизме кластеризацию генов, так, чтобы возникала конкуренция не только отдельных генов, но и их сцепок (для простых задач будет достаточно ввести хотя бы рекомбинацию в «половом процессе», т.е., организовать кластера генов М и Ж).
                        • 0
                          xxx: Я написал ИИ который умеет одну команду.
                          yyy: Фи, вы не написали Скайнет!
                          #irony, #именаизменены
                          • 0
                            Продолжение будет? :)
                            • 0
                              Да, но, возможно, не скоро.

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