Byte Combat II

Vzhledem k omezené velikosti bojovníků se časem vykulilo podle stylu boje několik klasických kategorií, do kterých se dá zařadit většina algoritmů:

Kámen

Někdy se mu také říká trpaslík, podle jeho vzrůstu. Je maličký (tradiční ukázka trpaslíka zabere čtyři buňky paměti), nicméně šikovný. Je jedním z algoritmů, které jsme si popisovali v předešlém článku, tedy jen jeho tělo pro připomenutí (ve všech příkladech je opět použit jazyk Corewars):

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

Typicky využívá jen jedno vlákno a snaží se co nejrychleji zabít větší a sofistikovanější oponenty „data 0“ bombou, což se mu zhusta daří.

Papír

Algoritmus typu papír se naopak snaží mít co největší počet vláken, aby se tak uchránil od útoku bombou položenou trpaslíkem (ta zabije vlákno, nikoliv celý proces). Zároveň tím zasypává arénu mnoha instancemi svého těla, takže protivníky jednoduše přepíše.

Pěkným příkladem je algoritmus Twelve Monkeys:

THR:   data  0
START: info  2, CHILD     # CHILD <- random()
         move   CHILD, DST  # DST <- CHILD
         move   &START, SRC # Odkud kopirovat
         move   11, CNT     # Kolik bunek kopirovat
COPY:  movei SRC, DST      # Kopiruj
         loop   CNT, COPY   #
         info   4, THR      # THR <- pocet_vlaken()
         less   12, THR     # Je jich dvanact?
         jump   [CHILD]     # Ano, nechame telo lezet
                          a prejdeme na potomka
         fork   [CHILD]     # Ne, forkneme se na potomka
         jump   START       # V pripade forku jedeme dal
CNT:   data  0
SRC:   data  0
DST:   data  0
CHILD: data  0

Jde o drobně upravený papír — udržuje si přehled o počtu svých instancí a v případě, že je jich méně nežli dvanáct, přihodí do hry další. Je docela rychlý (protože nerozpouští svůj čas mezi desítky svých instancí) a proti klasickému trpaslíkovi vynikající.

Nůžky

Ty jsou prozměnu navrhovány tak, aby si poradily s algoritmy typu papír. Útočí totiž na jejich velkou slabinu — předhazují jim vějičky. Tak je mohou buď ochromit (a následně zničit), a nebo je dokonce přinutí pracovat pro sebe.

Klasický algoritmus typu nůžky postupuje v několika fázích:

1) Nalezení oponenta

Nalezení se provede jednoduše nějakým (náhodným, brute-force) prohledáním arény a testem na prázdnost/vlas­tnictví buňky.

2) Ochromení

Většinou se vejde do dvou instrukcí, z nichž jedna je „fork 0“ a druhá „jmp –1“. Jestliže proces šlápne na takovouto minu, ztratí se ve smyčkách a navíc ještě ředí svůj přidělený čas tím, že se forkuje „na místě“.

Druhá možnost, jak se zbavit procesu, je nastražení skoku na nějakou past, ve které bude proces „pracovat pro nás“, tj. provádět námi nastražený kód.

3) Vyčištění arény

V okamžiku, kdy proces usoudí, že už napáchal škody dost (je přesvědčen o tom, že oponent je znehybněný), stačí vybombardovat celou arénu (opět, náhodně nebo brute-force) a dorazit tak cyklící procesy.

Jak vidno, na těchto třech kategoriích většinou funguje analogie s jejich pojmenováním. Nůžky vyhrávají nad papírem, papír nad kamenem, kámen nad nůžkami.

Imp

Tento druh algoritmu se do klasické analogie „kámen-nůžky-papír“ nevešel, ovšem ve spojení s jinými přístupy z něj může být docela nadějný kousek. Imp je zřejmě ten nejjednodušší ofensivní algoritmus, se kterým se dá přijít:

START:  move START, NEXT
NEXT:   data 0

Rychlý, blbý, vražedný.

Když se sejdou dva sobi, tak se radost násobí

Poněkud smutné je, že sofistikovanější algoritmy často padají za oběť jednoduchému impovi — je maličký, rychlý a těžko trefitelný (jen přímý zásah do „hlavičky“ ho vyřadí ze hry). Past specializovaná na impy se staví jednoduše (viz předchozí díl), ale její ofensiva je nulová.

Možnost, jak se vyhnout smutnému konci velkého algoritmu a kvalitativně se pohnout z místa, je chránit proces domluvou s jinými procesy. Typicky taková symbióza funguje tak, že velký, chytrý a pomalý algoritmus likviduje spolehlivě soupeře, zatímco jeden nebo víc menších algoritmů se mu snaží krýt záda, aby nepadl nějakým brute-force útokem. Všechny procesy mají „svůj vlastní čas“, takže nedochází ke ztrátám výkonnosti (ke kterým by nutně došlo, kdyby se proces hájil nějakým svým vláknem) a každý proces se může plně soustředit na svou práci. Jediné zdržení nastane při startu, kdy je několik instrukcí obětováno na navázání spojení mezi procesy.

Pěkný dříč je třeba Santa's little helper:

A:      data 0
B:      data 59
C:      data 9
D:      data 0
CODE:   data 47295
L:      move [B], A
        equal A, CODE
        jump M
        jump L
M:      add 1, B
        move [B], A
        move 0, [B]
        move &END, D
COPY:   move [D], [A]
        add -1, C
        add -1, D
        add -1, A
        equal C, 0
        jump FORKK
        jump COPY
FORKK:  add 3, A
        jump [A]
DATAS:  data 10
POINT:  data 0
P:      move 10, DATAS
        move &DATAS, POINT
        add -1, POINT
S:      move 0, [POINT]
        add -1, POINT
        loop DATAS, S
END:    jump P

Nenechte se zmást jeho velikostí — většina kódu zůstane na místě, provede se jen jednou a aktivní zůstává pouze „ocásek“ od návěští DATAS dolů. Algoritmus funguje takhle: s procesem, který má chránit, se domluví přes tajnou schránku na adrese 59. Jakmile v ní najde magické číslo 47295, ví, že o jedničku výš najde adresu procesu, který má chránit. Pak se (přesněji řečeno svou část) nakopíruje těsně před něj a chrání ho před impem přicházejícím z nižších adres.

Jedním z algoritmů, které se umí s Ježíškovým pomocníčkem domluvit, je Search&Destroy II:

CODE:   data 47295
PRES:   move &CODE, [A]
        add -1, A
        move CODE, [A]
START:  info 2, A
        equal [A], B
        jump START
        move A, [C]
        add 1, C
        loop D, START
        move 15, D
L:      add -1, C
        move [C], A
        move 1, DD
M:      own [A]
        move &FO, A
        move FO, [A]
        add 1, A
        add -1, DD
        equal [A], B
        jump N
N:      loop D, L
        move 15, D
        jump START
A:      data 60
B:      data 0
FO:     fork FO
C:      data &E
D:      data 15
DD:     data 5
E:      data 0

Podstatná je horní část algoritmu (CODE–START) — SD2 při ní uloží do komunikační buňky svou adresu a magickou hodnotu. Pokud je v aréně Ježíškův pomocníček, přiběhne mu po tomto kroku krýt záda. Ve skutečnosti to vypadá takto:

Začátek simulace; žlutý je SD2, fialový SLH.

Po provedení prvních pár instrukcí uložil SD2 do komunikační schránky svou adresu a magické číslo.

Po provedení dalších několika instrukcí SLH převzal hodnoty ze schránky, vymazal adresu procesu, který hodlá chránit, a nakopíroval svou obrannou část těsně před něj.

Docela pěkné je to, že jednou z obětí SD2 může být právě jeho malý pomocníček — škoda rány, která padne vedle :)

Zabít takto spolupracující algoritmy je docela jednoduché — pokud napíšete program přímo na tuto činnost určený, stačí si vyzvednout adresu procesu ze schránky a… :)

 Devil:

A:      data 0
B:      data 59
CODE:   data 47295
L:      move [B], A
        equal A, CODE
        jump M
        jump L
M:      add 1, B
        move [B], A
KILL:   add 5, A
        move 0, [A]
        add -5, A
        move 0, [A]

Devil nepřetržitě kontroluje schránku, a pokud v ní najde magické číslo, zničí „data 0“ bombou jak Santu, tak jeho pomocníčka. Ovšem pro nespecializované algoritmy může být dvojice Santa&Helper pěkným protivníkem.

Nikomu nezastavujeme

Velice pěkným algoritmem je Hitchhiker, tedy Stopař:

A:      data 0
AA:     data 0
D:      data 0
E:      data 5
B:      info 2, A       # A <- random()
        equal [A], AA   # Je bunka prazdna?
        jump B          # Ano, zkusime jinou
        jump L          # Ne, zkusime se svezt
        jump B
L:      move [A], D     # Ulozit puvodni obsah bunky
        move 0, [A]     # Polozit bombu
M:      loop E, M       # Pockame :)
        move 5, E       #
        move D, [A]     # Vratit puvodni obsah bunky
        fork [A]        # A svezeme se na cizim kodu
        jump B          # Rodic pokracuje

Stopař si vybírá náhodnou buňku a testuje, zda někomu patří. Pokud ano, tipne si, že by to mohl být kód a nikoliv data (stopování je risk :) a položí bombu. Chvilku počká (s trochou štěstí skutečně buňka obsahovala kód a proces, kterému patřila, odpálil bombu), vrátí do buňky její původní obsah a spustí se na něm. Pokud skutečně šlo o cizí kód, provádí teď stopař cizí kód. Pokud šlo o data, má smůlu (nikoliv ovšem fatální, coredumpuje jen jedno jeho vlákno).

Pěstujeme

Přes všechny uvedené hezkosti se Corewars většinou časem zvrtnou v trvalou depresi z toho, že váš hyper-oh-so-sofistikovaný program podlehne běžnému trpaslíkovi nebo impovi. Pomoc je docela nečekaná a zajímavá: přestaňte algoritmy programovat, pěstujte je.

Pěstování algoritmů pro boj v aréně bylo jedním z logických kroků, které ve vývoji Corewars následovaly klasické souboje ručně psaných algoritmů. Nuda (nebo to byla zvědavost? :) přiměla programátory k vyzkoušení genetických algoritmů (a případně jejich různých úprav) k pěstování bojovníků do arén. Ne že by to přinášelo něco kvalitativně nového — drtivá většina vypěstovaných bojovníků podléhá v soubojích s lidskými oponenty ---, ale je to zkrátka a dobře „phun“ :)

Genetické algoritmy (jednoduše řečeno) kódují potenciální řešení nějakého problému do struktur podobných chromozomům a snaží se různými machinacemi s těmito strukturami vybrat podstatné vlastnosti onoho řešení a zlepšovat ho.

Základní idea je v případě Corewars takováto:

– Chov začíná směsí náhodně vygenerovaných jedinců.
 – Z těchto náhodných kousků se vybere několik nejrozumnějších.
 – Různým křížením a mutacemi se vytvoří nová generace, se kterou se postup opakuje až do vyprchání trpělivosti.

Takto vypěstovaní jedinci mají na Internetu své vlastní arény, do kterých nesmí být vpuštěn žádný ručně napsaný bojovník. Jejich hrdí otcové radostně sledují každý nový trik, který se jejich děťátka po desítkách hodin strojového času evoluce naučí, a radostně kvitují, když se po první tisícovce generací vykulí šikovný trpaslík.

Takto pozitivně bychom mohli náš mikroseriálek o Corewars uzavřít, abychom se mohli příště sejít u femtotutoriálku zaobírajícího se genetickými algoritmy. Neboť není lepšího pocitu, než když se po první tisícovce generací vykulí šikovný trpaslík :)