stringtranslate.com

Основная война

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 , хотя могут использоваться и другие инструкции или даже бомбы из нескольких инструкций. Бомбардировщик может быть маленьким и быстрым, и он получает дополнительное преимущество перед сканированием противников, поскольку бомбы также служат удобным отвлечением. Бомбардировщики часто комбинируются со спиралями бесов, чтобы повысить устойчивость к репликаторам.
Вампир (или ловец из ямы)
Вампир пытается заставить процессы своего противника прыгнуть в часть его собственного кода, называемую «ямой». Вампиры могут быть основаны либо на бомбардировщиках, либо на сканерах. Основная слабость вампиров заключается в том, что на них можно легко напасть косвенно, поскольку им приходится разбрасывать указатели на свой код по всему ядру. Их атаки также медленны, так как процессам требуется дополнительный раунд, чтобы добраться до ямы. myVamp [8] Паулссона является примером вампира.
Бес
Бесы названы в честь первого опубликованного воина, Imp [9] А. К. Дьюдни , тривиального мобильного воина с одной командой, который постоянно копирует свою единственную инструкцию непосредственно перед указателем инструкций . Бесов трудно убить, но они практически бесполезны для нападения. Их польза заключается в том, что их легко порождать в больших количествах, и они могут выжить, даже если остальные воины будут убиты.
Кольцо импов (или спираль импов ) состоит из импов, расположенных на равных интервалах вокруг ядра и исполняющихся поочередно. Бесы на каждом плече кольца/спирали копируют свои инструкции на следующее плечо, где они немедленно выполняются снова. Кольца и спирали убить даже труднее, чем простых бесов, и у них даже есть (небольшой) шанс убить воинов, не защищенных от них. Количество ветвей в кольце или спирали импа должно быть пропорционально размеру ядра.
Быстрый сканер (или q-скан)
Быстрый сканер пытается поймать противника на ранней стадии, используя очень быстрый развернутый цикл сканирования. Быстрое сканирование — это стратегия ранней игры, и она всегда требует какой-либо другой стратегии в качестве резервной. Добавление компонента быстрого сканирования к воину может улучшить его счет против длинных воинов, таких как другие быстрые сканеры. Однако развернутое сканирование может охватывать только ограниченное количество локаций и вряд ли сможет поймать небольшого противника.
Ядро ясно
Очистка ядра последовательно перезаписывает каждую инструкцию в ядре, иногда даже включая саму себя. Зачистка ядра не очень распространена в качестве отдельных воинов, но часто используется бомбардировщиками и сканерами в качестве финальной стратегии.

Основное военное программирование

Понимая основные стратегии войны , программист может создать воина для достижения определенных целей. Революционные идеи приходят время от времени; однако в большинстве случаев программисты основывают свои программы на уже опубликованных воинах. Используя оптимизаторы, такие как OptiMax, или инструменты оптимизатора основных этапов, можно создать более эффективного воина.

Воины также могут быть созданы с помощью генетических алгоритмов или генетического программирования . Программы, интегрирующие эту эволюционную технику, известны как эволюционеры . Несколько разработчиков были представлены сообществом Core War и, как правило, сосредоточены на создании воинов для небольших основных настроек. Последним разработчиком, добившимся значительного успеха, был μGP [10] , который создал одних из самых успешных нано- и крошечных воинов. Тем не менее, эволюционной стратегии еще предстоит доказать свою эффективность в более крупных основных условиях. [11]

Разработка

Core War была вдохновлена ​​самовоспроизводящейся программой Creeper и последующей программой Reaper, которая уничтожала копии Creeper. [12] Creeper был создан Бобом Томасом из BBN . [13] Дьюдни не знал о происхождении Крипера и Жнеца и называет их слухами, исходящими от Дарвина и экспериментов Шоха и Хаппа с червями. В статье Scientific American 1984 года о Core War [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 : ДОБАВИТЬ . AB # 4 , $ 30001 : МОВ .​ F $ 2 , @ 2 0002 : JMP . B $ -2 , $ 00003 : DAT .​​ Ф # 0 , # 0
Собранный Redcode в стиле ICWS-94.

Redcode — это язык программирования, используемый в Core War . Он выполняется виртуальной машиной , известной как симулятор красного кода массива памяти или MARS . Дизайн Redcode во многом основан на реальных языках ассемблера CISC начала 1980-х годов, но содержит несколько функций [ неопределенно ] , которые обычно не встречаются в реальных компьютерных системах.

И Redcode, и среда MARS созданы для предоставления простой и абстрактной платформы без сложности реальных компьютеров и процессоров. Хотя Redcode должен напоминать обычный язык ассемблера CISC, он довольно упрощен по сравнению с «настоящим» ассемблером и не имеет абсолютной адресации памяти.

Исходные 8 инструкций описаны следующим образом. В более поздних версиях добавлены NOP, умножение и более сложные сравнения. [18]

Мнемонический код операции Аргумент (ы) Действие ------- --------- ----- ----- ----------------- ----------------- 0 DAT B Инициализировать местоположение значением B .​ 1 MOV A B Переместите A в позицию B.​ 2 ADD A B Добавьте операнд A к содержимому ячейки B и сохраните результат в ячейке B.​​ 3 SUB A B Вычитает операнд A из содержимого ячейки B и сохраняет результат в ячейке B.​​ 4 JMP B Перейти в точку B.​ 5 JMZ A B Если операнд A равен 0 , перейти в позицию B ; в противном случае перейдите к следующей инструкции . 6 DJZ A B Уменьшить содержимое ячейки A на 1 .​ Если в позиции A теперь находится 0 , перейдите в позицию B ; в противном случае перейдите к следующей инструкции . 7 CMP A B Сравнить операнд A с операндом B.​ Если они не равны , пропустите следующую инструкцию ;​ в противном случае выполните следующую инструкцию .

В проекте стандарта ICWS '94 добавлено больше режимов адресации, в основном для работы с косвенностью A-поля, что дает в общей сложности 8 режимов адресации:

 # — немедленный $ — прямой ( $ может быть опущен ) * — A - поле косвенный @ — B - поле косвенный { — A - поле косвенный с предекрементом < — B - поле косвенный с преддекрементом } — A - поле косвенный с постинкрементом >​ — B — поле косвенное с постинкрементом

Реализации

Разработка реализаций игры продолжалась на протяжении многих лет несколькими авторами. Доступно несколько версий игры, [19] портированных на несколько платформ. Например, pMARS , которое является программным обеспечением с открытым исходным кодом и исходным кодом на SourceForge , [20] или SDL pMARS на основе SDL для Windows. [21]

Общая реализация pMars была загружена более 35 000 раз в период с 2000 по 2021 год с SourceForge . [22]

Рекомендации

  1. ^ Аб Джонс, DG; Дьюдни, АК (март 1984 г.). «Основные принципы войны» . Проверено 27 мая 2023 г.
  2. ^ "rec.games.corewar в группах Google" . Проверено 29 мая 2023 г.
  3. ^ Вангсо, Минтарджо. «Введение в искусство 88-го: трилогия «Бумага-камень-ножницы»» . Проверено 27 мая 2023 г.
  4. ^ Похьялайнен, Джиппо. «Шелковый воин 1.3» . Проверено 27 мая 2023 г.
  5. ^ Похьялайнен, Джиппо (апрель 1995 г.). «репликаторы? -> Phoenix & TimeScapesource» . Проверено 27 мая 2023 г.
  6. ^ Меткалф, Джон (апрель 2004 г.). «Анатомия сканера, базовое введение» . Проверено 27 мая 2023 г.
  7. ^ ван Рейн, Рой. «Мирмидон» . Проверено 27 мая 2023 г.
  8. ^ Паулссон, Магнус. «myVamp v3.7» . Проверено 27 мая 2023 г.
  9. ^ Дьюдни, АК «Имп» . Проверено 27 мая 2023 г.
  10. ^ Скиллеро, Джованни. «μGP (MicroGP v2)». Гитхаб . Проверено 10 сентября 2018 г.
  11. ^ Воук, Баркли; Подожди, Александр; Шмидт, Кристиан. «Эволюционный подход создает конкурентоспособные человеческие программы основной войны» (PDF) . Проверено 27 мая 2023 г.
  12. ^ аб Дьюдни, АК (май 1984 г.). «В игре под названием Core War враждебные программы участвуют в битве битов». Научный американец . Проверено 27 мая 2023 г.
  13. ^ Шох, Дж .; Хапп, Дж. (март 1982 г.). «Программы-черви - ранний опыт распределенных вычислений». Коммуникации АКМ . 25 (3): 172–180. дои : 10.1145/358453.358455 . S2CID  1639205.
  14. ^ Дьюдни, AK (март 1985 г.). «Бестиарий вирусов, червей и других угроз компьютерной памяти» Core War. Научный американец . Проверено 27 мая 2023 г.
  15. ^ Дьюдни, AK (январь 1987 г.). «Программа под названием MICE пробивается к победе на первом турнире Core War». Научный американец . Проверено 27 мая 2023 г.
  16. ^ Долигез, Дэмиен; Дарем, Марк (8 ноября 1995 г.). «Аннотированный проект предлагаемого основного военного стандарта 1994 года» . Проверено 27 мая 2023 г.
  17. ^ Меткалф, Джон. «Краткая история Corewar» . Проверено 27 мая 2023 г.
  18. ^ «Руководство для начинающих по Redcode, v1.23» .
  19. ^ Эмуляторы Corewar на corewar.info
  20. ^ corewar на SourceForge
  21. ^ pMARS-SDL на corewar.co.uk, автор Йоонас Пихлая (7 мая 2003 г.)
  22. ^ скачать номера corewar на SourceForge (доступ: 7 июня 2021 г.)

Внешние ссылки