Слышали ли вы про 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
продолжение следует .....
|