STŘEDOŠKOLSKÁ ODBORNÁ ČINNOST
Genetický vývoj umělé inteligence piškvorek Číslo oboru: 1 Název oboru: Matematika a matematická informatika
Gymnázium, Brno-Řečkovice Terezy Novákové 2 621 00 Brno
Jan Šimonek sexta B 2006/2007
Prohlašuji, že jsem středoškolskou odbornou činnost vypracoval samostatně. Použitou literaturu a podkladové materiály uvádím v přiloženém seznamu.
V Brně
……………………..
2
Na tomto místě chci poděkovat Mgr. Zdeňku Votavovi za vstřícný a přátelský přístup a podnětné připomínky při zpracovávání mojí středoškolské odborné činnosti.
3
1 OBSAH 1
Obsah…………………………………………………………………….. 4
2
Úvod……………………………………………….................................... 5
3
Systémy umělé inteligence……………………......................................... 6
3.1
Skripty……………………... …….............................................................. 7
3.2
Genetický vývoj…….……………………………………………….......... 8
3.3
Neuronové sítě……………………………………………………….…… 9
4
Genetický vývoj skriptů umělé inteligence……………………………. 10
4.1
Umělá inteligence piškvorek s použitím skriptů………………..………… 10
4.2
Genetický vývoj skriptů umělé inteligence piškvorek………………......... 11
4.2.1
TPlocha…………………………………………………………………… 12
4.2.2
TUI……………………………………………………………………....... 12
4.2.3
Syntaxe skriptů……………………………………………………………. 14
4.2.4
TTurnaj…………………………………………………………………… 16
4.2.5
Množení UI…….………………………………………………………......21
5
Průběh evoluce, naměřené hodnoty…………………………………..... 22
6
Zobecnění systému…..…………………………………………………... 27
7
Závěr……………………………………………………………………... 28
8
Použitá literatura…………………………………….………………….. 29
4
2 ÚVOD Jako téma své středoškolské odborné činnosti jsem si vybral Genetický vývoj umělé inteligence piškvorek. Ve své práci se pokusím popsat tento systém genetického vývoje skriptů umělé inteligence piškvorek a následně jej zobecnit. Mělo by se jednat o kombinaci jednoho z nejčastějších a nejobecnějších druhů UI – skriptů s genetickým vývojem. Právě tyto skripty by měly podléhat evoluci a zlepšovat se a řídit chování jedinců v populaci. Tento systém se pak pokusím demonstrovat na příkladu umělé inteligence piškvorek. Toto téma jsem si nevybral náhodou, již několikrát jsem nad tímto tématem teoreticky uvažoval ale nikdy jsem se nerozhodl uvést jej do praxe. Myšlenka demonstrovat tento systém na umělé inteligenci piškvorek také nevznikla náhodou. Již dříve jsem udělal jednoduchý algoritmus, který se mi osvědčil a nyní jsem ho v pozměněné podobě použil také. Používám převážně programovací jazyk C++. Pro implementaci tohoto algoritmu jsem si tedy vybral tento programovací jazyk a volně šiřitelné prostředí a kompilátor programu Dev-C++.
5
3 SYSTÉMY UMĚLÉ INTELIGENCE Na začátek uvedu definici umělé inteligence:
Uznávaná nejobecnější definice, již vytvořil Marvin Minsky, definuje umělou inteligenci (Artificial Intelligence), zkráceně UI (AI) jako vědu, která se zabývá tím, jak přinutit stroje projevovat se takovým chováním, které by v případě člověka vykazovalo potřebu inteligence.1
Algoritmy umělé inteligence obecně využívají několika systémů: 1) Skripty – Na každou reakci se podle předem daného vzorce vypočítá reakce. Tento typ je nejrozšířenější, protože je nejjednodušší na implementaci. Typické použití jsou hry. 2) Genetický vývoj – Umělá inteligence se skládá z velkého množství unikátních jedinců, kde má každý svůj genetický kód a podle něj vypadá, chová se. Tito jedinci podléhají evoluci. Málo rozšířený typ, zvláště v umělé inteligenci, používá se většinou při řešení konkrétních úloh. 3) Neuronové sítě – Napodobují skutečnou strukturu mozku založenou na neuronech a jejich spojení. Neurony vyhodnocují vstupy a výstupní hodnoty na vstupy dalších neuronů Časté jsou ale i různé kombinace těchto tří základních systémů například typické spojení genetického vývoje s neuronovou sítí. Genetický vývoj určuje tvar neuronové sítě a fyzické vlastnosti jedince. Neuronová síť potom určuje jeho chování. Je to algoritmus nejvíce vycházející ze skutečnosti. Vykazuje velice dobré výsledky, jedinci jsou dostatečně přizpůsobiví nejen v průběhu generací ale i v průběhu života.
1
Umělá inteligence. Wikipedie. [cit. 2007-01-13] Dostupný z: http://cs.wikipedia.org/wiki/Um%C4%9Bl%C3%A1_inteligence
6
2.1
Skripty
Jsou pouhým naprogramováním určitého neměnného algoritmu podle jakého se daný jedinec chová. Používají různé funkce, kterými analyzují prostředí (popř. situaci), a na základě nich se pak vypočítá reakce. Je to nejstarší a nejjednodušší algoritmus umělé inteligence. Velmi často se s ním můžeme setkat v počítačových hrách. Pokročilé skripty už mají připraveno několik modelů chování, které jedinec používá v různých situacích. Například v případu hře piškvorky se jedinec rozhoduje mezi obranou a útokem. Jejich největší nevýhodou je jejich neměnnost a možnost předpovídat jejich chování ať už lidmi, nebo jinými pokročilejšími systémy umělé inteligence. Výhody jsou pak nižší hardwarové nároky než u jiných systémů, nepřítomnost fáze učení nebo počáteční fáze vývoje a jejich spolehlivost (přesně vždy udělají to samé nebo v rámci daných mezí).
7
2.2
Genetické algoritmy
Genetický vývoj je jednou z nejmladších a nejzajímavějších metod. Genetické algoritmy (=genetický vývoj) jsou algoritmy, které automaticky hledají řešení nějakého komplexního problému. Tyto algoritmy tvoří nějaký program, nebo popis řešení problému na základě genů. Geny mohou být tvořeny např. polem čísel, řetězci apod., případně dalšími doplňujícími hodnotami. Genetické algoritmy jsou založeny na evolučním procesu – přirozeném výběru, mutacích, křížením a hlavně velkou populací různých jedinců. Ti se pokoušejí splnit zadaný úkol a jsou bodově ohodnoceni, bodové ohodnocení je nejčastěji vyjádřeno pomocí hodnoty fitness (zdatnost) relativně vztažené k nějakému uměle naprogramovanému jedinci popřípadě k ideálnímu jedinci. předpokládaný graf fitness hodnoty 0,9 0,8 0,7
fitness
0,6 0,5 0,4 0,3 0,2 0,1 0 generace
Fitness narůstá skokově, vždy když se náhodnou mutací objeví úspěšný jedinec velmi rychle ovládnou jeho potomci celou populaci a hodnota se zvýší. Lépe bodově hodnocení jedinci pak mají více potomků v následující generaci. Potomci jsou tvořeni zmutovaným genetickým kódem rodiče(ů) případně jeho (jejich) částí.
Výhodou těchto systémů je především velká flexibilita. Programátor se také nemusí zabývat řešením problému, pouze genetickým algoritmem a interpretací genetického kódu. Nevýhodou je naopak v počáteční fázi vývoje malý až nulový přírůstek maximální hodnoty fitness v celé generaci a nemožnost vývoje jedince v průběhu jeho života bez kombinace např. s neuronovou sítí. Také interpretace genetického kódu je často velmi složitá.
8
2.3
Neuronové sítě
Princip neuronových sítí je inspirován principem činnosti lidského mozku. Je založen na matematickém modelu neuronů a jejich spojením. Neuron se dá schématicky vyjádřit
Kde x1, x2… xn představují vstupy neuronu (tzv. dendrity), w1, w2… wn představují synoptické váhy, y představuje výstup a ξ je tzv. vnitřní potenciál neuronu. Ten se vypočítá podle vzorce:
ξ = ∑i =1 n
wx i
i
Výstupní hodnota je dána přenosovou funkcí σ a prahovou hodnotou h.
y = σ (ξ ) Přenosových funkcí je hodně druhů pro příklad uvádím tu nejjednodušší tzv. ostrá
σ (ξ ) = {10−−ξξ≥≤hh nelinearita:
Takovéto neurony jsou pak spojeny do velkých sítí různých tvarů. Vždy tak že na vstup neuronu je připojen výstup jiného neuronu nebo je tento vstup používán jako jeden ze vstupů do neuronové sítě. Výhodou neuronových sítí je jejich přizpůsobivost a nevýhodou je naopak nutnost použití složitých učících algoritmů.
9
4
GENETICKÝ VÝVOJ SKRIPTŮ UMĚLÉ NTELIGENCE
Genetický vývoj skriptů umělé inteligence je systém, ve kterém se geneticky vyvíjejí skripty, podle kterých se řídí určitý jedinec. Skripty podléhají různým druhům více či méně náhodným mutacím při přenosu z rodiče na potomka a tudíž se vyvíjejí. Ve svém systému jsem se opíral právě o tuto základní myšlenku. Jako příklad toho systému jsem si vybral umělou inteligenci piškvorek, pro lepší pochopení zde uvedu základní principy při tomto problému bez použití genetického vývoje.
4.1
Umělá inteligence piškvorek s použitím skriptů
Piškvory jsou natolik známá hra, že její pravidla snad není třeba připomínat, spíše uvedu jakou konkrétní podobu pravidel budu používat. Hráči hrají na 5 vítězných křížků (koleček) ve sloupci, řadě nebo diagonálách. Hrací plocha má 10x10 políček, což na rozvinutí většiny taktik plně postačuje a zároveň když jsou všechna políčka obsazena a nikdo nevyhrál dojde k remíze dříve a program tím neztrácí drahocenný čas.
Skript v tomto systému prochází hrací plochu políčko po políčku (kromě těch na která už někdo hrál) a bodově je ohodnotí pro útok a pro obranu. Toto ohodnocení se pak spojí do jednoho pomocí skriptu, který ovlivní jestli UI bude útočit nebo bránit. UI nakonec bude hrát na políčko které má nejvyšší výslednou bodovou hodnotu. Jestliže více políček mají stejnou hodnotu, skript se náhodně rozhodne na které políčko bude hrát.
Při hodnocení políček jak pro útok tak pro obranu jsem použil několik funkcí: •
U sebe na aktuální pozici – spočítá kolik piškvorek by vzniklo maximálně vedle sebe pokud by sem UI zahrálo (režim útoku) nebo protivník (režim obrany)
•
Ohraničení řady na aktuální pozici – v řadě stejné jako „U sebe na aktuální pozici“ spočítá její ohraničení protivníkovým křížkem (kolečkem)
•
U sebe s definovaným směrem řady
•
U sebe na pozici X, Y a daným směrem řady
•
Co je na pozici X, Y
10
Příklad:
Políčko, které je hodnoceno je označeno puntíkem •
Křížek – U sebe na aktuální pozici – funkce vrátí 5
•
Křížek – Ohraničení řady na aktuální pozici – funkce vrátí 1
•
Kolečko – U sebe na aktuální pozici – funkce vrátí 3
•
Kolečko – Ohraničení řady na aktuální pozici – funkce vrátí 0
Funkce se také chovají různě pro jiné hráče a jiný hodnocení útoku nebo obrany. Jestliže funkce hodnotí obranu funkce počítají nepřátelské řady a políčka, jestliže útok počítají vlastní.
Pro hodnotící funkci, která rozhodne jestli se bude útočit nebo bránit jsem použil jednoduchý vzorec. Hodnocení = Útok + Obrana kde útok a obrana jsou hodnoty vrácené hodnocením útoku a obrany.
4.2
Genetický vývoj skriptů umělé inteligence piškvorek
Celý systém jsem rozdělil do několika tříd, které prováděly vždy jen jednu určitou úlohu: •
TPlocha – obsahuje hrací plochu a s ní spojené hodnotící funkce, použil jsem relativně malou ale dostačující hrací plochu o rozměrech 10x10 z důvodu rychlosti kódu.
•
TUI – jedinec obsahující vlastní genetický kód schopný hrát na ploše TPlocha
•
TTurnaj – obsahuje pole TUI (generace), hrací plochu TPlocha, statistické funkce a funkci pro výpočet fitness hodnoty a funkci pro rozmnožení generace
Dále jsem použil funkce, které jsem již nezahrnul do třídy. Tyto funkce sloužily na rozmnožení jednoho TUI a prováděly veškeré mutace. Nejdůležitější z nich je: •
MNUI – množí TUI, je to hlavní funkce která volá všechny ostatní funkce a tím zajišťuje veškeré mutace.
11
V hlavní funkci main se pouze vytváří instance třídy TTurnaj, volá se metoda evoluce() této třídy a inicializují se některé další věci.
4.2.1
TPlocha
Tato třída obsahuje hrací plochu, a s ní spojené metody. Uvedu zde pouze hlavičku této třídy, doplněnou dalšími komentáři, které jsou plně postačující na porozumění této třídě: class TPlocha { public: int plocha[maxRozmerPlochyX][maxRozmerPlochyY]; // obsahuje hrací plochu int hracNaTahu; // jaký hráč je právě na tahu
TPlocha(); // konstruktor ~TPlocha(); // destruktor TRada uSebe(int x, int y); // vrátí jak velká a čím je ohraničená nejdelší řada, která prochází tímto políčkem TRada uSebe(int x, int y, int hrac, int smer); // to stejné jak předchozí metoda jen je určen hráč a směr TRada uSebe(int x, int y, int smer); // nerozhoduje hráč, pouze směr inline int naPozici(int x, int y); // vrátí hodnotu na pozici x,y v hrací ploše bool jeMozneHrat(int x, int y); // jestli je možné hrát na pozici x,y v hrací ploše int hrej(int x, int y); // hraje právě hrajícím hráčem na pozici x,y void vymaz(void); // vymaže celou hrací plochu inline bool vPlose (int x, int y); // vrátí false jestli souřadnice x,y mimo hrací plochu };
4.2.2
TUI
Tato třída představuje jednoho jedince, schopného hrát na hrací ploše TPlocha. Obsahuje genetický kód, pravděpodobnosti, které se používají při mutacích, a metody pro táhnutí a uložení se do souboru.
class TUI { public: // Skripty útoku, obrany a vyhodnocení: string gUtok, gObrana, gVyhodnoceni;
12
// pravděpodobnosti mutací, funkcí apod. int pravdepodobnostMutace,pravdClenuRadku,pravdPodminky, pravdFunkce[3][9],pravdClena[3],pravdOperatora[4],pravdPromenne[4], pravdPH[2], pravdRadku[3],pravdZacatku[3],pravdMPOU[3];
int cisloRodice; // udává číslo rodiče v populaci (pro statistické funkce) int vUtok,vObrana; // hodnoty vrácené při hodnocení útoku a obrany int tahni (TPlocha &plocha); // hrej na pozici x,y int spocitej (int x, int y, int co, TPlocha &plocha); // spočítá hodnotu políčka na pozici x,y pro útok, obranu nebo vyhodnocení string ulozSe (void); // vrátí samo sebe ve tvaru řetězce
TUI(void); // konstruktor ~TUI(void); // destruktor };
Syntaxi skriptů vysvětlím v další kapitole. Pravděpodobnosti slouží při mutacích jedince při rozmnožování, to vysvětlím v kapitole s rozmnožováním. Metoda ulož se je využívána při ukládání jedinců do textového souboru pro případné další použití. Metody tahni a spocitej vysvětlím blíže:
int TUI::tahni (TPlocha &plocha); Metoda tahni prochází neobsazená hrací pole a volá metodu spocitej pro útok, obranu a vyhodnocení. V případě, že se ve vyhodnocovací skriptu neobjeví hodnota útoku nebo obrany tak se metoda spocitej pro skript útoku nebo obrany vůbec nevolá. Pak vybere políčko, které dostalo nejvíce bodů a zavolá metodu plochy hrej se souřadnicí tohoto políčka. V případě, že se vyskytnou políčka se stejným ohodnocením, vybere jedno z nich náhodně.
int TUI::spocitej (int x, int y, int co, TPlocha &plocha); Metoda spocitej spočítá bodové hodnocení pro políčko, jehož souřadnice je jí předána v parametru x a y pro útok, obranu nebo vyhodnocení (parametr co) na ploše plocha, podle genetických kódu gObrana, gUtok, nebo gVyhodnoceni. 13
Algoritmus této funkce schématicky vypadá takto: •
udělej kopii kódu
•
vymaž proměnné
•
dokud neprojdeme všechny řádky tak opakuj: -
odpreparuj řádek
-
dosaď proměnné
-
dokud jsou před příkazem podmínky a jestliže jsou splněny vymaž je a
pokračuj, jestliže ne přeskoč na další řádek -
jestliže je to cyklus vrať se zpět na daný řádek
-
jestliže je to příkaz odstraň ulož si proměnnou na začátku a operátor
(=, +=, -=) dosaď hodnotu za všechny funkce, dělení nulou nahraď dělením jedničkou a zavolej metodu TCalculator::solve a vrácenou hodnotu přiřaď, přičti nebo odečti k dané proměnné.
4.2.3
Syntaxe skriptů
Protože skripty se provádějí za běhu programu, mutují a je jich velké množství, prvním předpokladem pro navržení jejich syntaxe byla jednoduchost a co nejmenší délka. Skript není case-sensitive, ale doporučuji používat velká písmena. Také se ve skriptu nesmí vyskytovat žádné prázdné znaky (mezery, znaky Nového řádku apod.). Za návratovou hodnotu skriptu se považuje hodnota v proměnné A po ukončení skriptu. Celý kód je velice jednoduchý a skládá se z několika prvků: •
Příkaz
•
Cyklus
•
Podmínka
Příkaz je nějaký vzorec s proměnnými a funkcemi, jehož hodnota se přiřadí, přičte nebo odečte k proměnné. Má vždy podobu proměnnáOPERÁTORvýraz; Cyklus je typický cyklus s podmínkou na konci. Má tento tvar: podmínkaFřádek; Kde řádek je číslo řádku na který má cyklus skočit, řádky se počítají od nuly. Za řádek se považuje každý příkaz nebo cyklus (počet ; je stejný jako počet řádků).
14
Podmínka je jednoduchá podmínka, která může být vždy jen před jedním příkazem (Neexistuje blok příkazů.). Musí mít tuto syntaxi: IčísloOPERÁTORčíslo) Kde číslo je proměnná, nebo hodnota a operátor je znak = porovnání < je menší nebo > je větší.
Proměnné jsou celkem čtyři – A, B, C, D. V proměnné C je na začátku každého skriptu uložena souřadnice x právě zpracovávaného políčka a v proměnné D souřadnice y.
Funkce mají tvar: Xparam1,param2) X je název funkce, ten může být vždy jen jedno písmeno. param1, param2 jsou parametry funkce. Parametrem může být proměnná nebo celá hodnota. Parametry se oddělují čárkou a ukončují pravou kulatou závorkou, v případě že funkce nemá parametry kulatá závorka se nepíše. Hodnota může být záporná ale jako znaménko záporné hodnoty se nesmí používat – ale _ . Všude jinde ve skriptech se používá znaménko −. H J T S N V W O U
Hx,y) Jx,y) T S Nx,y,h,s) Vx,y) Ws) O U
hodnota na pozici x, y vrací 1 jestliže je možné hrát na pozici x, y jestliže není vrací 0 nejdelší řada křížků (koleček) na aktuální pozici ohraničení nejdelší řady křížků (koleček) na aktuální pozici délka řady na pozici x, y pro hráče h a směru s nejdelší řada na pozici x, y délka řady na aktuální pozici ve směru s bodové hodnocení obrany na aktuálním políčku bodové hodnocení útoku na aktuálním políčku
Hodnota je celočíselná hodnota z rozsahu int. Může být záporná se znaménkem záporu −, jen v argumentu funkce se z důvodu mutací používá _.
Příklady skriptů a jejich přepisy do C++:
a=n_1,a,b,c);ia=5)a=150;
int a=n(-1,a,b,c); if (a==5) a=150; 15
return a;
b+=Oa,a);a+=1;Ia<5)F0;a=b; :navesti; b+=O(a,a); a+=1; if (a<5) goto:navesti; a=b; return a;
a=t;Ia>5)Ia<10)a=100; a=t(); if (a>5) if (a<10) a=100; return a;
4.2.4
TTurnaj
Tato třída zajišťuje proces evoluce, přirozeného výběru a statistického výstupu. Takto vypadá hlavička třídy: class TTurnaj { public: TUI ui[maxPocetUI]; // generace UI int kdyVypadl[maxPocetUI]; // bodové hodnocení UI TPlocha plocha; // hrací plocha void zacniTurnaj (void); // zacne 1 kolo turnaje, bodové hodnocení UI uloží do kdyVypadl[maxPocetUI]; int hrej (int ui1, int ui2,int &cas1, int &cas2); // hraje 1x1 int hrej (int ui1, TUI ui2); // hraje 1xDanému hráči (využívá metoda fitness) void rozmnoz (void); // rozmnoží generaci
16
int fitness (int ui1); // vypočítá fitness piškvorky void evoluce(void); // zajišťuje celý evoluční proces TTurnaj(void); // konstruktor }; Hodnocení UI Nyní vysvětlím jakým způsobem jsou UI hodnoceny a jakým způsobem se vypočítá kolik budou mít potomků. Piškvorky hrají proti sobě turnaj, na začátku se náhodně rozlosuje pořadí kdo s kým bude hrát a pak proti sobě hrají jeden proti jednomu na tři sety. Ten kdo vyhraje postoupí do dalšího kola, které probíhá stejně. Ten kdo vypadne je vyřazen a vypočítá se jeho bodové hodnocení. Používal jsem dva způsoby, jeden upřednostňoval piškvorky, které měly méně náročný skript na hardware počítače a samozřejmě také do jakého kola postoupily a druhý zohledňoval pouze kolo do jakého postoupily. Evoluce v obou systémech probíhala značně odlišně.
Čas na generaci 2000 1800 1600 1400 t [s]
1200
systém 1 systém 2
1000 800 600 400 200 0 1
8
15
22
29
36
43
50
57
64
71
78
85
92
99
generace
Zde je graf, který srovnává dvě (na začátku zcela totožné populace UI), které se během sta generací začaly vyvíjet naprosto jiným směrem. Kdežto u systému, který ignoruje hardwarové nároky (systém 1 v grafu) se do skriptů začaly hromadit často zbytečné funkce a vznikaly tak velice dlouhé skripty, které obsahovaly velké množství funkcí a jen některé z nich byly skriptu užitečné. Ve druhém systému (systém 2 v grafu) měly piškvorky tendenci spíše ke kratším skriptům a užitečnějším a tudíž s nižšími hardwarovými nároky.
17
V tomto evolučním procesu byl poměr mezi „výkonem“ a hardwarovou náročností piškvorek nastaven velice striktně, proto došlo k tomu že v 95. generaci potomci úspěšných jedinců, kteří měli fitness hodnotu okolo 700 překročili hranici, kdy se jim jejich hardwarová náročnost a „výkon“ přestal vyplácet a vymřeli. Tudíž v 96. generaci celá populace prochází hlubokou krizí a to se okamžitě projeví na fitness hodnotě generace, která klesne na 0.
Nejvyšší fitness 1000 900 800
fitness
700 600
systém 1 systém 2
500 400 300 200 100 0 1
7
13 19 25 31 37 43 49 55 61 67 73 79 85 91 97 generace
Jako ideální poměr mezi „výkonem“ a hardwarovou náročností se mi jevil. Bodové hodnocení=kolo*200-čas Kde kolo, vyjadřuje kolo v turnaji do kterého jedinec postoupil a čas počet milisekund, který jedinec potřeboval na odehrání 1 setu v zápase. Takto nastavený evoluční proces vykazoval velice dobré výsledky, jak můžete vidět na následujících grafech:
18
fitness 1000 900 800
fitness
700 600 500 400 300 200 100 0 1
21 41 61 81 101 121 141 161 181 201 221 241 261 281 301 321 341 361 generace
Takto se dá upravit graf fitness hodnoty když se zprůměrňují okolní hodnoty, je na něm lépe vidět průběh vývoje.
Fitness 1000 900 800
fitness
700 600 500 400 300 200 100 0 1
21 41 61 81 101 121 141 161 181 201 221 241 261 281 301 321 341 361 generace
19
Množení UI Každému UI bylo přiřazeno bodové hodnocení. V systému, který zohledňoval hardwarové nároky, se hodnocení vypočítalo: Bodové hodnocení=kolo*200-čas (Viz předchozí podkapitola) Pak se počet potomků vypočítá podle vzorce: Počet potomků = Bodové hodnocení * 128 / celkový součet hodnocení Kde celkový součet hodnocení je suma všech bodových hodnocení v celé generaci. Počet potomků se zaokrouhluje směrem dolů a UI s nejvyšším hodnocením dostane navíc přiřazen počet potomků tak, aby v následující generaci byl počet UI znovu stejný.
V systému, který zohledňoval pouze výsledek v turnaji bylo hodnocení pouze kolo kdy UI vypadlo. Pak se počet potomků vypočítal podle této tabulky: kolo č. 1 2 3 4 5 6 7 8
počet potomků 0 1 2 3 4 5 6 8
Počet potomků byl nastaven tak, že v následující generaci byl stejný počet UI. Samotný proces množení jednoho UI vysvětlím dále.
Výpočet fitness hodnoty UI, které mělo nejvyšší hodnocení pak podstoupilo test fitness hodnoty. Výpočet fitness hodnoty je v této problematice obtížnější, protože neexistuje žádné přesné měřítko, jak je která strategie dobrá, či špatná. Proto je nejvhodnější určit fitness hodnotu jako poměr mezi prohrami a výhrami s nějakou pevně danou UI. V tomto případě to byl skript: Útok: a=T;Ia=5)a=100;a-=S; Obrana: a=T;Ia=5)a=50;a-=S; vyhodnocení
20
a=O+U; T znamená počet křížků (koleček) v řadě na aktuálně hodnocené pozici a S ohraničení této řady (viz Kapitoly Umělá inteligence piškvorek s použitím skriptů a Syntaxe skriptů ). Tato UI odehrála s nejlepší UI z generace 20 zápasů, za každou výhru se nejlepší UI z generace připočítaly dva body, za remízu jeden bod a za prohru žádný. Výsledný fitness se vypočítá takto: Fitness = Body * 1000 / 40
4.2.5
Množení UI
Nyní popíšu princip fungování několika funkcí, které zajišťují samotný proces množení, tedy především nejsložitější věc – mutace. V tomto programu jsem nepoužil metodu křížení kvůli velké obecnosti skriptů. Tudíž jedinec, který by vznikl křížením by měl genetický kód pravděpodobně naprosto nesmyslný. Mutace genetického kódu neprobíhali naprosto náhodně ale řídily se pravděpodobnostmi, které měl každý jedinec zahrnuty ve své genetické výbavě a které mohly také mutovat. Tyto funkce zajišťují veškeré mutace a množení:
Tato funkce obstarává všechny mutace, množení pomocí následujících funkcí: TUI MNUI (TUI UI); // množ UI Tyto funkce obstarávájí mutace na celém „řádku“ tedy kód mezi 2 středníky: bool MNPPrikaz (string &r, int pravdClenuRadku, int *pravdFunkce, int *pravdClena, int *pravdOperatora, int *pravdPromenne, int *pravdPH, int *pravdZacatku); // přidej příkaz bool MNURadek (string &r, int pravdClenuRadku, int *pravdFunkce, int *pravdClena, int *pravdOperatora, int *pravdPromenne, int *pravdPH, int *pravdZacatku); // uprav „řádek“ bool MNSRadek (string &r); // smaž „řádek“ A toto jsou pomocné funkce pro operaci s příkazem: bool MNUZacatek (string &r, int *pravdZacatku); // uprav začátek „řádku“ tedy // proměnnou operátor = += nebo -= bool MNSClena (string &r) // smaž člena řádku (proměnná, hodnota, funkce) bool MNPFunkci (string &r, int *pravdFunkce, int *pravdOperatora, int *pravdPromenne,
21
int *pravdPH); // přidej funkci bool MNPHodnotu (string &r, int *pravdOperatora); // přidej hodnotu bool MNPPromennou (string &r, int *pravdPromenne, int *pravdOperatora); // přidej // proměnnou bool MNUPromennou (string &r, int *pravdPromenne); // uprav proměnnou bool MNUOperator (string &r, int *pravdOperatora); // uprav +-* Tyto funkce slouží na mutace cyklu: bool MNPCyklus (string &r, int *pravdPromenne, int *pravdPH); // přidej cyklus bool MNUCyklus (string &r); // uprav cyklus/ bool MNSCyklus (string &r); // smaž cyklus Tyto funkce obstarávají mutace podmínky: bool MNPPodminku (string &r, int *pravdPromenne, int *pravdPH); // přidej podmínku bool MNUPodminku (string &r, int *pravdPromenne, int *pravdPH); // uprav podmínku bool MNSPodminku (string &r); // smaž podmínku A následující funkce obstarává změny pravděpodobností, kterými se všechny ostatní funkce řídí: bool MNUPravdepodobnost(TUI &UI); // uprav pravděpodobnosti
Mutace jsou principiálně velice jednoduché, ale na implementaci značně dlouhé. Celý program má celkově 2 900 řádků z čehož 1 400 řádků kódu zabírají funkce pro mutace a množení.
5 PRŮBĚH EVOLUCE, NAMĚŘENÉ HODNOTY Udělal jsem několik různých měření, s rozdílnými počátečními parametry pravděpodobností i genetických skriptů a rozdílnými systémy, také jsem udělal několik pokusů se záměrně udělanou chybou v systému, jestli se piškvorky přizpůsobí a chyby využijí. Opravdu se tak stalo a piškvorky dokázaly ve většině případů chyby zneužít ke většímu počtu potomků v další generaci. Velikost populace byla z hardwarových důvodů jen 128 jedinců ve větších generacích by nejspíše nedocházelo tak velkým výkyvům hodnoty fitness. Všechny evoluce byly počítány na počítači s procesorem AMD Athlon 64 3500+.
Evoluce s dobrým počátečním skriptem, se zohledňováním hardwarových nároků UI měly na začátku nastaveny skript. 22
Útok – A=T*T;
Čas na generaci
Obrana – A=T*T; Vyhodnocení
600
–
500
A=O*U+O+U; T
–
400
délka řady
nejdelší
t [s]
(Funkce
300
křížků/koleček)
200
Tento skript má fitness
100
hodnotu okolo 550 a je účinný,
přestože
0
je
1
13
25
37
49
61
73
85
97 109 121 133 145 157 169 181
generace
velice jednoduchý. Útok i obrana upřednostňuje
Fitness
daleko více delší řady křížků/koleček
než
1000 900
kratší a to s druhou
pak
daleko
více
zvýhodňuje ty políčka,
fitness
mocninou. Vyhodnocení
která jsou výhodná jak pro útok tak pro obranu.
800 700 600 500 400 300 200 100 0 1
13 25 37 49 61 73
Za 191 generací vývoje vypadal
85 97 109 121 133 145 157 169 181 generace
skript
nejlepšího jedince takto: Útok – B=JB,C)*VD,A)/A;A=B+T*T; Obrana – D=8+T+VA,D)+T/8;B=VA,B)-B;A=C+A;IC=A)IA=C)IC=A)A=T/U*T; Vyhodnocení – B=O-U+B*18-A;ID=D)A=U+O+U*A; Pro zpřehlednění se dá skript upravit jako: Útok – A= J0,X)*VY,0)+T*T; Obrana – A=T*T; Vyhodnocení – A=U+O;
23
Tedy vidíte, že nedošlo k žádné větší taktické obměně skriptu, jakákoliv větší změna totiž pro piškvorky znamenala ztrátu a tudíž méně potomků a vyhynutí.
Evoluce s žádným počátečním skriptem, bez zohledňování hardwarových nároků V této evoluci, piškvorky neměly přiděleny žádný počáteční skript, v první generaci tudíž hrály naprosto náhodně. Systém také nezohledňoval hardwarové nároky a proto se čas na generaci k závěru nepřiměřeně protáhl. Tudíž jsem z časových důvodů musel po 100 generacích evoluci zastavit. Fitness 1000 900 800
fitness
700 600 500 400 300 200 100 0 1
7
13 19
25 31 37
43 49
55 61 67
73 79 85
91 97
generace
Čas na generaci 2000 1800 1600 1400 t [s]
1200 1000 800 600 400 200 0 1
8
15
22
29
36
43
50
57
generace
24
64
71
78
85
92
99
Skript piškvorek se za 100 generací vyvinul takto: Útok – D=T;A+=A*NC,A,A,B);IB=C)A-=WC)+C+S;A+=S;B=C; Obrana – B=JA,D);IB=C)A+=A;A+=A-T;A+=JA,B); Vyhodnocení
–
D-=O*4*U;A-=U;IA
=O/D;B=B*U+O; Pro zpřehlednění ze skriptu odstraním přebytečné věci: Útok – A-=W0)+S;A+=S; Obrana – B=J0,0);IB=C)A+=A;A+=A-T;A+=JA,B); Vyhodnocení – D-=O*4*U;A-=U;A-=O/D; Tento skript tedy přílišnou taktikou neoplývá a jeho úspěch je založen především n funkci S v útoku a následným odečtením hodnoty útoku ve vyhodnocení. 100 generací je na vývoj lepší strategie příliš málo.
Evoluce bez počátečního skriptu, se zohledňováním hardwarových nároků Také v této evoluci neměli piškvorky žádný počáteční skript. Systém zohledňoval hardwarové nároky a to s výpočtem hodnocením. Hodnocení = Kolo*200-čas (podrobnosti viz Kapitola Turnaj)
Fitness 1000 900
600 500 400 300 200 100
generace
25
401 421 441 461 481 501
241 261 281 301 321 341 361 381
101 121 141 161 181 201 221
0 1 21 41 61 81
fitness
800 700
Čas na generaci 400 350 300
t [s]
250 200 150 100 50 461 481 501
361 381 401 421 441
261 281 301 321 341
181 201 221 241
81 101 121 141 161
1 21 41 61
0
generace
Takto vypadá upravený graf fitness hodnoty, když zprůměrujeme 5 sousedních hodnot, je na něm lépe vidět trend fitness hodnoty:
1000 900 800 700 600 500 400 300 200 100
generace
26
401 421 441 461 481 501
241 261 281 301 321 341 361 381
101 121 141 161 181 201 221
0 1 21 41 61 81
fitness
Fitness
Evoluce s chybou – extrémně velký čas potřebný na dokončení skriptu vede k velkému množství potomků
V tomto evolučním procesu jsem nechal záměrnou chybu. Jestliže UI měla extrémně náročný skript tak měla velké množství potomků. O něco méně náročnější skripty však vedly naopak ke zmenšení počtu potomků. UI toho rychle zneužila a již v 19 generaci se vyskytl jedinec, který tuto hranici překonal a v další generaci měl potomků nejvíce. Velice dobře je tento průlom vidět a následujícím grafu. Čas na generaci 9000 8000 7000 fitness
6000 5000 4000 3000 2000 1000 0 1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 generace
Fitness hodnota v této evoluci není zajímavá a pohybovala se okolo 400.
6 Zobecnění systému genetického vývoje umělé inteligence Obecně se tento princip dá použít kdekoliv, kde lze použít skripty a vyskytují se řádově stovky umělých inteligencí, kteří spolu nějakým způsobem soupeří. Nejčastější využité by mohl systém najít v počítačových hrách. Stačí udělat více obslužných funkcí, které skriptu slouží jako vstupní údaje a použít princip tohoto algoritmu, jak jsem ho popsal v případě piškvorek. Hierarchie částí tohoto algoritmu je názorně zobrazena na tomto diagramu:
27
Evoluce Reprodukční funkce Velké množství UI Skripty Runtime překladač skriptů Pravděpodobnosti skriptů Prostředí Prostředí Obslužné funkce Statistické funkce
7 Závěr Od evolučního procesu v systému genetického vývoje skriptů umělé inteligence jsem očekával nalezení nových taktik. To se také v menší míře stalo. Avšak kvůli nízké složitosti řešeného problému, kde existuje menší množství taktik, se v generacích nevyskytly opravdu vyspělé taktiky, které by více využívaly podmínek, cyklů a složitějších funkcí. Také k nim evoluce nedospěla z časových důvodů - Evoluce probíhaly jen několik stovek generací a vždy s relativně malým počtem jedinců - 128. Aby evoluce dospěla ke složitým taktikám, bylo by potřeba několika tisíců generací a řádově stovky jedinců v populaci. Genetický vývoj skriptů umělé inteligence se tak hodí spíše pro složitější problémy, kde existuje velké množství taktik. Také by se dal systém lehce rozšířit tak, aby se do výpočtu procesu evoluce zapojilo více počítačů zároveň a tím se proces několikanásobně zrychlil. Prakticky by se systém mohl využít především v počítačových hrách, kde se vyskytuje velké množství jedinců řízených umělou inteligencí, například v RPG hrách.
28
8 Použitá literatura PETR LUNER. Jemný úvod do genetických algoritmů. Dostupný z: http://cgg.ms.mff.cuni.cz/~pepca/prg022/luner.html
MAREK OBITKO. Genetic algorithms Dostupný z: http://cs.felk.cvut.cz/~xobitko/ga/
JIŘÍ ŠÍMA, ROMAN NERUDA. Teoretické otázky neuronových sítí. Dostupný z: http://www.cs.cas.cz/~sima/kniha.pdf
Umělá inteligence. Wikipedie. [cit. 2007-01-13] Dostupný z: http://cs.wikipedia.org/wiki/Um%C4%9Bl%C3%A1_inteligence
V ukázkovém programu také používám volně šiřitelnou knihovnu C++ expression calculator od Simona Gomizeljiho dostupnou z: http://www.Planet-Source-Code.com/vb/scripts/ShowCode.asp?txtCodeId=8146&lngWId=3
29
