15 мая 2023 года "Исходники.РУ" отмечают своё 23-летие!
Поздравляем всех причастных и неравнодушных с этим событием!
И огромное спасибо всем, кто был и остаётся с нами все эти годы!

Главная Форум Журнал Wiki DRKB Discuz!ML Помощь проекту


Слышали ли вы про 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




продолжение следует .....