====== Vězňovo dilema ======
Téma je vysvětleno ve 1. přednášce ve prvním výukovém týdnu. Vězňovo dilema a jeho varianty se vyskytují v mnohé liteatuře a každý si může najít alternativy, které mu nejvíce vyhovují. Dobrý startovní bod ke studiu problému je určitě relevantní [[http://en.wikipedia.org/wiki/Prisoner's_dilemma|stránka]] na wikipedii. Dobrý úvod do teorie her a vysvětlení základního názvosloví nabízí český text {[a4b99rph:Pelis2008]}


> {{section>courses:a4b99rph:internal:cviceni:veznovo_dilema:start#resources&editbtn}}

> {{section>courses:a4b99rph:internal:cviceni:veznovo_dilema:start#codes&editbtn}}

> {{section>courses:a4b99rph:internal:cviceni:veznovo_dilema:start#namety_k_diskusi_k_rozsireni&editbtn}}

====== Formulace problému ======
Princip //nekooperativní dvouhráčové// hry si vysvětlíme na konkrétním příkladu. Vypůjčíme si příklad z kapitoly 3, knihy {[a4b99rph:Shoham-Brown2009]}. Internetový provoz se řídí protokolem [[http://en.wikipedia.org/wiki/Transmission_Control_Protocol|TCP]]. Představte si, že na síti jste pouze vy (hráč A) a váš kolega (hráč B). Jedním ze základní algoritmů je tzv. //backoff// mechanismus. V okamžiku, kdy posíláte pakety tak, že dochází k ucpání sítě, oba ustoupíte (backoff) a opakujete vysílání po nějaké náhodné době. Takto funguje správná (**C**orrect) implementace. Špatná (**D**efective) implementace znamená, že neustoupí a doufá, že tak učiní ten druhý. Máte tak k dispozici dvě //strategie//: spolupracovat (**C**ooperate) a nespolupracovat (**D**efect). Jestliže vy a váš kolega volíte oba C, pak je průměrné zpoždění paketů 1 ms. Jestliže oba volíte D, pak je průměrné zpoždění 3 ms, kvůli vetší režii sítě. Konečně, v případě rozdílných strategií, putují pakety hráče volícího D bez zpoždění, naopak pocitivý hráč, hrající C má zpoždění 4 ms. Možné varianty strategií a výsledných zpoždění shrnuje naásledující tabulka. Řádky patří hráči A, sloupce B. Vektor na pozici [**C**,**D**] tedy říká: hráč A kooperuje (ustoupí), hráč B nikoliv. Pakety hráče A budou mít 4 ms zpoždění, pakety hráče B cestují bez zpoždění.

| ^ C ^ D ^
^ C | -1,-1 | -4, 0 |
^ D | 0,-4 | -3, -3|

Je to tzv. payoff matice. Jakou strategii zvolíte? Vaším cílem pochopitelně je, aby vaše pakety byly doručovány s co nejmenším zpožděním. Problémem je, že protokol neumožňuje, aby se hráči předem na pevno dohodli o společné strategii. Pakety se odesílají opakovaně, stejně tak je potřeba opakovaně volit vhodnou strategii. Jediné, co máte k dispozici u opakované hry, je její //historie//, víte tedy jak jste hrál v minulosti vy a jak váš kolega.




====== Formulace úlohy ======
Naprogramujte hráče (agenta) který bude hrát opakovanou nekooperativní dvouhráčovou hru. Na vstupu je známa matice zisků (payoff matrix), počet opakování může, ale nemusí být předem znám. Cílem je maximalizovat svůj zisk, připadně minimalizovat ztrátu.

[[.:specifikace|Podrobnější]] specifikace hráče a turnajů, které se budou hrát.

====== Odevzdávání ======
Úloha má dvě odevzdání, termíny jsou vidět v Upload systému
  - Jednoduchý hráč, který je splňuje formální požadavky, tj. je schopen hrát (úloha 03_PD_hrac). 
  - Chytrý hráč, který bude hrát proti všem ostatním. Jeho hlavním úkolem je obehrát ostatní, získat největší zisk (úloha 04_PD_tur). 

[[courses:a4b99rph:cviceni:veznovo_dilema:hodnoceni_a_terminy|Hodnocení a termíny]]. Kolik bodů můžete získat a za co.