Core War - это игра по программированию 1984 года,созданная Д. Дж. Джонсом и А. К. Дьюдни, в которой две или более боевых программ (называемых «воинами») соревнуются за контроль над виртуальным компьютером . Эти боевые программы написаны на абстрактном ассемблере, который называется Redcode .
Основная война | |
---|---|
Разработчики) | Д. Джонс и А. К. Дьюдни |
Релиз | Март 1984 г. |
Жанр (ы) | Программирование игры |
Геймплей
В начале игры каждая боевая программа загружается в память в случайном месте, после чего каждая программа по очереди выполняет одну инструкцию. Цель игры - вызвать завершение процессов противостоящих программ (что происходит, если они выполняют недопустимую инструкцию), оставляя победившую программу в исключительном владении машины.
Самая ранняя опубликованная версия Redcode определяла только восемь инструкций. Стандарт ICWS-86 увеличил это число до 10, а стандарт ICWS-88 увеличил его до 11. Используемый в настоящее время стандарт ICWS-94 содержит 16 инструкций. Однако Redcode поддерживает ряд различных режимов адресации и (начиная с ICWS-94) модификаторов инструкций, которые увеличивают фактическое количество возможных операций до 7168. Стандарт Redcode оставляет базовое представление инструкции неопределенным и не предоставляет программам средств доступа к нему. Арифметические операции могут выполняться с двумя адресными полями, содержащимися в каждой инструкции, но единственные операции, поддерживаемые с самими кодами инструкций, - это копирование и сравнение на равенство.
- Постоянная длина и время инструкции
- Каждая инструкция Redcode занимает ровно один слот памяти и требует для выполнения ровно одного цикла. Однако скорость, с которой процесс выполняет инструкции, зависит от количества других процессов в очереди, поскольку время обработки распределяется поровну.
- Круговая память
- Память адресуется в единицах одной инструкции. Пространство памяти (или ядро ) имеет конечный размер, но используется только относительная адресация , то есть адрес 0 всегда относится к текущей выполняемой инструкции, адрес 1 - к инструкции после нее и так далее. Максимальное значение адреса устанавливается на единицу меньше, чем количество ячеек памяти, и при необходимости будет повторяться. В результате существует взаимно однозначное соответствие между адресами и ячейками памяти, но программа Redcode не может определить какой-либо абсолютный адрес. Процесс, который не обнаруживает недопустимых инструкций или инструкций перехода, будет продолжать бесконечно выполнять последовательные инструкции, в конечном итоге возвращаясь к инструкции, с которой он был запущен.
- Многопроцессорность низкого уровня
- Вместо одного указателя инструкции симулятор Redcode имеет очередь процесса для каждой программы, содержащую переменное количество указателей инструкций, которые симулятор циклически перебирает. Каждая программа запускается только с одним процессом, но с помощью
SPL
инструкции в очередь могут быть добавлены новые процессы . Процесс умирает, когда выполняет инструкцию DAT или выполняет деление на ноль. Программа считается мертвой, если в ней больше не осталось процессов.
- Нет внешнего доступа
- Redcode и архитектура MARS не предоставляют функций ввода или вывода. Имитатор представляет собой замкнутую систему, единственными входными данными которой являются начальные значения памяти и очередей процессов, а единственным выходом является результат битвы, т. Е. Какие программы имеют уцелевшие процессы. Конечно, симулятор может по-прежнему разрешать внешний осмотр и модификацию памяти во время симуляции.
Версии Redcode
Существует несколько версий Redcode. Самая ранняя версия, описанная А. К. Девдни [1], во многих отношениях отличается от более поздних стандартов, установленных Международным основным военным обществом, и может считаться другим, хотя и родственным языком. Форма Redcode, наиболее часто используемая сегодня, основана на проекте стандарта, представленного в ICWS в 1994 году, который так и не был официально принят, поскольку примерно в то время ICWS фактически прекратил свое существование. Однако разработка Redcode продолжалась в неформальной манере, в основном через онлайн-форумы, такие как группа новостей rec.games.corewar
[2] .
Стратегия
Воинов обычно делят на несколько широких категорий, хотя настоящие воины часто могут сочетать поведение двух или более из них. Три из распространенных стратегии ( репликатор , сканер и бомбардировщик ) также известны как бумага, ножницы и камень , поскольку их эффективность друг против друга приближается к таковым у их однофамильцев в хорошо известной игровой площадке. [3]
- Бумага (или репликатор)
- Репликатор создает повторяющиеся копии самого себя и выполняет их параллельно, в конечном итоге заполняя все ядро копиями своего кода. Репликаторов трудно убить, но часто бывает трудно убить своих противников. Поэтому репликаторы имеют тенденцию иметь много связей, особенно с другими репликаторами.
- Шелк представляет собой особый тип очень быстрый репликатор, названный в честь шелкового Воина [4] Юха Pohjalainen. Большинство современных репликаторов относятся к этому типу. Репликаторы Silk используют параллельное выполнение для копирования всего кода с помощью одной инструкции и начинают выполнение копии до ее завершения. [5]
- Ножницы (или сканер)
- Сканер предназначен для работы с репликаторами. Сканер не атакует вслепую, но пытается определить местонахождение врага перед тем, как начать целевую атаку. Это делает его более эффективным против сложных противников, таких как репликаторы, но также делает его уязвимым для ловушек. Сканер обычно бомбит память SPL 0 инструкций. Это заставляет противника создавать огромное количество процессов, которые ничего не делают, кроме создания большего количества процессов, замедляя полезные процессы. Когда противник становится настолько медленным, что не может сделать ничего полезного, его память бомбардируется. Инструкции DAT . Сканеры также обычно более сложные и, следовательно, более крупные и хрупкие, чем другие типы воинов. [6]
- Один выстрел очень простой сканер , который сканирует только ядро до тех пор, пока не найдет первую цель, а затем окончательно переходит к стратегии атаки, как правило , сердечник ясно. Myrmidon [7] Роя ван Рейна является примером одного выстрела.
- Камень (или бомбардировщик)
- Бомбардировщик слепо копирует «бомбу» через равные промежутки времени в ядре, надеясь поразить врага. Бомба часто бывает Инструкция DAT , хотя могут использоваться другие инструкции или даже бомбы с несколькими инструкциями. Бомбардировщик может быть маленьким и быстрым, и они получают дополнительное преимущество перед сканированием противников, поскольку бомбы также служат удобным отвлечением. Бомбардировщики часто сочетаются со спиралями импа, чтобы получить дополнительную устойчивость против репликаторов.
- Вампир (или яма-ловец)
- Вампир пытается заставить процессы своего оппонента перейти в часть его собственного кода, называемую «ямой». Вампиры могут базироваться как на бомбардировщиках, так и на сканерах. Основная слабость вампиров состоит в том, что их легко атаковать косвенно, поскольку они должны по необходимости разбрасывать указатели на свой код по всему ядру. Их атаки также медленные, так как процессам требуется дополнительный раунд, чтобы достичь ямы. myVamp [8] от Paulsson - это пример вампира.
- Бес
- Импы названы в честь первого из когда-либо опубликованных воинов, Imp [9], созданного AK Dewdney , тривиальным мобильным воином с одной инструкцией, который постоянно копирует свою единственную инструкцию прямо перед указателем инструкции . Бесов трудно убить, но они почти бесполезны для нападения. Их польза заключается в том, что они легко могут появиться в большом количестве и могут выжить, даже если остальная часть воина будет убита.
- Имп кольцо (или имп спираль ) состоит из чертят , расположенных через равные промежутки вокруг сердечника и исполняющих попеременно. Бесы на каждом плече кольца / спирали копируют свою инструкцию в следующее плечо, где она немедленно выполняется снова. Кольца и спирали даже сложнее убить, чем простых бесов, и у них даже есть (небольшой) шанс убить воинов, не защищенных от них. Количество рукавов в имп кольце или спирали должно быть пропорционально размеру сердечника.
- Quickscanner (или q-scan)
- Quickscanner пытается поймать своего противника на ранней стадии, используя очень быстрый развернутый цикл сканирования. Быстрое сканирование - это стратегия на раннем этапе игры, которая всегда требует какой-либо другой стратегии в качестве резервной. Добавление компонента быстрого сканирования к воину может улучшить его результат против длинных воинов, таких как другие устройства быстрого сканирования. Однако развернутое сканирование может нацеливаться только на ограниченное количество местоположений и вряд ли сможет поймать небольшого противника.
- Ядро ясно
- Очистка ядра последовательно перезаписывает все инструкции в ядре, иногда даже включая себя. Очищения ядра не очень распространены в качестве самостоятельных воинов, но часто используются бомбардировщиками и сканерами в качестве стратегии конечной игры.
Основное программирование войны
С пониманием основной войной стратегии, программист может создать воин для достижения определенных целей. Революционные идеи приходят время от времени; Однако в большинстве случаев программисты основывают свои программы на уже опубликованных воинах. Используя оптимизаторы, такие как OptiMax или инструменты оптимизатора основных шагов, можно создать более эффективного воина.
Воинов также можно создавать с помощью генетических алгоритмов или генетического программирования . Программы, которые объединяют эту эволюционную технику, известны как эволюционеры . Сообщество Core War представило несколько эволюционеров, которые, как правило, сосредоточены на создании воинов для небольших основных настроек. Последней разработкой, имевшей значительный успех, был μGP [10], который произвел некоторых из самых успешных нано- и крошечных воинов. Тем не менее, эволюционная стратегия все еще должна доказать свою эффективность на более крупных базовых объектах. [11]
Разработка
Core War была вдохновлена самовоспроизводящейся программой под названием Creeper и последующей программой под названием Reaper, которая уничтожала копии Creeper. [12] Creeper был создан Бобом Томасом на BBN . [13] Дьюдни не знал о происхождении Крипера и Жнеца и называет их слухом, исходящим от Дарвина и экспериментов Шоха и Хаппа с червями . Тем не менее в статье Scientific American 1984 года о войне за ядро [12] упоминается игра Дарвина , в которую Виктор Высоцкий , Роберт Моррис и Дуглас Макилрой в Bell Labs в 1961 году сыграли . Слово «ядро» в названии происходит от памяти магнитного сердечника , устаревшая технология оперативной памяти .
Первое описание языка Redcode было опубликовано в марте 1984 г. в Core War Guidelines DG Jones и AK Dewdney . [1] Игра была представлена публике в мае 1984 года в статье, написанной Дьюдни в Scientific American . Дьюдни вернулся к Core War в своей колонке «Computer Recreations» в марте 1985 г. [14] и снова в январе 1987 г. [15]
Международное общество ядерных войн (ICWS) было основано в 1985 году, через год после первой статьи Дьюдни. ICWS опубликовал новые стандарты для языка Redcode в 1986 и 1988 годах и предложил обновление в 1994 году, которое никогда не было официально установлено в качестве нового стандарта. [16] Тем не менее, проект 1994 года был широко принят и расширен, и сегодня он составляет основу фактического стандарта Redcode. Руководили ICWS Марк Кларксон (1985–1987), Уильям Р. Бакли (1987–1992) и Джон Ньюман (1992–); в настоящее время ICWS не функционирует. [17]
Redcode
0000 : ДОБАВИТЬ . 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, он во многом отличается [ какой? ] из "настоящей" сборки.
Реализации
Разработка реализаций игры продолжалась на протяжении многих лет несколькими авторами. Доступно несколько версий игры [18], портированных для нескольких платформ. Например, pMARS, который представляет собой программное обеспечение с открытым исходным кодом с исходным кодом на Sourceforge , [19] или SDL pMARS для Windows на основе SDL . [20] Недавно был создан полностью веб-симулятор https://www.corewar.io/, устраняющий необходимость загрузки каких-либо инструментов для конкретной платформы.
Общая реализация pMars была загружена 30 000 раз в период с 2000 по 2017 год с Sourceforge . [21]
Рекомендации
- ^ а б Джонс, Д.Г. Дьюдни, АК (март 1984). «Основные принципы войны» . Проверено 11 марта 2013 .
- ^ "rec.games.corewar в группах Google" . Проверено 11 марта 2013 .
- ^ Вангсава, Минтарджо. «Введение в искусство в 1988 году: трилогия бумага - камень - ножницы» . Проверено 11 марта 2013 .
- ^ Похьялайнен, Джиппо. «Шелковый воин 1.3» . Проверено 11 марта 2013 .
- ^ Похьялайнен, Джиппо (апрель 1995 г.). «Репликаторы? - Источник Phoenix & TimeScape» . Проверено 11 марта 2013 .
- ^ Меткалф, Джон (апрель 2004 г.). «Анатомия сканера, базовое введение» . Проверено 11 марта 2013 .
- ^ ван Рейн, Рой. «Мирмидон» . Проверено 11 марта 2013 .
- ^ Паулссон, Магнус. «myVamp v3.7» . Проверено 11 марта 2013 .
- ^ Дьюдни, АК «Имп» . Проверено 11 марта 2013 .
- ^ Сквиллеро, Джованни. «мкГП (MicroGP v2)» . Проверено 10 сентября 2018 .
- ^ Ваук, Баркли; Подожди, Александр; Шмидт, Кристиан. «Эволюционный подход порождает конкурентоспособные программы ядерной войны» (PDF) . Проверено 11 марта 2013 .
- ^ а б Дьюдни, AK (май 1984). «В игре под названием Core War враждебные программы вступают в битву битов» . Scientific American . Проверено 5 октября 2017 .
- ^ Shoch, J .; Хапп, Дж. (Март 1982 г.). «Программы-черви - ранний опыт работы с распределенными вычислениями». Коммуникации ACM . 25 (3): 172–180. DOI : 10.1145 / 358453.358455 . S2CID 1639205 .
- ^ Дьюдни, А. К. (март 1985 г.). «Бестиарий вирусов, червей и других угроз компьютерной памяти» . Scientific American . Проверено 5 октября 2017 .
- ^ Дьюдни, А. К. (январь 1987 г.). «Программа под названием MICE прокладывает себе путь к победе в первом турнире Core War» . Scientific American . Проверено 5 октября 2017 .
- ^ Долигес, Дэмиен; Дарем, Марк (8 ноября 1995 г.). «Аннотированный проект предлагаемого основного военного стандарта 1994 года» . Проверено 11 марта 2013 .
- ^ Меткалф, Джон. «Краткая история Corewar» . Проверено 11 марта 2013 .
- ^ Эмуляторы Corewar на corewar.info
- ^ corewar на sourceforge
- ^ pMARS-SDL на corewar.co.uk, автор Joonas Pihlaja (7 мая 2003 г.)
- ^ скачать номера coreware на sourceforge (доступ 2017-03-22)
Внешние ссылки
- Core War - война программистов
- Основная страница информации о войне
- Руководство по Redcode для новичков
- Аннотированный проект предлагаемого основного военного стандарта 1994 года
- Основная военная библиография
- Corewar.io - полностью веб-симулятор