Wojny Rdzeniowe czyli Core Wars

Pamiętacie Wojny Rdzeniowe? Odpowiedź zignoruję – nawet osoby kojarzące nazwę raczej nie przypomną sobie szczegółów owej cybernetycznej rozrywki z epoki pierwszych pecetów.

Idea programowalnej maszyny walczącej sięga starożytności, jednak nie będziemy cofać się aż tak daleko. Wystarczy skok do lat osiemdziesiątych XX wieku, kiedy rozwój nauki i technologii pozwolił na przestudiowanie tematu walczących ze sobą… programów.

Ankieta, taka na szybko. Czy wiesz, co to są Wojny Rdzeniowe (Core Wars)?

— Informatyk Zakładowy (@InfZakladowy) July 14, 2022

Wojny Rdzeniowe były swoistym e-sportem – rywalizacją, w której programiści tworzyli programy walczące autonomicznie na wirtualnej arenie. Pierwsze wersje „arbitrów” (oprogramowania sędziującego) działały w trybie tekstowym i prezentowały jedynie wynik zmagań. Szybko powstały jednak warianty uwzględniające wizualizację areny i działań podejmowanych przez walczące programy.

Arena

Rdzeń, czyli przestrzeń, w której walczą programy-wojownicy, składa się z określonej liczby komórek pamięci. Rozmiar rdzenia jest ustalany dowolnie, w turniejach było to z reguły od 2000 do 8000 komórek. Charakterystyczne dla Wojen Rdzeniowych są dwie cechy:

• arena jest zapętlona – gdy zaczniemy przechodzić do kolejnych komórek pamięci, dotrzemy po pewnym czasie do komórki startowej od drugiej strony
• komórki pamięci nie mają „globalnej” numeracji widocznej dla wojowników, kod może operować jedynie na adresach względnych, rozumianych jako przesunięcie w tył lub w przód względem aktualnie rozpatrywanej komórki.

Pojedyncza komórka pamięci mieści jedną instrukcję i jej dwa parametry. Przed rozpoczęciem rozgrywki arbiter losuje obszary pamięci, do których kopiuje programy dwóch (lub więcej) wojowników. Program składający się z 10 instrukcji zajmie więc 10 kolejnych komórek pamięci. Arbiter gwarantuje, że wylosowane obszary są rozłączne, ale nie informuje programów o odległości od przeciwnika, ani o tym, w którą stronę jest do niego bliżej.

Następnie arbiter rozpoczyna wykonywanie na zmianę po jednej instrukcji z każdego programu obecnego na arenie. Gra kończy się zwycięstwem, gdy na arenie zostanie tylko jeden program lub remisem, gdy po zadanej liczbie ruchów (np. 30 tysięcy) nie udało się wyłonić zwycięzcy.

Wojownicy

Programy walczące w Wojnach Rdzeniowych napisane są w języku programowania Redcode, przypominającym nieco asembler. Programista ma do dyspozycji instrukcje kopiowania pamięci, operacje arytmetyczne, porównywanie komórek pamięci oraz kilka wariantów skoków warunkowych i bezwarunkowych. Dostępnych jest kilka typów argumentów, m.in.: literały, adresy bezpośrednie (wskaźniki) oraz adresy pośrednie (wskaźniki na wskaźnik).

Wstęp do programowania w Redcode można znaleźć na tej stronie.

Od prawdziwych asemblerów na prawdziwe komputery, Redcode różni się rozkazem tworzącym procesy potomne. Zaletą rozmnożenia jest większa odporność, bo przegrana danego wojownika następuje dopiero po śmierci ostatniego z jego procesów. Wadą jest wolniejsza praca każdego z nich – przydział czasu wykonania jest wspólny dla wszystkich „klonów”. Jeśli jeden wojownik rozmnoży się do 10 kopii, w ciągu dziesięciu kolejek każda kopia wykona tylko jedną instrukcję.

Warunki zwycięstwa

W zestawie instrukcji Redcode występuje instrukcja DAT oznaczająca dane. W takiej komórce program może przechowywać dowolną wartość liczbową. Przed umieszczeniem na arenie wojowników, do wszystkich komórek pamięci wpisywana jest wartość „DAT-zero” zaś próba wykonania instrukcji DAT kończy się zniszczeniem procesu.

Główną strategią każdego programu będzie więc próba nadpisania kodu przeciwnika instrukcją DAT. Istnieje wiele możliwych taktyk – np. strzelanie po arenie na oślep, próba wyszukania kodu przeciwnika na arenie i zamazanie go śmiercionośną instrukcją, próba zamknięcia przeciwnika w pętli rozmnażania (by spowolnić jego inne procesy, jeśli jakieś istnieją) i późniejsze uśmiercenie oraz wiele innych.

Szybko dostrzeżemy jednak balans między złożonością a niezawodnością. Jeśli kod wojownika będzie bardzo skomplikowany (a więc składający się z wielu instrukcji), wojownik taki będzie bardziej podatny na prostacki ostrzał na ślepo.

Wynik pojedynczej rozgrywki zależy ściśle od początkowego ułożenia programów w pamięci, więc w walkach turniejowych każdy mecz składa się z kilkudziesięciu lub kilkuset osobnych partii. Dopiero ich podsumowanie pozwoli wskazać zwycięzcę pojedynku.

Strategie

Niektóre programy nigdy nie wygrają w żadnej potyczce. Przykładem jest stacjonarny wojownik składający się z pojedynczej instrukcji „skocz o zero komórek” – przez całą partię będzie zajmował jedną komórkę pamięci, z której nigdy (samodzielnie) nie wyjdzie. Innym przykładem jest Skoczek, program złożony z instrukcji „skopiuj zawartość tej komórki do kolejnej komórki”. Ponieważ wskaźnik wykonania procesu przesuwa się o jedno „oczko” do przodu, taki program będzie sekwencyjnie zamazywał kolejne komórki pamięci swoją jedyną instrukcją. Najczęstszy efekt – zamiana rozjechanego przeciwnika w drugiego Skoczka i remis.

Wiele programów zawiera jednak bardziej złożone, wielopoziomowe konstrukcje. Można do nich zaliczyć różne warianty i kombinacje poniższych modułów:

• szybkie skopiowanie kodu do kilku miejsc w pamięci i uruchomienie niezależnych kopii
• skopiowanie w różne miejsca w pamięci wabików wyglądających jak kod wojownika
• szybki skan pamięci by jak najszybciej zlokalizować przeciwnika
• algorytmy dokładnego przeszukiwania pamięci
• bezpośredni atak (kierowany lub losowy) instrukcjami DAT
• atak instrukcją klonowania, by spowolnić przeciwnika

Nie ma jednej, uniwersalnej strategii. Trzem popularnym strategiom nadano angielskie nazwy papier-kamień-nożyce, bo każda z nich jest statystycznie lepsza od jednej konkurentki a gorsza od drugiej.

Społeczność

W dzisiejszych czasach pasjonaci dowolnego hobby mogą odnaleźć się w internecie. We wczesnych latach 90’ był on jednak dostępny tylko w środowiskach akademickich, więc wielu miłośników Wojen Rdzeniowych wywodziło się właśnie stamtąd. Internet nie był jednak jedynym źródłem wiedzy – dużym zainteresowaniem cieszyła się prasa komputerowa, która chętnie pisała o ciekawostkach tego typu.

W Polsce pierwsza informacja na temat Wojen pojawiła się prawdopodobnie w magazynie Komputer, już we wrześniu 1987. Potem, w latach 1992-1995, cykl artykułów opublikowano w miesięczniku Enter – redakcja zorganizowała nawet dwie edycje Mistrzostw Polski w Wojnach Rdzeniowych, wzięło w nich udział kilkadziesiąt osób. Z publikacjami tymi można zapoznać się na stronie domowej Łukasza Grabuń, polecam lekturę!

Przez wiele lat pasjonaci prowadzili w internecie rankingi typu „król wzgórza” (King of the Hill, KotH) zawierające listę dwudziestu najlepszych wojowników danej kategorii. Jeśli na wzgórze wdzierał się nowy program, inny musiał z takiego rankingu wylecieć. Parametry areny na niektórych wzgórzach były bardzo nietypowe, np. w formacie „nano” rozmiar pamięci wynosi raptem 80 komórek!

Zmierzch zainteresowania Wojnami Rdzeniowymi zbiegł się z przełomem wieków. Można śmiało powiedzieć, że w owym czasie prawie wszystko zostało już wymyślone a temat zwyczajnie wyeksploatowano. W ostatnich latach aktywności społeczność skupiała się raczej na meta-hobby, którym było doskonalenie algorytmów ewolucyjnych „hodujących” wojowników oraz optymalizatorów skracających ich kod.

Dziedzictwo

Pomysł autonomicznych programów walczących na arenie powraca regularnie w coraz to nowych odsłonach. Pamiętam, że w połowie lat ‘90 grałem w Digital Warriors, mało znaną grę twórców legendarnego Robbo. Na stronie Internet Archive można w nią zagrać w emulatorze online!

Nowszym przykładem jest Robocode, arena udająca fizyczne środowisko walki czołgów. Programy sterujące czołgami mogą skanować otoczenie, wykrywać przeciwników i podejmować akcje ofensywne i defensywne. Do dyspozycji mają różnorodne akcje – min. ruch w przód i w tył, obroty kadłubem i wieżą oraz strzał z działa. Nowocześniejszą wersję tego samego pomysłu jest Robocode Tank Royale.

Co ciekawe – w odróżnieniu od Wojen Rdzeniowych, człowiek nie musi samodzielnie definiować wszystkich reguł zachowania robota. Można użyć technik uczenia maszynowego, które polegają – w pewnym uproszczeniu – na określeniu reguł gry i puszczeniu zawodnika „na żywioł”. Podczas tysięcy i milionów partii sieć neuronowa zaczyna samodzielnie uczyć się, które sekwencje zachowań prowadzą do sukcesu (trafienie przeciwnika, wygrana runda) a które do porażki (otrzymanie obrażeń, przegrana runda).

Jeśli temat cię interesuje, polecam dwa filmy o uczeniu ze wzmacnianiem. Pierwszy demonstruje tworzenie i trenowanie sieci neuronowej, która – po kilkudziesięciu godzinach nauki – potrafi przejechać skomplikowany tor w grze Trackmania.

Drugi film pokazuje możliwości frameworka OpenAI. Tam trenowane są dwie kategorie ludzików biegających po arenie – są to Uciekający i Goniący. Obserwacja kolejnych pokoleń sztucznej inteligencji wywołuje ciarki na plecach. Obie grupy nie tylko uczą się współpracować, by osiągać cel wymagający koordynacji działań, ale odnajdują błędy w symulacji areny i wykorzystują je np. do przeskakiwania przez ściany.

Wojny Rdzeniowe to już przeszłość. Warto wiedzieć, że istniały, ale współczesne „gry w programowanie” są o wiele ciekawsze. Chcecie przeczytać o nich osobny artykuł? Proszę o informację w komentarzu!