Vězňovo dilema - výsledky turnaje

Jsou zde výsledky turnaje v opakovaném vězňově dilematu! (Pokud nevíte oč jde, přečtěte si příspěvek, ve kterém byl turnaj avizován, nebo alespoň jeho konec. Pravidla jsou popsána tam.)

Sešlo se celkem jedenáct soupeřících strategií (dvanáctá přišla pozdě a bude tak vyhodnocena pouze neoficiálně). Následuje seznam strategií.

Strategie jsou očíslovány v pořadí, v jakém jsem je obdržel. Jméno autora uvádím prioritně to, o jaké požádal. Nevyjádřil-li autor preference, uvádím jméno, které jaké používá ke komentování na tomto blogu. Jestliže autor dosud nekomentoval, nebo pokud se mi nepodařilo přiřadit mejl k přezdívce komentátora, uvádím jméno uvedené v mejlu. Jeden autor požádal o anonymitu. Omlouvám se, pokud jsem špatně doplnil diakritiku u jmen, která došla bez ní.)

• S1 (zaslal Matúš Šimkovič): Pokud jsem v minulém tahu spolupracoval, nechť p je relativní četnost soupeřových spoluprací po mé spolupráci. Pokud jsem zradil, nechť p je četnost soupeřovy spolupráce po mé zradě. Nelze-li tyto relativní četnosti spočítat, nechť p = 1/2. Nechť dále E_s = 5p - 7 a E_z = 6p - 6. Spolupracuji s pravděpodobností exp E_s / (exp E_s + exp E_z).
  

Pravděpodobně se jednalo o nejzajímavější strategii a za pozornost stojí i autorův doprovodný komentář, k němuž se ještě vrátím po uvedení výsledků.

Pravdupovediac nemám veľké očakávnia čo sa týka úspechu tohoto modelu, hlavne tá markovská sieť je veľmi tupý model, HMM alebo niečo komplexnejšie by dávalo väčší zmysel. Myslím, že skôr bude zaujímavé ako si povedie probabilistický model proti tým deterministickým. Teda vo vzájomných zápasoch. Evolúciu je veľmi ľahké vyhrať pomocou nepotizmu (pozdravný kód na začiatku série a potom spolupracovať so súkmeňovcami).

Další strategie:

• S2 (zaslal čtenář Stan): Zrazuji, pokud soupeř zradil alespoň třikrát, nebo pokud zradil v prvním tahu. Jinak spolupracuji.
  
• S3 (anonymní): V prvním tahu zradím a v druhém spolupracuji. Jindy, pokud v předchozích dvou tazích soupeř hrál stejně, hraji to, co hrál soupeř v předchozích dvou tazích. Pokud soupeř hrál různě, hraji opak toho, co jsem sám hrál v minulém tahu.
  
• S4 (zaslal Adam Pekár): Spolupracuji v prvních třech tazích, zrazuji v posledních dvou. Jindy spolupracuji, právě tehdy když soupeř spolupracoval aspoň v 85% tahů.
  
• S5 (zaslal čtenář Satai): Spolupracuji v prvních třech tazích, zrazuji v posledním. Jindy spolupracuji s pravděpodobností rovnou relativní četnosti spolupráce soupeře.
  
• S6 (zaslal Martin Nuhlíček): V prvním tahu spolupracuji, jindy hraji to, co soupeř v minulém tahu. Po první zradě soupeře ovšem spolupracuji.
  
• S7 (zaslal čtenář Tasselhof): V prvním tahu hraji náhodně. V 2n. a 2n+1. tahu hraji to, co soupeř hrál v n. tahu.
  
• S8 (zaslal Matej Kačaljak): Zradím, pokud je splněna aspoň jedna z podmínek: a) soupeř zradil aspoň ve dvou ze tří předchozích tahů, b) pokud jsem sám v předchozím tahu zradil a předtím spolupracoval, c) pokud jsem nezradil ani jednou v předchozích deseti tazích. Vždy spolupracuji v tazích 20, 40, 60 a 80.
  
• S9 (zaslal Ladislav Dolinka): Mám dvě podstrategie. První je zradit právě tehdy když soupeř zradil v obou předchozích tazích (v prvních dvou tazích spolupracuji), druhá je zradit vždy po první zradě soupeře. Začnu první podstrategií. Po každém desátém tahu zjistím, zda můj zisk za posledních deset tahů leží mezi 16 a 34 body, pokud ano, vyměním podstrategii. Po výměně strategie vynuluji počítače zrad.
  
• S10 (zaslal Milan Mach): Tahy 1 a 2: spolupracuji. Tahy 3-29: hraji to, co soupeř v minulém tahu. Tahy 30-84: zradím, pokud soupeř zradil aspoň osmkrát, jinak hraji to, co soupeř v minulém tahu. Tah 85: zradím. Tahy 86 a 87: zradím, pokud soupeř zradil aspoň osmkrát, jinak spolupracuji. Tahy 88-97: Pokud soupeř zradil v tahu 87 nebo pokud zradil aspoň čtyřikrát, zradím, jinak spolupracuji. Tahy 98-100: zradím.
  
• S11 (zaslal Jan Mrzena): Tah 1: spolupracuji. Tah 2: dělám to, co soupeř v rahu 1. Tah 100: zradím. Jindy: když soupeř v minulém tahu zradil a já jsem spolupracoval v předminulém, nebo když soupeř zradil ve dvou předchozích tazích, zradím, jinak spolupracuji.
  

Po termínu došla klasika:

• S12 (zaslal čtenář benep9am): V prvním tahu spolupracuji, jindy hraji to, co soupeř v minulém tahu.
  

No a nakonec zde byla automaticky nasazená Plně náhodná strategie:

• S0 (automaticky ve hře): Spolupracuj s pravděpodobností 50%.
  

Ligový turnaj

Výsledky zápasů ligového turnaje a konečné pořadí jsou uvedeny v následujících tabulkách:







Vítězem se stala strategie S2, kterou zaslal čtenář Stan. Blahopřeji.

Neoficiální turnaj s účastí pozdě došlé strategie S12 by dopadl takto:





Rozdíly v pořadí (například výrazný posun S11 nahoru v druhé tabulce) jsou dány nejen účastí další strategie, ale i vlivem náhody. Při testování jsem turnaj nechal proběhnout několikrát a pořadí v čele se měnilo pokus od pokusu. (Tento fakt mě činí zranitelným vůči obvinění, že jsem simulaci opakoval tak dlouho, než dopadla tak, jak jsem si přál. Jako důkaz toho, že jsem to nedělal, mohu nabídnout pouze své slovo.)

Na co náhoda naopak vliv neměla, to je postavení strategií na chvostu, kde se usídlila má oblíbená S1 a spolu s ní S8. Tyto strategie dokonce dopadly hůř, než náhodná S0. Důvodem je přílišné zrazování. Tyto strategie sice vyhrávají většinu svých zápasů, ale vyhrávají je s malým celkovým ziskem. Mluví o tom jedna z Axelrodových zásad pro podobné hry: nebýt závistivý. Závistivostí se zde myslí touha mít víc bodů, než každý ze soupeřů ve vzájemné konfrontaci. To vede ke zkáze; mnohem lépe si vedou ti, kdo se spokojí s prohrou za oboustranně výhodnějších podmínek.

Druhé poučení je: nerozhodujte se náhodně. Nejlepší probabilistická strategie S5 je podprůměrná, S1 na své využívání náhodného generátoru doplatila ještě výrazněji. Házení kostkou do optimálního rozhodování nepatří.

Evoluční turnaj

Jak se dařilo strategiím v dlouhodobém přežívání? Výsledky jsou mírně odlišné od jednorázového turnaje. S2 získávala své úspěchy proti S0 a dalším náhodně zrazujícím strategiím. Ty však velmi rychle vyhynuly a zhruba od patnácté generace začíná S2 ztrácet. Evoluční turnaj vyhrála strategie S10, jejímu autoru blahopřeji! Konečné pořadí a graf následují:







(V grafu je S0 černá a ostatní jsou barveny od červené po zelenou, S1 je nejčervenější a S11 nejzelenější.) Strategie vymíraly v tomto pořadí: S1 a S8 (8. generace), S0 (9. generace), S5 (25. generace), S3 (28. generace), S7 (38. generace).

Sto generací byla příliš krátká doba nato, aby došlo ve vývoji k dramatickým zvratům. Možná by stálo za to nechat simulaci běžet déle. To jsem učinil, ovšem již ne pouze s jedenácti strategiemi figurujícími v této soutěži, ale s výrazně větší množinou strategií.

Československo proti zbytku světa

Samozřejmě mě zajímalo, jak by si vedli čtenáři tohoto blogu v konfrontaci s nějakou jinou skupinou. Uspořádal jsem tedy soutěž podle úplně stejných pravidel na blogu LessWrong [*], jehož mezinárodní čtenářská obec je o poznání rozsáhlejší než zde. Soutěže se zúčastnilo 21 strategií (plus Plně náhodná). Výsledky tamního turnaje a popis účastnických strategií najdete pod tímto odkazem. Zde uvedu pouze výsledky turnaje s účastí všech strategií, tj. jedenácti zdejších a jednadvaceti konkurenčních. Naše strategie jsou tentokráte označeny C1-C11, náhodná Z, konkurenční strategie pak vystupují pod písmeny A-U [*].




V ligovém turnaji se našim strategiím vedlo se střídavými úspěchy. Celkově naše strategie získaly v průměru 9297 bodů na zápas, konkurence pak 9702 bodů. Nejlépe dopadla jedenáctka na pěkném třetím místě, nejhůře se naopak dařilo jedničce, která ale stále nechala za sebou strategie označené jako U, Q a L. L byla strategie „vždy zraď“. U byla velmi podobná naší S1 (neboli C1): probabilistická strategie snažící se analyzovat pravděpodobnost, že soupeř zradí, spočítat střední zisk, a nakonec si hodit kostkou. Strategie P, Q a U se taktéž pokoušely o nepotismus: tj. spolupracovat s kopiemi sebe sama a zrazovat ostatní. To samozřejmě bylo málo platné v ligovém turnaji, kde se strategie samy se sebou nepotkaly, ale mělo to pomoct v turnaji evolučním.

V evolučním turnaji se z našich nejlépe dařilo S11. Následuje pořadí po sté generaci.







(Naše strategie jsou v grafu červené.)

I zde bylo sto generací příliš málo k tomu, aby se mohly projevit zvraty, kdy úspěšná strategie vyhubí svou hlavní „potravu“ a jakmile nemá koho vykořisťovat, začne sama vymírat. Proto jsem nechal stejnou simulaci běžet po dobu tisíce generací, a obrázek je mnohem zajímavější:





Na začátku vidíme přibližně stejný obrázek jako na předchozím grafu. Dokonce se na chvíli dostala do čela naše S11, potom se ovšem začíná projevovat změna prostředí, kdy vymírá řada neúspěšných strategií, a dopředu se dostávají strategie I a S4; S11 nakonec vymírá někdy po pětisté generaci. Ve hře zůstávají pouze I, S4 a O. Strategii O se nedařilo zrovna slavně na začátku turnaje, ale v okamžiku, kdy jedinými soupeři jsou I a S4, začíná profitovat. Strategie O totiž zradí již v devadesátém osmém tahu, zatímco I a S4 až v devadesátém devátém. Díky tomu získá O ve vzájemných zápasech s I a S4 o sedm bodů navíc, a tento rozdíl stačí k jejímu úspěchu. Kdyby se nechala simulace běžet o něco déle, zůstala by jedinou přeživší strategií.