[recovery mode] Выращивание искусственного интеллекта на примере простой игры17.09.2017 02:22

fb0ecdf14af14a8e89c5971fb8ce5ecc.jpg

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

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

Набор команд


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

Мне требовалось, чтобы ИИ мог читать и выводить данные, работать с памятью, выполнять вычисления и логические операции, делать переходы и циклы. Я наткнулся на язык 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 реализует самомодифицируемый код. Может выполнять любые алгоритмы, доступные на обычном языке программирования. Код легко изменяется и выдерживает любые манипуляции.

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


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

e8062c77f97c4c2cbe5497b3ac3ceb8f.jpg

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

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

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

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


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

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

08c4879f8925415b8966a5affc5dfbbb.jpg

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

Эволюция


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


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

5cc9ba60802d4c73ba76c2238d9b9e48.jpg

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


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

Заключение


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

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

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

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

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

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

Может, они мир захватят, а вдруг?


Ссылки


  1. Генетические алгоритмы
  2. Копирование Бита — Простейшая Вычислительная Машина / Олег Мазонка
  3. URISC — Википедия
  4. Полнота по Тьюрингу — Википедия

© Geektimes