- hledání v prostředí s protivníkem
- na zkoušce
- záleží podle chování protivníka
- vždy zisk - 1. volba
- kamarád vyučující - 2. volba
- bez apriorní informace / oč hodnota - 3. volba
- očekáváná hodnota
- bez apriorní znalosti bereme, že jsou uniformě rozložené
- $(\min + \max) / 2$
- šachy - nelze prohledat všechny stavy
- pruning (prořezávání)
- heuristická vyhodnocovací evaluační funkce
- Or - náš tah
- AND - volba soupeře
- proti racionálnímu hráči - minimax algoritmus
- Alpha - nejlepší tah pro max
- Beta - nejlepší tak pro min
- po zjištění volby $c_1$, kdy hledáme minimum, víme, že výsledek nebude vyšší, jak 2, můžeme zbytek podstromu C zahodit
- nelze prozkoumat celou hru ani s prořezáváním
- heuristická vyhodnocovací funkce
- omezení hloubky (časový limit)
- cutoff test - jestli se zanořovat dál
- racionální hráči != protihráči
- chtějí maximalizovat svůj zisk, né minimalizovat můj zisk
- aliance = hráči se mohou domluvit, co budou hrát
- lze přeformulovat na hru 2 hráčů, kdy druhý hráč hraje 2x a lze použít minimax algoritmus
- algoritmus expectiminimax
- chance
- chování lidí na burze - stock market
- nezáleží jenom na pořadí záleží i na velikosti
- aproximace pomocí vzorkování - výběr náhodných vzorků
- nejlepší tah je který soupeř nepředpokládá
- blafování
- averaging over clairvoyance - monte carlo nemusí být aplikovatelné
- simuluji jako bych viděl karty, ale v realitě my ty karty nevidíme
- na zkoušku
- nikdy nebudeme mít ideální funkci na řazení tahů
- nějaká permutace tahů se bude vždy opakovat - např. kombinace 4 tahů
- při větší hloubce se nám razantně změní směr
- toto nechceme a chce prohledávat stavy, kdy tato razantní změna nebyla
- pokud budeme prohledávat do hloubky 20, nevíme co se stane v tahu 21
- utíkáme s věží abychom ji aktuálně neztratili → někdy ji ztratit musíme
- “uřezávání prstů, když o ruku jednou přijdeme”
- singular extension - singulární rozšíření
- najdeme jasně lepší tahy - zapamatování tahu
- pči eval aplikujeme lepší tahy navíc
- “aplikuje až po tý akci”
- nezaručuje zachování výsledku
- dopředné prořezávání
- nechává v každém tahu jen pár nejlepších tahů
- null move heuristika
- necháme soupeře táhnout na začátku 2x
- spodní odhad pro ohodnocení
- pevně dané začátky (opening v šachu), postupuje podle nich
- konec hry
- dané řešení - král + pěšec vs král, … - eliminace např. 20 tahů
- podmínky or kombinaci hodnot proměnných
- Faktorizovaná reprezentace stavů
- máme cíl - splnit a nesplnit vs užitek
- úplné přiřazení = každé proměnná má přiřazenou hodnotu
- konzistentní / legální = přiřazení neporušuje žádnou podmínku
- doména proměnné neporušuje unární omezení
- úprava domén pro danou proměnou - např.
X1 != 3 → D1 = {1,2,4,5}
- pouze jednou před vyhledáváním
- stejně jako předchozí, ale pro binární omezení
- pro každou hodnotu z proměnní i existuje hodnota pro j, aby neporušovala podmínku
- algoritmus ac-3
- checkuje omezení celého grafu
- ternání omezení nebo kombinace binárních dohromady
- obecně K-konzistence
- při prohledávání používáme backtracking
- pamatujeme si pouze operátor, lze jednoduše vrátit zpět a nahradit jiným operátorem
- minimum-remaining-values () - nejmenší větvení
- degree heuristic - proměnná v největším počtu omezení nepřiřazených proměnných
- dobré pro rozvrh - máme nějaké řešení, přijde další podmínka, upraví se