Prg2 CZ Mat st 10:40 24. 4. 2024
Prg2 CZ Mat čt 12:20 25. 4. 2024
a pak i Praktické cvičení

https://www.youtube.com/watch?v=BKorP55Aqvg


1. Mějme standardní šachovnici. Na šachovnici je zadáno startovní (S) políčko, cílové (C) políčko a figurka.

Následuje série úloh:
1.1 Dostanu se figurkou ze startu do cíle?
Rozhodněte, zdali lze ze startovního políčka dosáhnout cílové políčko pomocí koně (figurka šachů).
1.2 Jaká je nejkratší cesta ze startu do cíle?
V kolika nejméně tazích koněm (figurka šachů) lze dosáhnout cílové políčko ze startovní pozice (figurka šachů), pokud nelze vraťte hodnotu "-1".
1.3 Vypsat-evidovat nejkratší cestu
Vypište nějakou nejkratší cestu koněm (figurka šachů) ze starotvního políčka do cílového.


1.5 Modifikace předchozích úkolů (jak dosažení, nejkratší cesta (délka) tak nejkratší cesta (výpis)), pro:
1.5.2 jiné figurky: střelec, věž, dám, baba jaga, ... (obecně jiný druh pohybu po šachovnici)
1.5.3 nestandardní šachovnice: s překážkami (zakázané pole), nestandardní rozměry (třeba 11x11), toroidní (cirkulární) pole, ...


2. Games and MiniMax algorithm
2.2. AIMA - theory repetition
2.2.1 What is a game? (formal definition, statespace - tree graph, what we could to do with - what ask for: who win, best strategy, travers: BFS, DFS, iterative BFS, minimax, static evaluation function ...)

2.4 Sum Game
Write a minimax algorithm that solves Sum game. 
Sum game is a discrete, deterministic, perfect information, zero sum game (confrontation) of two players.  
Two players alternate moves, in each move one player plays and chooses a number (positive integer; from the nonempty set of possible moves). 
The numbers of both players together form a sequence.
The numbers in the sequence are sumed. 
The player who first reaches the specified (positive integer) number wins or the player who first exceeds the specified number loses.


Sum game play examples:

Input: reach/limit number = 4, possible moves = {1, 2}

Example 1:
P1 move: 2
P2 move: 2 and wins

Example 2:
P1 move: 2
P2 move: 1
P1 move: 1 and wins

Example 3:
P1 move: 1
P2 move: 2 
P1 move: 1 and wins

Example 4:
P1 move: 1
P2 move: 2 
P1 move: 2 and loose
respectively (1,2,2) loose


Input: reach/limit number = 5, possible moves = {2}

P1 move: 2
P2 move: 2 
P1 move: 2 and loose

respectively (2,2,2) loose, force lost, player must play



2.4.1 What means "win".
2.4.3 What is "strategy".
2.4.5 Difference: "who win" vs. "who and how many win" vs. "optimal strategy"(how I should play in this state to get to optimal state).

2.4.7 What returs a MiniMax algorithm?
- reward of optimal strategy
- the action that leads to the optimal strategy from given state


2.6. What means "Write a minimax algorithm that solve Sum game"?

2.6.1 First approach: return value/reward of the optimal strategy
2.6.1.1 What all is need to know to define state of the game?

2.6.2 Second approach: return the action that leads to the optimal strategy from the given state

2.6.5 Third approach: implement a game, where You play against computer

2.6.8 Print tree of game (for small limit number)

2.8. Generate appropriate test cases