Основная война
 Запуск под симулятором pMARS | |
| Разработчик(и) | Д.Г. Джонс и А.К. Дьюдни |
|---|---|
| Первоначальный выпуск | Март 1984 г. |
| Тип | Программирование игры |
| Веб-сайт | www |
Core War — это игра по программированию 1984 года , созданная Д. Г. Джонсом и А. К. Дьюдни , в которой две или более боевых программ (называемых «воинами») соревнуются за контроль над виртуальным компьютером . Эти боевые программы написаны на абстрактном языке ассемблера под названием Redcode . Стандарты языка и виртуальной машины изначально были установлены Международным обществом основных войн (ICWS), но позже стандарты были определены консенсусом сообщества.
Геймплей
[ редактировать ]В начале игры каждая боевая программа загружается в память в случайном месте, после чего каждая программа по очереди выполняет одну инструкцию. Цель игры — заставить процессы противостоящих программ завершиться (что происходит, если они выполняют недопустимую инструкцию), оставив победившую программу единоличным владением машиной.
Самая ранняя опубликованная версия Redcode определяла только восемь инструкций. Стандарт ICWS-86 увеличил это число до 10, а стандарт ICWS-88 увеличил его до 11. Используемый в настоящее время проект стандарта 1994 года содержит 16 инструкций. Однако Redcode поддерживает ряд различных режимов адресации и (начиная с проекта стандарта 1994 года) модификаторов инструкций, которые увеличивают фактическое количество возможных операций до 7168. Стандарт Redcode оставляет базовое представление инструкций неопределенным и не предоставляет программам средств доступа к нему. . Арифметические операции могут выполняться с двумя адресными полями, содержащимися в каждой инструкции, но единственные операции, поддерживаемые над самими кодами команд, — это копирование и сравнение на равенство.
- Постоянная длина и время инструкции
- Каждая инструкция Redcode занимает ровно один слот памяти и выполняется ровно за один цикл. Однако скорость, с которой процесс выполняет инструкции, зависит от количества других процессов в очереди, поскольку время обработки распределяется поровну.
- Круговая память
- Память адресуется в единицах одной инструкции. Пространство памяти (или ядро ) имеет конечный размер, но только относительная адресация используется , то есть адрес 0 всегда относится к текущей выполняющейся инструкции, адрес 1 — к инструкции после нее и так далее. Максимальное значение адреса устанавливается равным на единицу меньшему, чем количество ячеек памяти, и при необходимости выполняется перенос. В результате между адресами и ячейками памяти существует взаимно однозначное соответствие, но программа Redcode не может определить какой-либо абсолютный адрес. Процесс, который не встречает недопустимых инструкций или инструкций перехода, будет продолжать выполнять последовательные инструкции бесконечно, в конечном итоге возвращаясь к инструкции, с которой он начался.
- Низкоуровневая многопроцессорность
- Вместо одного указателя инструкций симулятор Redcode имеет очередь процессов для каждой программы, содержащую переменное количество указателей инструкций, которые симулятор циклически проходит. Каждая программа запускается только с одним процессом, но в очередь можно добавлять новые процессы с помощью команды
SPLинструкция. Процесс умирает, когда он выполняет DAT или выполняет деление на ноль. Программа считается мертвой, если в ней больше не осталось процессов.
- Нет внешнего доступа
- Redcode и архитектура MARS не предоставляют никаких функций ввода или вывода. Симулятор представляет собой закрытую систему, единственным входом которой являются начальные значения памяти и очередей процессов, а единственным выходом — результат битвы, т. е. какие программы сохранили выжившие процессы. Конечно, симулятор все еще может позволять внешний осмотр и модификацию памяти во время моделирования.
Версии Редкода
[ редактировать ]Существует несколько версий Redcode. Самая ранняя версия, описанная А. К. Дьюдни. [1] во многих отношениях отличается от более поздних стандартов, установленных Международным основным военным обществом, и может считаться другим, хотя и родственным языком. Форма Redcode, наиболее часто используемая сегодня, основана на проекте стандарта, представленном ICWS в 1994 году, который так и не был официально принят, поскольку примерно в то время ICWS фактически прекратил свое существование. Однако разработка Redcode продолжалась неформально, в основном через онлайн-форумы, такие как rec.games.corewar[2] группа новостей .
Стратегия
[ редактировать ]Воинов обычно делят на несколько широких категорий, хотя настоящие воины часто могут сочетать поведение двух или более из них. Три из распространенных стратегий ( репликатор , сканер и бомбардировщик ) также известны как «бумага, ножницы и камень» , поскольку их эффективность друг против друга приближается к эффективности их однофамильцев в известной детской игре. [3]
- Бумага (или репликатор)
- Репликатор создает повторяющиеся копии самого себя и выполняет их параллельно, в конечном итоге заполняя все ядро копиями своего кода. Репликаторы трудно убить, но часто им трудно убить своих противников. Таким образом, репликаторы имеют тенденцию набирать много связей, особенно с другими репликаторами.
- Шелк — это особый тип очень быстрого репликатора, названный в честь Шелкового Воина. [4] Юха Похьялайнен. Большинство современных репликаторов относятся к этому типу. Репликаторы Silk используют параллельное выполнение для копирования всего кода с помощью одной инструкции и начинают выполнение копии до ее завершения. [5]
- Ножницы (или сканер)
- Сканер создан, чтобы побеждать репликаторы. Сканер не атакует вслепую, а пытается обнаружить врага, прежде чем начать целенаправленную атаку. Это делает его более эффективным против трудноуничтожимых противников, таких как репликаторы, но также делает его уязвимым для приманок. Сканер обычно бомбит память SPL 0 инструкций. Это заставляет врага создавать огромное количество процессов, которые ничего не делают, а создают еще больше процессов, замедляя полезные процессы. Когда враг становится настолько медлительным, что не может сделать ничего полезного, память подвергается бомбардировке. Инструкции DAT . Сканеры также, как правило, более сложны и, следовательно, крупнее и более хрупкие, чем другие типы воинов. [6]
- Одноразовый сканер — это очень простой сканер, который сканирует ядро только до тех пор, пока не найдет первую цель, а затем навсегда переключается на стратегию атаки, обычно на зачистку ядра. Мирмидон [7] Роя ван Рейна является примером ваншота.
- Камень (или бомбардировщик)
- Бомбардировщик слепо копирует «бомбу» через определенные промежутки времени в ядро, надеясь поразить противника. Бомба часто представляет собой Инструкция DAT , хотя могут использоваться и другие инструкции или даже бомбы из нескольких инструкций. Бомбардировщик может быть маленьким и быстрым, и он получает дополнительное преимущество перед сканированием противников, поскольку бомбы также служат удобным отвлечением. Бомбардировщики часто комбинируются со спиралями бесов, чтобы повысить устойчивость к репликаторам.
- Вампир (или ловец из ямы)
- Вампир пытается заставить процессы своего противника прыгнуть в часть его собственного кода, называемую «ямой». Вампиры могут быть основаны либо на бомбардировщиках, либо на сканерах. Основная слабость вампиров заключается в том, что на них можно легко напасть косвенно, поскольку им приходится разбрасывать указатели на свой код по всему ядру. Их атаки также медленны, так как процессам требуется дополнительный раунд, чтобы добраться до ямы. мойВамп [8] Паулссона является примером вампира.
- Бес
- Бесы названы в честь первого опубликованного воина, Беса. [9] от AK Dewdney , тривиального мобильного воина с одной командой, который постоянно копирует свою единственную инструкцию непосредственно перед указателем инструкций . Бесов трудно убить, но они практически бесполезны для нападения. Их польза заключается в том, что их легко порождать в больших количествах, и они могут выжить, даже если остальные воины будут убиты.
- Кольцо импов (или спираль импов ) состоит из импов, расположенных на равных интервалах вокруг ядра и исполняющихся поочередно. Бесы на каждом плече кольца/спирали копируют свои инструкции на следующее плечо, где они немедленно выполняются снова. Кольца и спирали убить даже труднее, чем простых бесов, и у них даже есть (небольшой) шанс убить воинов, не защищенных от них. Число ветвей в кольце или спирали импа должно быть пропорционально размеру ядра.
- Быстрый сканер (или q-скан)
- Быстрый сканер пытается поймать противника на ранней стадии, используя очень быстрый развернутый цикл сканирования. Быстрое сканирование — это стратегия ранней игры, и она всегда требует какой-либо другой стратегии в качестве резервной. Добавление компонента быстрого сканирования к воину может улучшить его счет против длинных воинов, таких как другие быстрые сканеры. Однако развернутое сканирование может охватывать только ограниченное количество локаций и вряд ли сможет поймать небольшого противника.
- Ядро ясно
- Очистка ядра последовательно перезаписывает каждую инструкцию в ядре, иногда даже включая саму себя. Зачистка ядра не очень распространена в качестве отдельных воинов, но часто используется бомбардировщиками и сканерами в качестве финальной стратегии.
Основное военное программирование
[ редактировать ]Понимая основные стратегии войны , программист может создать воина для достижения определенных целей. Революционные идеи приходят время от времени; однако в большинстве случаев программисты основывают свои программы на уже опубликованных воинах. Используя оптимизаторы, такие как OptiMax, или инструменты базового оптимизатора, можно создать более эффективного воина.
Воины также могут быть созданы с помощью генетических алгоритмов или генетического программирования . Программы, интегрирующие эту эволюционную технику, известны как эволюционеры . Несколько разработчиков были представлены сообществом Core War и, как правило, сосредоточены на создании воинов для небольших основных настроек. Последним разработчиком, добившимся значительного успеха, был μGP. [10] которая произвела на свет одних из самых успешных нано- и крошечных воинов. Тем не менее, эволюционной стратегии еще предстоит доказать свою эффективность в более крупных основных условиях. [11]
Разработка
[ редактировать ]Core War была вдохновлена самовоспроизводящейся программой Creeper и последующей программой Reaper, которая уничтожала копии Creeper. [12] Creeper был создан Бобом Томасом из BBN . [13] Дьюдни не знал о происхождении Крипера и Жнеца и называет их слухами, исходящими от Дарвина и экспериментов Шоха и Хаппа с червями. 1984 года Статья в журнале Scientific American о войне ядра . [12] тем не менее, цитирует игру «Дарвин» , в которую играли Виктор А. Высоцкий , Роберт Моррис и Дуглас Макилрой в Bell Labs в 1961 году.
Слово «Core» в названии происходит от слова « память с магнитным сердечником» , устаревшей технологии оперативной памяти . Этот термин тогда и до сих пор обычно используется для обозначения рабочей памяти в дампах рабочей памяти, называемых дампами ядра , в Unix и большинстве Unix-подобных систем. Кроме того, имя файла по умолчанию, используемое для дампов ядра в таких системах, обычно «core» или содержит слово «core».
Первое описание языка Redcode было опубликовано в марте 1984 года в Core War Guidelines Д.Г. Джонсом и А.К. Дьюдни . [1] Игра была представлена публике в мае 1984 года в статье, написанной Дьюдни в журнале Scientific American . Дьюдни вновь обратился к Core War в своей колонке «Компьютерные развлечения» в марте 1985 года. [14] и снова в январе 1987 г. [15]
Международное общество основных войн (ICWS) было основано в 1985 году, через год после публикации оригинальной статьи Дьюдни. ICWS опубликовал новые стандарты языка Redcode в 1986 и 1988 годах и предложил обновление в 1994 году, которое так и не было официально установлено в качестве нового стандарта. [16] Тем не менее, проект 1994 года был широко принят и расширен, и сегодня он составляет основу фактического стандарта Redcode. Режиссерами ICWS были Марк Кларксон (1985–1987), Уильям Р. Бакли (1987–1992) и Джон Ньюман (1992–); в настоящее время [ когда? ] ICWS прекратил свое существование. [17]
Редкод
[ редактировать ]0000: ADD.AB # 4, $ 3
0001: MOV.F $ 2, @ 2
0002: JMP.B $ -2, $ 0
0003: DAT.F # 0, # 0
Redcode — это язык программирования, используемый в Core War . Он выполняется виртуальной машиной , известной как симулятор красного кода массива памяти или MARS . Дизайн Redcode во многом основан на реальных CISC языках ассемблера начала 1980-х годов, но содержит несколько особенностей. [ нечеткий ] обычно не встречается в реальных компьютерных системах.
И Redcode, и среда MARS созданы для предоставления простой и абстрактной платформы без сложности реальных компьютеров и процессоров. Хотя Redcode должен напоминать обычный язык ассемблера CISC, он довольно упрощен по сравнению с «настоящим» ассемблером и не имеет абсолютной адресации памяти.
Исходные 8 инструкций описаны следующим образом. В более поздних версиях добавлены NOP, умножение и более сложные сравнения. [18]
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
Реализации
[ редактировать ]Разработка реализаций игры продолжалась на протяжении многих лет несколькими авторами. Доступно несколько версий игры, [19] портирован на несколько платформ. Например, pMARS — программное обеспечение с открытым исходным кодом которого , исходный код находится на SourceForge . [20] или SDL . на основе SDL pMARS для Windows [21]
Общая реализация pMars была загружена более 35 000 раз в период с 2000 по 2021 год с SourceForge . [22]
Ссылки
[ редактировать ]- ^ Jump up to: а б Джонс, Д.Г.; Дьюдни, АК (март 1984 г.). «Основные принципы войны» . Проверено 27 мая 2023 г.
- ^ «rec.games.corewar в группах Google» . Проверено 29 мая 2023 г.
- ^ Вангсо, Минтарджо. «Введение в искусство 88-го: трилогия Бумага-Камень-Ножницы» . Проверено 27 мая 2023 г.
- ^ Остроботний, Джиппо. «Шелковый воин 1.3» . Проверено 27 мая 2023 г.
- ^ Похьялайнен, Джиппо (апрель 1995 г.). «репликаторы? -> Phoenix & TimeScapesource» . Проверено 27 мая 2023 г.
- ^ Меткалф, Джон (апрель 2004 г.). «Анатомия сканера, базовое введение» . Проверено 27 мая 2023 г.
- ^ ван Рейн, Рой. «Мирмидон» . Проверено 27 мая 2023 г.
- ^ Паулссон, Магнус. «myVamp v3.7» . Проверено 27 мая 2023 г.
- ^ Дьюдни, АК «Имп» . Проверено 27 мая 2023 г.
- ^ Скиллеро, Джованни. «μGP (MicroGP v2)» . Гитхаб . Проверено 10 сентября 2018 г.
- ^ Вок, Баркли; Подожди, Александр; Шмидт, Кристиан. «Эволюционный подход создает конкурентоспособные человеческие программы основной войны» (PDF) . Проверено 27 мая 2023 г.
- ^ Jump up to: а б Дьюдни, АК (май 1984 г.). «В игре под названием Core War враждебные программы участвуют в битве битов» . Научный американец . Проверено 27 мая 2023 г.
- ^ Шох, Дж. ; Хапп, Дж. (март 1982 г.). «Программы-черви — ранний опыт распределенных вычислений» . Коммуникации АКМ . 25 (3): 172–180. дои : 10.1145/358453.358455 . S2CID 1639205 .
- ^ Дьюдни, AK (март 1985 г.). «Бестиарий вирусов, червей и других угроз компьютерной памяти» Core War . Научный американец . Проверено 27 мая 2023 г.
- ^ Дьюдни, AK (январь 1987 г.). «Программа под названием MICE пробивается к победе на первом турнире Core War» . Научный американец . Проверено 27 мая 2023 г.
- ^ Долигез, Дэмиен; Дарем, Марк (8 ноября 1995 г.). «Аннотированный проект предлагаемого основного военного стандарта 1994 года» . Проверено 27 мая 2023 г.
- ^ Меткалф, Джон. «Краткая история Corewar» . Проверено 27 мая 2023 г.
- ^ «Руководство для начинающих по Redcode, v1.23» .
- ^ Эмуляторы Corewar на corewar.info
- ^ corewar на SourceForge
- ^ pMARS-SDL на corewar.co.uk, автор Йоонас Пихлая (7 мая 2003 г.)
- ^ скачать номера corewar на SourceForge (доступ 07.06.2021)