CoreWars: организация "холма" в УрГУ
Курсовая работа студента гр. КН–301 Скробова А.Л.
Научный руководитель – Баклановский М.В.
Уральский государственный университет им. А.М.Горького
Математико-механический факультет
Кафедра вычислительной математики
Екатеринбург, 2005
В работе объясняется необходимость создания на базе мат-меха УрГУ сервера-"холма" для битв компьютерных программ, и детально описывается его предполагаемая организация. Внимание уделяется интересным усовершенствованиям правил CoreWars, которые помогли бы выделить данный сервер среди остальных. На настоящий момент в России не существует подобных "холмов", хотя за рубежом их действует около десятка.
CoreWars – первая из попыток имитировать на ЭВМ биологическую эволюцию. CoreWars – это "вселенная", в которой специальным образом написанные программы-бойцы, называемые CoreWarriors, полноценно живут в биологическом смысле: рождаются и умирают, двигаются и размножаются, общаются и нападают друг на друга, ставят западни и маскируются, и даже чинят свои повреждения. В этом смысле CoreWars называют "соревнованием компьютерных вирусов", т.к. последним, так же как и CoreWarriors, присущи названные черты. Отличием CoreWars от повседневной жизни компьютерных вирусов является то, что в CoreWars "вирусы" соревнуются друг с другом, а не просто сосуществуют с ничего не подозревающими "мирными" программами. По-видимому, удачные CoreWarriors, будучи реализованными для какой-нибудь реальной ЭВМ, были бы чрезвычайно успешными вирусами и на ней. Однако, как мы увидим позже, архитектура "процессора" CoreWars настолько необычна, что перенос программ-бойцов на реальные ЭВМ потребовал бы недюжинной смекалки.
В работе [14] для CoreWars-подобных экспериментов вводится название "бинология" – от "binary biology". К настоящему времени создано бесчисленное множество бинологических миров – от соревнования Quake-ботов до детских игр, обучающих программированию на примере соревнующихся программ. Однако CoreWars стал классическим бинологическим миром, и наверное, наиболее исследованным из их всех. Например, с использованием CoreWars как модели биологической эволюции был исследовал вопрос первичности репродукции по отношению к метаболизму [15]. Основное отличие CoreWars от бинологических миров, спроектированных непосредственно для моделирования эволюции, таких как Tierra, – то, что это игра, соревнование. Хотя в собственно битвах участвуют только CoreWarriors, на самом деле CoreWars – соревнование авторов этих бойцов. В этой двойственности – игра программистов и объект исследования бинологов – и заключается особый характер CoreWars.
По информации [2] и [4], прототип CoreWars под названием "Darwin" был придуман в 1961 В.Высоцким, Р.Моррисом и Д.МакИлроем. Впервые широкая публика узнала об этой игре в 1972, после публикации в журнале Software – Practice and Experience статьи под псевдонимом "Алеф-Нуль". Но настоящую популярность игра приобрела весной 1984, когда Д.Джонс и А.Дьюдни начали в журнале Scientific American серию статей о CoreWars [5]. По словам Дьюдни, на создание CoreWars его вдохновила история о компьютерном вирусе Creeper, парализовавшем работу ARPANET и побежденном специально для этого написанным вирусом Reaper, который самоуничтожился сразу после завершения своей миссии. Интересно, что Моррис, один из авторов Darwin, – отец создателя первого сетевого червя [12], буквально обрушившего Интернет в 1988, так что компьютерные вирусы и CoreWars имеют общие корни. Сам же Дьюдни в своих статьях многократно заявлял, что CoreWars не имеет отношения к "компьютерной заразе".
Сразу же после выхода статей Дьюдни начались многочисленные соревнования; до сих пор активной остаётся созданная в 1991 ньюсгруппа rec.games.corewar (несколько сообщений в день). До 1993–1994 выходило несколько бюллетеней, посвящённых CoreWars – их архивы лежат на http://para.inria.fr/~doligez/corewar/ и http://www.corewar.info/newsletter.htm. Один из этих бюллетеней – "Core Warrior" – выходит до сих пор.
В игре Darwin – прототипе CoreWars – программы-бойцы выполнялись на реальной IBM 7090, и писались на ассемблере этой ЭВМ. В CoreWars, напротив, используются специально созданные язык RedCode и выполняющий программы на этом языке компьютер "Memory Array RedCode Simulator" (MARS). Самый главный элемент MARS, давший название самой игре – это "the core", память в виде кольца. (Как указывает Jargon File, так хакеры называли ферритовую память больших ЭВМ.) Каждая ячейка памяти представляет собой "машинное слово" неопределённой величины. В одной ячейке хранится код команды и два её операнда: таким образом, все команды имеют одинаковую длину и одинаковое число операндов. Некоторые команды игнорируют один или оба своих операнда; тогда их можно опускать, и они примут значение по умолчанию 0. Подробное описание RedCode приведено в приложении.
Все операнды в
RedCode-программах – беззнаковые числа от 0 до CORESIZE–1, где CORESIZE – размер
памяти; вся арифметика выполняется по модулю CORESIZE. Однако
для удобства допускается использовать в программах отрицательные числа: при
компиляции они будут нормализованы. Кольцевая память MARS не имеет начала: адресация всегда выполняется относительно
текущей команды. Так, например, команда mov 0, 1 перемещает себя в следующую ячейку памяти. Эта команда является
простейшей программой-бойцом, затирающей всю память своими копиями –
"импом".
Данные хранятся в виде операндов команд; обычно это неиспользуемые самой командой
операнды, или команда dat – сама она невыполнима, и приводит к уничтожению
выполнившего её потока. Другое применение команды dat –
"бомбардировка" вражеских программ в расчёте, что они выполнят эту
команду как свою часть. Второй простейший боец из статьи Дьюдни – именно такой
бомбардировщик: mov 3, 7; add #4, -1; jmp -2; dat. Он бомбит память с интервалом в
четыре команды; поскольку CORESIZE обычно делится на 4,
это приводит к тому, что он не уничтожит себя. Поскольку изначально вся память MARS заполнена командами dat, последнюю строчку
предыдущей программы можно опускать.
Третий
интересный приём, применяемый в CoreWarriors – использование декрементации для атаки. При одном из
режимов адресации – предекрементном – операнд указывает на указатель на объект,
с которым будет работать команда, и этот указатель декрементируется перед
использованием. Этот режим предназначался для реализации циклов; например, такой
бомбардировщик – mov 2, <2; jmp
-1; dat 0, -2 – заполняет командами dat (с разными операндами)
всю память перед собой. Когда он опишет полный круг по памяти, он затрёт себя и
самоуничтожится. Подобный приём – "core clear" – часто применяется бойцами
как "последняя надежда", когда другие приёмы не возымели успеха. Предекремент
выполняется даже для игнорируемых операндов: так, программа mov
2, <2; jmp -1, <1; dat <333, -2 будет бомбить dat-ами
ячейки памяти через одну. Более того, если такая бомба попадёт в противника, и
он выполнит команду dat <333, ххх – то перед смертью он декрементирует ячейку
памяти на расстоянии 333 от себя – возможно, повреждая код другого потока. Эта
идея развивается в "декрементном бомбардировщике" jmp
1, <-1; jmp -1, <-1, который декрементирует
все ячейки перед собой по кругу. Более короткая программа, делающая то же самое
– djn.a 0, <-1.
Одна битва (CoreWar) начинается с того, что в случайных местах памяти располагаются программы-бойцы. Затем программы выполняются по очереди, по одной команде за ход. Битва длится, пока не останется только один CoreWarrior, или пока не будут выполнены MAXCYCLES команд каждой программы; в последнем случае объявляется ничья.
Одна из особенностей MARS – встроенная поддержка
многопоточности: команда spl порождает новый поток по указанному адресу, продолжая
выполнение и по старому – подобно инструкции BBW (Branch Both Ways) из
юмористической подборки "Opcodes which should existed" 1970-х. Переключение программ происходит
независимо от переключения их потоков; т.е. каждая из N программ будет получать 1/N
процессорного времени независимо от того, сколько в каждой из них потоков, и
каждый из K потоков программы будет получать 1/K процессорного
времени, назначенного этой программе. Потоки программы выполняются в порядке их
создания, по одной инструкции за квант. Программа считается побеждённой, если
уничтожены все её потоки; перед разработчиком бойца ставится дилемма – сделать
программу более живучей (больше потоков) или более быстрой (меньше потоков).
Типичные программы-бойцы имеют около десятка потоков; ограничение на количество
потоков одной программы – MAXPROCESSES – задаётся правилами соревнования.
Для поражения
многопоточных противников используются "ловчие ямы" – бомбы вида jmp 0 или spl 0, которые не уничтожают поток, но и не дают ему выполнять осмысленной
работы; таким образом процессорное время отбирается от остальных потоков
программы-противника. Потом, когда обездвиженный противник будет найден в
памяти, его можно будет уничтожить точечными бомбардировками. Более интересный
вариант этого приёма – это "захват в рабство", когда команды перехода
указывают на собственный код бойца; таким образом он может заставить своего
противника выполнять нужный себе код – фактически, отбирая у противника
процессорное время в свою пользу.
Резюмируя перечисленные приёмы, CoreWars можно назвать соревнованием программ за захват ресурсов ЭВМ – памяти и процессорного времени, точно так же как эволюцию биологических видов – соревнованием за захват ресурсов планеты.
Существуют реализации MARS для всех распространённых ПК и многих больших ЭВМ; часто их авторы вносят собственные расширения в RedCode – другими словами, боец может быть "непереносим" между разными реализациями MARS. Созданное Дьюдни в 1985 общество International Core War Society (ICWS) утвердило два стандартных диалекта RedCode – ICWS-84 и ICWS-88; сейчас используется в основном диалект ICWS-94, имеющий статус чернового стандарта.
Одно из наиболее популярных нестандартизованных расширений MARS – p-space, впервые реализованный в эмуляторе pMARS (1995). p-space – это личная память каждого CoreWarrior: небольшой участок памяти (адресуемый абсолютно, т.е. от ячейки 0 до ячейки PSPACESIZE –1), доступ к которому имеет только сама программа-боец. Перед началом каждого раунда в ячейку 0 записывается результат предыдущего раунда. Содержимое всех остальных ячеек сохраняется между раундами, и поэтому CoreWarrior может сохранять там информацию о стратегии противника для её использования в следующем раунде. Однако противник может дописать в код бойца инструкции записи в его p-space; эта технология называется "brainwashing". Соответственно, боец, рассчитывающий на содержимое p-space при выборе своей стратегии, должен как-то проверять его целостность. В общем, p-space можно рассматривать как бинологический аналог "памяти вида". Его использование, однако, не получило большой популярности; чтобы получить от него существенные преимущества, нужны более сложные программы и большее число раундов дуэли, чем это имеет место в CoreWars.
pMARS (portable MARS) (http://www.koth.org/pmars/) – самая популярная реализация MARS; она существует в вариантах для DOS, Windows, Macintosh, Amiga и Linux. Её модификация с усовершенствованной графикой – pMARS-SDL (http://www.cs.helsinki.fi/u/jpihlaja/cw/pmars-sdl/index.html) – поддерживает Windows и X11. Существует множество других реализаций:
Большой список различных CoreWars-систем приведён в [13].
В Интернете есть так называемые "холмы" – открытые CoreWars-соревнования. "На холме" сидят несколько десятков (иногда сотен) лучших CoreWarriors; по электронной почте или через веб-форму принимаются заявки на участие с кодом бойца; ежедневно или еженедельно заявки обрабатываются, и холм обновляется. Чем дольше боец просидит на холме, тем больше чести достаётся его автору. Первый холм, созданный в Intel В.Шубертом в 1991, больше не существует. Существующие ныне холмы:
Общепринятые условия соревнований – CORESIZE=8000, PSPACESIZE=500, MAXCYCLES=80000, MAXPROCESSES=8000, дуэль, ограничение на длину программы – 100 команд, минимальное расстояние между программами при старте – 100 команд. Используются и другие значения – как правило, отличающиеся от этих в 10 или 100 раз: например, 80000 ("большой холм") или 800 ("крошечный холм").
Из всех холмов наиболее популярен KOTH.org, запущенный вторым по счёту (1993) и остающийся до сих пор рекордсменом по длительности своего функционирования. До недавнего времени наряду с ним был весьма популярен Pizza Server – третий холм в истории (1994). В России же, насколько я смог понять, вообще нет ни одного холма. Это тем более удивительно, что чемпион третьего международного турнира ICWS (1988) – Е.Лилитко из Переславля-Залесского. Поэтому конечной целью данной работы было подготовить почву для создания CoreWars-холма на мат-мехе УрГУ. Соответственно, первым делом нужно было подготовить требования к такому серверу. Очевидно, он должен мочь выполнять уже написанные программы, и для этого он должен быть совместимым со стандартом де-факто – KOTH.org (ICWS-94 + p-space). Можно будет изначально "загрузить" на холм те несколько тысяч бойцов, что доступны на существующих (в т.ч. остановленных) холмах и в базах данных CoreWars, таких как http://www.netapt.com/~daveey/art/code/corewars/bots/ – тогда первые посетители придут не на пустой холм, а на уже заполненный наиболее выдающимися программами-бойцами.
Кроме того, хотелось бы реализовать уникальные "фишки", которые привлекли бы к нашему серверу пользователей KOTH.org:
Для расширения CoreWars можно предложить следующие идеи:
1. Ограничение доступных команде ячеек некоторой её окрестностью. Сейчас CoreWarrior имитирует всевидящий и всесильный организм, который видит всю память целиком, может выполнять операции над любой её ячейкой, и может мгновенно перемещаться в любую из них. Мне кажется, что было бы более бинологически оправданным ограничить область действия программы, т.к. это приближает бинологическую модель жизни к её биологическому прототипу, – поэтому такое ограничение способствовало бы выработке биологически состоятельных стратегий для CoreWarriors. Впрочем, более существенный недостаток CoreWars как модели биологической эволюции – то, что любые два CoreWarriors конкурируют, т.е. все "бинологические виды" как бы занимают одну и ту же нишу. Однако путь к преодолению этого ограничения, намеченный в [10], – позволить CoreWarriors изменять способ интерпретации своих соперников MARS-ом – совершенно уничтожит CoreWars как игру (требующую предопределённых правил) и поэтому не представляется мне интересным для реализации на холме УрГУ.
Другой вариант ограничения операций программ-бойцов над удалёнными ячейками памяти – пропускать некоторое число квантов потока, выполняющего такие операции, – мне также кажется менее интересным, чем названный.
2. Традиционным способом визуализации CoreWar были совершенно ненаглядные ряды строк: пользователь должен "держать в уме", что все эти строчки связаны в одно кольцо. Более того, такой способ неверно передаёт расстояние между ячейками памяти. Более наглядный, но менее компактный способ предложен в [16] – изображать кольцо памяти именно в виде кольца. Но есть один способ расширить MARS, одновременно облегчая визуализацию и сохраняя совместимость с имеющимися программами, – перейти от одномерного кольца к двумерному тору: тогда изображение памяти в виде матрицы станет естественным. В условиях двумерной памяти можно задать 4 направления выполнения и переключаться между ними, подобно языку Befunge. Для программ на RedCode, где каждая команда имеет одинаковую длину и структуру, это достаточно просто и естественно. Операнды команд, таким образом, превращаются в пары чисел – сдвиг "вверх" и "вправо" от текущей ячейки до указываемой.
Оба названных усовершенствования названы во второй статье Дьюдни, но только как общие концепции; их разработку и обоснование я взял на себя.
3. Случайно выбирать величину квантов для переключения между потоками CoreWarriors, или даже выполнять несколько потоков одновременно (сами команды при этом остаются атомарными). В таких условиях в CoreWarriors пришлось бы задействовать явные средства синхронизации. Среда для соревнования параллельных программ уже существует (http://www.gridwars.com/), поскольку параллельные вычисления имеют большую прикладную значимость; однако C-подобный язык GridWars, CxC, крайне далёк от ассемблер-подобного RedCode. Мне казалось бы интересным "скрестить" параллельное программирование и CoreWars. Задача реализации CoreWars на параллельной ЭВМ была поставлена в [3], однако там нет никакой информации об её выполнении.
4. Устраивать соревнования большой кучи бойцов одновременно, в большой памяти – для проверки не столько силы атаки, сколько живучести бойца. В принципе, такие соревнования ведутся на некоторых холмах, но недостаточно популярны. Может быть, имеет смысл устраивать "гонки на выживание" – побеждённого бойца сразу же заменяет новый, очки начисляются за время жизни бойца? Ещё одна интересная идея – битвы небольшого (3–4) числа бойцов; очевидно, это потребует совершенно иных стратегий, чем для дуэлей.
5. Устраивать "соревнования эволюторов".
Известно, что создание CoreWarriors методами генетического программирования достигло большого успеха: на некоторых холмах первые места держат эволюционные программы, на других они соревнуются с написанными человеком на равных. Речь здесь идёт не о программах, сгенерированных эволютором от начала до конца, а об использовании эволюционных программ как основы для написания собственных. Даже не используя эволюционные программы непосредственно, из них можно почерпнуть массу свежих идей, не использованных ещё в человеческих программах. Однако, поскольку качественная имитация эволюции CoreWarriors требует колоссальных вычислительных затрат, разные авторы эволюторов используют свои подходы для упрощения модели эволюции. Одна из поставленных задач в рамках "Холма УрГУ" – реализация универсального микроядра MARS, которое использовалось бы и в онлайн-соревнованиях CoreWarriors, и в эволюторах. Затем можно было бы запустить наряду с холмом CoreWarriors параллельный холм программ-эволюторов: побеждает та, которая сгенерирует самого лучшего бойца, а место бойца-вершины эволюции определяется как раз на основном холме.
Перри рассматривает два способа эволюционной генерации бойцов: выращивая их в собственном мире, где они соревнуются друг с другом (бинологическая модель естественного отбора), и выращивая их на холмах, где они соревнуются с творениями человека – Перри сравнивает это с выработкой биологическими животными навыков сосуществования с неестественными объектами: уворачиваться от автомобилей, избегать проводов под напряжением и т.д. Как заключил Перри, тренировка бойцов на холмах эффективнее, но она ограничена в своих возможностях, поскольку развиваются очень узкий спектр способностей бойцов, и в них не так вероятно найти множество свежих идей.
6. Реализовать "со-эволюцию".
Перри предлагает довести узконаправленную тренировку на холмах до крайности – сводя генерируемых бойцов всё время с одним и тем же CoreWarrior, вывести таким образом для него "идеального противника". Мне кажется, что было бы чрезвычайно интересно заложить возможность самосовершенствования в самом CoreWarrior: увеличив число раундов дуэли, например, до 1000, позволить соперникам "со-эволюционировать" на всём её протяжении. Таким образом, мы получим сразу пару "идеальных противников" – интересно, насколько сильно они будут отличаться от своих изначальных версий.
Такое расширение CoreWars объединяло бы в одном соревнование бойцов и соревнование эволюторов, притом в одной программе они сочетались бы оба.
Есть и более изощрённые идеи относительно развития CoreWars; так, например А.Вэйт [18] предлагает заменить "устаревшие" цифровые программы-бойцы на квантовые, выполняемые под управлением виртуальной машины QMARS – эмулятора квантового компьютера. К сожалению, я недостаточно знаком с аппаратом квантовых вычислений, чтобы как-то это прокомментировать, но сама идея квантовых программ-бойцов кажется мне чрезвычайно привлекательной для отдельного исследования.
Подводя итог всему изложенному, я представляю себе "Холм УрГУ" в виде следующей схемы:
,–––––––микро-MARS––––эволюторы
"видеомагнитофон" | \ `––––––––|––––––.
\ | \ | \
блок визуализации \ холм эволюторов \
| \ \ | \ \
онлайн-визуализация–\–\–>веб-сайт<–––холм бойцов
\ \
\ \
офлайн-MARS
(для тестирования бойцов "на дому")
В этой схеме блок визуализации получает на входе в реальном времени либо информацию о проходящей битве (от виртуальной машины MARS), либо воспроизводимую по записи информацию (от "видеомагнитофона"; запись производится той же виртуальной машиной). Офлайн-MARS включает такой блок визуализации (вместе с "видеомагнитофоном") и собственно виртуальную машину; для онлайн-битв блок визуализации используется в виде Java-аплета.
Команды RedCode:
dat (84) – уничтожает выполнивший поток. Операнды игнорируются. Если указан один
операнд, то считается, что это операнд B.mov A, B (84) – копирует A в B.add A, B (84) – добавляет к B значение A.sub A, B (84) – вычитает из B значение A.jmp A (84, изменена в 86) – задаёт A как следующую команду для
выполнения. Операнд B игнорируется.jmz A, B (84, изменена в 86) – если значение B
равно 0, то задаёт A как
следующую команду для выполнения; иначе игнорируется.cmp A, B (84) – сравнивает значения A и B;
если они равны, то игнорируется, иначе пропускает следующую команду.jmn A, B (84, изменена в 86) – если значение B
равно 0, то игнорируется; иначе задаёт A как следующую команду для выполнения.djn A, B (86) – уменьшает значение B на единицу; если
новое значение B не равно 0, то задаёт A как следующую команду
для выполнения. (Эквивалентно sub #1, B; jmn A, B)spl A (86, изменена в 88) – создаёт новый
поток, выполнение которого начинается с адреса A. Первая
команда нового потока будет поставлена на выполнение после следующего перехода
к текущему потоку, т.е. после выполнения команд всех остальных существующих
потоков. Операнд B игнорируется.slt A, B (88) – сравнивает значения A и B; если A < B, то пропускает
следующую команду, иначе игнорируется. Поскольку сравнение выполняется по
модулю CORESIZE, 0 – наименьшее число, -1 (равное CORESIZE–1) – наибольшее.mul A, B (94) – умножает B на значение A.div A, B (94) – заменяет B частным от деления
на значение A. Если A равно 0, то выполнивший команду поток уничтожается.mod A, B (94) – заменяет B остатком от деления на
значение A. Если A равно 0, то выполнивший команду поток уничтожается.seq A, B (95) – альтернативная мнемоника команды cmp.sne A, B (95) – сравнивает значения A и B;
если они равны, то пропускает следующую команду, иначе игнорируется.nop (95) – игнорируется вместе со своими операндами. Используется для отладки
программ-бойцов.ldp A, B (p) – копирует в B значение
ячейки p-space с индексом, задаваемым значением A.stp A, B (p) – копирует значение A в ячейку p-space с индексом, задаваемым значением B.Обозначение в скобках после команды указывает версию RedCode, в которой она впервые появилась: "Core War Guidelines" [9] (84), ICWS-86 [7] (86), ICWS-88 [8] (88), ICWS-94 подверсии 3.2 [17] (94), ICWS-94 подверсии 3.3 [6] (95), pMARS 0.8 (p). В случаях, когда семантика команды различалась в разных версиях RedCode, приведена наиболее новая, а в скобках дан комментарий о первой версии RedCode с текущей семантикой данной команды.
Режимы адресации:
add #1, A увеличивает значение A на единицу.dat 1; add $-1, A увеличивает
значение A на единицу. Знак прямой адресации ($) можно опускать.dat 1; add @1, A;
dat -2 увеличивает значение A на единицу.dat 1; add <1, A; dat -1 увеличивает
значение A на единицу и изменяет операнд B последней команды dat на -2.dat 1; add >1, A; dat -2 увеличивает
значение A на единицу и изменяет операнд B последней команды dat на -1.*X, {X,
}X соответственно.Предекременты и/или постинкременты выполняются до самой команды и могут изменять её операнды – в последнем случае выполняться будет команда с изменёнными операндами. Если оба операнда команды выполняют предекременты и/или постинкременты, то операнд A обрабатывается раньше операнда B. Кроме того, предекременты и постинкременты выполняются даже для игнорируемых операндов.
Начиная с ICWS-94, все операнды всех команд допускают все виды
адресации. Если операнд A команд jmp, jmz, jmn, djn, spl –
непосредственное значение, то происходит переход в ту же ячейку памяти, точно
так же, как если бы операндом A было $0. Если операнд B команд djn,
mov, add, sub, mul, div, mod – непосредственное значение, то изменяется
оно само: например, команда djn #42, #1 после выполнения превращается в djn #42, #0;
переход выполняется, превращая команду далее в djn #42, #-1
– только затем будет выполняться следующая команда. Таким же образом команда add #1, #2 после выполнения превращается в add #1, #3.
Размер данных, с которыми по умолчанию работает команда, – только операнд B слова, либо оба
операнда слова (для add, sub, mul, div, mod, slt) и слово целиком (для остальных
команд), – определяется меньшим из размеров его операндов. В ICWS-94,
кроме того, определены модификаторы, которые явно задают части слова,
обрабатываемые командой:
Модификатор
отделяется от команды точкой. Например, mov.ab A, B копирует
операнд A слова, задаваемого операндом A, в операнд B слова,
задаваемого операндом B; mov.x A, A меняет
местами операнды A и B слова, задаваемого операндом A; cmp.f A, B сравнивает слова, задаваемые операндами A и B, игнорируя различия в командах и
режимах адресации этих слов, а cmp.i A, B принимает такие различия во внимание.
Команды работы с p-space всегда обрабатывают один из операндов, но не оба, потому что ячейки p-space представляют собой числа, а не слова. Как и с другими командами, по умолчанию используется операнд B слова, задаваемого операндом команды. Адресация p-space, так же как и основной памяти, циклическая: адрес PSPACESIZE+X указывает на ту же ячейку, что и адрес X.
Формат файлов RedCode:
Регистр
символов не различается. Команды записываются по одной в строке. Перед командой
может быть символьная метка; такая метка может использоваться как операнд в
командах – при компиляции она заменяется относительным адресом помеченной
команды. Допускаются комментарии от символа ; до конца строки. Определены
псевдокомментарии, содержащие информацию о программе: ;redcode (версия RedCode), ;author (автор программы-бойца), ;strategy (описание бойца), ;name (название бойца), ;version (версия бойца), ;date (дата написания
программы-бойца). Псевдокомментарии не влияют на выполнение программы; их
использование зависит от конкретной реализации холма. Отдельно стоит
псевдокомментарий ;assert, задающий условие
компиляции программы-бойца: например, ;assert CORESIZE==8000.
Предопределённые значения, такие как CORESIZE, зависят
от конкретной реализации и обрабатываются так же, как метки.
Допускается псевдокоманда equ, аналогичная
по действию директиве #define препроцессора
языка Си. Символьный идентификатор, стоящий слева от псевдокоманды, во всём
последующем тексте программы заменяется текстовой строкой, стоящей справа от
этой псевдокоманды. В начале программы может присутствовать псевдокоманда org; в конце программы
может присутствовать псевдокоманда end.
Псевдокоманды org и end задают метку команды, с которой должно начинаться выполнение
программы; если они отсутствуют, то выполнение будет начинаться с первой
команды программы. Содержимое программы после псевдокоманды end игнорируется. Операндом команды
может быть выражение, составленное из скобок, знаков арифметических (+ – * / %) и логических (&& || ! == != <= >=) операций,
целых чисел (допускается шестнадцатеричная запись в виде 0xABCD)
и меток. При компиляции выражение вычисляется и заменяется своим значением по
модулю CORESIZE.
Бинологическая модель: модель биологического мира, в которой в качестве живых существ рассматриваются компьютерные программы.
Бинология: изучение бинологических моделей; "двоичная биология".
Эволютор (evolver): программа или блок программы, моделирующий биологическую эволюцию (мутации, скрещивание, естественный отбор).
Генетическое программирование: использование эволюторов в компьютерных программах.
Со-эволюция двух и более видов: ход эволюции, в котором критерии естественного отбора для одного вида меняются как результат эволюционных изменений других видов.