Prírodou inšpirované algoritmy

Bojovníci

Bojové programy môžeme rozdeliť podľa inteligencie, agresivity a veľkosti. Do kategórie malých, agresívnych a nie veľmi inteligentných patria IMP a DWARF. Na ďalšom stupni sú programy, ktoré sú väčšie, trochu menej agresívne, ale dostatočne bystré na to aby si poradili s nižšou triedou. Bystrejšie programy majú schopnosť rozhodovať o útoku spolu s kopírovaním seba mimo nebezpečenstva. Každý z týchto programov obsahuje časť kódu, ktorý je podobný kódu GEMINI. GEMINI je iba funkcia na kopírovanie bojového programu, ktorého je súčasťou, o 100 adries za aktuálnu pozíciu a na nastavenie novej kópie ako aktívnej. Takto vznikli BIGFOOT a JUGGERNAUT. Na ďalšom stupni náročnosti sa nachádzajú bojové programy SCANNER a RAIDAR. Títo bojovníci sú však príliš dlhí na to aby sa mohli reprodukovať v tomto prostredí.

DWARF: Je to veľmi primitívny a nebezpečný program. Bombarduje každú 5 adresu s nulou. Nula je celé číslo označujúce nevykonateľnú dátovú inštrukciu. Ak dopadne do nepriateľského programu môže spôsobiť zastavenie (prehru).

• DAT -1
• ADD #5 -1
• MOV #0 @-2
• JMP -2

Toto je celý Dwarf. Do relatívnej adresy 1 zapíše -1, potom k nej pripočíta 5. Na tretej adrese zadáva, že na adresu, ktorej hodnota je na adrese o dve pozície späť zapíš nulu. Posledná inštrukcia je návrat o 2 pozície v adresnom poli, t.j. na adresu 2. Tam opäť inkrementuje adresu 1 o hodnotu 5 a 0 sa zapíše na adresu 10. A potom ďalej na 15, 20, 25.... . Dwarf je imobilný, ale zasahuje celé pole.

Je na zamyslenie, že statický bojový program, ktorý má viac ako 4 inštrukcie sa môže a vyhnúť zásahu od Dwarf-a. Nepriateľ má iba tri možné stratégie:

1. hýbať sa a tým sa vyhnúť bombardovaniu,
2. absorbovať zásahy a opraviť poškodenie alebo
3. zaútočiť prvý.

Pri poslednej stratégii bojový program musí mať "veľa šťastia", aby Dwarf zasiahol. Má okolo 1600 vykonávacích cyklov skôr ako dostane zásah. Ak 2. program je tiež Dwarf, tak každý program vyhrá 30% času.

TRAP-DWARF: Modifikácia, ktorá každú bombu (nulu) ochráni inštrukciou PCT.

IMP: Je to jednoriadkový bojový program: MOV 0 1 Je schopný sa premiestniť v pamäťovom poli. Kopíruje obsah relatívnej adresy 0 do 1. Program sa pohybuje poľom rýchlosťou jednej adresy za cyklus.

IMP GUN: Vylepšením klasického Imp o inštrukciu SPL sme vytvorili továreň na Imp.

• SPL 2
• JMP -1
• MOV 0 1

IMP PIT(stomper): Je to jediná možnosť ako sa môže väčší program ochrániť pred ImpGun.

• MOV #0 -1
• JMP -1

IMP vs. DWARF Bombardovanie pamäťového poľa nulami Dwarf-om je rýchlejšie ako pohyb Imp-u, ale to neznamená, že Dwarf má výhodu. Otázkou je či Dwarf zasiahne Imp, keď ho dobehne. Ak Imp zasiahne Dwarf-a prvý, tak mu zmení kód. Ak Dwarf vykoná inštrukciu na 4-tej adrese JMP -2 a na 2 adrese bude Impov MOV 0 1. Výsledkom bude, že Dwarf bude zničený a stane sa Imp-om, ktorý sa bude nekonečným prenasledovateľom prvého Imp-u v poli.

GEMINI

• DAT 0
• DAT 99
• MOV @-2 @-1
• CMP -3 #9
• JMP 4
• ADD #1 -5
• ADD #1 -5
• JMP -5
• MOV #99 93
• JMP 93

Skladá sa s troch hlavných časti. Dve dátové inštrukcie na začiatku slúžia ako smerníky, označujú kde sa skopíruje nasledujúce inštrukcia. Cyklus v strede programu premiestňuje každú inštrukciu o 100 pozícii ďalej za ich aktuálnu pozíciu. Pri každom prechode cyklom sa oba smerníky inkrementujú o hodnotu 1, tým označujú novú zdrojovú a cieľovú adresu. Porovnávacia inštrukcia CMP spolu s cyklom testuje hodnotu prvej dátovej inštrukcie. Ak tá bola inkrementovaná už 9-krát, čo znamená, že celý program sa už skopíroval, tak vyskočíme s cyklu. Cieľová adresa je uložená v druhej inštrukcii a jej hodnota je 99, počas kopírovania sa však raz inkrementuje, čiže v novej verzii programu bude DAT 100. Táto chyba, ktorá vznikla pri prepisovaní sa opraví pomocou inštrukcie MOV #99 93 a vykonávanie sa prenesie na novú kópiu.

JUGGERNAUT: Kopíruje sa o 10 pozícii dopredu (na rozdiel od Gemini, ktorý skáče o 100). Ako Imp pokúša sa prejsť cez všetkých svojich nepriateľov. Vyhráva oveľa častejšie ako Imp, pretože prepísané programy sú menej schopné vykonávať časti Juggernaut-ovho kódu.

BIGFOOT: Ďalší program založený na Gemini mechanizme, vytvára interval veľkých prvočísiel medzi kópiami. Je ťažké ho chytiť a má aký istý ničiaci účinok ako Juggernaut.

RAIDAR: Udržuje dve strážne veže v okolí programu. Každá strážna veža pozostáva zo 100 nasledujúcich adries obsahujúcich jednotky a je oddelená od programu pomocou nárazovej zóny pozostávajúcej zo 100 prázdnych adries. Raidar rozdeľuje svoj čas medzi systematické útočenie na vzdialenú oblasť v pamäťovom poli a kontrolu adries svojich strážnych veží. Ak zbadá nejakú zmenu, predpokladá, že sa jedná o útok Dwarf-a, Imp-u alebo nejakého iného neinteligentného programu. Raidar sa potom skopíruje na opačnú stranu od poškodenej strážnej veže, opraví ju a vytvorí novú strážnu vežu na nechránenej strane a vráti sa k normálnym operáciám.

SCANNER: Tento program napísal Jones ako opravujúci sa program, ktorý môže prežiť nejaké útoky, i keď nie všetky. Udržuje dve kópie seba, ale aktívna je len jedna. Bežiaca kópia periodicky sníma druhú kópiu, či nebola zmenená. Zmeny sa zistia pri porovnávaní. Vždy sa predpokladá, že vykonávacia kópia je správna. Ak sa nájdu nejaké zlé inštrukcie, tak sú nahradené a riadenie sa prenesie na druhú kópiu, ktorá začne skúmať prvú. Je to čisto defenzívny program. Dokáže prežiť útok Dwarf-a, Imp-a, Juggernaut-a a podobných pomaly postupujúcich útočníkov.

COMMANDO: Je opísaný pri Prvom Core War turnaji.

Chang1:

• MOV #0 -1
• JMP -1
• DAT +9
• Start: SPL -2
• SPL 4
• ADD #-16 -3
• MOV #0 @-4
• JMP -4
• SPL 2
• JMP -1
• MOV 0 1

MICE:

• ptr: DAT #0
• start: MOV #12 ptr
• loop: MOV @ptr <5
• DJN loop ptr
• SPL @3
• ADD #653 2
• JMZ -5 -6
• DAT 833

Aj títo dvaja bojovníci sú opísaní pri prvom Core War turnaji.