Kombinatorické Hry a Minimax
23.04.2026
28.04.2026

Plán hodiny: 
0. dotazy k minulým cvičením a přednášce 
1. seznámíme se (zopakujeme) úplné základy kombinatorické hry (dvou háčů s nulovým součtem a perfekrní informací; z pohledu teorie her)
2. seznámíme se algoritmem minimax pro výpočet optimální strategie
3. algoritmus minimaxu si demonstrujeme na příkladu jednoduché hry - sum game
4. algoritmus minimaxu na sum game si naprogramujeme 


Kombinatorické hry dle AIMA (Russel, Norvig) kap 5.
- popis her
- deterministické, perfect information hry dvou hráčů s nulovým součtem  
- stav hry, co je to stav hry?
- strom hry co je jedna konkretni cesta z korene stromu hry do listu? 
- cil hry - maximalizace uzitku/vyhrat
- procházení stromu hry 
- ohodnocení stavů hry 
- strategie
- minimax algoritmus - hodnota optimální hry vs hledání strategie hry


Zadání:
Sum Game

Mějme hru H dvou hráčů. 
Hráči se pravidelně střídají po jednom tahu. 
V každém tahu povinně zvolí hráč jedno číslo K z ze zadané množiny T celých kladných čísel (pro oba hráče je množina stejná a zůstává celou hru neměnná; je zadána listem). 
Zvolená čísla se (za oba hráče) společně sčítají do součtu S.

Je dána limitní hodnota-konstanta L.

Vyhrává ten hráč, který po přidání svého čísla, v součtu všech čísel, přesně dosáhne zadané hodnoty L. 
Prohrává ten hráč, který: a) není vyhrávajícím, pokud oponent vyhrál nebo b) přesáhne svým tahem v součtu hodnotu L. 

Limitní hodnota L a množina čísel-tahů T jsou parametry hry. 

Pravidla možných vstupů:
- vstupy mohou být prázdné
- S < L



0. Mějme limit hry 5 a možné tahy (pro oba hráče stejné) [2,3]
0.3 Nakreslete strom hry, pokud začíná maxový hráč
0.5 Určete optimální cenu hry pro maxového hráče
0.7 Určete optimální strategii hry pro maxového hráče



1.
Napište funkce 
maxPlay(odehraneTahy, pozadovanySoucet, mnozinaTahu) 
a minPlay(odehraneTahy, pozadovanySoucet, mnozinaTahu) vrací hodnotu otimalni hry 

Funkce 

function MAX-VALUE(state) returns a utility value (analogická funkce dle AIMA)
a function MIN-VALUE(state) returns a utility value (analogická funkce dle AIMA) vrací hodnotu optimální hry pro daného hráče, pro:
- max hráče vrací hodnotu: 1 v případě výhry a -1 v případě prohry
- min hráče vrací hodnotu: -1 v případě výhry a 1 v případě prohry
remíza není možná

Pokud funkce nedostanou vstupní parametry, pak jsou parametrům dosazeny defaultní hodnoty:
odehraneTahy - prázdný list 
pozadovanySoucet - 10 (kladná int hodnota), 
intervalHodnot - [2, 3] (list kladných intů)

1.3 Rozmyslete si, jak trstovat implmentované funkce, resp. na jakých datech testovat Vase funkce, které případy chcete pokrýt
(stav uz je vyhra a prohra; za jediny tak musi byt vyhra prohra; za jediny tah existuje vyhra/prohra; za dva tahy existuje vyhra/prohra; za vice tahu ...) 


2.
Napište funkci implementující minimax algoritmus pro hru H function MINIMAX-DECISION-MAX(state) returns an action (analogická funkce MINIMAX-DECISION(state) dle AIMA)
- vrací tah optimalizující výhru pro MAXového hráče

2.2
Napište funkci implementující minimax algoritmus pro hru H function MINIMAX-DECISION-MIN(state) returns an action (analogická funkce MINIMAX-DECISION(state) dle AIMA)
- funkce vrací tah optimalizující výhru pro MINového hráče

2.1
Napište funkci implementující minimax algoritmus pro hru H
- funkce vrací tah optimalizující výhru pro MINoveho hráče


3.
Implementujte hru H

3.1
Verzi PC vs PC

3.2
Verzi Člověk vs PC


A co velke stromy her?: orezavani (ztratove a bez ztratove) a heuristiky (kterou vetev vypoctu vybrat driv; "kudy se vydat" pri prohledavani)


Vypocty na stromu hry?
Kolik "vypoctu" budeme delat ....
Co kdyz mame zadane 3 mozne tahy [1,2,3] a limit hry je 100. 
Nejdelsi vetev bude vetev samych 1 tj hloubka 100
Nejkratsi vetev bude vedet samych 3 tj hloubka 100/3 tj hloubka 33(34)
Pri branching faktoru 3 a minimalni hloubce, bude strom hry na posledni vrstve obsahovat 3^33 nodu ...  



Alfa Beta prunnning: 
AIMA, demonstrace 
Co znamena alfa a co beta?


4.0
Doprogramujte do metod minimaxu alfa-beta prunning
(AIMA)