Kombinatorické Hry a Minimax algoritmus
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 (konkrétně: kompetitivní, deterministické, dvou hráčů s nulovým součtem a perfektní 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
5. rozmyslíme, jak algoritmus vhodně testovat 
6. vytvoříme hru AI vs AI a AI vs Člověk 


Kombinatorické hry dle AIMA (Russel, Norvig) kap 5.
- popis her
- deterministické, kompetitivní, perfect information hry dvou hráčů s nulovým součtem  
- stav hry, co je to stav hry?
- strom hry, co je jedna konkrétní cesta z kořene stromu hry do listu? a co reprezentuje celý strom hry
- cíl hry - maximalizace užitku/vyhrát
- procházení stromu hry 
- ohodnocení stavů hry 
- strategie vs optimální strategie hry
- minimax algoritmus - hodnota optimální hry vs hledání strategie hry
- úprava algoritmu pro hru více hráčů


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

Otázka: jak pro implementaci definovat stav hry?

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 testovat implementované funkce, resp. na jakých datech testovat Vaše funkce, které případy chcete pokrýt
(stav už je výhra a prohra; za jediný tak musí byt výhra prohra; za jediný tah existuje výhra/prohra; za dva tahy existuje výhra/prohra; za vice tahu ...; speciální případy hry, kde víte výsledek\optimální strategii;) 


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 velké stromy her?: ořezávaní (ztrátové a bez ztrátové) a heuristiky (kterou větev výpočtu vybrat dřív; "kudy se vydat" při prohledávání)


Výpočty na stromu hry?
Kolik "výpočtů" budeme dělat ....
Co když máme zadané 3 možné tahy [1,2,3] a limit hry je 100. 
Nejdelší větev bude větev samých 1 tj. hloubka 100
Nejkratší větev bude  samých 3 tj. hloubka 100/3 tj hloubka 33(34)
Při branching faktoru 3 a minimální hloubce, bude strom hry na poslední věstvi obsahovat 3^33 nodu ...  



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


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