Core Wars Forum

Okładka newslettera polskiej sekcji ICWS, listopad 1988

Program działalności polskiej sekcji ICWS

  1. Najważniejsza kwestia, którą nalezy szybko rozwiązać jest wyposażenie zainteresowanych w emulatory REDCODE działające na komputerach, które używają. W tej chwili posiadamy programy na IBM XT, na ukończeniu jest program na ATARI 130XE. Najmniej zaawansowane są prace nad ZX-SPECTRUM. Istnieje co prawda MARS na ten komputer, które autorem jest Zbigniew Janik, ale wymaga jeszcze poprawek. “Spectrumowcy”, łączcie się! Połączcice swoje siły, aby jak najszybciej osiągnąć cel i zająć się w końcu meritum sprawy — programowaniem w REDCODE.
  2. Wydanie gazetki jako forum wymiany doświadczeń czytelników.
  3. Wydanie broszury “Wojny Rdzeniowe — opis standardu”. Prace nad tym zostały rozpoczete. Wydanie w najbliższym miesiącu.
  4. Popularyzacja tej gry w Polsce. Związana z tym jest współpraca z miesięcznikiem KOMPUTER, który obiecał pomóc swoimi publikacjami.
  5. Organizacja 1 Ogólnopolskiego Turnieju Wojen Rdzeniowych. Z tym musimy niestety poczekać, aż wszyscy zainteresowani będą w posiadaniu odpowiednich emulatorów i nabiorą wprawy w programowaniu REDCODE.

Wojny rdzeniowe — strategia walki

Napisał Jacek Krywult.

Historia gry CORE WARS sięga roku 1984, kiedy to na łamach miesięcznika “Scientific American” ukazał się artykuł A.K. Dewdneya opisujący jej idee i zasady. Od tego czasu stała się ona bardzo popularna na całym świecie, a jej entuzjaści utworzyli “International Core War Society”, który obecnie kieruje William Buckley z Kaliforni. Gra ta nie jest obca również dla polskiego czytelnika, a jej opis zamieścił Wł. Majewski i J. Tatarkiewicz we wrześniowym numerze KOMPUTERA z 1987.

Reguły gry

W grze biorą udział dwa programy — wirusy napisane w specjalnym języku niskiego poziomu (rys. 1) umieszcozne w pamięci komputera oraz program MARS symulujący instrukcje REDCODE. Każda instrukcja zajmuje jedną komórkę pamięci, a wszystkie adresy są względne. MARS wykonuje na przemian po jednej instrukcji każdego wirusa, a rozgrywka zostaje uznana za zakończoną, gdy napotka on niewłaściwy (niewykonalny) rozkaz np. DAT 0. Remis zachodzi w dwóch przypadkach: gdy obydwa programy kontynuują swoje działanie po zadanym limicie czasu lub wykonają taką samą liczbę instrukcji zanim się zatrzymają (np. DAT 0).

Prości żołnierze

Najprostszy wirus nazwany Skoczkiem zawiera tylko jeden rozkaz

    MOV $0, $1

Obydwa te argumenty są bezpośrednie. Pierwszy odwołuje się tej samej instrukcji, drugi do adresu następującego po niej. W wyniku MOV $0, $1 zostaje przekopiowany do następnej komórki rdzenia, do której MARS odwoła się w kolejnym cyklu. Proces ten powtarza się i Skoczek zostawia za sobą ogon złożony z instrukcji MOV $0, $1. Ten najprostszy program z uwagi na swoją szybkość wcale nie jest taki łatwy do pokonania i wiele innych wirusów osiąga z nim remi.

Na zupełnie innej strategii opiera swoje działanie Karzeł.

    Licznik     DAT 0                           DAT 0
    START       ADD #5, Licznik                 ADD #5, -1
                MOV Licznik, @Licznik           MOV -2, @-2
                JMP START                       JMP -2

Wykonywanie tego programu zaczyna się od etykiety START. Instrukcja ADD #5, Licznik dodaje do wartości znajdującej się w polu B pod adresem Licznik. W następnym cyklu MOV Licznik, @Licznik powoduje przesłanie instrukcji DAT po adres -2+5=3 (względem MOV). W cyklu trzecim następuje JMP START, czyli skok do początku. Cały proces powtarza się. Karzeł umieszcza instrukcje DAT w co piątej komórce, licząc na to, że trafi program przeciwnika i go uszkodzi.

Jak Kuba Bogu, tak Bóg Kubie

Zdawać by się mogło, że nie ma żadnej możliwości obrony przed zadeptaniem przez Skoczka lub bombami Karła. A jednak i to znalazł się sposób. Aby uniknąc ataku Skoczka, nalezy na początku programu umieścić Stoper skoczków np. taki:

                DAT 0
    START       MOV $-1, $-2
                JMP $-1

Ponieważ atak może nadejść tylko z jednej strony, instrukcja MOV $-1, $-2 w niekończącej się pętli wpisuje dwie komórki wcześniej ``DAT 0```. Doprowadza to (rozważania dlaczego nie zawsze pozostawiam czytelnikom) do uśmiercenia Skoczka.

Jeżeli jednak nie potrafi on przedostać się przez Stoper, to może go tak przeskoczyć? Oto wirus o groźnej nazwie Zaraza:

    Licznik     DAT 70
    START       ADD #100, Licznik
                MOV imp, @Licznik
                SPL @Licznik
                JMP START
    imp         MOV $0, $1

Program ten strzela w co 100 komórkę rdzenia instrukcją MOV 0,1, a następnie dzieli się na dwa procesy. Pierwszy to Skoczek przesłany poprzez MOV imp, @Licznik pod adres określony pod etykietą Licznik, a drugi to pętla programu głównego. Od tej chwili Zaraza to dwa wirusy wykonujące się na przemian. Cały cyukl powtarza się i w pamięci komputera przed do przodu cała wciąż odnawiana bateria Skoczków.

Jak nie zadeptać, to może uciec

Całkiem odmienną klasę wirusów tworzą programy przemieszczające się w pamięci, zdolne uciec przed bombami Karła, czy zadeptaniem przez Skoczka. Oto przykład proste mikroba gatunku Bliźniaków, który tworząc swoje identyczne kopie przemieszcza się po rdzeniu.

    ZRODLO      DAT 0
    START       MOV #6, ZRODLO
                MOV #100, CEL
    KOPIA       MOV @ZRODLO, CEL
                DJN KOPIA, ZRODLO
                JMP 95
    CEL         DAT 0

Dwie pierwse instrukcje MOV ładują liczniki ZRODLO i CEL, a pętla złożona z dwu następnyuch kopiuje program 100 komórek dalej. Stara kopia jest opuszczana i instrukcja JMP 95 następuje skok do nowej. DO największej wady tych programów należy to, że są bardzo łagodne, a Skoczek i Zaraz wręcz nie potrafią z nikim wygrać! Prawie za każdym razem osiągają remis. Bardziej agresywny jest wirus oparty na pomyśle samego Dewdneya, o wymownej nazwie COMMANDO:

                MOV #0, $-3
                JMP $-1
    START       SPL $-2             ; uruchom stoper
                MOV imp, $115       ; prześlij skoczka 115 komórek dalej
                SPL 114             ; uruchom przesłanego skoczka
                MOV #12, $-7        ; prześlij długości programyu do komórki -7
                MOV #100, $5        ; prześlij adres z celem;
                                    ; do komórki 5
    KOPIA       MOV @-9, <4         ; prześlij instrukcję wskazaną
                                    ; przez komórkę -9
                                    ; pod adres wskazany przez 
                                    ; komórkę 4 zmniejszony o 1
                DJN KOPIA, $-10     ; kopiuj dopóki komóka -10 jest różna od 0
                JMP 93              ; skocz pod etykietę start nowej kopii
    imp         MOV $0, $1

Program ten rozpoczyna swoje działania od ustawienia Stopera skoczków (SPL $-2), a następnie przesyła czekającego pod etykietą imp skoczka 115 komórek do przodu. W celu uniknięcia zbombardowania przez Karła, COMMANDO przepisuje całą swoją zawartość 100 komórek dalej i poprzez skok JMP 93 rozpoczyna cały proces od nowa. Staregia działania jest barzdo prosta. Należy wysłać skoczki, które zadepczą program przeciwnika i zmuszą go do wykonywania instrukcji MOV $0, $1. Na tak powstałe skoczki czekają już śmiercionośne stopery rozstawione na polu walki. Nic więc dziwnego, że podobny wirus zajął wysoką pozycję w czasie pierwszego Turniej Wojen Rdzeniowych zorganizowanych w 1985 r. w U.S.A. Jednak pala zwycięstwa przypadła Myszy napisanej przez Chipa Wendella:

    zrodlo      DAT 0
    START       mov #12, zrodlo     ; załaduj ilość komórek do
                                    ; przesłania do źrodła
    PETLA       MOV @zrodlo, <cel   ; kopiuje się w pętli, aż zrodlo
                DJN PETLA, zrodlo   ; będzie równe 0
                SPL @cel            ; dziel się
                ADD #653, cel       ; zwiększ wskaźnik celu o 653
                JMZ start, zrodlo   ; skacz na początek, gdy 
                                    ; zrodlo=0
    CEL         DAT 833

Autor analizując działanie róznych wirusów doszedł do wniosku, że żaden program nie może być bezpieczny jeżeli przez cały czas walki przebywa tylko w jednym miejscu pamięci. Narażony jest wtedy na rozdeptanie przez Skoczka, zniszczenie przez podsuwane przez przecznika instrukcje, czy rozrzucane bomby. Dlatego Musz całą swoją “inteligencję” opiera na przepisywaniu się z jednego obszaru pamięci w drugi, dzielenie się, rozsylanie swoich kopii gdzie jest możliwe i spadaniu na przeciwnika znienacka, niszcząc jego program. Aby być jeszcze barzdiej agresywnym kopiuje nie tylko siebie, ale również 5 komórek znajdujących się za nim w nadziei, że zdnaj się tam instrukcje typu DAT 0, które następnie spuści na przeciwnika.

Czy jednak potrafi obronić się przed szybkim Skoczkiem? Umożliwa to samobójcza opcja:

                JMZ START, zrodlo
                DAT 833

W przypadku, gdy pierwsza instrukcja DAT (zrodlo) jest różna od zera, Mysz woli zezwolić na wykonanie instrukcji DAT 833 i umrzeć niż skończyc swój żywot jako Skoczek.

A co dalej?

Pomimo prostoty i zwięzłości języka REDCODE, lista jego możliwości wcale nie jest wyczerpana. Entuzjaści Wojen Rdzeniowych wciąż znajdują coraz to nowe strategie walki, tricki i chwyty programowe.

Pozwala to na pisanie wirusów coraz doskonalszych, napadających na swoich wrogów z determinacją i zaciekłością. Na najwyższym poziomie kompilacji znajdują się wirusy obdarzone “inteligencją”. Odnajdują one program przeciwnika i podsuwają mu zabójcze pułapki lub nakazują wykonywanie swego własnego programu w czasie przydzielonym dla wroga. Niektóre z nich mają możliwośc nie tylko reprodukcji, ale i samoregenracji uszkodzonych części. Uciekają z obszarów bombardowanych przez Karła w zacisze pustych obszarów pamięci, niszczą Skoczki, zniewalają Myszy. Z pewnością Czytelnicy sami znajdą nowe strategie walki, przechodzeni z defensywy do ofensywy, reperacji szkód i samoreprodukcji, czego życzy im autor.

Tajemnice REDCODE

Znana jest wszystkim instrukcja JMP a. Powoduje ona przekaznie przez program sterowania pod adres określony przez argument a. Ale co z polem argumentu b, czy musi być niewykorzystywane?

Może znakomicie spełniać funkcje instrukcji DAT b, np.

    ADD #5, $2
    MOV $-2, @1
    JMP $-2, 0

JMP $-2, $0 spełnia rolę instrukcji JMP -2 i DAT 0.

Można także stosować inny trick:

    JMP -5, <Licznik

Spowoduje on zmniejszenie zawartości pola B o jeden pod etykietą Licznik przy każdym wykonaniem tej instrukcji, niezależnie od skoku.

Antyimp

Oto prosty wirus przedrzeźniający Skoczka:

    START       DJN 0, <1
                JMP $-1, $-2

Kompendium instrukcji języka REDCODE wg. Core Wars Standard ’86

oznaczenie argumenty znaczenie
DAT B instrukcja niewykonywalna, przechwouje dane potrzebne do pracy programu, jej wykonanie zabija daną część programu
MOV A,B prześlij zawartość komórki A do komórki B
ADD A,B dodaj zawartość komórki A do komórki B i zapisz sumę w komórce B
SUB A,B odejmij zawartość komórki A do komórki B i zapisz różnicę w komórce B
JMP A skocz pod adres A
JMZ A,B skocz pod adres A, gdy zawartość komórki B=0
JMN A,B skocz pod adres A, gdy zawartość komórki B<>0
DJN A,B odejmij 1 od zawartości komórki B i skocz pod adres A, gdy B<>0
CMP A,B porównaj zawartość komórki A i B, gdy równe przeskocz następną instrukcję
SPL B podziel wirysa na dwie części. Jedna jest wykonywa od adresu B, a druga od adresu następującego po SPL. Każdy program można podzielić na 64 na przemian wykonywane niezależne procesy. Jeżeli liczba ta została przekroczona SPL nie daje żadnego efektu

Tryby adresacji

Argumenty A i B mogą stosować jeden z czterech trybów adresacji

oznaczenie nazwa działanie
# natychmiastowe MARS wykorzystuje argument dokładnie takim, jakim on jest np. ADD #1, 10, MOV #0.
$ lub bez oznaczenia bezpośrednie argument oznacza adres, do którego odwołuje się bieżąca instrukcja programu, A=5 wskazuja piątą instrukcję za obecnie wykonywaną; MOV 0,1
@ pośrednie argument oznacza adres, pod którym [znajduje] się wskaźnik, gdzie znajduje się poszukowana wartość np. MOV #0, @-1
< pośrednia zmniejszona MARS używa argumentu jako adresu wskaźnika, gdzie znajduje się poszukiwana wartość (jak w adresowaniu pośrednim), ale tuż przed wykorzystaniem wskaźnika jego wartość jest zmniejsznaa o 1 np. MOV #0, <5

UWAGA: argumenty instrukcji JMP, JMZ, JMN, DJN nie może być w trybie natychmiastowym.

TRON recenzja

Chciałbym polecić wszystkim czytelnikom naszej broszury, którzy zainteresowani sa ideą Wojen Rdzeniowych oraz tych, którzy nie mogą sobie wyobrazić Core Wars amerykański film pt. “TRON”.

Jest to obraz ukazujący walkę genialnego programisty oraz jego “dzieci” programów-wirusów z SUPERKOMPUTEREM obdarzonym pewną inteligencją. Radziłbym obejrzeć ten film, który — choć nie jest najszowszym przebojem – przyciąga ciekawymi efektami scenarii stworzonej już przez autentyczny komputer graficzny typu CRAY 2.

Życzę powodzenia w zdobyciu dobrej kopii oraz przyjemnego oglądania.

– Piotr Kapliński