|
Autor: Pečiva
Jan download
(zdrojové soubory, tato Obsah: |
 |
Podle mého osobního názoru jsou genetické techniky hlavní cestou, jak vytvořit inteligentní počítačové protivníky pro dnešní hry. Proto jsem se touto cestou vydal i já. Do své aplikace pro virtualní realitu jsem přidal dvě rakety představující dva protivníky. Vtělil jsem jim základní rysy chování, které bylo závislé na určitých "konstantách", které se v teorii genetiky nazývají geny. Po té jsem vždy zhodnotil "životaschopnost" jednotlivých jedinců a křížením těch nejlepších jsem získával vždy novou populaci.
Hlavní cíl programu je vypěstovat inteligentní rakety schopné útočit proti sobě, popřípadě i po hráči představovaném člověkem. Rakety se pohybují v aréně, která určitým způsobem omezuje jejich pohyb. Ty rakety pátrají po druhých raketách. Jakmile nějakou zahlídnou, letí za ní a snaží se jí sestřelit. Pokud se jí to povede, získává frag. Při dosažení určitého skóre se simulace zastaví a do další populace se pokříží ti s největším skóre a také jsou přidáni jedinci z předchozí populace, aby se částečně zabránilo degeneraci celé populace. Průběh celého genetického vývoje je zapisován do souboru genetic.txt. Tam je také nejvhodnější hledat výsledky.
Program je založený na grafické knihovně Open Inventor, nástroji pro vývoj interaktivních 3D aplikací. Já jsem použil ne originální Open Inventor od SGI, ale knihovnu od Systems In Motion, Coin3D pro některé její přednosti. Pro běh programu je potřebné OpenGL pro renderování grafiky, alespoň jeho softwarová verze, což splňují téměř všechny počítače. Požadavky na výkon jsou ale značné. Nedoporučuju nic pod Celerony a Pentia II.
Program má několik režimů, které se řídí parametry příkazového řádku:
Především chci upozornit, že na počítačích bez hardwarové akcelerace OpenGL je vhodné přidat na příkazový řádek parametr -noaccel, který vypne omezí množství zobrazované grafiky na minimum.
Pro kompilaci projektu je potřeba Microsoft Visual Studio verze 6, knihovna Coin3D verze 1 a knihovna GLUT, verze alespoň 3.6. Coin3D je velmi rozsáhlý balík, a proto jsem k projektu přidal i zkompilovaný soubor, abych ulehčil práci s instalací tohoto 40MB balíku. Pro případný další vývoj se knihovna Coin3D dá stáhnout volně z www.coin3d.org a knihovna GLUT z xxxxxxxxx. Po jejich instalaci je potřeba správně nastavit cesty ve Visual Studiu. Kompilace na Linuxu by po vytvoření odpovídajícího makefile měla být taky možná.
Pro spuštění genetického vývoje je potřeba počítat s hodinami vývoje. 30 populací trvá orientačně 4 hodiny při čtyřech jedincích v populaci na Pentiu II 400MHz. Aplikace v tomto režimu zobrazuje každý stý snímek, čas simulace tedy plyne 100krát rychleji. Zobrazované snímky spíše pouze informují o tom, že program pracuje, hodnotná je informace pouze o čísle populace popřípadě i informace o aktuálním skóre. Program ukončíme stiskem klávesy ESC.
Parametry příkazového řádku: <žádné>
Genetický vývoj bez časové komprese má pouze demonstrační význam. Je možno sledovat, jak program pracuje. Čas simulace se oproti režimu s časovou kompresí prodlouží 100krát.
Parametry příkazového řádku: -lowspeed
Po vypěstování určité populace si můžeme chtít otestovat, oč je jedinec z poslední populace lepší než nějaký jedinec z první populace. Právě k tomu slouží tento mód. Na příkazovém řádku zadáme parametry dvou jedinců, a pak můžeme na obrazovce sledovat jejich souboj.
Parametry příkazového řádku: -lowspeed -single <parametr1 jedince1> <par2 jed1> <par3 jed1> <par1 jed2> <par2 jed2> <par3 jed2>
Tento mód ukazuje možnosti knihovny Open Inventor. Nejsou zde ani nepřátelské rakety, ani možnosti genetického vývoje.
Parametry příkazového řádku: -nogenetic -lowspeed
| -single <params> | S parametrem se zadávají parametry dvou jedinců, které chceme vidět ve vlastním souboji. |
| -lowspeed | Parametr mění rychlost simulace. Pokud není uveden, beží čas 100krát rychleji. |
| -noaccel | Parametr omezuje množství zobrazované grafiky na minimum. Umožňuje tak plynulý běh programu i na počítačích bez hardwarově akcelerované grafiky. |
| -user | Parametr umožní uživateli pohybovat se nezávisle na obou bojujících raketách. Pohyb uživatele se pak ovládá pomocí myši a kláves w,a,s,d,e,z. |
| -nogenetic | Ukazuje program v původní podobě bez implementované umělé inteligence. |
Inteligence raket vychází ze snahy napodobit chování realného hráče. Proto má raketa dva stavy: hledání nepřítele a chování při útoku. Pokud raketa hledá nepřítele, používá jednak radar, který je všesměrový, ale má krátký dosah, a dále používá pohled z kabiny, který je pouze dopředu a jehož dosah je značný a s dobou pohledu jedním směrem se prodlužuje. Raketa mění směr s určitou frekvencí, která je dána konstantou, která je každé raketě vlastní. Tato hodnota je vlastně gen, který má vliv na úspěšnost rakety. Optimální hodnota této proměnné se nedá spočítat a s obtíží se dá odhadnout, proto je lepší její hodnotu naleznout geneticky. Další takovou vlastností je rychlost pohybu rakety, při nižší rychlosti má raketa větší manévrovací schopnosti, kdežto z vyšší rychlosti zase může těžit jiným způsobem. Při nalezení protivníka se chování rakety radikélně mění. Raketa směřuje ke druhé raketě, a protože může vystřelit pouze jednou za určitou dobu a navíc při výstřelu ji druhá raketa s určitou pravděpodobností také zahlédne, měla by střílet pouze za určitých podmínek, kdy má velikou pravděpodobnost, že se trefí. Je použit pouze velmi zjednodušený přístup, kdy se začíná střílet až ve chvíli, kdy je raketa dostatečně blízko. Tato vzdálenost je dána třetím genem.
Mnou implementované algoritmy mají množství nedostatků ve svém chování a pro realné využití by bylo potřeba na nich ještě zhruba měsíc pracovat. Nicméně chyby se týkají pevně implementovaných algoritmů chování raket, nikoliv vlastního genetického algoritmu, proto se domnívám, že pro tohoto problému to postačí.
Při startu programu je vygenerována náhodná populace, to znamená geny jsou nastaveny náhodně v rozmezí nějakých hodnot. Při třech genech na jedince by bylo vhodné zvolit počet členů populace mezi třemi až šesti. A protože do další populace vždy postupuje i polovina nejlepších jedinců z předchozí populace, bylo by vhodné počet jedinců ještě zvětšit. Nicméně kvůli výkonostním problémům bylo nutné zvolit pouze čtyři členy.
Hodnocení populace probíhá tak, že vždy dva jedinci se utkají ve vzájemném souboji a hraje se na pět fragů, tedy zásahů soupeře. Při čtyřech jedincích na populaci je to šest soubojů. Simulace každého souboje, přesto že je 100krát zrychlená, trvá od zlomků sekundy po často až k jedné minutě pro některé specifické kombinace jedinců. Po vzájemných soubojích se hodnotí skóre všech jedinců v populaci. Vezme se polovina populace vybraná z těch nejlepších jedinců a ta postupuje do dalšího kola. Navíc se tito jedinci pokříží tak, aby doplnili populaci do celkového počtu čtyřech jedinců. Křížení probíhá tak, že se vezmou hodnoty daného genu od obou jedinců, tato hodnota je vlastně float-point číslem, a náhodně se vybere se hodnota z okolí hodnoty prvního jedince, druhého jedince, nebo kombinace obou. To se provede pro všechny geny. Po té, co máme novou populaci vytvořenou, můžeme začít s novou simulací.
Simulace běžela 4 hodiny na 400MHz Pentiu II. Bylo vypěstováno 38 populací a poslední populace byla podrobena testování, aby se zjistil přínos genetického vývoje. Byl vybrán jeden prvek a otestován v souboji s prvkem z první populace. Zjistilo se, že daný prvek je opravdu úspěšnější. Při větší testovací množině se ukázalo, že toto není pravidlem. Jako jeden z důvodů bych uvedl malé množství jedinců v populaci, které by podle mě mělo být dvojnásobné, čož by zhruba zčtyřnásobilo dobu výpočtu. Pro problídnutí výsledků jedné z mých simulací jsem do projektu přidal i soubor bin/genetic100.txt.
Mezi nedostatky projektu by se dalo uvést, že hodnoty některých genů rostou vpodstatě do nekonečna a zdá se, že čím je větší, tím je jeho jedinec úspěšnější. Toto nejsou chyby genetických algoritmů, ale nedostatečně propracovaných algoritmů použitých při tvorbě vlastní inteligence raket. Ač jsem během tohoto projektu nedosáhl výsledků použitelných v praxi, přesto se domnívám, že je to správná cesta, která však vyžaduje značné množství programátorské práce.
|
|
|
|
 Sledovaná nepřátelská loď změnila směr. |
 Byli jsme zahlédnuti nepřátelskou lodí. Kdo se trefí dříve? |
