Stavový prostor je dvojice (S, O), kde S (States) jsou stavy, a O (Operators) operátory kterými lze stavy měnit. Úloha je definována dvojicí (s0, G), kde symbol s0 ∈ S značí počáteční stav a symbol G ⊂ S množinu cílových stavů této úlohy (Goals). Řešením úlohy je posloupnost operátorů.
Možné optimalizace:
To samé jako prohledávání do šířky, ale místo fronty použijeme zásobník.
A* search algorithm, A* Pathfinding for Beginners
Na rozdíl od předchozích metod jde o tzv. informovanou metodu. To znamená, že má informaci o cílovém stavu. Metoda se obzvlášť hodí pro nalezení nejkratší cesty mezi dvěma body v rastru.
Stavy jsou ohodnoceny jako součet F = G + H, kde G je cena cesty do tohoto místa (typicky se přičítá 1 k ceně předchozího místa, ale jdeme-li například bažinou, bude určitě větší) a H heuristická funkce, tzv. spodní odhad (při řešení pohybu k cíli to bude například vzdušná vzdálenost k němu).
Algoritmus je pak následující:
Při rozkladu na podúlohy se používají AND/OR grafy.
Problém A je řešitelný, pokud je řešitelný alespoň jeden z jeho podproblému. Jde o OR graf. Problém E je řešitelný, pokud jsou řešitelné všechny jeho podproblémy – AND graf.
AND/OR grafy jsou složené z těchto dvou typů grafu. Rozkladem na podúlohy myslíme právě to, že pro řešení jednoho uzlu je potřeba vyřešení jeho poduzlů.
Obecný AND/OR graf může vypadat takto:
V tomto případě je potřeba pro splnění A splnit B, C a jeden z [D, E]. S takovým grafem se špatně pracuje a proto jej často převádímě na takový, kde je v každé vrstvě
jeden typ grafu.
AND/OR graf se řeší odspodu (od listů). Ohodnotí se všechny listy podle toho, jestli jsou kladným, nebo záporným výsledkem. Jejich rodičovský uzel je pak kladný nebo záporný podle toho, jestli jde o AND nebo OR uzel. A takhle to jde po jednotlivých vrstvách až ke kořenu.
U her se střídají 2 hráči a oba chtějí vyhrát. Algoritmus nepočítá s tím, že by druhá strana měla udělat chybu.
U těchto her platí:
Na základě těchto dvou bodů lze vytvořit AND/OR graf pro celou úlohu.
Tahle hra je příkladem hry, kde je konečný počet řešení.
Je to hloupý, ale aspoň ten obrázek není velký. Sestavíme AND/OR graf, kde každý uzel bude znázorňovat, kolik zbývá po tahu hráče na stole sirek. Přechod z liché vrstvy do sudé je tah hráče na prvním tahu, přechod ze sudé do liché je tah protihráče.
Po sestavení hry označíme koncové stavy zelenou barvou, pokud šlo o výhru hráče na tahu, nebo červeně, pokud šlo o výhru oponenta. Podle pravidel AND/OR grafu pak obarvujeme vyšší stavy. Zjistíme snadno, že sebrání 2 sirek vede k drtivé výhře.
Při implementaci se pro procházení grafu používá například BFS nebo DFS.
U složitých her se počítá jen několik tahů dopředu z důvodů strojového času, paměťové náročnosti (obrovský graf) nebo v zásadě prostě proto, že není konečný počet tahů.
Jelikož nemáme cílové stavy, je potřeba určit si maximální hloubku stromu. Poté koncové listy tohoto stromu ohodnotíme. Čím vyšší hodnocení, tím lepší stav pro hráče na tahu, čím nižší, tím lepší stav pro oponenta. Při použití CHARu je rozsah 256 hodnot. Maximální hodnota, 127, znamená vítězný tah, minimální hodnota, -127, znamená úplnou prohru.
Dva důležité kroky, které je potřeba provést, je výběr všech tahů, které vůbec dávají smysl (například u piškvorek, u hada je tahů tak málo, že se volí všechny) a hlavně zvolení správné heuristické funkce, která bude hodnotit stav po jednotlivých tazích. U tic-tac-toe (piškvorky 3×3) je třeba vhodná heuristika počet trojic, kterými může soupeř zvítězit.
Po ohodnocení listů procházíme strom stejně jako algoritmus DFS. U každého našeho tahu vybíráme z možných hodnot tu nejvyšší, u soupeřova tu nejnižší. Projdeme celý strom, čímž ohodnotíme kořenový uzel. To nám poradí, který tah máme tedy udělat – je to ten, který vede k uzlu se stejnou hodnotou, jako má kořenový uzel.
Jde o vylepšenou verzi MiniMaxu, která eliminuje procházení větví, u kterých je jasné, že se nestanou. V těchto případech je totiž pro hráče na tahu vždy výhodnější vydat se jinou cestou. Na obrázku je ukázka minimaxu a zbytečných větví, které jsou šedé.
Na začátku alfabety si vytvoříme 2 proměnné: alfa a beta a přiřadíme je kořenovému uzlu. Alfa má hodnotu nejnižší možnou, beta nejvyšší možnou. Pokud v procházení grafu postupujeme směrem dolů, opisujeme alfa a beta do spodního uzlu. Pokud postupujeme směrem nahoru, tak:
Pokud jde o koncový uzel, tak bereme místo alfy/bety jeho ohodnocení.
Optimalizace spočívá v tom, že když se stane, že je alfa větší než beta, můžeme tuto větev opustit a zbylé uzly nekontrolovat. Algoritmus je složité vysvětlit, ale jednoduché pochopit podle ukázky.
Ukázka práce MiniMax a AlfaBeta algoritmů jsou zde – dole na stránce.