Hlavní navigace

Byte Combat

Tomáš Znamenáček 22. 11. 2001

Předem upozorňuji, že následující článek je určen především individuím, která při informačně vypjatějších konverzacích s partnerkou touží po gdb a po propařených nocích šeptají melodramaticky "segmentation fault, core dumped".

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:

CoreWars, obrázek

Ž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“).

Našli jste v článku chybu?

18. 1. 2002 16:38

Pouchetty (neregistrovaný)

Myslim, ze sis odpovedel. Kdybys mohl nekoho oddelat jenom svoji bunkou, nemohl bys mu trebas podvrhnout svuj kod. Mozna by to slo vyresit taky tak, ze by to bylo jedno, ale existovala by instrukce DIE :-))

12. 1. 2002 19:13

J. (neregistrovaný)

Nepochopil jsem, proc se rozlisuje, zda jsou v pameti data nebo instrukce. Myslim, ze zakladni koncepce pocitace byla, ze si programator muze psat do pameti co chce, kam chce a obdobne muze kamkoliv jumpnout. Nevim, proc by pro me melo byt dulezite, zda nekdo adrese, na kterou chci skocit, rika datova bunka.

Proc to je v CoreWars jinak? Aby existovala nejaka moznost, jak zahubit cizi proces?



Lupa.cz: Avast po spojení s AVG propustí 700 lidí

Avast po spojení s AVG propustí 700 lidí

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

120na80.cz: Jak oddálit Alzheimera?

Jak oddálit Alzheimera?

120na80.cz: Rakovina oka. Jak ji poznáte?

Rakovina oka. Jak ji poznáte?

DigiZone.cz: Sony KD-55XD8005 s Android 6.0

Sony KD-55XD8005 s Android 6.0

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Vitalia.cz: Znáte „černý detox“? Ani to nezkoušejte

Znáte „černý detox“? Ani to nezkoušejte

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

Měšec.cz: Golfové pojištění: kde si jej můžete sjednat?

Golfové pojištění: kde si jej můžete sjednat?

Lupa.cz: Seznam mění vedení. Pavel Zima v čele končí

Seznam mění vedení. Pavel Zima v čele končí

Podnikatel.cz: Na poslední chvíli šokuje vyjímkami v EET

Na poslední chvíli šokuje vyjímkami v EET

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

120na80.cz: Boreliózu nelze žádným testem prokázat

Boreliózu nelze žádným testem prokázat

Vitalia.cz: Co pomáhá dítěti při zácpě?

Co pomáhá dítěti při zácpě?

Lupa.cz: EET v e-shopech? Zdražení a horší komfort

EET v e-shopech? Zdražení a horší komfort