|
|
Obousměrné heuristické vyhledávání
Hřebejk, Tomáš ; Vyskočil, Tomáš (vedoucí práce) ; Zajíček, Ondřej (oponent)
Účelem této bakalářské práce je shrnout nejdůležitější poznatky ohledně obousměrného heuristického prohledávání a přinést nějaké nové myšlenky. Jsou zde popsány dva algoritmy, které vznikly jako pokus o vylepšení dosud nejlepších algoritmů v této oblasti. Tyto algoritmy byly experimentálně porovnány s jednosměrným algoritmem. Na základě výsledků porovnání je možné říci, že obousměrné heuristické algoritmy mohou být výrazně rychlejší než jednosměrné. Kromě toho je v textu popsáno, jak je možné převádět různé úlohy na problém nalezení nejkratší cesty a jak získat dobrou heuristiku. Pro ukázku byl vytvořen program, který používá algoritmy pro hledání nejkratší cesty k řešení zobecněného hlavolamu.
|
|
|
Arimaa challenge - static evaluation function
Hřebejk, Tomáš ; Majerech, Vladan (vedoucí práce) ; Baudiš, Petr (oponent)
Arimaa je strategická desková hra pro dva hráče. Byla navržena tak, aby nebylo nebylo jednoduché vytvořit počítačový program, který by dokázal porazit nejlepší lidské hráče. V této práci jsme se zaměřili na návrh statické ohodnocovací funkce pro hru Arimaa. Úkolem ohodnocovací funkce je určit, který hráč má v dané pozici výhodu a jak je velká. Tento problém jsme rozdělili do několika částí, které jsme řešili samostatně. Nejvíce jsme se věnovali efektivnímu rozpoznávání významných vzorů na desce, například gólovým hrozbám. Základním prvkem navržené ohodnocovací funkce je mobilita. Pro každou figurku odhadneme počet kroků potřebný k tomu, aby se tato figurka přesunula na ostatní místa herní desky. Dále jsme se zabývali strojovým učením. Navrhli jsme nový algoritmus pro učení ohodnocovací funkce podle her expertů. Součástí práce je i implementace herního programu, který demonstruje navržené metody. Powered by TCPDF (www.tcpdf.org)
|
|
|
Obousměrné heuristické vyhledávání
Hřebejk, Tomáš ; Vyskočil, Tomáš (vedoucí práce) ; Zajíček, Ondřej (oponent)
Účelem této bakalářské práce je shrnout nejdůležitější poznatky ohledně obousměrného heuristického prohledávání a přinést nějaké nové myšlenky. Jsou zde popsány dva algoritmy, které vznikly jako pokus o vylepšení dosud nejlepších algoritmů v této oblasti. Tyto algoritmy byly experimentálně porovnány s jednosměrným algoritmem. Na základě výsledků porovnání je možné říci, že obousměrné heuristické algoritmy mohou být výrazně rychlejší než jednosměrné. Kromě toho je v textu popsáno, jak je možné převádět různé úlohy na problém nalezení nejkratší cesty a jak získat dobrou heuristiku. Pro ukázku byl vytvořen program, který používá algoritmy pro hledání nejkratší cesty k řešení zobecněného hlavolamu.
|
host ::
RSS.