[CZ] Vězňovo dilema - strategie

Na dnešních cvičeních se pokusíme zopakovat turnaj strategií pro vězňovo dilema, o kterém jste si povídali s Romanem na přednášce. Každý z vás si napíše vlastní strategii a pustíme je proti sobě.

Pravidla vězňova dilematu

Vězňovo dilema je hra pro dva hráče. Je založena na příběhu dvou vězňů: dva kamarádi spolu páchali zločiny tak dlouho, až je jednou chytili. Neměli ale dost důkazů a ačkoliv je podezřívali z mnoha věcí, dokázat jim mohli jen tu poslední. Posadili je tedy každého do jedné místnosti a nabídli jim nižší trest za to, že svého kamaráda zradí.

Každý vězeň tedy má dvě možnosti, buď spolupracovat s tím druhým (cooperate), nebo ho zradit (defect). Pokud oba spolupracují, nic moc jim nedokážou a dají jim menší trest. Pokud jeden spolupracuje a druhý ho zradí, tak zrádce odejde bez trestu a spolupracující dostane dlouhý trest. Konečně, pokud se zradí oba navzájem, dostanou oba trest, který je ale sice větší, než kdyby spolupracovali, ale menší než ten, co by dostal spolupracující, kdyby spolupracoval jen jeden z nich.

Nahradíme-li délku trestu body (tj. kratší trest = více bodů) a vězně hráči, můžeme se na hru podívat z pohledu teorie her. Dostáváme hru s následující matici odměn:

 CD
C 3 0
D 5 1

V matici jsou na řádcích moje volby a ve sloupcích volby protihráče. Čísla určují počet bodů, které dostanu v každé situaci (druhý hráč má matici stejnou).

Když se na matici podíváme, tak můžeme určit, jak budou hráči hrát. Racionální hráč bude nejspíš uvažovat nějak takto:

  • Mohu buď spolupracovat, nebo zradit.
  • Když budu předpokládat, že mě protihráč zradí, vyplatí se mi ho zradit (1>0)
  • Když budu předpokládat, že protihráč bude spolupracovat, vyplatí se mi ho zase zradit (5>3).
  • Zradím tedy svého protihráče.

Stejným způsobem bude uvažovat i protihráč, a oba navzájem se tedy zradí a dostanou jeden bod. Pokud se vězňovo dilema hraje jen jednou, nemohou racionální hráči dosáhnout jiného výsledku (pokud se předtím nedomluví a nevěří si).

Iterované vězňovo dilema

Mnohem zajímavější situace ale nastane, když se vězňovo dilema hraje opakovaně mezi dvěma hráči, kteří (oba) mají za úkol maximalizovat svůj bodový zisk. V takové situaci totiž existuje možnost oplatit zradu v předchozím kole a existuje tedy i možnost, aby oba hráči spolupracovali.

Pro iterované vězňovo dilema a pro vznik spolupracujících strategií je ale důležité, aby hráči nevěděli, kolikrát se bude vězňovo dilema opakovat (jinak se vyplatí v posledním kole zradit, díky tomu se ale vyplatí zradit i v předposledním kole, atd.).

Strategie pro iterované vězňovo dilema

Pro iterované vězňovo dilema existuje několik jednoduchých strategií:

  • Always Defect - hraje vždycky zradu nezávisle na druhém hráči (ve zdrojových kódech je nazvána Always Deceive)
  • Always Cooperate - vždy spolupracuje nezávisle na tom, jak hraje druhý hráč 
  • Random - hraje náhodně
  • Tit-for-tat - v prvním kole spolupracuje, v dalších hraje to, co hrál protihráč v předcházejícím kole, tj. zradí, pokud zradil (oplácí zradu), a spolupracuje, pokud spolupracoval

Samozřejmě lze vymyslet ještě spoustu dalších strategií. Pro inspiraci se můžete podívat do Axelrodova článku o turnaji, který provedl v 80. letech.

Soutěž na cvičeních

V dnešních zdrojových kódech najdete jednoduchý prográmek, který spouští turnaj strategií, které najde v daném adresáři. Očekává, že strategie je java .class soubor (zkompilovaná Java), ve kterém je třída, která je potomkem třídy Strategy. Jméno třídy si vyberte sami, nějaké unikátní (třeba svůj login). Ve třídě potom implementujte metody getName a getAuthorName, které vrací jméno strategie respektive jméno autora.

Dále musíte implementovat metodu reset, která se volá vždy po skončení hry proti jiné strategii (předtím, než začnete hrát s jinou strategií). Nejdůležitější metodou je nextMove, která vrací váš další tah. Vracejte konstanty Move.COOPERATE nebo Move.DECEIVE. Skrz metodu reward se dozvíte po každém tahu, jak hrál váš soupeř a kolik jste dostali bodů.

Na začátku souboru evolution.prisoner.strategies.PrisonerDilemma je nastaven adresář, ve kterém se hledají strategie. Je nastaven na místo, kam strategie ukládá prostředí IntelliJ IDEA. Pokud používáte jiné prostředí, změňte tuto cestu podle jeho nastavení (např. v Eclipse by to mělo být build/classes/evolution/prisoner/strategies).

Last modified: Monday, 22 October 2018, 10:13 PM