Wojna rdzenia -Core War

Wojna o Rdzeń
Zrzut ekranu z wojny rdzenia
Gra Core War działająca w ramach symulatora pMARS
Deweloper(zy) DG Jones i AK Dewdney
Uwolnienie Marzec 1984
Gatunki Gra w programowanie

Core War to gra programistyczna z 1984 rokustworzona przez DG Jones i AK Dewdney, w której dwa lub więcej programów bojowych (zwanych „wojownikami”) rywalizuje o kontrolę nad wirtualnym komputerem . Te programy bojowe są napisane w abstrakcyjnym języku asemblera zwanym Redcode .

Rozgrywka

Na początku gry każdy program bitewny jest ładowany do pamięci w losowej lokalizacji, po czym każdy program wykonuje kolejno jedną instrukcję. Celem gry jest spowodowanie zakończenia procesów przeciwnych programów (co dzieje się, jeśli wykonają nieprawidłową instrukcję), pozostawiając zwycięski program w wyłącznym posiadaniu maszyny.

Najwcześniejsza opublikowana wersja Redcode zawierała tylko osiem instrukcji. Norma ICWS-86 zwiększyła tę liczbę do 10, podczas gdy norma ICWS-88 zwiększyła ją do 11. Obecnie używany projekt normy z 1994 r. zawiera 16 instrukcji. Jednak Redcode obsługuje wiele różnych trybów adresowania i (począwszy od projektu standardu z 1994 roku) modyfikatory instrukcji, które zwiększają rzeczywistą liczbę możliwych operacji do 7168. Standard Redcode pozostawia niezdefiniowaną podstawową reprezentację instrukcji i nie zapewnia dostępu do niej programów . Operacje arytmetyczne mogą być wykonywane na dwóch polach adresowych zawartych w każdej instrukcji, ale jedyne operacje obsługiwane na samych kodach instrukcji to kopiowanie i porównywanie pod kątem równości.

Stała długość i czas instrukcji
Każda instrukcja Redcode zajmuje dokładnie jeden slot pamięci i jej wykonanie zajmuje dokładnie jeden cykl. Szybkość, z jaką proces wykonuje instrukcje, zależy jednak od liczby innych procesów w kolejce, ponieważ czas przetwarzania jest dzielony równo.
Pamięć okrągła
Pamięć adresowana jest w jednostkach jednej instrukcji. Przestrzeń pamięci (lub rdzeń ) ma skończony rozmiar, ale używane jest tylko adresowanie względne , to znaczy adres 0 zawsze odnosi się do aktualnie wykonywanej instrukcji, adres 1 do instrukcji następującej po niej i tak dalej. Maksymalna wartość adresu jest równa o jeden mniej niż liczba lokalizacji w pamięci i będzie zawijana w razie potrzeby. W rezultacie istnieje zależność jeden do jednego między adresami i lokalizacjami pamięci, ale nie jest możliwe, aby program Redcode mógł określić jakikolwiek adres bezwzględny. Proces, który nie napotka żadnych nieprawidłowych instrukcji lub instrukcji skoku, będzie kontynuował wykonywanie kolejnych instrukcji w nieskończoność, ostatecznie powracając do instrukcji, w której się rozpoczął.
Wieloprzetwarzanie niskiego poziomu
Zamiast pojedynczego wskaźnika instrukcji, symulator Redcode ma kolejkę procesów dla każdego programu zawierającą zmienną liczbę wskaźników instrukcji, przez które przechodzi symulator. Każdy program uruchamia się tylko jednym procesem, ale nowe procesy można dodawać do kolejki za pomocą SPLinstrukcji. Proces umiera, gdy wykonuje instrukcję DAT lub dokonuje dzielenia przez zero. Program jest uważany za martwy, gdy nie ma już żadnych procesów.
Brak dostępu z zewnątrz
Redcode i architektura MARS nie zapewniają żadnych funkcji wejściowych ani wyjściowych. Symulator jest systemem zamkniętym, w którym jedynym wejściem są początkowe wartości pamięci i kolejek procesów, a jedynym wyjściem jest wynik bitwy, czyli to, które programy mają procesy, które przeżyły. Oczywiście symulator może nadal umożliwiać zewnętrzną inspekcję i modyfikację pamięci podczas trwania symulacji.

Wersje Redcode

Istnieje wiele wersji Redcode. Najwcześniejsza wersja opisana przez AK Dewdney różni się pod wieloma względami od późniejszych standardów ustanowionych przez International Core War Society i można ją uznać za inny, choć powiązany język. Najczęściej używana obecnie forma Redcode opiera się na projekcie standardu przedłożonym ICWS w 1994 roku, który nigdy nie został formalnie zaakceptowany, ponieważ w tym czasie ICWS przestał funkcjonować. Rozwój Redcode jest jednak kontynuowany w sposób nieformalny, głównie za pośrednictwem forów internetowych, takich jak rec.games.corewar grupa dyskusyjna .

Strategia

Wojownicy są zwykle podzieleni na wiele ogólnych kategorii, chociaż prawdziwi wojownicy często mogą łączyć zachowanie dwóch lub więcej z nich. Trzy z popularnych strategii ( replikator , skaner i bombowiec ) są również znane jako papier, nożyce i kamień , ponieważ ich wydajność względem siebie jest zbliżona do ich imienników w dobrze znanej grze na placu zabaw.

Papier (lub replikator)
Replikator tworzy powtarzające się kopie samego siebie i wykonuje je równolegle, ostatecznie wypełniając cały rdzeń kopiami swojego kodu. Replikatory są trudne do zabicia, ale często mają trudności z zabiciem swoich przeciwników. Dlatego replikatory mają tendencję do zdobywania wielu powiązań, szczególnie z innymi replikatorami.
Jedwab jest szczególnym rodzajem bardzo szybkim replikatora, nazwany Silk Wojownika Juha Pohjalainen. Większość nowoczesnych replikatorów jest tego typu. Replikatory Silk wykorzystują wykonywanie równoległe do kopiowania całego kodu za pomocą jednej instrukcji i rozpoczynają wykonywanie kopii przed jej zakończeniem.
Nożyczki (lub skaner)
Skaner jest przeznaczony do pokonania replikatorów. Skaner nie atakuje na ślepo, ale próbuje zlokalizować wroga przed wykonaniem ukierunkowanego ataku. Dzięki temu jest bardziej skuteczny przeciwko trudnym do zabicia przeciwnikom, takim jak replikatory, ale także naraża go na wabiki. Skaner zwykle bombarduje pamięć instrukcjami SPL 0 . Powoduje to, że wróg tworzy ogromną liczbę procesów, które nie robią nic poza tworzeniem większej liczby procesów, spowalniając użyteczne procesy. Kiedy wróg staje się tak powolny, że nie jest w stanie zrobić niczego pożytecznego, pamięć zostaje zbombardowana instrukcjami DAT . Skanery są również ogólnie bardziej złożone, a przez to większe i bardziej kruche niż inne typy wojowników.
Jeden strzał jest bardzo prosty skaner, który skanuje tylko rdzeń aż znajdzie pierwszą bramkę, a następnie przełącza się na stałe w strategię ataku, zwykle rdzeniem jasne. Myrmidon Roya van Rijna jest przykładem oneshota.
Kamień (lub bombowiec)
Bombowiec na ślepo kopiuje „bombę” w rdzeniu w regularnych odstępach czasu, mając nadzieję trafić wroga. Bomba jest często instrukcją DAT , chociaż można użyć innych instrukcji, a nawet bomb wieloinstrukcyjnych. Bombowiec może być mały i szybki, a ponadto zyskuje dodatkową przewagę nad skanowaniem przeciwników, ponieważ bomby służą również jako wygodne odwracanie uwagi. Bombowce są często łączone ze spiralami chochlików, aby uzyskać dodatkową odporność na replikatory.
Wampir (lub traper)
Wampir próbuje sprawić, by procesy przeciwnika wskoczyły do ​​fragmentu jego własnego kodu zwanego „dołem”. Wampiry mogą opierać się na bombowcach lub skanerach. Główną słabością wampirów jest to, że można je łatwo zaatakować pośrednio, ponieważ z konieczności muszą rozsiać po całym rdzeniu wskazówki do swojego kodu. Ich ataki są również powolne, ponieważ proces dotarcia do dołu zajmuje dodatkową rundę. myVamp by Paulsson jest przykładem wampira.
Chochlik
Impy zostały nazwane na cześć pierwszego opublikowanego wojownika, Impa autorstwa AK Dewdneya , trywialnego mobilnego wojownika z jedną instrukcją, który nieustannie kopiuje swoją jedyną instrukcję tuż przed wskaźnikiem instrukcji . Chochliki są trudne do zabicia, ale prawie bezużyteczne do ataku. Ich zastosowanie polega na tym, że można je łatwo rozmnażać w dużych ilościach i mogą przetrwać, nawet jeśli reszta wojownika zostanie zabita.
Pierścień chochlika (lub spirala chochlika ) składa się z chochlików rozmieszczonych w równych odstępach wokół rdzenia i działających naprzemiennie. Chochliki na każdym ramieniu pierścienia/spirali kopiują swoją instrukcję do następnego ramienia, gdzie jest natychmiast ponownie wykonywana. Pierścienie i spirale są jeszcze trudniejsze do zabicia niż zwykłe chochliki i mają nawet (małą) szansę na zabicie wojowników, którzy nie są przed nimi chronieni. Liczba ramion w pierścieniu impaktowym lub spirali musi być względnie pierwsza w stosunku do rozmiaru rdzenia.
Quickscanner (lub q-scan)
Szybki skaner próbuje wcześnie złapać przeciwnika za pomocą bardzo szybkiej rozwiniętej pętli skanowania. Szybkie skanowanie to strategia we wczesnej fazie gry i zawsze wymaga innej strategii jako kopii zapasowej. Dodanie komponentu szybkiego skanowania do wojownika może poprawić jego wynik przeciwko długim wojownikom, takim jak inne szybkie skanery. Jednak rozwinięty skan może celować tylko w ograniczoną liczbę lokalizacji i jest mało prawdopodobne, aby złapać małego przeciwnika.
Wyczyść rdzeń
Rdzeń jasny sekwencyjnie nadpisuje każdą instrukcję w rdzeniu, czasami nawet sam siebie. Czyszczenia rdzenia nie są zbyt popularne jako samodzielni wojownicy, ale są często używane jako strategia końcowa przez bombowce i skanery.

Programowanie wojny podstawowej

Dzięki zrozumieniu strategii Core War programista może stworzyć wojownika, aby osiągnąć określone cele. Rewolucyjne idee przychodzą raz na jakiś czas; jednak przez większość czasu programiści opierają swoje programy na już opublikowanych wojownikach. Używając optymalizatorów, takich jak OptiMax lub narzędzi optymalizacji core-step, można stworzyć bardziej efektywnego wojownika.

Wojownicy mogą być również generowani przez algorytmy genetyczne lub programowanie genetyczne . Programy, które integrują tę technikę ewolucyjną, znane są jako ewolutory . Kilka ewolucyjnych zostało wprowadzonych przez społeczność Core War i skupiają się na generowaniu wojowników dla mniejszych ustawień podstawowych. Najnowszym ewolutorem, który odniósł znaczący sukces, był μGP, który wyprodukował jednych z najbardziej udanych nano- i maleńkich wojowników. Niemniej jednak strategia ewolucyjna nadal musi udowodnić swoją skuteczność w większych środowiskach podstawowych.

Rozwój

Core War został zainspirowany samoreplikującym się programem o nazwie Creeper i kolejnym programem o nazwie Reaper, który niszczył kopie Creepera. Creeper został stworzony przez Boba Thomasa w BBN . Dewdney nie był świadomy pochodzenia Creepera i Reapera i odnosi się do nich jako plotka pochodząca od Darwina i eksperymentów z robakami Shocha i Huppa. Artykuł w Scientific American z 1984 r. na temat Core War przytacza jednak grę Darwin , w którą grali Victor A. Vyssotsky , Robert Morris i Douglas McIlroy w Bell Labs w 1961 r. Słowo „rdzeń” w nazwie pochodzi od pamięci z rdzeniem magnetycznym , technologia pamięci o dostępie swobodnym .

Pierwszy opis języka Redcode został opublikowany w marcu 1984 r. w Core War Guidelines autorstwa DG Jones i AK Dewdney . Gra została przedstawiona publiczności w maju 1984 roku w artykule napisanym przez Dewdneya w Scientific American . Dewdney powrócił do Core War w swojej kolumnie „Computer Recreations” w marcu 1985 r. i ponownie w styczniu 1987 r.

International Core Wars Society (ICWS) zostało założone w 1985 roku, rok po oryginalnym artykule Dewdneya. ICWS opublikował nowe standardy dla języka Redcode w 1986 i 1988 roku, a w 1994 zaproponował aktualizację, która nigdy nie została formalnie ustalona jako nowy standard. Niemniej jednak, projekt z 1994 roku został powszechnie przyjęty i rozszerzony i stanowi podstawę de facto standardu dla Redcode dzisiaj. ICWS kierował Mark Clarkson (1985-1987), William R. Buckley (1987-1992) i Jon Newman (1992-); obecnie ICWS nie działa.

Czerwony kod

 0000:  ADD.AB  #   4, $   3
 0001:  MOV.F   $   2, @   2
 0002:  JMP.B   $  -2, $   0
 0003:  DAT.F   #   0, #   0
Zmontowany Redcode w stylu ICWS-94

Redcode to język programowania używany w Core War . Jest wykonywany przez maszynę wirtualną znaną jako Memory Array Redcode Simulator lub MARS . Projekt Redcode jest luźno oparty na rzeczywistych językach asemblerowych CISC z wczesnych lat 80-tych, ale zawiera kilka funkcji, których zwykle nie można znaleźć w rzeczywistych systemach komputerowych.

Zarówno Redcode, jak i środowisko MARS zostały zaprojektowane tak, aby zapewnić prostą i abstrakcyjną platformę bez złożoności rzeczywistych komputerów i procesorów. Chociaż Redcode ma przypominać zwykły asembler CISC, jest dość uproszczony w stosunku do "prawdziwego" asemblera i nie ma absolutnego adresowania pamięci

Oryginalne 8 instrukcji jest opisanych w następujący sposób, późniejsze wersje dodały NOP, mnożą i bardziej złożone porównania. 

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.

Standardowy projekt ICWS '94 dodał więcej trybów adresowania, głównie w celu radzenia sobie z pośrednim polem A, dając w sumie 8 trybów adresowania: 

   # — 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

Realizacje

Rozwój implementacji gry kontynuowany był przez lata przez kilku autorów. Dostępnych jest wiele wersji gry, przeniesionych na kilka platform. Na przykład pMARS który jest oprogramowanie open source z kodu źródłowego na Sourceforge lub SDL oparte pMARS SDL dla systemu Windows. Niedawno powstał w pełni internetowy symulator https://www.corewar.io/ eliminujący konieczność pobierania narzędzi specyficznych dla platformy.

Wspólna implementacja pMars została pobrana ponad 35 000 razy w latach 2000-2021 z Sourceforge .

Bibliografia

Zewnętrzne linki