Я, Робот

Третьего дня надыбал занятную flash-игрушку LightBot - впрочем, занятна она будет только программистам. Там надо запрограммировать роботца зажигать лампы в лабиринте. В наличии 7 команд-движений (типа "вперед", "зажечь", "направо"), 12 ячеек под основной метод программы и две подпрограммы по 8 команд каждая. Однако, возникла мысль написать программу, составляющую успешные программы для робота.

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

Дальше - проще. Каждое решение (бот) это вектор ячеек размером 28 со значением 0-7 в каждой ячейке (0 - "пустая" команда). Изначально создаем кучу таких решений решительно случайным образом (хаха) - это будет поколение 0.

Если альфа ГА это случайность, то омега безусловно - фитнес-функция (ФФ). Грубо говоря, ФФ оценивает решение, что позволяет сравнивать их по критерию "лучше/хуже". ФФ вещь довольно тонкая.. например, первоначально я стал штрафовать за число ходов, сделанных программой - оказалось, что популяция программ стремительно вырождалась в "пустые" команды. Поэтому сейчас ФФ выглядит так: это штрафные баллы, начисляемые за 1) незаженные лампочки при останове бота, 2) расстояние до ближайшей негорящей лампы, 3) таймаут, 4) структурные повреждения (типа вызов функции 1 из функции 1). Соответственно, у хорошего бота маленький фитнес, у плохого бота - большой.

Так, об чем я? ..А. Значит у нас есть поколение 0, состоящее из случайных решений с большими фитнесами (да, большой не всегда хорошо). Наша задача - найти одного бота без штрафа за лампы и без штрафа за таймаут.

Следующее поколение получается так: 1) часть ботов (лучшие) отмечаются как избранные - они перейдут в следующее поколение без изменений 2) оставшиеся места занимают либо мутанты со случаными искажениями кода, либо полноценные потомки двух родительских программ из прошлого поколения. Да - половое размножение реализовано. Нет - тема сисек не раскрыта.

Ок.. далее поколение за поколением ГА ищет всё более удачные решения, пока наконец-то на вершине популяции не окажется окончательная программа, проходящая лабиринт с лампами.

Всякие подробности:

программу можно взять тут - 44Kb, включая исходники под VC++ 7.1 (программа под win32, запускалась под XP32 исключительно).

ключики запуска:

botsearcher.exe [stage] [max_pop] [best_num] [rnd_seed]

stage - уровень (1..12, default 1),

max_pop - максимум решений в поколении (default 10),

best_num - столько лучших решений будет перенесено в следующее поколение  (default 2),

rnd_seed - seed для ГСЧ. если не указан, то будет разный каждый запуск.

пример: botsearcher.exe 10 100 10 0

внутри есть консолька с командами:

find - автоматом ищет решение с нулевыми штрафами за лампы и за таймаут,

find N - ищет решение с фитнесом <= N,

gen N - ищет до поколения N,

list - показывает текущее поколение,

map - показывает текущий этаж,

bulb N - показывает карту растояний для лампы N,

stage N - загружает этаж N,

bot N - показывает детали бота N, 

fit N - прогоняет "тест" для бота N (это больше для дебага).

информация о каждом боте выглядит примерно так:

bot 00) bulb: 0/1, fitness: 14 (b: 10+2, t: 0, st: 2)   **<>*__*J1_1 *<>*J^_^ J<2j_1>2 : 0

где:

bulb 0/1 - 0 ламп зажглось после отработки программы. всего ламп = 1.

fitness: 14 (b: 10+2, t: 0, st: 2) - фитнес = 14, при этом за лампы 10 штрафа, 2 за расстояние до ближайшей погашенной лампы, 0 за таймаут и 2 за внутренние проблемы.

легенда команд: _ - пусто, * - зажигание, <> - налево/направо, J - прыгать, ^ - вперед, 1/2 - вызов функций 1 и 2.

0 в самом конце это номер поколения откуда решение родом.

Уф.. известные баги:

1) не проверяю нигде валидность введеных параметров. 

2) настоящий LightBot почему-то "принимает" откровенно таймаутные программы, например для 11-го этажа:

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

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

Минивикторина: у кого какая скорость при запуске 1М поколений на 11-м этаже?

botsearcher.exe 11 10 2 0

gen 1000000

на тачке моего работодаде.. датля.. тьфу. короче на рабочей тачке 401 sec, 2494 g/sec

Слава Роботам!