Prírodou inšpirované algoritmy

Prvý Core War Turnaj

Do turnaja vstúpilo 31 programov ale len tri sa ukázali ako najviac zdatné. Definitívnym víťazom bol program s názvom MICE od Chipa Wendella z Rochesteru, N.Y..

V hre Core War sú dve základné pravidlá. Prvé je, že konkurenčné programy sa striedajú pri vykonávaní svojich inštrukcií. Striedanie riadi MARS. V podstate simuluje akcie počítača. Priebežne aktualizuje obsah poľa jadra v súlade s vykonávaním inštrukcií. Dovolí jednu inštrukciu vykonať pre jednu stranu počas jedného cyklu. Druhé pravidlo je, že ak program nemôže vykonať inštrukciu, tak prehral. Ak program obsahuje inštrukciu SPL A, je považovaný za porazeného, až keď všetky jeho vlákna zomrú.

COMMANDO: Bojový program Dewdneyho na tomto turnaji. Prvých päť inštrukcii:

MOV #0 -1

JMP -1

SPL -2

MOV 10 113

SPL 112

Na začiatku sa nachádza Imp Pit. Vykonávanie aktuálneho programu začína na tretej inštrukcii SPL -2. Commando v nasledujúcich dvoch cykloch vykoná prvú a štvrtú inštrukciu a v potom druhú a piatu. Každý prúd sa vykonáva nezávisle polovičnou rýchlosťou. Na začiatku teda spustí Imp-Pit a potom premiestni iný Imp na adresu 113. Ten je aktivovaný druhou inštrukciou SPL. Potom sa skopíruje do nového segmentu 100 adries za terajšiu pozíciu. Nová kópia skočí ako na padáku na nepriateľské územie a aktivuje sa inštrukciou JMP v originálnom programe, ktorý tým končí svoju púť okrem Imp Pit-a.

Na turnaji nemohol každý program bojovať s každým, pretože to nedovoľoval čas. Pri 31 programoch by to bolo 465 bojov, tak sa rozdelili do dvoch približne rovnakých divízii. II.divíziu vyhralo Dewdneyho Commando. Prvý štyria s každej divízie postúpili do ďalšieho kola. Tri programy vyšli víťazne. Boli to CHANG1 od Morrison J. Chang z Floral Park, N.Y. a dvaja od Chipa Wendella: MIDGET a MICE. MIDGET a MICE remizovali s CHANG1 a MICE rozbil MIDGETa.

Každý finálový pár odbojoval spolu 4 zápasy. Limit bol 15.000 inštrukcii pre každého, alebo asi dve minúty reálneho času. V každom prípade boli bojové programy dané na náhodné miesto v poli a za každým výsledok bol rovnaký. Medzi MICE a CHANG1 to bola štyri krát remíza.

Core War turnaj sledovali na monitore. Bojisko bolo zobrazené ako m x n rozmerne pole s 8000 bodmi, kde každý bod bol 1 adresa. Jeden bojovník bol zobrazený svetlo modrou farbou a druhý ostrou červenou. Ak niekto obsadil nejakú adresu, tak sa tá rozsvietila jeho farbou. Takže ak tam bola predtým inštrukcia konkurenta a prepísala sa, tak sa zmenila farba políčka.

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

MICE: Je to jeden s najkratších reprodukujúcich sa programov. Má iba 8 inštrukcií, dve, pomocou ktorých sa vytvorí nová kópia z programu vo vzdialenosti 833 adries za umiestnením aktuálnej kópie v poli. Tretia a štvrtá inštrukcia demonštrujú zopár ďalších možnosti jazyka Redcode. Slovo loop je len návestie, ktoré stojí pred adresou a zjednodušuje písanie programov. Inštrukcia DJN znamená, že MARS má skočiť na adresu s návestím Mloop ak na adrese s návestím ptr nie je nula. Znak @ vyjadruje nepriame adresovanie, t.j. že kopírujeme obsah adresy, ktorá sa nachádza na adrese označenej za týmto znakom (za návestím ptr). Číslo uložené za návestím ptr sa priebežne mení dekrementovaním pomocou inštrukcie DJN. Začína na poslednej adrese programu a postupne sa dekrementuje na nulu, kedy končí kopírovanie. Podobne aj adresy na ktoré sa ukladajú inštrukcie sú zadané nepriamym adresovaním. Na relatívnej adrese 5 sa nachádza hodnota 833 a prvá inštrukcia pristane na adrese 832 za MOV inštrukciou; ako naznačuje znak "<" , cieľová adresa je dekrementovaná a MOV sa vykonáva. Takže MICE si najskôr kopíruje chvost. Inštrukcia SPL, ktorá nasleduje hneď za inštrukciou s návestím loop prenesie vykonávanie na novú kópiu MICE. Po úspešnom narodení rodičovský program začína odznova. Nie je žiadne obmedzenie koľko potomkov môže mať takýto program. A každý program robí to isté.

Väčšinou CHANG1 začínal v rohu hore vľavo s modrou farbou a MICE pred polovicou obrazovky s červenou farbou.

Boj začal: MICE sa začal prudko rozmnožovať a za chvíľu bola obrazovka plná červených pásikov. Medzitým CHANG1 aktivoval Imp továreň na konci svojho reťazca (posledné tri inštrukcie). Keď vykonávanie došlo po inštrukciu SPL, tak sa rozdelilo do dvoch vetiev. Jedna vykonávala klasický Imp MOV 0 1. Druhá JMP -1, čo začalo proces odznova. Problémom bolo, že sa tým vykonávanie spomaľovalo. Napríklad ak existovalo 1000 Impov, t.j. 1000 nezávislých vetiev, tak program postupoval 1000 krát pomalšie. Otázkou bolo či dokáže podkopať MICE.

Pokiaľ Imp sa reprodukoval, CHANG1 zabil niekoľko kópií MICE pomocou dátových bômb. Dátové bomby pozostávali z núl, ktoré pomocou inštrukcie MOV pristávali na územie, ktoré sa pokladalo za nepriateľské. Kľúčová inštrukcia v CHANG1 programe je MOV #0 @ -4. Nula sa premiestnila na adresu, ktorá bola obsahom adresy 4 miesta pred touto inštrukciou. Poloha sa priebežne inkrementovala o hodnotu 16 pre zaisteniu dobrej polohy hrádze z núl.

Imp rozvinul svoju deštruktívnu silu a nepriatelia zomierali. MICE však priebežne kontroloval či jeho prvá inštrukcia je nula. Ak nie, tak MICE dovolil vykonať nevykonateľnú dátovú inštrukciu a zomrel.

Zopár kópií MICE bolo zabitých dátovými bombami a ostatné vykonali svoju vlastnú popravu vykonaním nevykonateľnej inštrukcie. Ako môže MICE prežiť? Odpoveď leží v jeho schopnosti množiť sa. Veľa MICE-ov pristálo na nepriateľských Imp bojovníkoch. Po istom čase MICE urobil výsadok aj na základný program CHANG1 a zničil ho. CHANG1 však vytvoril dostatočné množstvo Imp bojovníkov (nezávislých vetiev programu) aby tak vydržal do konca časového limitu. Takže výsledok bol REMÍZA.

ZÁVER: Po tomto turnaji, ktorý bol prvý svojho druhu Dewdney v jednom článku z januára 1987 vyjadril svoju víziu "V budúcnosti na ďalších Core War turnajoch budú asi bojovníci mať dlhší zdrojový kód a budú inteligentnejší. T.j. budú klásť falošné stopy a budú útočiť na svojich nepriateľov náhle a s rozhodnutím."