Основная война -Core War
| Основная война | |
|---|---|
 Игра Core War под управлением симулятора pMARS
| |
| Разработчики) | Д. Джонс и А. К. Дьюдни |
| Выпускать | Март 1984 г. |
| Жанр (ы) | Программирование игры |
Core War - это игра по программированию 1984 года,созданная Д. Дж. Джонсом и А. К. Дьюдни, в которой две или более боевых программ (называемых «воинами») соревнуются за контроль над виртуальным компьютером . Эти боевые программы написаны на абстрактном ассемблере, который называется Redcode .
Геймплей
В начале игры каждая боевая программа загружается в память в случайном месте, после чего каждая программа по очереди выполняет одну инструкцию. Цель игры - вызвать завершение процессов противостоящих программ (что происходит, если они выполняют недопустимую инструкцию), оставляя победившую программу в исключительном владении машины.
Самая ранняя опубликованная версия Redcode определяла только восемь инструкций. Стандарт ICWS-86 увеличил это число до 10, а стандарт ICWS-88 увеличил его до 11. Используемый в настоящее время проект стандарта 1994 года содержит 16 инструкций. Однако Redcode поддерживает ряд различных режимов адресации и (начиная с проекта стандарта 1994 г.) модификаторы инструкций, которые увеличивают фактическое количество возможных операций до 7168. Стандарт Redcode оставляет базовое представление инструкции неопределенным и не предоставляет программам средств доступа к нему. . Арифметические операции могут выполняться с двумя адресными полями, содержащимися в каждой инструкции, но единственные операции, поддерживаемые с самими кодами инструкций, - это копирование и сравнение на равенство.
- Постоянная длина и время инструкции
- Каждая инструкция Redcode занимает ровно один слот памяти и требует для выполнения ровно одного цикла. Однако скорость, с которой процесс выполняет инструкции, зависит от количества других процессов в очереди, поскольку время обработки распределяется поровну.
- Круговая память
- Память адресуется в единицах одной инструкции. Пространство памяти (или ядро ) имеет конечный размер, но используется только относительная адресация , то есть адрес 0 всегда относится к текущей выполняемой инструкции, адрес 1 - к инструкции после нее и так далее. Максимальное значение адреса устанавливается на единицу меньше, чем количество ячеек памяти, и при необходимости будет повторяться. В результате существует взаимно однозначное соответствие между адресами и ячейками памяти, но программа Redcode не может определить какой-либо абсолютный адрес. Процесс, который не обнаруживает недействительных инструкций или инструкций перехода, будет продолжать бесконечно выполнять последовательные инструкции, в конечном итоге возвращаясь к инструкции, с которой он был запущен.
- Многопроцессорность низкого уровня
- Вместо одного указателя инструкций симулятор Redcode имеет очередь обработки для каждой программы, содержащую переменное количество указателей инструкций, которые симулятор выполняет циклически. Каждая программа запускается только с одним процессом, но новые процессы могут быть добавлены в очередь с помощью
SPLинструкции. Процесс умирает, когда выполняет инструкцию DAT или выполняет деление на ноль. Программа считается мертвой, если в ней больше не осталось процессов.
- Нет внешнего доступа
- Redcode и архитектура MARS не предоставляют функций ввода или вывода. Симулятор представляет собой замкнутую систему, единственными входными данными которой являются начальные значения памяти и очередей процессов, а единственным выходом является результат битвы, т. Е. Какие программы имеют уцелевшие процессы. Конечно, симулятор может по-прежнему разрешать внешний осмотр и модификацию памяти во время симуляции.
Версии Redcode
Существует несколько версий Redcode. Самая ранняя версия, описанная А. К. Девдни, во многих отношениях отличается от более поздних стандартов, установленных Международным базовым военным обществом, и может рассматриваться как другой, хотя и связанный, язык. Форма Redcode, наиболее часто используемая сегодня, основана на проекте стандарта, представленного в ICWS в 1994 году, который так и не был официально принят, поскольку примерно в то время ICWS фактически прекратил свое существование. Однако разработка Redcode продолжалась в неформальной манере, в основном через онлайн-форумы, такие как группа rec.games.corewar новостей .
Стратегия
Воинов обычно делят на несколько широких категорий, хотя настоящие воины часто могут сочетать поведение двух или более из них. Три из распространенных стратегии ( репликатор , сканер и бомбардировщик ) также известны как бумага, ножницы и камень , поскольку их эффективность друг против друга приближается к таковым у их однофамильцев в хорошо известной игровой площадке.
- Бумага (или репликатор)
- Репликатор создает повторяющиеся копии самого себя и выполняет их параллельно, в конечном итоге заполняя все ядро копиями своего кода. Репликаторов трудно убить, но часто бывает трудно убить своих противников. Поэтому репликаторы, как правило, имеют много связей, особенно с другими репликаторами.
- Шелк представляет собой особый тип очень быстрый репликатор, названный в честь шелкового Воина Юха Pohjalainen. Большинство современных репликаторов относятся к этому типу. Репликаторы Silk используют параллельное выполнение для копирования всего кода с помощью одной инструкции и начинают выполнение копии до ее завершения.
- Ножницы (или сканер)
- Сканер создан для того, чтобы побеждать репликаторы. Сканер не атакует вслепую, но пытается определить местонахождение врага перед тем, как начать целевую атаку. Это делает его более эффективным против сложных противников, таких как репликаторы, но также делает его уязвимым для ловушек. Сканер обычно бомбит память инструкциями SPL 0 . Это заставляет врага создавать огромное количество процессов, которые ничего не делают, кроме создания большего количества процессов, замедляя полезные процессы. Когда противник становится настолько медленным, что не может сделать ничего полезного, память бомбардируется инструкциями DAT . Сканеры также обычно более сложные и, следовательно, более крупные и хрупкие, чем другие типы воинов.
- Один выстрел очень простой сканер , который сканирует только ядро до тех пор, пока не найдет первую цель, а затем окончательно переходит к стратегии атаки, как правило , сердечник ясно. «Мирмидон » Роя ван Рейна - это пример одного выстрела.
- Камень (или бомбардировщик)
- Бомбардировщик слепо копирует «бомбу» через равные промежутки времени в ядре, надеясь поразить врага. Бомба часто является инструкцией DAT , хотя могут использоваться другие инструкции или даже бомбы с несколькими инструкциями. Бомбардировщик может быть маленьким и быстрым, и они получают дополнительное преимущество перед сканированием противников, поскольку бомбы также служат удобным отвлечением. Бомбардировщики часто сочетаются со спиралями импа, чтобы получить дополнительную устойчивость против репликаторов.
- Вампир (или яма-ловец)
- Вампир пытается заставить процессы своего оппонента перейти в часть его собственного кода, называемую «ямой». Вампиры могут базироваться как на бомбардировщиках, так и на сканерах. Основная слабость вампиров заключается в том, что их легко атаковать косвенно, поскольку они должны по необходимости разбрасывать указатели на свой код по всему ядру. Их атаки также медленные, так как процессам требуется дополнительный раунд, чтобы достичь ямы. myVamp от Paulsson - пример вампира.
- Бес
- Бесы названы в честь первого из опубликованных воинов, Беса, созданного А.К. Дьюдни , банальным мобильным воином с одной инструкцией, который постоянно копирует свою единственную инструкцию прямо перед указателем инструкции . Бесов трудно убить, но они почти бесполезны для нападения. Их польза заключается в том, что они легко могут появиться в большом количестве и могут выжить, даже если остальная часть воина будет убита.
- Имп кольцо (или имп спираль ) состоит из чертят , расположенных через равные промежутки вокруг сердечника и исполняющих попеременно. Бесы на каждом плече кольца / спирали копируют свою инструкцию в следующее плечо, где она немедленно выполняется снова. Кольца и спирали даже сложнее убить, чем простых бесов, и у них даже есть (небольшой) шанс убить воинов, не защищенных от них. Количество рукавов в имп кольце или спирали должно быть пропорционально размеру сердечника.
- Quickscanner (или q-scan)
- Quickscanner пытается поймать своего противника на ранней стадии, используя очень быстрый развернутый цикл сканирования. Быстрое сканирование - это стратегия на раннем этапе игры, которая всегда требует какой-либо другой стратегии в качестве резервной. Добавление компонента быстрого сканирования к воину может улучшить его счет против длинных воинов, таких как другие устройства быстрого сканирования. Однако развернутое сканирование может нацеливаться только на ограниченное количество местоположений и вряд ли сможет поймать небольшого противника.
- Ядро ясно
- Очистка ядра последовательно перезаписывает все инструкции в ядре, иногда даже включая себя. Очищения ядра не очень распространены в качестве самостоятельных воинов, но часто используются бомбардировщиками и сканерами в качестве стратегии конечной игры.
Основное программирование войны
С пониманием основной войной стратегии, программист может создать воин для достижения определенных целей. Революционные идеи приходят время от времени; Однако в большинстве случаев программисты основывают свои программы на уже опубликованных воинах. Используя оптимизаторы, такие как OptiMax или инструменты оптимизатора основных шагов, можно создать более эффективного воина.
Воинов также можно создавать с помощью генетических алгоритмов или генетического программирования . Программы, которые объединяют этот эволюционный метод, известны как эволюционеры . Сообщество Core War представило несколько эволюционеров, которые, как правило, сосредоточены на создании воинов для небольших основных настроек. Последней разработкой, добившейся значительного успеха, стала μGP, которая произвела на свет одних из самых успешных нано- и крошечных воинов. Тем не менее, эволюционная стратегия еще должна доказать свою эффективность на более крупных базовых объектах.
Разработка
Core War была вдохновлена самовоспроизводящейся программой под названием Creeper и последующей программой под названием Reaper, которая уничтожала копии Creeper. Creeper был создан Бобом Томасом на BBN . Дьюдни не знал о происхождении Крипера и Жнеца и называет их слухом, исходящим от Дарвина и экспериментов Шоха и Хаппа с червями . Тем не менее в статье Scientific American 1984 года о войне за ядро цитируется игра Дарвина , в которую Виктор Высоцкий , Роберт Моррис и Дуглас Макилрой в 1961 году в Bell Labs играли . Слово «ядро» в названии происходит от памяти магнитного сердечника , устаревшего технология оперативной памяти .
Первое описание языка Redcode было опубликовано в марте 1984 г. в Core War Guidelines DG Jones и AK Dewdney . Игра была представлена публике в мае 1984 года в статье, написанной Дьюдни в Scientific American . Дьюдни вернулся к Core War в своей колонке «Computer Recreations» в марте 1985 года и снова в январе 1987 года.
Международное общество ядерных войн (ICWS) было основано в 1985 году, через год после первой статьи Дьюдни. ICWS опубликовал новые стандарты для языка Redcode в 1986 и 1988 годах и предложил обновление в 1994 году, которое никогда не было официально установлено в качестве нового стандарта. Тем не менее, проект 1994 года был широко принят и расширен, и сегодня он составляет основу фактического стандарта Redcode. Руководили ICWS Марк Кларксон (1985–1987), Уильям Р. Бакли (1987–1992) и Джон Ньюман (1992–); в настоящее время ICWS не функционирует.
Redcode
0000: ADD.AB # 4, $ 3
0001: MOV.F $ 2, @ 2
0002: JMP.B $ -2, $ 0
0003: DAT.F # 0, # 0
Redcode - это язык программирования, используемый в Core War . Он выполняется виртуальной машиной, известной как имитатор Redcode массива памяти или MARS . Дизайн Redcode частично основан на реальных языках ассемблера CISC начала 1980-х годов, но содержит несколько функций, которые обычно не встречаются в реальных компьютерных системах.
И Redcode, и среда MARS предназначены для предоставления простой и абстрактной платформы без сложности реальных компьютеров и процессоров. Хотя Redcode призван напоминать обычный язык ассемблера CISC, он довольно упрощен по сравнению с «реальной» сборкой и не имеет абсолютной адресации памяти.
Исходные 8 инструкций описаны ниже, более поздние версии добавили NOP, умножение и более сложные сравнения.
OPcode Mnemonic Argument(s) Action
------- --------- ----- ----- ----------------------------------
0 DAT B Initialize location to value B.
1 MOV A B Move A into location B.
2 ADD A B Add operand A to contents of location B and store result in
location B.
3 SUB A B Subtract operand A from contents of location B and store result in
location B.
4 JMP B Jump to location B.
5 JMZ A B If operand A is 0, jump to location B; otherwise continue with
next instruction.
6 DJZ A B Decrement contents of location A by 1. If location A now holds 0,
jump to location B; otherwise continue with next instruction.
7 CMP A B Compare operand A with operand B. If they are not equal, skip next
instruction; otherwise execute next instruction.
В проект стандарта ICWS '94 добавлено больше режимов адресации, в основном для работы с косвенным адресом A-поля, что дает в общей сложности 8 режимов адресации:
# — immediate
$ — direct (the $ may be omitted)
* — A-field indirect
@ — B-field indirect
{ — A-field indirect with predecrement
< — B-field indirect with predecrement
} — A-field indirect with postincrement
> — B-field indirect with postincrement
Реализации
Разработка реализаций игры продолжалась на протяжении многих лет несколькими авторами. Доступно несколько версий игры, портированных для нескольких платформ. Например, pMARS, который представляет собой программное обеспечение с открытым исходным кодом с исходным кодом на Sourceforge , или SDL pMARS для Windows на основе SDL . Недавно был создан полностью веб-симулятор https://www.corewar.io/, устраняющий необходимость загрузки каких-либо инструментов для конкретной платформы.
Общая реализация pMars была загружена с Sourceforge более 35000 раз в период с 2000 по 2021 год .