Minulý rok na konci srpna se během konference, která nesla název European Conference on Artificial Intelligence, a která proběhla v Praze, odehrála soutěž s názvem Angry Birds AI Competition (aibirds.org).
Cílem účastníků soutěže bylo vytvořit takovou umělou inteligenci, která by byla schopna hrát populární hru Angry Birds, a která by v nejlepším případě byla schopna dosáhnout lepšího celkového skóre ve vybraných kolech, než lidský hráč.
Angry Birds je počítačová hra postavená na simulaci interakce objektů, které podléhají fyzikálním zákonům. Cílem hráče je zničit všechna prasátka, která jsou rozmístěna v hrací ploše, často ve složitých konstrukcích, jež jsou tvořeny různě velkými dřevěnými, kamennými a ledovými bloky. Toho lze docílit vymršťováním omezené zásoby rozzuřených opeřenců z praku. Organizátoři poskytli účastníkům soutěže software, skrze jehož rozhraní bylo možné hru ovládat a provádět základní rozpoznání stavu herního světa. Software byl schopný dodat informace o pozici, rotaci a typu herního objektu, a přijmout pokyn k odpálení opeřence tak, aby proletěl daným bodem.
Náš tříčlenný tým, ve složení Tomáš Borovička, lídr týmu a vedoucí laboratoře datových věd na Fakultě informačních technologií, Karel Rymeš a Radim Špetlík, v té době oba studenti prvního ročníku bakalářského studia, začal na umělé inteligenci pracovat na začátku června.
Začali jsme rešerší. Ta vyřadila hned několik přístupů, o kterých jsme původně uvažovali. Jako neefektivní se například ukázalo snažit se odhadnout výsledek interakce objektů herního světa provedením vlastní fyzikální simulace. Tento přístup neměl šanci na úspěch ze dvou důvodů. Za prvé kvůli tomu, že data o pozicích a rotacích herních objektů získaná skrze rozhraní softwaru dodaného organizátory nebyla přesná. Díky tomu nebyly přesné ani výstupy simulace. Druhým důvodem bylo to, že umělá inteligence měla časový limit, během něhož musela dané kolo odehrát, a doba potřebná k provedení potřebného počtu zmíněných simulací byla příliš vysoká. Z rešerše též vyplynulo, že vzhledem k nízkému počtu trénovacích kol, nemá smysl pokoušet se postavit jádro naší umělé inteligence na strojovém učení. Organizátoři totiž pro účely soutěže každý rok připravují zcela nová herní prostředí, která se v běžně dostupných variantách hry nevyskytují. Nedávalo tedy smysl snažit se strojově naučit našeho agenta na takto omezené množině nám dostupných herních kol.
Začali jsme tedy přemýšlet, na čem postavíme jádro naší umělé inteligence. Shodli jsme se na tom, že bude nejlépe, pokud se bude co nejvíce podobat inteligenci skutečné, tedy pokud její herní styl bude, pokud možno, co nejvíce připomínat způsob, jakým hraje člověk. Zjistili jsme, že člověk řeší herní situace v Angry Birds jejich abstrakcí a převedením dosud neviděného případu na takový, s nímž se již setkal a jehož abstraktní řešení si uchoval v paměti. Tyto obecné vzory řešení herních situací jsme označili jako meta-strategie. Příkladem takového zobecnění může být meta-strategie „shoď na prasátko nejbližší konstrukci“. Konstrukce se mohou lišit způsobem, jakým jsou sestaveny, stejně tak se může lišit vzájemná pozice prasátka a konstrukce, ale z hlediska meta-strategie jde o herní situaci, kterou lze víceméně jednoznačně rozpoznat, a jejíž řešení je známé.
Pozastavme se nyní u našeho konceptu meta-strategie a osvětleme si rozdíl mezi ní a mezi tím, co označujeme za strategii. Zatímco meta-strategie je obecným popisem sestavení herní situace, jemuž přísluší obecný popis jejího řešení, strategie přináší konkrétní postup, jak danou herní situaci vyřešit, a v jejím rámci se uplatňuje lokální optimalizace. Uveďme si příklad. Mějme dřevěnou konstrukci a vedle ní prasátko. Naše umělá inteligence označí tuto herní situaci za případ meta-strategie „shoď na prasátko nejbližší konstrukci“. To však nestačí. Nyní je třeba určit způsob, jakým bude konstrukce shozena. Způsobů, jak toho docílit, je více a volba toho konkrétního závisí hned na několika skutečnostech. Je prasátko nalevo nebo napravo od konstrukce? Jak daleko od ní je? Jak je konstrukce široká a vysoká? Z jakého materiálu jsou bloky, které konstrukci tvoří? To všechno jsou otázky, které je třeba zohlednit, a které v našem případě vedou na dvě strategie. Cílem první bude konstrukci na prasátko povalit; taková strategie se hodí v případě, že prasátko je napravo od konstrukce a při vhodném zásahu do její horní části se na něj svalí. Cílem druhé bude poškodit základy konstrukce tak, aby se sesula směrem doleva; taková strategie se hodí v případě, že prasátko je nalevo od konstrukce a poškození jejích základů v levé spodní části bude mít za následek pád herních bloků přímo na něj. V rámci jedné meta-strategie jsme tedy našli dvě strategie.
Avšak co je hlavním určujícím znakem strategie? Vraťme se k našemu příkladu a ke strategii, při níž se snažíme konstrukci povalit směrem doprava. I když jde již o poměrně přesný popis toho, co chceme udělat, stále je zde spousta nejasností ohledně konkrétního provedení dané akce. Nyní se již neptáme, jakým způsobem chceme konstrukci na prasátko shodit, ptáme se, kam přesně chceme konstrukci zasáhnout, aby se náš záměr podařil. Přesné místo zásahu se liší podle toho, jakým způsobem a z bloků jakého typu je konstrukce sestavená. Toto místo je tedy třeba hledat individuálně, pro každou konstrukci zvlášť. Vidíme, že hlavním určujícím znakem strategie je lokální optimalizace.
Kromě již uvedené meta-strategie používá naše umělá inteligence několik dalších. Jmenujme například jednoduchou, ale často velmi účinnou meta-strategii „stref napřímo co nejvíce prasátek najednou“ nebo velmi úzce definovanou meta-strategii „uvolni kulatý herní blok tak, aby se rozkutálel a přejel prasátko“. Každá z těchto meta-strategií opět obsahuje několik strategií.
Jak ovšem naše umělá inteligence pozná, jakou meta-strategii, potažmo strategii, má pro momentální herní situaci vybrat? Před každým výstřelem rozzuřeného opeřence z praku oznámí všechny meta-strategie, kolik odhadují, že nahrají bodů, budou-li použity. Nestačí ovšem vybrat tu z nich, která vypadá nejslibněji, co do počtu strefených prasátek. Opeřenci nejsou všichni stejní a jejich schopnosti se liší. Někteří zvládají skvěle prorážet dřevo, ale neporadí si s ledem, jiní dokáží prorazit led, ale proti blokům z ostatních materiálů jsou bezmocní. Vybírat je tedy třeba i s ohledem na dostupné opeřence a na typy bloků, které bude třeba prorazit. Jakmile je proveden výběr meta-strategie, je odeslán pokyn rozhraní, které ovládá hru, a tah je odehrán.
Z výsledků letošního i minulého ročníku soutěže lze vyčíst, že našemu týmu se podařilo vytvořit umělou inteligenci, která obstojí v konkurenci týmů z univerzit z celého světa; jmenujme např. rakouskou Technische Universität Wien, německou Universität Paderborn či univerzitu se sídlem v Argentině, UTN Facultad Regional Santa Fe. I když se nám podařilo zvítězit v soutěži Angry Birds AI Competition 2014 i Angry Birds AI Competition 2015 (ta se letos odehrála v Buenos Aires v Argentině) člověk stále umí hrát Angry Birds o něco lépe. A proto cílem pro příští rok je vylepšit naše řešení do takové míry, abychom byli schopni porazit lidského hráče.
Autor: Radim Špetlík
Foto: Ondřej Hlaváč, VIC ČVUT