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

Недавно ездил к родителям разбирать свои старые вещи, включая подборки журналов - наткнулся на "В Мире Науки" ажно за 1989 год.
Вообще-то это перевод "Scientific American", но суть не в этом - в то время в журнале вел постоянную колону Alexander Dewdney, посвященную разным аспектами CS, оттуда-то я впервые и узнал про "войны в памяти"...


Про эту игру (Core Wars) мало кто слышал - такое развлечение исключительно для программистов (или тех, у кого программирование - хобби). Суть его в сражении, но не между людьми, а между специальными программами. Цель - написать такую программу-бойца, которая победит остальных.

Как происходит бой? Программы загружаются в общую закольцованную область памяти (в оригинале - 8K, если не ошибаюсь) и одновременно запускаются. Та, что проработает дольше всех - победитель. Программа, которая исполнила недопустимую инструкцию (DAT), "умирает". Понятно, что сам автор таких инструкций в неё не добавляет - ими "бомбят" память другие программы в надежде испортить конкурентов. Кроме того, пытаясь уйти от бомбёжки, почти все программы то и дело перемещают себя в памяти.

Пишутся бойцы с использованием разновидности ассемблера, которая называется Redcode, а исполняются с помощью специального интерпретатора, который понимает скомпилированный с Redcode байт-код. Кстати, первый такой интерпретатор носил звучное название MARS (Memory Array Redcode Simulator).

В оригинальной версии Redcode было всего 10 команд (копирование, арифметика, переходы, запуск потока выполнения) и пара способов адресации (все относительные, поскольку в зацикленной памяти абсолютная адресация бессмысленна).

Простейший боец состоит из всего лишь одной команды:

mov 0, 1

Что она делает? Происходит копирование содержимого текущей ячейки в следующую, после передачи управления на нее процесс повторится уже в новой позиции - фактически вся память "затирается" этой командой, уничтожая чужие коды.

Понятно, что выиграть такой программой не получится - только подчинить чужого бойца своей воле, но ведь можно же написать и более сложную программу, которая помещает в память инструкцию DAT, выполнение которой приводит к аварийному завершению потока управления - а вот это как раз именно то, что нужно.

Чуть более сложная программа, которая этим занимается (бомбит командой DAT каждую пятую ячейку памяти, самоубийство исключается за счет собственного размера в 4 ячейки):

        DAT -1
        ADD #5      -1
        MOV #0      @-2
        JMP -2

Развлечение прижилось, и в 1994 году был принят новый "стандарт" для Redcode - набор команд расширился более чем вдвое, появилось семь (!) способов адресации, "приватная" память для каждого бойца, не входящая в общий массив памяти.

Программы стали выглядеть сложнее (уже неприятно напоминая ассемблер для некогда популярной однокристаллки) :-(

Вот это новый mov/"Imp":

        mov.i $0, $1

А это разновидность "bomber'a":

        mov.i   $3,     $7
        add.ab  #4,     $-1
        jmp.a   $-2,    #0
        dat.f   #0,     #0

"Сoreclear":

        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

В общем, забава эта довольно увлекательна, более подробно про нее можно почитать здесь или здесь, есть довольно активное community.

Наиболее подходящим интерпретатором (по моему мнению) сейчас является pMARS.

Боевых достижений!