|
|
PNS for the game Arimaa
Majerech, Ondřej ; Hric, Jan (vedoucí práce) ; Valla, Tomáš (oponent)
Arimaa je strategická desková hra, kterou se stále počítačům nepovedlo pokořit. Problematický je zejména velký větvící faktor stromu hry a celková její charakteristika, díky které je obtížné sestrojit vhodnou ohodnocovací heuristiku pro alfa-beta prohledávání. Proof-Number Search je algoritmus nezávislý na dobré ohodnocovací heuristice, který byl již úspěšně použit na řešení koncovek jiných deskových her. V této práci jsme adaptovali a implementovali algoritmus Proof-Number Search pro hru Arimaa.
|
|
|
Solving Algorithms for Multi-agent Path Planning with Dynamic Obstacles
Majerech, Ondřej ; Surynek, Pavel (vedoucí práce) ; Vlk, Marek (oponent)
V předložené práci představujeme problém multiagentního hledání cest s dynamickými překážkami, tedy zobecnění multiagentního hledání cest, ve kterém jsou v prostředí náhodně se pohybující překážky. Takové zobecnění lze vnímat jako abstrakce neúplné znalosti o prostředí nebo jako zjednodušení multiagentního hledání cest, kde ne všichni agenti jsou zahrnuti v kooper- ativním algoritmu. Představujeme úpravu tří algoritmů pro multiagentní hledání cest pro prostředí s dynamickými překážkami: Local-Repair A* (LRA*), Windowed Hierarchical Cooperative A* (WHCA*) a Operator De- composition s Independence Detection (OD/ID). Dále představujeme dvě heuristiky pro uvedené algoritmy v dynamickém prostředí: Navracení na cestu a odhad pohybu překážek. V experimentech zjišťujeme, že LRA* a WHCA* se pro dynamické prostředí hodí nejlépe. Navracení na cestu úspěšně zlepšuje čas běhu plánovače za cenu malého prodloužení nalezených cest. Odhad pohybu překážek úspěšně zvládá snížit potřebu hledat nový plán, ale ve většině případů časová náročnost naší implementace převyšuje výkonnostní výhody plynoucí z menšího počtu hledání nových plánů. 1
|
|
|
PNS for the game Arimaa
Majerech, Ondřej ; Hric, Jan (vedoucí práce) ; Valla, Tomáš (oponent)
Arimaa je strategická desková hra, kterou se stále počítačům nepovedlo pokořit. Problematický je zejména velký větvící faktor stromu hry a celková její charakteristika, díky které je obtížné sestrojit vhodnou ohodnocovací heuristiku pro alfa-beta prohledávání. Proof-Number Search je algoritmus nezávislý na dobré ohodnocovací heuristice, který byl již úspěšně použit na řešení koncovek jiných deskových her. V této práci jsme adaptovali a implementovali algoritmus Proof-Number Search pro hru Arimaa.
|
host ::
RSS.