SnakeEvolution

Simulácia evolúcie neurónovej siete, ktorej cieľom je naučiť sa hrať klasickú hru Snake.

Autor: Michal Štefaňák

Popis

Pôvodná hra Snake vznikla už v roku 1976. Zaujímavé je že pôvodná verzia bola pre dvoch hráčov. Jednoduchosť a chytľavý koncept túto hru spopularizovali až sa jej najpopulárnejšia varianta dostala v roku 1998 na mobilné telefóny Nokia. Túto verziu už väčšina ľudí dobre pozná. Na malej statickej, väčšinou štvorcovej obrazovke hráč ovláda hada, s ktorým zbiera jedlo po, ktoré sa náhodne objavuje na mape. Zjedením jedla had rastie a zaberá väčšiu časť mapy. S každým získaným jedlom hráč dostane bod, had narastie a hra je ťažšia, pretože hráč s hadom nemôže naraziť do do svojeho chvostu, alebo do steny a miesta je stále menej a menej. To si vyžaduje chvíľu praxe a určitú známku stratégie ako hru hrať. Bežný hráč sa takéto jednoduché pravidlá rýchlo naučí a dosiahne celkom zaujímavý výsledok. No čo keby sme to chceli naučiť len pár neurónov? Dokáže sa pár neurónov naučiť zbierať body v tejto klasickej hre, alebo je na to potrebné človeka? To sa dozvieme v tejto práci.

Definícia problému

Aby sme pár neurónov (ďalej už neurálnu sieť) naučili hrať hru Snake, môžeme použiť množstvo metód ako napríklad posilované učenie, alebo evolučný algoritmus. Práve evolučný algoritmus som sa rozhodol použiť, pretože cieľom práce je niečo simulovať a simulovať evolúciu znie dobre. No evolučný algoritmus je potrebné správne nastaviť. Obsahuje veľké množstvo parametrov, ktorých nastavovaním sa dá evolúcia posúvať správnym smerom a meniť rýchlosť tohoto posúvania.

Cieľ

Práca má dva ciele, jeden ofociálny a jeden neoficiálny.

- Oficiálny cieľ práce je zistiť najvhodnejšie nastavenie parametrov evolučného algoritmu, aby sme urýchlili učenie neurónovej siete.

- Neoficiálny cieľ práce - môj súkromný cieľ je vycvičiť agenta, ktorý stabilne dosiahne aspoň skóre 10 a nebude to vyzerať ako náhodné zbieranie bodov.

Metóda

Ako už bolo spomínané, práca bude využívať evolučný algoritmus, aby simulovala evolúciu neurínovej siete. Pre tento účel budem používať programovací jazyk Python. Ten ponúka množstvo knižníc, ktoré k tomu môžem využiť. Pre prácu s maticami váh neurónovej siete knižnicu Numpy. Pre interpretovanie výsledkov a vykresľovanie grafov knižnicu Matplotlib. A v neposlednom rade pre (nie tak dôležité, ale pre mňa veľmi dôležité) zobrazenie hry knižnicu Tkinter.

Model

Agenti

Každý agent pozostáva z neurónovej siete. Agent "vidí" do ômych smerov (hore, dole, vľavo, vpravo, vpravo-hore, vpravo-dole, vľavo-dole, vľavo-hore) od hlavy hada. Pre každý smer vidí vzdialenosť k stene, vzdialenosť k jablku (ak ho v daný smer vidí) a vzdialenosť ku svojemu chvostu (ak ho v daný smer vidí). Čiže na vstupnej vrstve má 24 neurónov (8 smerov x 3 indikátory) + 4 neuróny predstavujúce smer do ktorého ide hlava hada. Celkovo 28 neurónov. Počet skrytých vrstiev a neurónov v nich je pre zjednodušenie problému pevne daný - skryté vrstvy sú dve a obsahujú 20 a 12 neurónov. Váhy väzieb medzi neurónami sú z počiatku náhodné z uniformného rozdelenia, následne sú menené mutáciami agentov. Na výstupe neurónovej siete je smer akým sa má had ďalej uberať, čiže 4 neuróny pre Hore, Dole, Vľavo, Vpravo.

Prostredie

Prostredím v ktorom agenti pôsobia je obyčajná hra snake ako aj evolúcia v ktorej sa nachádzajú. Pre simuláciu evolúcie je potrebné simulovať viacero generácií E a v každej generácii je populácia agentov o veľkosti N. Každý agent hrá samostatnú inštanciu hry Snake g krát (g je viac ako 1, pretože agenti môžu mať niekedy "smolu" a skončiť rýchlo - tým by sme zabili potencionálne úspešných jedincov, alebo "šťastie" - tým by sme odmeňovali jedincov, ktorý si to nezaslúžia). Výsledky g hier sa pre každého agenta spriemerujú.

Po odohraní hier agentov v danej generácii sa vypočíta fitness (skóre) najlepšieho agenta. Fitness sa počíta ako funkcia počtu dosiahnutých bodov a počtu krokov, ktoré agent urobil. Konkrétna funkcia vyzerá nasledovne:

kde steps je počet krokov, ktoré agent vykonal a points sú body, ktoré získal. Táto funkcia sa po mnohých pokusoch ukázala byť najefektívnejšia. Cieľom tejto fitness funkcie je zo začiatku odmeňovať agentov, ktorý prežijú čo najdlhšie, čiže urobia viacej krokov, no neskôr odmeňovať zbieranie bodov. Viac krokov (steps) má pozitívny príspevok k fitness, ale pri vysokom počte krokov a nízkom počte bodov môže byť tento prínos znížený kombinovaným efektom. Viac bodov (points) výrazne zvyšuje fitness kvôli silným pozitívnym príspevkom exponentiálnych a polynomických výrazov. Kombinovaný efekt môže výrazne znižovať fitness, ak je počet krokov vysoký a počet bodov relatívne nízky, avšak pri vysokom počte bodov je tento efekt menej výrazný.

Podľa fitness sa vyberú jedinci pre ďalšiu generáciu (podľa miery elitizmu e). Teda sa vyberie N * e najlepších jedincov pre ďalšiu populáciu.

Ďalej sa generácia doplní novo vytvorenými agentami (potomkami), ktorí vzniknú krížením dvoch náhodne vybratých agentov. Tento výber funguje na ruletovom výbere. Sčítajú sa všetky hodnoty fitness a vygeneruje sa náhodné číslo od 0 po sum(fitness). Jedincom sa podľa ich fitness priradí úsek od 0 po sum(fitness) a podľa náhodného čísla vygenerovaného predtým sa vyberie zodpovedajúci jedinec podľa toho ktorému úseku toto číslo náleži. Pre tento výber by išlo použit napríklad náhodný výber, ale to by neodmieňalo lepších agentov. Ďalej by sa mohol použiť turnajový výber, kde sa vyberie istý počet náhodných agentov z celej populácie, podľa veľkosti turnaja a z nich sa vyberie najlepší. No to by predstavovalo nový parameter evolučného algoritmu, čiže veľkosť turnaja a pri nesprávnom nastavení by mohlo spôsobovať difúziu alebo konfúziu.

Kríženie jedincov funguje nasledovne: dvom rodičom sa postupne prechádzajú jednotlivé váhy na neurónoch a náhodne sa vyberá váha jedného alebo druhého rodiča, ktorá sa použije pre potomka.

Potomkovia sú ešte zmutovaný podľa miery mutácie m. Mutácia funguje tak, že kaźdá váha na jednotlivých vrstvách má pravdepodobnosť m že zmutuje - pričíta sa k nej hodnota z normálneho náhodného rozdelenia.

Kód

Kód je dostupný v tomto repozitári.