[ главная ]   [ рейтинг статей ]   [ справочник радиолюбителя ]   [ новости мира ИТ ]



Ответов: 0
25-02-12 07:01







   Web - программирование
PHP


ASP






XML



CSS

SSI





   Программирование под ОС











   Web - технологии








   Базы Данных









   Графика






Данные




Программирование под ОС / Assembler /

Core Wars - сражение между программами

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




Комментарии

 Ваш комментарий к данному материалу будет интересен нам и нашим читателям!



Последние статьи: Программирование под ОС / Assembler /

Первая программа на linux
23-05-2010   

Ассемблер, который я буду использовать - NASM (Netwide Assembler, nasm.2y.net). Этот выбор объясняется тем, что: Во первых, он мультиплатформенный, т.е. для портирования программы на разные ОС достаточно только изменить код взаимодействия с системой, а всю программу переписывать не нужно... подробнее

Кол. просмотров: общее - 4227 сегодня - 0

Использование пакета NuMega Driver Studio для написания WDM - драйверов устройств
17-05-2010   

Разработка WDM - драйвера с использованием только DDK является сложной и трудоемкой задачей. При этом приходится выполнять много однотипных операций: создание скелета драйвера, написание inf - файла для его установки, создание приложения для тестирования и т.п... подробнее

Кол. просмотров: общее - 4061 сегодня - 0

Система классов DriverWorks
17-05-2010   

Возможно, идея писать драйвера объектно-ориентированными и кажется на первый взгляд нелогичной. Но при более близком знакомстве с DriverStudio и с драйверами в общем, оказывается, что это не так уж страшно и довольно удобно... подробнее

Кол. просмотров: общее - 3918 сегодня - 0

Объект устройства device object
17-05-2010   

Объекты устройств являются экземплярами класса KDevice или KPnpDevice. Эти классы являются краеугольными камнями архитектуры DriverWorks: они представляют собой как бы программный образ тех устройств, которые присутствуют в системе... подробнее

Кол. просмотров: общее - 4050 сегодня - 0

Объекты для управления оборудованием
17-05-2010   

Как было упомянуто выше, объект устройства управляет работой устройства при помощи специальных объектов, управляющих работой оборудования - портами В/В, прерываниями, памятью, контроллерами ПДП. Драйвер создает эти объекты для представления физических параметров устройства... подробнее

Кол. просмотров: общее - 4158 сегодня - 0



  WWW.COMPROG.RU - 2009-2012 | Designed and Powered by Zaipov Renat | Projects