Obsah
24e - Metódy hrania hier
- prehľadávanie AND/OR grafu
Jednoduché hry
- hry pri ktorých sa dá v reálnom čase prehľadať celý ich AND/OR graf
- napr. hra s braním zápaliek (na začiatku je N zápaliek, v každom ťahu môže hráč zobrať 1 - 3 zápalky, kto zoberie poslednú vyhrá/prehrá)
Zložité hry
- hry, pri ktorých je úplne prehľadávanie AND/OR grafu nemožné
- napr. šachy
- prehľadáva sa len do dopredu danej hĺbky - ak sa v tejto hĺbke nenachádza riešenie je treba ich nejakým spôsobom hodnotiť
- nasledujúce metódy
- kladné hodnoty - priaznivé stavy pre hráča A
- záporné hodnoty - priaznivé stavy pre hráča B
MiniMax
- základom je rekurzívna procedúra MiniMax, ktorá ohodnocuje ťah do uzlu
- Procedura MiniMax:
- Nazvěme předaný vstupní uzel uzlem X.
- Je-li uzel X listem (konečným stavem hry, nebo uzlem v maximální hloubce) vrať ohodnocení tohoto uzlu. Jinak pokračuj.
- Je-li na tahu hráč A, tak postupně pro všechny jeho možné tahy (bezprostřední následníky uzlu X a hráče B) volej proceduru MiniMax a vrať maximální z navrácených hodnot. Je-li X kořenovým uzlem vrať i tah, který vede k nejlépe ohodnocenému bezprostřednímu následníkovi.
- Je-li na tahu hráč B, tak postupně pro všechny jeho možné tahy (bezprostřední následníky uzlu X a hráče A) volej proceduru MiniMax a vrať minimální z navrácených hodnot.
- dochádza k zbytočnému vyšetrovaniu niektorých stavov
Alfa a Beta rezy
- zabránia zbytočnému vyšetrovaniu ťahov
- Procedura AlfaBeta:
- Nazvěme předaný vstupní uzel uzlem X.
- Je-li X počátečním/kořenovým uzlem, nastav a = -¥, b = ¥ (v praxi nastav hodnoty těchto proměnných na minimální a maximální možnou hodnotu).
- Je-li uzel X listem (konečným stavem hry, nebo uzlem v maximální hloubce) ukonči proceduru a vrať ohodnocení tohoto uzlu.
- Je-li uzel typu AND (na tahu je hráč B) jdi na bod 5, jinak pokračuj (uzel je typu OR, na tahu je hráč A):
- Dokud je a < b, tak postupně pro první/další tah (bezprostředního následníka uzlu X a hráče B) volej proceduru AlfaBeta s aktuálními hodnotami proměnných a a b. Po každém vyšetřeném tahu nastav hodnotu proměnné a na maximum z aktuální a navrácené hodnoty .
- Ukonči proceduru, vrať aktuální hodnotu proměnné a a pro kořenový uzel vrať i tah, který vede k nejlépe ohodnocenému bezprostřednímu následníkovi.
- (Uzel je typu AND, na tahu je hráč B):
- Dokud je a < b, tak postupně pro první/další tah (bezprostředního následníka uzlu X a hráče A) volej proceduru AlfaBeta s aktuálními hodnotami proměnných a a b. Po každém vyšetřeném tahu nastav hodnotu proměnné b na minimum z aktuální a navrácené hodnoty .
- Ukonči proceduru a vrať aktuální hodnotu proměnné b.
Hry s neurčitosťou
- napr. hry s kockou
- rekurzívna procedúra
- Procedura ExpectMiniMax:
- Nazvěme předaný vstupní uzel uzlem X.
- Je-li uzel X listem (konečným stavem hry, nebo uzlem v maximální hloubce) vrať ohodnocení tohoto uzlu. Jinak pokračuj.
- Je-li na tahu hráč A, tak postupně pro všechny jeho možné tahy (bezprostřední následníky uzlu X a hráče B) volej proceduru ExpectMiniMax a vrať maximální hodnotu z hodnot expectimax. Je-li X kořenovým uzlem vrať i tah, který vede k nejlépe ohodnocenému bezprostřednímu následníkovi.
- Je-li na tahu hráč B, tak postupně pro všechny jeho možné tahy (bezprostřední následníky uzlu X a hráče A) volej proceduruExpectMiniMax a vrať minimální hodnotu z hodnot expectimin.