Experiment se zpětnovazebním učením neuronových sítí křížených genetickými algoritmy.
Zadáním projektu do předmětu SFC bylo vytvořit program, který by aplikoval metody softcomputingu. Zvolil jsem si hru Piškvorky. Na následujících řádcích podrobněji popíšu princip hry, analýzu, návrh a implementaci.
Hlavním cílem projektu bylo pokusit se řešit úlohu hráče pomocí neuronové sítě.
Jeden čtverec pole budeme dále nazývat "buňka".
Hra samotná bude probíhat podle výše uvedených pravidel. Naším cílem je vytrénovat co nejlepší umělou inteligenci, abychom ji mohli nasadit do soutěže Piškvorkiáda 2007. Za tím účelem použijeme:
Cílovým údajem, který chceme v každém kole získat, je, do které buňky umístit hráčův symbol. Ten získáme takto: Na výstupní vrstvě neuronové sítě je pro jednu buňku pole jeden výstupní neuron a jeho výstup znamená ohodnocení vhodnosti umístění symbolu do příslušné buňky. Symbol umístíme na buňku příslušející neuronu s nejvyšším výstupem.
Vzhledem k teoreticky nekonečné velikosti hracího pole není možné aplikovat neuronovou síť na pole jako celek.
Je nutné použít vícekrát síť určité velikosti a její výsledky vhodně normalizovat a kombinovat.
Velikost sítě musí být samozřejmě minimálně taková, aby pokryla jakoukoliv N-tici sousedících symbolů.
Je však lepší použít větší, neboť potenciální pětice symolů je zasazena do určitého kontextu (okolí).
Je určitě vhodné zvolit čtverec, protože hra je rozměrově symetrická.
Volím tedy čtverec o velikosti 7 × 7.
Na vstupu sítě bude prázdná buňka reprezentována nulou, buňka se symbolem přiřazeným hodnotícímu hráči hodnotou 1.0, a buňka s protihráčovým symbolem hodnotou -1.0.
Výstup jednotlivých neuronů má význam hodnocení vhodnosti umístění symbolu na příslušnou buňku v kontextu aktuálně zkoumané oblasti. Čím vyšší číslo, tím je buňka vhodnější.
Pomocí sítě budeme hodnotit buňky ve všech čtvercích zvolené velikosti existujích v poli. Pořadí je irelevantní, nicméně budeme postupovat od levého horního rohu "po řádkách" a "po sloupcích" do pravého dolního rohu. Pro každou buňku si budeme pamatovat všechna její hodnocení a experimentálně vyzkoušíme používat jejich různé přepočtené hodnoty.
Učení neuronové sítě pomocí reinforcement learningu by bylo velice dlouhé a neefektivní. Proto použijeme svoje praktické znalosti hraní této hry nabyté během přednášek méně zajímavých předmětů (mezi které SFC jistě nepatří :-) a naučíme síť pomocí sady vzorových situací na herním poli (viz třída {@link cz.dynawest.piskvorky.TrainSetGenerator}). Poté budeme síť učit pomocí reinforcement learningu na hrách dvou neuronových sítí proti sobě.
Takto naučených sítí vytvoříme více. Jedna síť bude jedincem. Každou dvojici jedinců necháme proti sobě soutěžit sudý počet her, dokud jeden z nich nepovede o více než dva body. Populaci sítí seřadíme podle dosaženého skóre a rozdělíme na tři části. Jedince v části s nejnižšími skóre vyřadíme ze soutěže. Jedince ve střední a části ponecháme v soutěži. Jedince v části s nejvyššími skóre ponecháme v soutěži a jejich křížením doplníme populaci o počet jedinců v první části.
U hry piškvorky je možno použít reinforcement learning. Problematické ovšem zůstává rozhodnutí, jak ho aplikovat. Běžný způsob (Q-learning) předpokládá, že výstupy sítě získaný v kolech bližších k získání odměny má větší vliv na výsledek. V piškvorkách ovšem klíčovým momentem není vítězství, ale moment získání převahy. A určení tahu, kdy byla jedním z hráčů získána převaha, je silně intuitivní.
Proto je vhodné RL použít, ovšem jako okrajovou záležitost, hrající spíše roli "řízené mutace" pro genetické algoritmy.
Na konci každého půlkola hry se uloží, jaký tah hráč zvolil (kam umístil symbol). Na základě toho se dá kompletně zrekonstruovat průběh hry. Během procedury Q-learningu máme již k dispozici informaci o celkovém počtu tahů. Spustíme tedy rekonstrukci hry na hracím poli a určitý počet kol před koncem začneme s učením pomocí posilování: Neuronové síti dame aktuální stav na vstup, provedeme výpočet a odečteme výstup. Z logu zjistíme, která buňka byla vybrána, a příslušnému výstupu nastavíme chybu podle výsledku hry: Pokud upravujeme vítěze, výstupu přiřadíme kladnou odchylku (chceme posílit výběr této buňky). Pokud upravujeme poraženého, výstupu přiřadíme odchylku zápornou (chceme oslabit výběr této buňky).
Jelikož je celá plocha hodnocena postupně se posunujícím oknem a neuronová síť pracuje na vzniklých úsecích, při učení posilováním budeme síti předkládat pouze ty úseky, ve kterých se vybraná buňka nachází.
Pokud tedy budeme používat okno 7 × 7 a pro RL použijeme deset posledních tahů, bude provedeno celkem 7 × 7 × 10 = 490 cyklů.
Analýza, návrh a implementace neuronových sítí jsou popsány v {@link cz.dynawest.ai dokumentaci balíčku AI}.
Analýza, návrh a implementace genetických algoritmů jsou popsány v {@link cz.dynawest.ai.ga dokumentaci balíčku AI.GA}.
Hrací pole je implementováno jako dvourozměrné pole. Za účelem dosažení "nekonečnosti" je indexované takto:
(Více viz třída {@link piskvorky.InterlacedPlayground}).
Dále jsou implementovány algoritmy hledání hranic pole a hledání pětic (Více viz metoda {@link piskvorky.InterlacedPlayground.FindLinesOfSymbols}).
Poslední verzi aplikace je možno stáhnout zde.
