| Abstract: |  Tato práce poskytuje popis a porovnání několika algoritmů a jejich variant, které mají za úkol nějakým způsobem urychlit výpočet. Toho dosahují zkrácením výpočtu o procházení některých stavů, které uznají jako zbytečné navštěvovat a prohledávat. Jsou zde představeny celkem tři algoritmy. Prvním z nich je Minimax, který je jeden ze základních algoritmů teorie her. Způsob prořezávání v tomto algoritmu je založen na neprocházení uzlů, které je v rámci výpočtu již zbytečné navštěvovat. Ty pozná podle dříve získaných hodnot. Druhým a jediným stochastickým algoritmem v této práci je Monte-Carlo Tree Search. Jeho prořezávání je také stochastické a vyřazuje uzly, které vypadají nevýhodně. Posledním a nejdůležitějším algoritmem této práce je Lineární program, který počítá smíšené strategie v Nashově ekvilibriu. Rozšíření tohoto algoritmu je založeno na postupném skládání lineárního programu a postupného přidávání jednotlivých akcí obou hráčů. Takto může skončit výpočet dříve než přidáme všechny akce. Tento algoritmus se jmenuje Double oracle a v této práci je představeno ještě jedno možné rozšíření. To je založené na úpravě algoritmu, který vybírá akce přidávané do výpočtu a je postaveno na odhadování výsledku pomocí algoritmu Minimax. V této práci lze najít porovnání výkonu při hře mezi sebou a porovnání potřebných zdrojů.
|
|---|