Alg a Prg

Konzultace - temat zapoctovych programů
Poznamky: 
- prima ze se ptate - palec nahoru!
- maticova knihovna (2D list vs numpy) vs kalkulator.... proc? SVD, QR (komplexnejsi algos kdy se treba i neco naucite) vs scitani matic (nyni uz newbie); 
format zapisu matic- matlab
- u her: simulator hry vs ai pro hrace

Teoreticke cviceni je spojeno s praktickym: co jsme teoreticky probrali to jsme implementovali

3. Rekurze: úvod do teorie a priklady: dle BTS_Naive_priklady_1_4.py
T -> n-arni T -> BT -> BST; BT jako datova struktura a jeji rekurzivni definice 


DFS pre in post
# https://www.enjoyalgorithms.com/blog/binary-tree-traversals-preorder-inorder-postorder

DFS vs BFS 
BFS potomky vrcholu a az potom potomky potomku

5. Rekurzivni DFS pres meta algoritmus prochazeni stromu na nerekurzivni prochazeni stromu - obecne

5.2 Stack: def, implementace (array, linkedList); priklady; LIFO
5.6 Fronta: def, implementace (array, linkedList, circular array); priklady; FIFO

5.8 Date Structure v meta algoritmu: a] stack; b] fronta a jejich simulace na konkretnim strome
- FIFO a LIFO resp. Fronta a Stack jako princip usporadani

Meta algoritmus 
a dosazeni DS:
a] Stack
b] Q
simulovat/krokovat na tabuli pro zadany strom t


7. DFS pro BT: rekurze a stack
9. BFS pro BT: fronta

10. AIMA: Russel, Norvig: 3. Solving Problems by Searching; DFS a BFD
https://aima.cs.berkeley.edu/

11. Porovnani DFS a BFS
11.1 Slozitost na cas a prostor   
Urcete prostorovou slozitost DFS a BFS v zavislosti na houbce (BT) stromu

13. Implementace BFS frontou a DFS stack a rekurze 
13.2 Implementace Stacku a Fronty v Pythonu napr.:
a] collections
b] list: popleft(), pop() a pop(-1), append(),...

https://www.geeksforgeeks.org/deque-in-python/



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