Vězňovo dilema - strategie

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 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:

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
• 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 adresáři strategies. Očekává, že strategie je Pythonovský soubor, ve kterém je funkce create_strategy(). Tato funkce vrací samotnou strategii, jako objekt s metodami reset, last_move, author_name, a strategy_name. Jméno souboru a strategie si vyberte sami, nějaké unikátní. Ve třídě potom implementujte metody strategy_name a author_name, které vrací jméno strategie respektive jméno autora (vaše).

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 play, která vrací váš další tah. Vracejte konstanty C nebo D. Skrz metodu last_move se dozvíte po každém tahu, jak hrál váš soupeř.

V __main__ bloku v souboru tournament.py je nastaven adresář, ve kterém se hledají strategie.

Úkol

Dnešní úkol je jednoduchý - napište a pošlete strategii pro vězňovo dilema. Pokud pošlete nějakou strategii už do turnaje během cvičení a nechcete ji měnit, nemusíte posílat nic dalšího.

Termín:

pondělí 4. 3. 2024 15:00 (potom pustím turnaj)

Body:

• 7 bodů za poslání libovolné strategie
• Další body lze získat za umístění v turnaji
  • nejlepších 20 % - 3 body
  • nejlepších 21-40 % - 2 body
  • nejlepších 41-60 % - 1 bod