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, ve které existuje tah do prohrávající pozice.
- Vyhrávající pozice je pozice, ve které existuje tah do prohrávající pozice.
- Prohrávající pozice jsou ještě všechny prohrávající pozice.
Ukázkové hry
Tahání
- 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í?
