====== Markovské rozhodovací procesy ======
Stáhněte si kuimaze balík {{ :courses:b3b33kui:cviceni:sekvencni_rozhodovani:kuimaze.zip |}}. Úkolem je naimplementovat funkce find_policy_via_value_iteration(...) a find_policy_via_policy_iteration(...) s těmito vstupy a výstupy:

Vstupy: ''find_policy_via_value_iteration(problem, discount_factor, epsilon)'' a ''find_policy_via_policy_iteration(problem, discount_factor)'', kde: 
  * ''problem'' je prostředí - objekt typu ''kuimaze.MDPMaze''
  * ''discount_factor'' je z rozmezi ''(0,1)''
  * ''epsilon'' je maximalní povolená chyba pro Value jednotlivých stavů (pouze pro value iteration)

Výstupy: 
Očekávaný výstup je slovník, kde klíčem je dvojice (x,y) tuple a hodnotou je optimální akce (stačí uvažovat dosažitelné stavy a pro terminální stavy nechť je výstup ''None''). 

Metody implementujte v souboru ''mdp_agent.py''; který odevzdejte do [[https://cw.felk.cvut.cz/upload/|Upload systému]]. V balíku kuimaze.zip je i soubor ''mdp_sandbox.py'', který ukazuje základní práci s MDPMaze, můžete ho použít jako start k další implementaci (viz též popis Základních metod níže).

Timeout: na jednotlivé běhy value/policy iteration pro danou instanci problému máte časový limit 30s.


====== Bodové hodnocení a termíny ======
Termín odevzdání úlohy lze vidět v [[https://cw.felk.cvut.cz/upload/|Upload systému]]. 

Hodnocení je rozděleno následovně:
   - Automatické hodnocení testuje správnost policy (match správných a vámi vrácených akcí pro všechny stavy) na vzorku prosředí a popř. s různými discount factory.
   - Manuální hodnocení je založeno na hodnocení kódu (clean code).

^ Hodnocený výkon ^ min ^ max ^ poznámka ^
| Kvalita algoritmu value iteration | 0 | 2.5 | Ohodnocení algoritmu automatickým evaluačním systémem. |
| Kvalita algoritmu policy iteration | 0 | 2.5 | Ohodnocení algoritmu automatickým evaluačním systémem. |
| Kvalita kódu | 0 | 1| Komentáře, struktura, elegance, čistota kódu, vhodné pojmenování proměnných... |

Automatické hodnocení:
  * match v policy 95% a více (průměr na n testovaných bludištích): 2.5 bodu
  * match v policy 90%-95% : 2 body
  * match v policy 85%-90% : 1.5 bodu
  * match v policy 80%-85% : 1 bod
  * match v policy 70%-80% : 0.5 bodu
  * méně než 70% match: 0 bodů

Kvalita kódu (1 bod):
  * vhodné komentáře, nebo kód je srozumitelný natolik, že komentáře nepotřebuje
  * rozumně dlouhé, respektive krátké metody/funkce
  * jména proměnných (podst. jména) a funkcí (slovesa) pomáhají čitelnosti a srozumitelnosti
  * kusy kódu se neopakují (žádné copy-paste)
  * rozumné šetření pamětí a procesorovým časem
  * konzistentní názvy i rozložení kódu v celém souboru (oddělovat slova ve všech metodách stejně, atp.)
  * přehledná struktura kódu (vyvarujte se např. nepythonovskému přiřazování mnoha proměnných v jednom řádku)
  * ...

Můžete následovat pro Python určený [[https://www.python.org/dev/peps/pep-0008/|PEP8]]. Většina editorů (jistě PyCharm) na nedostatky s ohledem na PEP8 i sám upozorňuje. Můžete se také inspirovat např. [[https://github.com/zedr/clean-code-python|zde]] nebo si přečíst o idiomatickém pythonu na [[https://medium.com/the-andela-way/idiomatic-python-coding-the-smart-way-cc560fa5f1d6|mediu]] či u [[http://python.net/~goodger/projects/pycon/2007/idiomatic/handout.html|pythonu]].


===== Základní metody =====
Ke komunikaci s prostředím MDPMaze slouží následující metody:

''get_all_states()'' : vrátí seznam všech dosažitelných stavů, tedy bez zdí. V tomto případě jsou to weighted stavy i s rewards, tedy (state.x, state.y, state.reward) 

''is_terminal_state(state)'' : True pokud ze stavu nevede cesta zpět - cílový dobrý, nebo naopak cílový špatný/nebezpečný - představte si propast, nebo minu. 

''get_actions(state)'' : Pro daný stav navrátí seznam možných akcí, které se typicky použijí v následující metodě. Akce je typu [[https://docs.python.org/3.4/library/enum.html|enum]], ale tím se nemusíte zabývat, viz příklad použití v ''mdp_sandbox.py''

''get_state_reward(state)'': Obvykle není potřeba, vstupem je pojmenovaná dvojice (state.x, state.y).

''get_next_states_and_probs(state, action)'' : pro daný stav a požadovanou akci navrátí seznam dvojic ''( (state.x, state.y), probability )'' ; např. ''[ ( (2,3), 0.3), ( (3,3), 0.7)]'' 


''state'' je [[https://docs.python.org/3/library/collections.html#collections.namedtuple|pojmenovaná n-tice]] buď (state.x, state.y, state.reward) nebo (state.x, state.y). 

''visualise(dictlist=None)'' : bez parametru visualizuje obvyklé bludiště. Jinak očekává seznam slovníků ''{'x': x_coord, 'y': y_coord, 'value: val'}'', kde val může být buď skalární hodnota, nebo seznam/n-tice o čtyřech prvcích. Zde můžete konkrétně využít k vizualizaci:
  - rewards ci values přirazených jednotlivým stavům - viz ''env.visualise(get_visualisation_values(utils))''
  - policy - viz ''env.visualise(get_visualisation_values(policy))''

Rovněž zůstávají k dispozici obvyklé metody ''render(), reset()''

Základní příklad použítí je vidět v souboru ''mdp_sandbox.py''