Alg a Prg

Hry
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 
- 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


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ů)


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

4.0
Doprogramujte do metod alfa-beta prunning