Konečná hra s úplnou informací
Podle přednášky 8. prosince 2006:
- Věta (Shannon): V konečné hře s úplnou informací alespoň pro jednoho hráče existuje neprohrávající strategie.
Definice prohrávající a vyhrávající pozice (rekursivně)
- Prohrávající pozice je pozice, ze které nemohu táhnout dál (příklad: při braní sirek nemám co tahat).
- Vyhrávající pozice je pozice, ve které existuje tah do prohrávající pozice (příklad: při braní sirek mohu vzít takový počet, že soupeř se dostane do prohrávající pozice).
- Prohrávající pozice jsou ještě všechny ostatní pozice.
Příklad: Strom pozic pro braní sirek z počátečního počtu pět (nezamotejte se v tom, vyhrávající pozice jsou z pohledu «čtverečkového» hráče, když jsem čtverečkový a táhnu na začátku 2, mám zaručené vítězství):
Ukázkové hry
Braní sirek
- z jedné hromádky dané tahy (třeba {1, 2})
- libovolný tah z libovolné ze dvou hromádek
- Řešení: rekursí, kešování výsledků pro již spočtené stavy (booleovské pole)
Braní čísel
- Na začátku řada čísel (třeba 5, 10, 19, 7).
- Mohu brát číslo z kteréhokoli konce.
- Vyhrává hráč s větším součtem sebraných čísel.
- Řešení: Mini Max, Nega Max, Alfa Beta Prořezávání, Statické Ohodnocení
