В этой статье я поделюсь опытом выращивания простейшего искусственного интеллекта (ИИ) с использованием генетического алгоритма, а также расскажу про минимальный набор команд, необходимый для формирования любого поведения.
Результатом работы стало то, что ИИ, не зная правил, самостоятельно освоил игру крестики-нолики и нашел слабости ботов, которые играли против него. Но начал я с еще более простой задачи.
Набор команд
Все началось с подготовки набора команд, которым мог располагать ИИ. Языки высокого уровня содержат сотни различных операторов. Чтобы выделить необходимый минимум, я решил обратиться к языку Ассемблер. Однако, оказалось, что и он содержит множество команд.
Мне требовалось, чтобы ИИ мог читать и выводить данные, работать с памятью, выполнять вычисления и логические операции, делать переходы и циклы. Я наткнулся на язык Brainfuck, который содержит всего 8 команд и может выполнять любые вычисления (т.е. полон по Тьюрингу). В принципе, он подходит для генетического программирования, но я пошел дальше.
Я задался вопросом: какое минимальное количество команд необходимо для реализации любого алгоритма? Как оказалось — одна!
Процессор URISC содержит всего одну команду: вычесть и пропустить следующую инструкцию, если вычитаемое было больше уменьшаемого. Этого достаточно для построения любого алгоритма.
Олег Мазонка пошел еще дальше, он разработал команду BitBitJump и доказал, что она полна по Тьюрингу. Команда содержит три адреса, копирует один бит из первого по второму адресу памяти и передает управление на третий адрес.
Позаимствовав идеи Олега, для упрощения работы, я разработал команду SumIfJump. Команда содержит четыре операнда: A, B, C, D и выполняет следующее: к ячейке по адресу B прибавляет данные из ячейки по адресу A, если значение получилось больше заданного*, то переходит по адресу C, иначе переходит по адресу D.
Когда операнд 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 минут.
Интересные моменты
- Когда ИИ «лидер» совершал случайную ошибку и не набирал достаточное количество очков, популяция начинала деградировать, т.к. потомство формировалось из «второстепенных» родителей.
- Бывало так, что в потоке с аутсайдерами, которые топтались на месте, происходила удачная мутация, обеспечивающая взрывной рост набираемых очков. После чего этот поток становился лидером.
- Иногда в течение долгого времени не происходило никаких удачных мутаций, и даже 500 тыс. поколений не хватало, чтобы завершить отбор.
Заключение
В заключение я проделал то же с игрой крестики-нолики. Размер генома использовал тот, что и в первом случае. Количество шагов было увеличено до 1024, а размер популяции до 64 (для более быстрого расчета). Расчет занял несколько больше времени. Все происходило примерно по тому же сценарию.
Сначала ИИ играл против «рандомайзера». Я так назвал бота, который ходит случайным образом. Довольно быстро ИИ начал его обыгрывать, заполняя какую-либо строчку. Далее я усложнил задачу, добавив рандомайзеру немного разума: занимать линию, если есть возможность, либо защищаться. Однако, и в этом случае ИИ нашел слабости бота и стал обыгрывать его. Пожалуй, рассказ об этом — это тема для отдельной статьи.
Сын просил написать программу, чтоб ИИ играли между собой, а не с ботом. Были идеи сделать то же для игры шашки или го, однако, для этого у меня уже не хватило времени.
Единственный метод, который я применял для получения новых особей, — это мутация. Можно также использовать кроссовер и инверсию. Возможно, эти методы ускорят получение требуемого результата.
В конце родилась идея: дать ИИ возможность управлять всеми процессами на ПК и бороться за ресурсы компьютера. Подключить ПК к интернету, а в качестве вычислительных мощностей использовать пул старых биткойн ферм…
Как сказал, проводя аналогичный эксперимент, блогер Михаил Царьков:
Может, они мир захватят, а вдруг?
Ссылки
Комментарии (28)
unxed
17.09.2017 02:14+1> Были идеи сделать то же для игры шашки или го, однако, для этого у меня уже не хватило времени.
Как писал Норберт Винер, человека вполне можно передать по телеграфу, но в настоящий момент технические сложности представляются непреодолимыми.
masterdak Автор
17.09.2017 02:22+1С го вполне можно попробовать для начала на доске с небольшим количеством клеток.
masterdak Автор
17.09.2017 02:28Сложность была не столько техническая, сколько личная — мало свободного времени для программирования.
unxed
17.09.2017 03:59Да не, вы клёвую штуку сделали, и я понимаю, что, в принципе, это дело должно масштабироваться и под более сложные задачи. Ирония была про то, что в более сложных задачах частенько вылезают досадные мелочи, масштаб которых (и затраты времени, соответственно) бывает очень сложно оценить заранее :)
Tremere
17.09.2017 08:20непонятно конечно, где же тут ИИ, если все четко алгоритмировано, и по факту состояние всегда зависит только от внешних сигналов, но никакой накопленной памяти нет
masterdak Автор
17.09.2017 08:23никакой накопленной памяти нет
Память есть. ИИ берет данные из нулевого адреса (ячейка ввода) и может складывать их внутрь себя, далее обрабатывать их и выводить с учетом этого какой-либо результат.
masterdak Автор
17.09.2017 08:32Все, что ИИ положил «в себя», т.е. запомнил, так в нем и остается до тех пор, пока он играет с ботом.
rock3tup
17.09.2017 08:27+2Обратите внимание на этот интересный проект
artemev
17.09.2017 13:10Тема очень интересная, и у меня возник ряд вопросов. Если найдете время ответить, буду очень признателен!
1. Почему геном содержит именно 256 генов? Чем обусловлена эта цифра?
2. Допустим ген содержит цифру 42 (или любую другую из возможных). И что это значит на практике? Как соотносится значения генов и действия, выполняемые Вашим ИИ?
3. Как происходит процесс «обдумывания» очередного хода (крестики-нолики)? Или обученный таким образом ИИ на основе уже сделанных ходов просто «знает» какой ход ему нужно сделать. Значит ли это, что каждый раз на одни и те же действия бота будет один и тот же ответ ИИ?masterdak Автор
17.09.2017 14:15- В зависимости от сложности задачи, можно сделать геном больше, но вычисления будут больше времени занимать. В моем случае этой длинны оказалось достаточно. Поскольку геном — это и код, и адреса памяти. Удобно использовать значения типа Byte — от 0 до 255, чтобы любые значения могли ссылаться на полный диапазон ячеек генома. Для более сложной задачи можно использовать тип данных Word от 0 до 65 535, тогда размер генома целесообразно делать 65 536 ячеек.
- Допустим, ячейка N15 содержит цифру 42. При запуске с этого места операнд A будет обращаться к 42 ячейке памяти: возьмет от туда данные для добавления к адресу B. Адрес B будет взят из 16-ой ячейки (15 + 1).
- Процесс обдумывания хода у ИИ достаточно сложный. Я пытался анализировать то, что он делает, но понять это достаточно трудно. Видно только, что он что-то «усиленно» считает перед тем, как дать ответ.
Здесь можно сделать по-разному. Я перезагружал ИИ после каждого боя с ботом, поэтому он начинал всякий раз одинаково и действовал однотипно. Можно между боями перегрузу не делать, тогда ИИ будет модифицироваться в процессе боя и вести себя всякий раз по-разному.
artemev
17.09.2017 14:37Спасибо, буду разбираться, т.к. подход достаточно необычный и заслуживает внимания.
4ainik
17.09.2017 18:21Да забавная статья! И что еще более забавно, что ИИ превзошел создателя, если опираться на п3. :)
А можно посмотреть все исходники проекта? Может выложите на github?masterdak Автор
17.09.2017 18:29Нельзя сказать, что ИИ превзошел создателя. Дело в том, что код из одной инструкции — это просто набор чисел. Поэтому, глядя на числа, очень трудно понять суть того, что происходит. Это только Нео из Матрицы умел делать :)
Код выложить могу, но позже, т.к. желательно провести рефакторинг и сделать минимальные инструкции, а на это нужно время.4ainik
17.09.2017 18:35Да было бы очень интересно посмотреть на завершенный проект, а то в общих словах как-то не очень понятно.
Понял только что буфер 256байт, есть набор примитивных инструкций 2или 3 работающих с этим буфером. То что «это» как-то работает это понятно и то что «ОНО» что-то вычисляет тоже понятно, непонятно другое: как оно взаимодействует и вообще хотелось бы отдельную более подробную статью про то как ОНО играет в крестики нолики…
Ardogar
17.09.2017 16:19Вовремя, кстати, статья подоспела, так как на этих выходных я решил-таки разобраться с генетическим алгоритмом в играх nes. Попробовал два разных подхода, первый — lua-скрипт в эмуляторе, работает почти идеально, за сутки решает уровень, но только для двух версий марио, а второй — самообучающаяся программа, которая может проходить довольно много игр. Очень интересно сделана, нужно сначала записать небольшой реплей с прогрессом, скормить обучалке, она сама проанализирует и решит, какой цели нужно добиваться. Процесс, правда, долгий, за сутки в 6 потоков набирается минута-две геймплея, но в любом случае, наблюдать за этим интересно.
В принципе, если кому-нибудь интересно, могу попробовать написать гайд по запуску, так как в процессе нарвался на несколько неочевидных вещей.
darkfrei
17.09.2017 16:46Как присваивались баллы в разных вехах?
masterdak Автор
17.09.2017 18:42+1В первой (простой) игре во всех вехах система баллов была одинаковая:
— один балл за запрос ввода;
— один балл за вывод чего-либо после ввода;
— один балл за правильный ответ.
И так по кругу, до тех пор пока ИИ не совершит ошибку.
В крестиках-ноликах система баллов была другой:
— по одному очку за правильный ввод и вывод;
— 100 очков за победу;
— 50 за ничью;
— 0 за поражение.darkfrei
17.09.2017 21:10Запрос ввода и вывода был один раз в такт?
Что запрашивало и что выводило, поконкретнее? Например, в крестиках-ноликах опрашивалось содержание каждого поля и ставился крестик (нолик)?masterdak Автор
17.09.2017 22:52+1В крестиках-ноликах бот ждал, когда ИИ начнет запрашивать данные на ввод. ИИ мог совершить некоторое количество вычислений перед тем, как запросить данные. То же и с выводом. Т.е. процесс ввода и вывода занимал у ИИ не по одному такту.
На ввод и вывод подавалось значение от 0 до 255. Занимаемая ячейка была той, что соответствовала остатку от целочисленного деления на 9. Например вводится «142»: 142 mod 9 = 7. Значит заполняется ячейка номер 7. Если она занята, то заполняется следующая свободная.
Ячейки нумеровались так:
0 1 2
3 4 5
6 7 8
napa3um
17.09.2017 20:59Вы генетическим алгоритмом сделали автоматический аппроксиматор дерева решений крестиков-ноликов в код «одноинструкторного» процессора. Методы ИИ тут условно присутствует, конечно, но ИИ — не выращенный код, а сам генетический алгоритм, ищущий «дерево решений крестиков-ноликов в виде кода одноинструкторного процессора». (Возможно, моя критика не очень понятна и кажется лишь претензией к терминологии.)
Для применения генетического алгоритма необходима модель искомого «фенотипа решателя» (выращиваемого ИИ) такая, чтобы малые изменения генотипа приводили с высокой степенью вероятности либо к «летальному исходу», либо к малому изменению адаптивного успеха особи (т.е., чтобы случайными мутациями «нащупывался» неслучайный градиент приспособленности на условном ландшафте «репродуктивного успеха»). И в случае проекции «алгоритм игры в крестики-нолики ? код одноинструкторного процессора» это не так (по сути, для «голого» одноиструкторного процессора вообще трудно придумать полезную задачу, в которой бы малые изменения кода приводили к малым изменениям успеха в решении задачи). Да, вы вручную ввели дополнительные условия (ваша таблица «вех эволюции»), чтобы как-то создать «градиент репродуктивного успеха», однако на этапе уже непосредственно отбора на успех в игре в крестики-нолики ваш генетический алгоритм, по-сути, вырождается в что-то типа метода Монте-Карло (вариант полного перебора, в котором все варианты просто перемешиваются в случайно порядке). Дерево решений крестиков-ноликов просто очень маленькое, и потому с высокой вероятностью умещается в ваши параметры размера генотипа и размера поколения, но успех отбираемой особи в игре, по сути, уже не зависит от успеха своих родителей (им важно лишь дожить до этапа 3). Для любой другой мало-мальски сложной задачи ваш метод не сработает.
Чтобы таки вырастить универсальный ИИ, необходимо обеспечить возможность эволюционной организации фенотипа (чтобы особи могли обособлять и развивать отдельные «органы», которые и будут являться суб-моделями происходящего в окружающей среде, и «органы» управления ими, которые могли бы уже и выражаться одноинструкторным процессорами, и всё это с возможностью наращивать бесконечные иерархии). Бесструктрный код одноинструкторного процессора, выращиваемый генетически, сам внутри себя к такой организации фенотипа тоже мог бы прийти (т.е., чтобы все эти «органные абстракции» сами родились внутри него, не требуя от программиста сложного описания «иерархичного фенотипа», чтобы этот код сам разбивался на подпрограммы), но тогда нужно обеспечить в генетическом механизме кластеризацию генов, так, чтобы возникала конкуренция не только отдельных генов, но и их сцепок (для простых задач будет достаточно ввести хотя бы рекомбинацию в «половом процессе», т.е., организовать кластера генов М и Ж).
Daddy_Cool
19.09.2017 11:30xxx: Я написал ИИ который умеет одну команду.
yyy: Фи, вы не написали Скайнет!
#irony, #именаизменены
yans
Коммент про биткоин-фермы навел на параноидальную мысль что биткоины — изобретение уже существующего ИИ с целью создать большой пул вычислительных мощностей, потом обрушив биткоины ИИ скупит эти мощности дешево для собственной работы.
vsb
Эти мощности умеют только считать SHA-1 хеши. В отрыве от биткоина довольно бесполезная задача.
yesasha
Вдруг SHA-1 полон по Тьюрингу?