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í (s₀, G), kde symbol s₀ ∈ 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ů.

Breadth-first search

1. Vytvoř frontu a vlož do ní počáteční stav
2. Vyjmi stav z fronty (je-li fronta prázdná, úloha nemá řešení)
   • Pokud je to cílový stav, skonči
3. Použij operátory a vygenerované stavy vlož do fronty. Pokračuj od bodu 2.

Možné optimalizace:

• Zkoumat, jestli jsme v bodě 3 nevygenerovali cílový stav
• Pamatovat si už prozkoumané stavy a kontrolovat jestli v bodě 3 negenerujeme stav kterým jsme už prošli

Depth-first search

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í:

1. Vlož počáteční stav do seznamu stavů.
2. Opakuj následující:
   1. Najdi stav s nejmenší hodnotou F a označ ho za aktuální.
   2. Odstraň ho ze seznamu.
   3. Pro každý z možných vygenerovaných stavů proveď…
      • Pokud je to nepřípustný stav (např. pohyb „do zdi“), ignoruj ho. Jinak pokračuj.
      • Pokud ještě není na seznamu, přidej ho na něj. Označ aktualní stav za jeho předka. Zaznamenej hodnoty F, G a H tohoto stavu.
      • Pokud už je na seznamu, zkontroluj jestli to není lepší cesta použitím hodnoty G (cena cesty do tohoto stavu). Nižší G by znamenalo že je to výhodnější cesta. Pokud tomu tak je, nastav předka takového stavu na aktuální stav a přepočítej G a F tohoto stavu.
   4. Skonči pokud:
      • Jsi našel a zpracoval cílový stav. V takovém případě byla nalezena optimální cesta.
      • Cílový stav nebyl nalezen a seznam stavů je prázdný. V takovém případě neexistuje žádná cesta.
3. Od cílového stavu jdi po předcích stavů až do počátečního stavu. To je nejkratší cesta.

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í:

• Hráč na tahu vyhrává, pokud existuje aspoň jeden jeho tah, který vede k přímému vítězství
• Hráč na tahu vyhrává, pokud k jeho vítězství vedou všechny možné soupeřovy tahy

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í.

• Na stole jsou 3 sirky
• Každý hráč může v každém kole odebrat 1, 2 nebo 3 sirky
• Kdo sebere poslední sirku, prohrál

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ů.

Minimax

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.

Alpha-beta pruning

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:

• jestliže jde o náš tah a hodnota beta na listu je vyšší, než hodnota alfa rodičovského prvku, alfu touto betou nahradíme.
• jestliže jde o soupeřův tah a hodnota alfa na listu je nižší, než hodnota beta rodičovského prvku, betu touto alfou nahradíme.

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.

• stavový prostor (stavy a operátory), úloha (počáteční stav, koncové stavy)
• řešení úlohy: prohledávání stavového prostoru, výsledek je řada operátorů
• strom, prohledávání (BFS, DFS, uniform cost search, greedy search, A*)
• rozklad na podúlohy: AND/OR
• hraní her: dva hráči, střídají se
• jednoduché: AND/OR pro celou úlohu
• složité hry: minimax, alfa-beta