Stfw.RuCore Wars - сражение между программами
🕛 07.07.2006, 15:01
Слышали ли вы про Core Wars? Вряд ли. Максимум - один из десяти читателей. Тот, что постарше, тот, что лет 15 назад был программистом или сочувствующим...Развлечение это (а Core Wars - игра) исключительно программистское. Ибо суть его в сражении, но не между людьми. Сражении между программами. И цель - написать такого бойца, который победит остальных.
Как происходит бой? Всё просто - программы-бойцы загружаются в общую область памяти и одновременно запускаются. Та, что проработает дольше всех - победитель. Программа, которая исполнила недопустимую инструкцию, "умирает". Понятно, что сам автор таких инструкций в неё не добавляет - ими "бомбят" память другие программы в надежде испортить конкурентов. Кроме того, пытаясь уйти от бомбёжки, почти все программы то и дело перемещают себя в памяти. Память же закольцована - вслед за последней ячейкой идёт первая. Пардон, нулевая, конечно. Программисты мы или нет? :-)
"Самобеглый" mov или, иначе, Имп - простейшая программа-боец из одной команды:
mov.i $0, $1
Команда эта просто копирует себя же в следующую ячейку, после чего исполняется уже в новой позиции, таким образом "намазывая" себя на всю память в системе.
Чем эта штука интересна? Дело в том, что набор команд в Core Wars довольно ограничен - по сути, он состоит из команд mov (копирование памяти из ячейки в ячейку), арифметики и jmp (переход) с небольшими вариациями. Классический размер программы-бойца, как правило, тоже невелик - от одной (!) команды (это - классический "самобеглый" mov) до десятка. Десяток - много.
Что это значит? Это значит, что бойцов можно "выращивать" генетическим методом! Сама по себе идея генетически создавать программы очевидна, но я впервые вижу, чтобы это давало практические результаты. А ведь даёт. Автор статьи утверждает, что уже через 100 поколений появились кое-какие "бойцы", а к тысячному поколению они даже достигли определённых высот в военном искусстве. Увы, не то чтобы высот совсем уж невероятных, но - лиха беда начало.
Ну а теперь более подробно.
Core Wars
Цель этого проекта состоит в том, чтобы доказать, что corewarriors могут учиться, моделируя развитие. Это будет доказано, используя программу компьютера, которая моделирует развитие, используя генетический алгоритм. Данная программа была сначала подготовлена и представлена в классе Искусственного интеллекта в Wilmington Колледже в Весеннем семестре 1998. Класс преподавался Джимом Фитзсиммонсом, Ph. D.
Эта - секция, представляет бомбежку. Бомбежка состоит из использования MOV инструкции, чтобы переместить одну инструкцию(команду) поверх другой. Например, давайте посмотрим на очень простой bomber, написанный A. K. Dewdney (Dewdney, A. K., Вселенная Кресла):
mov.i $3, $7 add.ab #4, $-1 jmp.a $-2, #0 dat.f #0, #0
Выполнение начинается с MOV инструкции. Эта инструкция перемещает, любое значение из 3 линии (в нашем случае это DAT инструкция) в 7 линию. Далее выполняется ADD инструкция, которая добавляет 4 ко второму операнду инструкции MOV. Соответственно второй операнд у инструкции MOV изменяется с 7 на 11. JMP инструкция посылает выполнение назад MOV, который повторяет бомбёжку снова. Давайте посмотрим, как два воина борются против друг друга и как убивает DAT бомба.
mov.i $3, $7 <- выполнение для этого воина начинается здесь add.ab #4, $-1 jmp.a $-2, #0 dat.f #0, #0 (empty line) (empty line) (empty line) (empty line) mov.i $3, $7 <- выполнение для этого воина начинается здесь add.ab #4, $-1 jmp.a $-2, #0 dat.f #0, #0 (empty line) (empty line) (empty line) (empty line) . . .
Использование empty line помогает лучше пояснить происходящие процессы. На следующем шаге "тела" обоих воинов выглядят следующим образом:
mov.i $3, $11 <- выполнение для этого воина продолжается здесь add.ab #4, $-1 jmp.a $-2, #0 dat.f #0, #0 (empty line) (empty line) (empty line) dat.f #0, #0 (empty line) mov.i $3, $11 <- выполнение для этого воина продолжается здесь add.ab #4, $-1 jmp.a $-2, #0 dat.f #0, #0 (empty line) (empty line) (empty line) dat.f #0, #0 . . . (lots more empty lines)
На третьем шаге можно увидеть, что первый воин записал на место инструкции JMP первого воина свою инструкцию DAT. Естевственно, что второй воин выйдет на ошибку.
mov.i $3, $15 add.ab #4, $-1 jmp.a $-2, #0 <- выполнение для этого воина продолжается здесь dat.f #0, #0 (empty line) (empty line) (empty line) dat.f #0, #0 (empty line) mov.i $3, $15 add.ab #4, $-1 dat.f #0, #0 <- выполнение для этого воина продолжается здесь dat.f #0, #0 (empty line) (empty line) (empty line) dat.f #0, #0 (empty line) (empty line) (empty line) dat.f #0, #0 . . . (lots more empty lines)Следущий пример, опясывающий борьбу программ-воинов, на жаргоне называется "расщепление". В программе можно использовать SPL инструкцию, чтобы создать два или больше процессов. Эта инструкция может также использоваться, чтобы добавить длительность (долговечность) жизни программы-бойца. Если мы добавляем SPL инструкцию к началу воина рассмотренного в предыдущем примере, то мы получим:
spl.a #0, #0 mov.i $3, $7 add.ab #4, $-1 jmp.a $-2, #0 dat.f #0, #0
то есть инструкция SPL предварительно запустить пераллельную копию процесса воина и вероятность того, что инструкция JMP будет стёрта воином противником уменьшится.
Следующий метод борьбы называется "coreclear" (перевести не удалось :-). Перед запуском тело такого воина выглядит следующим образом:
mov.i $2, <-1 jmp.a $-1, #0 dat.f #0, #0
После нескольких циклов, тело программы будет выглядеть следующим образом:
dat.f #0, #0 dat.f #0, #0 dat.f #0, #0 dat.f #0, #0 dat.f #0, #-5 mov.i $2, <-1 jmp.a $-1, #0 dat.f #0, #0 . . . (empty lines)
Инструкция MOV берёт DAT, который стоит после JMP и помещает по адресу -1, то есть перед собой и при этом уменьшает на еденицу второй операнд у уже перемещённой инструкции DAT. При следующем цикле инструкция MOV переместит инструкцию DAT по адресу, указанному во втором операндре DATa -1 (а там уже к тому времени будет -1). DAT попадает на две строки вверхи и в DAT непосредственно перед MOV запишется значение -2, и так далее.
Следующая терминалогия в Core-войнах - это "указатели". Давайте посмотрим модифицированный код coreclear'a:
mov.i $2, <-1 jmp.a $-1, <-2 dat.f #0, #0
Посмотрим, что же происходит после выполнения команд MOV и JMP:
. . . (more empty lines) dat.f #0, #0 dat.f #0, #-2 mov.i $2, <-1 jmp.a $-1, <-2 dat.f #0, #0 . . . (more empty lines)
В обычном coreclear'e DAT уменьшается на 1, но сдесь же на 2. Проследим дальше за выполнением программы:
. . . (more empty lines) (empty line) dat.f #0, #0 (empty line) dat.f #0, #0 (empty line) dat.f #0, #0 dat.f #0, #-6 mov.i $2, <-1 jmp.a $-1, <-2 dat.f #0, #0 . . . (more empty lines)
Получается, что каждая вторая линия попадает под обстрел атакующего воина, естевственно, что такой вариант coreclear'a более эффективен в поиске и уничтожении противника.
Теперь давайте разберёмся, что такое мутирующий(видоизменющийся) воин. Для этого изменим воина бомбящего каждую 4-ю строчку:
spl.a #0, #0 mov.i $3, $5 add.ab #4, $-1 jmp.a $-2, #0 dat.f >-1, #0
dat.f >-1, #0 имеет преимущество перед инструкциями DAT с числами 0. Теперь наш воин помимо того, чтобы бомбить вогруг себя собирается ещё и по себе нанести удар. Теперь посмотрим как выглядит тело программы после первого цикла:
. . .(строки с инструкцией dat.f >-1, #0 через каждую четвёртую строчку) dat.f >-1, #0 (empty line) spl.a #0, #0 mov.i $3, $1 <- about to execute this instruction add.ab #4, $-1 jmp.a $-2, #0 dat.f >-1, #0 (empty line) dat.f >-1, #0 (empty line) (empty line) (empty line) dat.f >-1, #0 . . .(строки с инструкцией dat.f >-1, #0 через каждую четвёртую строчку)
Далее MOV помещает на инструкцию ADD DAT-бомбу:
. . .(строки с инструкцией dat.f >-1, #0 через каждую четвёртую строчку) dat.f >-1, #0 (empty line) spl.a #0, #0 mov.i $3, $1 dat.f >-1, #0 <- здесь начинается мутация jmp.a $-2, #0 dat.f >-1, #0 (empty line) dat.f >-1, #0 (empty line) (empty line) (empty line) dat.f >-1, #0 . . .(строки с инструкцией dat.f >-1, #0 через каждую четвёртую строчку)
Чтоже произойдёт дальше ? Инструкция DAT завершит выполнение процесса, но прежде она увеличит на 1 второй операнд у инструкции MOV