Byte Combat

Intro

…zašedlé pláně, po kterých s hvízdáním prolétá scheduler. Tma se snáší jako strach na víčka nadějí – v písku se v posledním tažení válí proces, zmrzačený a připravený téměř o veškeré své instrukce. Strach se blíží, zvuk sílí a proces v posledním záchvěvu zkouší fork někam do bezpečí – zásah. Přichází jeho veličenstvo SIGSEGV a tma…

Corewars jsou – ač by se to podle úvodu nezdálo – hra. Bez krve. Bez zvukových efektů. Téměř bez grafiky. Strategie, dalo by se říci. Ovšem pro jistou sortu lidí (jemně načrtnutou v prvním odstavci) královsky zábavná.

Historie CoreWars sahá (alespoň co já vím) někam do osmdesátých let. Princip je jednoduchý – na virtuálním stroji bez ochrany paměti je simulováno několik programů virového charakteru – bojovníků, kteří se snaží zabrat co největší kus paměti, zlikvidovat konkurenty, případně obojí.

Hráč-programátor se snaží naprogramovat dostatečně tuhý algoritmus, který by v konkurenčním prostředí pokud možno přežil, v lepším případě vyvraždil ostatní procesy. Prosté.

Architektura

Virtuální aréna je poměrně jednoduchá: n paměťových míst, veškeré adresování je prováděno modulo n aritmetikou, každá buňka může obsahovat data, nebo instrukci (ve smyslu výlučného nebo). V aréně (tj. paměti) jsou umístěny procesy, rozdělování strojového času mezi bojovníky obstarává round robin. Každý proces se může skládat z více vláken, čas vyhrazený procesu je rovnoměrně rozdělován mezi „jeho“ vlákna.

Při zápisu do paměti získává proces „vlastnictví“ zapsané buňky, což je podstatné prakticky jen pro bodování – proces může klidně provádět kód cizího programu a číst data z cizích buněk. Veškěré adresování je relativní vzhledem k poloze instrukce. Pokus o provedení datové buňky má za následek nekompromisní ukončení.

Programování bojovníků probíhá v různých assembleru podobných jazycích – klasikou CoreWars je Redcode, poněkud přítulnějším jazykem používaným v některých implementacích je Corewars (ano, drobet zmatek, jmenuje se stejně jako hra samotná).

Soupeře je možné zabít tak, že ho donutíte vykonat nepovolenou instrukci – donutíte ho „provést“ datovou buňku paměti. K tomu stačí zapsat libovolná data do buňky, na kterou právě ukazuje soupeřův IP, modelová situace:

A: IP1 == 4; provede se instrukce, IP1++, přerušení
B: IP2 == něco; provede se zápis 0×01 na [IP1], IP2++, přerušení
A: IP1 == 5, provádí se… oh, provádí se datová buňka, exitus A

(proces B nezná IP1, zápis na [IP1] je většinou náhoda nebo brute-force řešení, viz dále)

Barbarian: First Encounters

Nebudeme dlouho chodit kolem horké kaše – jednoduchý bojovník v jazyce Corewars vypadá skutečně prostě, není důvod si ho neukázat:

BODY:   move BODY, NEXT
NEXT:   data 0

Pojmenujme si tenhle program třeba „A“. Nedělá nic jiného, než že své tělíčko plazí krok za krokem pamětí vpřed. Pokud potká jiný proces, s docela slušnou šancí ho doslova převálcuje. Maximální rychlost, minimální inteligence.

O jednu buňku delší je jiný bojovník (říkejme mu „B“; někdy mám pocit, že mě teoretické vzdělání deformuje :)

TRAP:   data 0
LOOP:   move 0, TRAP
        jump LOOP

Co se stane, když se spolu potkají? Jedna z možností: Proces A se pohrne vpřed: udělá kopii svého těla (jedna instrukce) na offset 1, zvedne IP a je přerušen. Následně proces B v poklidu přepíše buňku s návěštím TRAP nulou – pokud bude mít štěstí, bude IP procesu A ukazovat zrovna na tuhle buňku a dojde k modelové situaci úmrtí A. Pokud štěstí mít nebude, bude B zrovna na své druhé instrukci (která nic nepřepisuje) a proces A přepíše buňku s návěštím LOOP (…a začnou se dít věci, ale to už je jiná pohádka).

Velice pěkný je třeba takovýhle úprkář:

C:      data 123
        data 0
        data 0
V:      data 123
L:      equal C, V
        jump L
START:  move START, NEXT
NEXT:   data 0

Dokud se nic neděje, sedí si na bobku a kontroluje situaci. Jakmile někdo šlápne na rozdrcené žárovky před vchodem (návěští C), začne prchat:

Žluťoučká část paměti je proces A: začal těsně pod stropem paměti, přetekl na začátek a valí se dopředu. Růžový nudlík uprostřed je náš úprkář, čeká na impuls. Buňky s tečkou uprostřed obsahují kód, bez tečky jsou buňky datové. Jakmile proces A dorazí k návěští C a přepíše „data 123“ svým tělem, úprkář si toho všimne a začne se chovat přesně jako A: začne prchat směrem k vyšším adresám.

Instrukční sada

Instrukční sada je poměrně bohatá – programátor má k dispozici tradiční přístupy do paměti, možnost vytvoření nového vlákna, generátor náhodných čísel, porovnání, testy, aritmetické operace včetně násobení… Problém je v tom, že většina dobrých programů jsou programy malé. Jak vidno z uvedených příkladů, program na deset instrukcí je ve světě Corewars docela boubelka a (v závislosti na velikosti paměti) může být lehce zasáhnutelný například algoritmy, které bombardují arénu zápisy dat, jako třeba tenhle (říkejme mu C :):

L:      add 5, A
        move 0, [A]
        jump L
A:      data &A

Tento kód provádí kobercový nálet na celou arénu – cokoliv většího než tři buňky dostane zásah (což ovšem nemusí znamenat jistou smrt). Ach, ano, zabije většinou i sám sebe :)

A bylo slyšet pláč a skřípění zubů…

Jak probíhá samotný souboj v aréně? Souboje se účastní dva a více procesů, výherce se různí podle bodování. Bodovat se dá podle obsazené paměti, podle schopnosti přežít (tj. jistý počet bodů za každý přežitý tik hodin), podle fragů nebo podle různých kombinací a vah všech zmíněných kritérií. Aby byl výsledek alespoň trochu objektivní, hraje se většinou na větší počet kol.

Zajímavým a poměrně typickým jevem je nevyrovnanost bojovníků. Pokud si vezmeme naše tři algoritmy: A je v jasné výhodě proti C (aby C zabil A, musel by se trefit do jeho „hlavičky“, do té doby ho ale A s velkou pravděpodobností přepíše). B (případně jeho decentní modifikace) je v jasné výhodě proti A (je přímo navrhovaný jako jeho soupeř), ovšem proti C prakticky nemá šanci.

Možnosti tu jsou

Předpokládané pokračování tohoto článku se bude zabývat dalšími typy bojovníků, klasickými přístupy k boji v aréně a pěstováním bojovníků pomocí genetických algoritmů, zatím se můžete mrknout na corewars.sf.net a vyzkoušet si boj v aréně naostro v jedné z jeho implementací ve slušivém GTK kabátku.

Další odkazy? Dobrá, http://www.go­ogle.com/sear­ch?q=corewars :)

(Abych nezapomněl: jednou z implementací Corewars – byť s poněkud paranoidnější syntaxí a lepšími možnostmi – měl ještě donedávna Microsoft. Slyšel jsem ale, že teď uz ji nepodporují, pokud byste snad měli o něco podobného zájem, jmenovalo se to tuším „Microsoft Dungeon Of Sadism“).