Magazyn Enter, luty 1992

Andrzej Stasiewicz

Kowboj, Ferret i inni wojownicy

Wojny rdzeniowe powstały w 1984 roku. Wymyślił je A.K.Dewdney — jeden z autorów popularnego miesięcznika przyrodniczego „Scientific American” i po raz pierwszy przedstawił na łamach swego pisma. Wojny rdzeniowe są grą dla miłośników komputerów i programowania.

Ci, który tępią wszystkie gry jako ogłupiający narkotyk dla dzieciaków, niech jeszcze chwilę poczekają. Z jednej strony jest to bowiem zwykła gra, gdzie na udeptanej ziemi potykają się dwaj adwersarze. Z innej już poważne wyzwanie dla poważnych programistów. Rzadko kiedy udaje się tak dobrze połączyć zabawę z profesją, sportowe emocje z chłodną kalkulacją. Mają też Wojny niezaprzeczalne walory edukacyjne. Spotykamy tu bowiem prawdziwy język asemblerowy. Jest okazja efektownie wejsć w coś, co dla wielu staniesię celem i treścią życia.

Prawdopodobnie Wojny rdzeniowe były inspiracją dla twórców pierwszych wirusów komputerowych. Skoro postawiono problem: napisz program, który przeżyje na specjalnie spreparowanej arenie, szybko ktoś wyostrzył sobie zadanie: napisz program, który przeżyje w standardowym środowisku komputera. To szkoda dla ludzkości, że nie Wojny, a wirusologia przeżywa swoją świetność.

W Wojny rdzeniowe gra się stosunkowo łatwo, choć wirtuozeria jest trudna i wymaga sporo pracy oraz sprytu. Szczególnie wypada polecić tę grę ludziom młodym, awanturniczo nastawionym do świata i mającym nadmiar wolnego czasu.

Do gry potrzebny jest komputer oraz specjalne oprogramowanie. Na takie oprogramowanie składają się następujące elementy:

  1. Edytor wojownika.
  2. Kompilator.
  3. Arena wraz z sędzią walki i systemem punktacji.

Jest to niezbędne minimum, które musi mieć każdy strateg Wojen rdzeniowych. Przed dwoma laty otrzymałem pakiet oprogramowania amerykańskiej firmy Amran, firmowany ponadto przez centralę w Kalifornii. Niestety, nie była to udana praca, przede wszystkim wysoce nieprzyjazna i z błędami interpretacyjnymi. Postanowiłem więc sam napisać odpowiedni program, któremu nadałem tytuł, jakżeby inaczej, Wojownik. Przez półtora roku Wojownik działał w studenckiej sieci komputerowej w Katedrze Fizyki w Białymstoku. Wygląda na to, że teraz, dzięki redakcji naszego miesięcznika, Wojownik ma szansę ujrzeć więcej światła.

Wojownik zawiera trzy podstawowe elementy wymienione wcześniej. W jego skład wchodzi wchodzi też odpluskwiacz (czyli tzw. debugger) umożliwiający śledzenie zachowań programu na arenie — rzecz niezwykle przydatna do nauki programowania. Istotnym i unikalnym elementem jest coś, co możnaby nazwać sorterem: przyrząd oceniający siłę każdego wojownika we wskazanej grupie. Szykując się do zawodów bierzemy wielu swoich wojowników, wpuszczamy ich na całą noc na arenę i rano mamy wyniki. Pojawia się możliwość programowania metodą prób i błędów — sorter weryfikuje drobne mutacje w ciałach wojowników, wybierając najsprawniejszego. Wojownik zarządza też bibliotekami programów przed i po kompilacji. Na dyskietce, którą proponujemy Państwu, wraz z Wojownikiem znajdują się wszystkie przykłady opisane w tym artykule. Przykłady te należy wykonywać pod nadzorem odpluskwiacza, uważnie śledząc akcje na arenie. W innej bibliotece znajduje się światowy dorobek dyscypliny: Kowboj, Ferret i inni wojownicy.

Istotą gry jest pisanie programów, które walczą ze sobą jeden na jednego w specjalnie przygotowanym obszarze pamięci. Programy wykonują ruchy kolejno, o co dba sędzia walki. Programy nastawione agresywnie starają się uszkodzić przeciwnika, defensywne koncentują się na unikach i odbudowie swojego ciała. Przegrywa ten, który z powodu uszkodzeń nie jest w stanie wykonać poprawnej operacji. Program-wojownik powstaje i doskonali się w ćwiczebnych turniejach w Waszych domowych zaciszach, Potem nie można mu już pomóc, jest zdany wyłącznie na strategie, w jakie został zaopatrzony.

Programy do walki powstają w wymyślonym przez Dewdneya języku zwanym Redcode. To dość ubogi język, w którym znajdujemy kilka typowych rozkazów asemblera. Ducha Redcode musimy dokładnie poznać i ogarnąć umysłem. Wszystkie rozkazy stosunkowo łatwo jest zapamiętać i sobie przyswoić, nieco wysiłku potrzeba na opanowanie podstawowych struktur programowych języka. Gotowy program poddaje się kompilacji, czyli tłumaczeniu ze zrozumiałego dla ludzi dialektu Redcode na zapis zrozumiały dla sędziego walki. Dwa takie kompilaty umieszca się na arenie (czyli w pamięci komptera), nastawia liczbę ciosów na, powiedzmy, 10.000 i czeka na zwycięzcę.

Rozkazy

Zatem batalię czas zacząć. Na początek wymienimy wszystkie rozkazy Redcode. Jest ich jedenaście:

  1. DAT A B (przechowanie jednej lub dwóch danych)
  2. MOV A B (skopiowanie A do B)
  3. ADD A B (zsumowanie A i B i umieszczenie wyniku w B)
  4. SUB A B (odjęcie A od B i umieszczenie wyinku w B)
  5. JMP A (skok do A)
  6. JMZ A B (skok do A, o ile B=0)
  7. JMN A B (skok do A, o ile B nie jest zerem)
  8. DJN A B (zmniejszenie B o 1 i skok do A, o ile B nie jest równe zero)
  9. CMP A B (pominięcie jednej instrukcji programu, o ile A=B)
  10. SPL A (uruchomienie równoległego programu (wielozadaniowość!) zapisanego pod adresem A)
  11. SLT A B (pominięcie jednek instrukcji programu, o ile A<B)

Rozkazy Redcode omówię potem bardziej szczegółowo, teraz wymieniłem je, byśmy pojęli ogólną strukturę języka. Otóż, jak widać, linia programu będzie składać się z jednego z wymienionych słów kluczowych języka Redcode i z jednego lub dwóch argumentów związanych z tym słowem. Słowa kluczowe wraz z argumentami składają się na program i będę umieszczone na arenie walki. Sędzie walki będzie kolejno pobierał napisane przez nas rozkazy wraz z ich argumentami i wykonywał je. Gdy trafi na rozkaz niemożliwy do wykonania — przegraliśmy.

Przyjrzyjmy się jeszcze orzez chwilę strukturze areny. Jest to obszar pamięci, w który wpisuje się nasz program i na którym toczy się bój. Arena liczy ileś komórek — powiedzmy 100. W każdej komórce musi zmieścić się słowo kluczowe oraz dwa związane z nim argumenty — to warunek, by można było umieścić na arenie walczący program. To miejsce w komórce, w które wpisany jest rozkaz Redcode nazwijmy polem operacji. Miejsce z zapisanymi argumentami to będę pola argumentu A i argumentu B. Zatem arena składa się z komórek, zaś każda z komórek ma następującą strukturę: Pole operacji…Pole argumentu A…Pole argumentu B.

Arena jest zamknięta w kółko, o znaczy komórka numer 100 jest tą samą komórką, co komórka numer 0, komórka numer 101 to komórka numer 1 i tak dalej. W ten sposób programy-wojownicy są zamknięci między linami ringu i w bitewnym zapamiętaniu nie stratują pamięci naszych komputerów. Przed bitwą arena jest czyszczona, ściślej sędzia walki wpisuje do każdej jej komórki instrukcję DAT $0 $0 (o typach argumentów będzie za chwilę) i potem sędzia umieszcza na arenie pierwszego wojownika. Począwszy od adresu 0 umieszcza wszystkie instrukcje programu wraz z ich argumentami. Następnie losuje dystans, w jakim ma stanąć przeciwnik. Począwszy od wylosowanej komórki umieszcza wszystkie instrukcje przeciwnika, oczywiście też z ich argumentami. Wreszcie zaczyna się bój: sędzie kolejno czyta z areny, co chce zrobić dany wojownik i robi to. Może to być ostrożne badanie otoczenia w poszukiwania wroga lub uszkodzeń (rozkaz CMP), atak lub ucieczka z zagrożonego rejonu areny (rozkaz MOV), włączenie do boju towarzyszy broni (SPL) czy gwałtowne zmiany strategii (rozkazy skoków).

Typy argumentów

Musimy jeszcze dokładnie poznać strukturę argumentów A i B oraz ich znaczenie w każdym z rozkazów języka Redcode. Jest to bezsprzecznie najtrudniejsza częśc programowania. Każdy z argumentów może występować w jednym z czterech typów. Nie każdy rozkaz toleruje wszystke cztery typy argumentu, ale o tym potem. By zaznaczyć sędziemu walki, o jaki typ nam chodzi, przed każdym argumentem umieszcza się jeden z symboli: #, $, @. <. Jeśli nie umieścimy żadnego symbolu, kompilator uzna najczęściej chyba stosowany typ $. Cóż znaczą typy?

Typy argumentów są sprawą niezwykle istotną. Nie ma mowy, by prześlizgnąć się nad tym zagadnieniem bez pełnego zrozumienia. Sędzia walki, zanim wykona jakikolwiek rozkaz, musi odszukać prawdziwe adresy argumentów i prawdziwe ich wartości. Na chwilę staniemy się sędzią walki i zobaczymy, jak on to robi. Abstrahujemy na razie od sensu programu, szukamy jedynie adresów argumentów i ich wartości w linii programu oznaczonej etykietą start (tak się oznacza pierwszą linię programu). By usprawnić to niełatwe zadanie, wprowadzimy takie oto oznaczenia:

Teraz ćwiczenia w odnajdywaniu adresów i argumentów.

  ; Przykład a)
              DAT $1          #0
  start       ADD #1          $-1
              …

Ponieważ argument A w wykonywanej linii jest typu #, bierzemy go, jak i jego adres takim, jakim jest:

Argument B w tym przykładzie jest typu adresowego $, zatem nie jest wartością argumentu, a jego adresem. Mamy tutaj:

Pełne opracowanie argumentów polega zatem na wyznaczeniu dwóch adresów i wyciągnięciu spod tych adresów dwóch par tamtejszych argumentów. Nie wszystkie rozkazy Redcode potrzebują całej szóstki wartości, niemniej sędzia zawsze wyznacza je wszystkie.

Oto inny przykład, w którym znów interesuje nas jedynie opracowanie argumentów w linii startowej:

  ; Przykład b)
              DAT $1          @1
  start       MOV @1          <1
              DJN $-2         $1
              DAT $1          <1
              …

Wyłuskanie wartości argumentów spod tych adresów jest nietrudne: wystarczy zajrzeć do wyznaczonych numerów komórek areny:

Redcode

Znając typy argumentów musimy znów wrócić do rozkazów Redcode. Okazuje się bowiem, że niektóre rozkazy funckjonują różnie z różnymi typami argumentów, choć ich „zapach” pozostaje bez zmian, zresztą zgodnie ze znaczeniem angielskiego wyrazu, z którego zostały urobione. Przy okazji powtórnego omawiania rozkazów ostatecznie uściślę ich definicje. Przykłady ilustrują stan areny przed wykonaniem rozkazu (lewa strona każdego przykładu) i po jego wykonaniu (prawa strona).

DAT A B
Argument B jest niezbędny, A mozna pominąc podczas pisania programu. Wówczas sędzia walki pozostawi w polu argumentu A instrukcji DAT wartość $0. Instrukcji DAT sędzie walki nie wykonuje, uznając program, które się tego domaga, za pokonany. Dlatego musimy dbać, by nasz program nie natrafił na nią w trakcie działania. Z instrukcji DAT możemy jedynie czerpać przechowywaną w polu argument B wartość, możemy też ją zmieniać. Za to instrukcję tę będziemy starać się wbudować w program przeciwnika, tak by niczego nie podejrzewając spróbował ją wykonać. Będziemy prowadzić ostrzał pozycji przeciwnika bombami — instrukcjami DAT.
MOV A B
Gdy argument A jest typu #, następuje wpisanie jego wartości w pole argumentu B tej komórki areny, której adres opisuje, co precyzyjniej wyartykuujemy tak: Jeśli A jest typu # B-adres-B-wartość = A. W akcji wygląda to tak (z lewej — przed wykonaniem rozkadu, na prawo po):
  ; Przykład c)
  start MOV #123 $1       MOV #123 $1
        JMN $-1 #0        JMN $-1 #123
          …
Natomiast jeśli A nie jest typu #, sędzia walki spowoduje skopiowanie całej linii programu z komórki areny opisanej adresem A-adres do komórki B-adres:
  ; Przykład d)
  start MOV #1 $3         MOV $1 $3
        ADD #1 $1         ADD #1 $1
        DAT $10           DAT $10
        DAT $0            ADD #1 $1
          …

Rozkazu MOV używają mobilni wojownicy. Wykorzystuje się go też do rzucania bomb, czyli np. instrukcji DAT. Zauważmy też, ze MOV powinien raczej nazywać się CPY (od copy), gdyż po przeniesieniu komórki areny w nowe miejsce sędzia nie oczyszcza starego miejsca. Wykorzystują to niektóre programu i badają arenę, by móc stwierdzić: tu był przeciwnik.

ADD A B
SUB A B
Te rozkazy omówię razem, gdyż różnica między nimi jest tak nikła, że niewarta więcej uwagi, niż zapamiętania, że pierwszy dodaje, a drugi odejmuje. Będę mówił tylko o dodawaniu. Gdy argument A jest typu #, następuje zsumowanie wyznaczonego przez sędziego argumentu A z argumentem B i wpisanie wyniku w pole argumentu B: Jeśli A jest typu # B-adres-B-wartość = A-adres-A-wartość + B-adres-B-wartość Efekt na arenie jest taki:
  ; Przykład e)
        DAT $1 $5         DAT $1 $7
  start ADD #2 $-1        ADD #2 $-1
Za to jeśli typ argumentu A nie jest #, akcja wygląda tak: B-adres-A-wartość = B-adres-A-wartość + A-adres-A-wartość, B-adres-B-wartość = B-adres-B-wartość + A-adres-B-wartość. Na arenie znaczy to, że np.:
  ; Przykład f)
        DAT     @1         DAT @1
  start ADD $-1 $1         ADD $-1 $1
        DAT                DAT $0
Przy okazji przypomnijmy sobie, że pierwszy argument instrukcji DAT jest ignorowany przez sędziego walki, który dla porządku wpisuje tam $0. Niemniej pole tego argumentu tam jest i bierze udział w tych operacjach, w których potrzebują go inne instrukcje.
JMP A
Jest to, jak można się domyślić, rozkaz bezwarunkowego skoku do linii programu umieszczonej w komórce areny numer A-adres. Spójrzmy na przykłady:
  ; Przykład g)
  start JMP #1          ; skok tutaj
  
  ; Przykład h)
  start JMP $1
        JMP $-1         ; skok tutaj
          
  ; Przykład i)
  start JMP @1
        DAT $1
        SUB #1 $-1      ; skok tutaj
W pierwszym przykładzie argument bierzemy takim, jakim on jest. Dotyczy to też adresu, zatem mamy skok pod bieżący adres, czyli do bieżącej linii programu. To co się tam stało, nie jest dobre: wojownik będzie do końca uwięziony w tej jednej, całkiem jałowej z wojskowego punktu widzenia linii programu.