čtvrtek 18. srpna 2011

Opakované vězňovo dilema: simulace


Na konci tohoto článku je výzva k účasti v soutěži (odměnou je pouhá čest, nicméně i to může být dostatečnou motivací pro vlastníky soutěživého ducha). Pokud vás tedy úvod článku zaujme, ale nezbyde vám trpělivost přečíst jej celý, podívejte se aspoň na závěrečnou sekci.

Nedávno jsem dočetl Dawkinsův Sobecký gen, kde mě zaujal popis experimentu, který provedl Robert Axelrod, a jehož cílem bylo zjistit, jak si vedou různé strategie hrající vězňovo dilema (dále jen VD). (O vězňově dilematu jsem již relativně nedávno psal, nicméně jestli si nejste jisti, v čem VD spočívá, nebo co se přesně míní strategií, dozvíte se to níže.) Nepodařilo se mi najít Axelrodův vlastní popis experimentu, a tak nabízím aspoň Dawkinsovu parafrázi [*]:

Strategie přípustné v opakovaném VD jsou zjevně omezeny pouze naší vynalézavostí. Můžeme zjistit, která je nejlepší? To byla otázka, kterou si Axelrod položil. Dostal zábavný nápad uspořádat soutěž, a vyzval experty přes teorii her, aby předložili strategie. Strategie, v příslušném smyslu, jsou naprogramovaná pravidla pro konání, a tak bylo vhodné, aby účastníci posílali své vstupy v programovacím jazyce. Bylo předloženo čtrnáct strategií. Pro jistotu Axelrod přidal patnáctou, nazvanou „Náhodná“, která prostě vybírala své tahy náhodně, a sloužila tak jako jakási základní „nestrategie“: jestli strategie neumí uhrát lepší výsledky než Náhodná, je jistě dost špatná.

Axelrod přeložil všech patnáct strategií do jednoho programovacího jazyka a nechal je běžet vzájemně proti sobě na jednom velkém počítači [*]. Každá strategie byla spárována se všemi ostatními (všetně kopie samy sebe) a sehrála opakované VD. Poněvadž bylo 15 strategií, na počítači běželo 15x15, tj. 225 jednotlivých zápasů. Poté, co každý pár prošel 200 tahy zápasu, zisky byly sečteny a vyhlášen vítěz.


Což mě vedlo k myšlence Axelrodův pokus zopakovat. Výhodou je, že si dnes vystačím s docela malým počítačem. Na druhé straně nemám snadný přístup k vedoucím expertům přes teorii her, a tak jsem se musel smířit s okruhem svých známých. Dále následuje popis a výsledky mého experimentu.

Především, VD je popsáno v mém již výše odkazovaném článku (nebo kdekoli jinde na webu). Pro účast v zamýšleném experimentu ovšem stačilo znát následující pravidla:

Základní informace: Strategií v následujícím textu myslíme program poskytnutý účastníkem soutěže nebo vytvořený podle jeho instrukcí. Strategie se utkávají navzájem v párech a hrají proti sobě standardní VD; každou takovou jednotlivou hru nazývám tahem. V každém tahu mají obě soupeřící strategie na výběr dvě možnosti, tradičně nazývané spolupráce a zrada (je dobré ignorovat konotace těchto slov). V závislosti na svém rozhodnutí získají strategie určitý počet bodů. Konkrétně:

  • Jestliže obě strategie hrají spolupráci, obě získají po 4 bodech.
  • Jestliže obě strategie hrají zradu, získají obě po 1 bodu.
  • Jestliže strategie hrají různě, pak ta, která hrála zradu, obdrží 7 bodů a ta, která hrála spolupráci, obdrží 0 bodů.


Jak bude posuzována úspěšnost: Navržené strategie se utkají proti sobě každá s každou v jednom zápase. (Na rozdíl od zmíněného Axelrodova experimentu strategie nenastupují proti kopiím sebe samých.) Každý takový zápas bude mít N tahů, kde N je pevné číslo stejné pro všechny zápasy. Například, bude-li N=10, sehrají každé dvě strategie zápas na deset tahů a v každém z nich musí zvolit jednu z možností {spolupráce, zrada}. (N je ve skutečnosti různé od 10, ale jeho přesnou hodnotu se účastníci dozvědí až po zaslání strategií.) Strategie se nakonec seřadí podle získaných bodů (dle pravidel bodování uvedených výše) ve všech tazích všech zápasů. Nerozhoduje tedy počet vyhraných zápasů. Například, strategie, která dvakrát prohraje 74:76 a 50:100 na tom bude v celkovém hodnocení lépe než strategie, která dvakrát vyhraje 60:30 a 51:50.

Jak může vypadat strategie: Nejjednodušší strategie jsou „vždy spolupracuj" a „vždy zraď“. Strategie si ale může pamatovat historii interakce se svým soupeřem v rámci jednoho zápasu, tudíž například jsou možné strategie „zraď, ale pokud v předchozím tahu soupeř zradil, spolupracuj“, nebo „pokud počet soupeřových zrad v předchozích tazích převyšuje počet jeho spoluprací, zraď, jinak spolupracuj“. Strategie může být plně nebo částečně náhodná: „zraď se 75% pravděpodobností“, nebo „spolupracuj, ale pokud soupeř v předchozím tahu zradil, zraď s 25% pravděpodobností“ jsou platné strategie. Zápasy náhodnách strategií se budou simulovat s užitím pseudonáhodného generátoru. Strategie může záviset explicitně na číslu tahu, jako např. „spolupracuj kromě 124. tahu, kdy zraď“. (Pokud N<124, podmínka se samozřejmě nikdy nerealizuje.)

Jak strategie nemůže vypadat: Strategie nemohou mít přístup k údajům z jiných zápasů: „pokud soupeř vyhrál poslední zápas, vždy zraď“ je nepřípustná strategie. Strategie nevidí dovnitř ostatních strategií, což vylučuje např. „pokud soupeřova strategie je vždy bezpodmínečně spolupracovat, zraď“. Netřeba dodávat, že strategie zná jen výsledky minulých tahů, ne toho současného, nelze tedy „zraď, pouze pokud v témže tahu soupeř také zradí“. Strategie jsou anonymní, nelze tedy „zraď, ale pokud hraješ proti strategii, kterou navrhl buddhista, spolupracuj“. Strategie nezná hodnotu N, a nemůže k němu přistupovat ani nepřímo. Nezle tedy „zraď v posledním tahu“.


Došlo mi těchto pět strategií (jmény jsem je vybavil já podle jejich nápadných vlastností, nikoli jejich autoři):

  • (Mstivá): Spolupracuj do první zrady soupeře, nebo do pátého tahu. Od šestého tahu zrazuj vždy.
  • (Benevolentní): V prvním tahu spolupracuj. Poté spolupracuj, pokud soupeř spolupracoval aspoň ve dvou třetinách předchozích tahů.
  • (Složitá): V každém třetím tahu spolupracuj s pravděpodobností 40%. Jindy spolupracuj, právě tehdy když soupeř spolupracoval v obou dvou předchozích tazích. V prvních dvou tazích spolupracuj vždy.
  • (Oko za oko): Udělej to, co soupeř dělal v minulém tahu. V prvním tahu spolupracuj.
  • (Náhodná): V prvním tahu spolupracuj. Potom spolupracuj s pravděpodobností 1/3, pokud soupeř v předchozím tahu spolupracoval, a s pravděpodobností 1/10, pokud soupeř v předchozím tahu zradil.

Číslo N jsem předem stanovil na 188. Takto vypadala tabulka pro sehrání všech zápasů:


M B S O N celkem bilance pořadí
M 221:200 337:176 209:202 292:187 1059:765 4-0-0 1,41 4
B 200:221 588:875 752:752 351:218 1891:2066 1-1-2 2,51 1
S 176:337 875:588 320:313 331:324 1702:1562 3-0-1 2,26 2
O 202:209 752:752 313:320 271:271 1538:1552 0-2-2 2,05 3
N 187:292 218:351 324:331 271:271 1000:1245 0-1-3 1,33 5



Sloupec označený ∅ shrnuje průměrný bodový zisk na jeden tah. Teoretické maximum je sedm bodů, ale aby strategie dosáhla tohoto výsledku, musely by všechny její soupeřky spolupracovat bez ohledu na její vlastní permanentní zrazování. Maximum, kterého mohou dosáhnout všechny strategie zároveň, je pět bodů. Jeden bod je maximum, které se dá zaručit bez ohledu na soupeře: strategie „vždy zraď“ si nemůže vést hůře. Dá čekat, že pokud účastníci nebudou příliš hloupí, dosáhnou průměrů někde mezi jedním a pěti body.

Axelrod dělil strategie do kategorií „nice“ a „nasty“; chtele-li, „slušné“ a „svinské“. Slušná strategie nikdy nezradí dříve než její soupeř (může ale zrazovat v odvetě). Svinská strategie naopak klidně podrazí jako první. Vzhledem k této definici jsou z pěti účastnic svinské tři: M, S a N; B a O jsou slušné. Přítomnost sviní je důležitá, protože dělá hru zajímavou: slušné strategie spolu vždy spolupracují, a pokud jsou ve hře samé slušné strategie, skončí soutěž nudnou všeobecnou remízou s průměrným ziskem čtyř bodů na tah.

Svinskost či slušnost ještě neříká nic moc o tom, jak často strategie spolupracuje nebo zrazuje. Když se spolu utkají strategie „v prvním tahu zraď a pak spolupracuj“ a „spolupracuj až do první zrady soupeře, pak zrazuj“, ta první, ač technicky svině, ve většině tahů spolupracuje, zatímco druhá, ač technicky slušná, ve většině tahů zradí. Nicméně podívejme se na výsledky experimentu.

Vede se lépe strategiím svinským, nebo slušným? Je lepší spolupracovat, nebo zrazovat? Slušné strategie obsadily první a třetí místo, což není špatné — navzdory intuici, že být svině se vyplácí. Podívejme se na příčiny úspěchu či neúspěchu jednotlivých strategií detailněji.

Vítězná Benevolentní strategie vděčí za svůj úspěch své ochotě spolupracovat. Dokázala vyhrát pouze jeden zápas, ale kromě zápasu se Mstivou strategií byly její zisky vždy tučné. Jako slušná strategie si rozdělila pěkných 752 bodů za remízu s druhou slušnou strategií Oko za oko. Její síla spočívala právě v její benevolentnosti v souboji se strategiemi S a N. Tyto strategie občas zradily bezdůvodně, ale také se mstily za zradu. Zatímco B občasnou zradu přehlédla a pokračovala ve spolupráci, O spustila řetězec odvet, na kterém obě soupeřky tratily.

Složitá strategie na první pohled nevypadá moc rozumně. Čím vysvětlit tu bizarní vášeň pro třítahové periody? Přesto, tři vítězství mluví v její prospěch. Složitá strategie dokázala efektivně parazitovat na benevolentnosti pozdější vítězky a 875 bodů z tohoto souboje bylo klíčovým elementem úspěchu.

Oko za oko je klasická stabilní strategie, která v podobných střetnutích okupuje pravidelně přední příčky. (V Axelrodově pokusu byla strategií vítěznou.) Zde nezvítězila, a hlavním důvodem byla její přílišná mstivost. Oko za oko nabízí jistotu, že všechny její zápasy dopadnou remízou nebo prohrou o sedm bodů. Aby O byla lepší, než B, musely by ve hře být svině, které dokáží efektivně parazitovat na slabosti B. V tomto případě tomu tak nebylo.

Mstivá strategie je svině nejen v technickém smyslu, ale i ve smyslu praktickém: v 188 tazích zradí přinejmenším 183 krát. To by se mohlo vyplatit, kdyby soupeři byli extrémně naivní. Jelikož nejsou, aktivuje tato strategie nejpozději od sedmého tahu sérii vzájemných zrad, odkud plyne skromný zisk jednoho bodu na tah. Mstivá strategie dokázala ve vzájemném zápase porazit všechny své protivnice, ale její nejvyšší zisk v zápase byl ubohých 337 bodů. Poučení je nasnadě: snažit se v každém obchodě oškubat svého partnera nemusí být ideální cesta ke zbohatnutí. (Neúspěch Mstivé strategie padá z velké části na vrub absurdně nízkému pořadí tahu, ve kterém začíná zrazovat, a to padá na vrub triviálnímu omylu. Autor této strategie původně zaslal „spolupracuj do první zrady soupeře, a vždy zraď v posledním tahu“. Poté, co byl upozorněn na to, že strategie nemá prostředky k poznání, že nastal poslední tah, opravil autor hranici počátku zrazování z posledního na pátý tah, zřejmě věře tomu, že počet tahů se bude pohybovat někde těsně nad pětkou. Stejná strategie, která ovšem začíná zrazovat později, je naopak velmi úspěšná, jak bude vidět níže.)

Náhodná strategie byla ze všech jednoznačně nejhorší, což lze přičíst faktu, že byla jejím autorem stvořena v časové tísni během několika málo minut. I když se nejedná o stejnou Náhodnou strategii jako v případě Axelrodova pokusu, má k ní docela blízko: citlivost na tah soupeře je velmi malá, pravděpodobnosti 1/3 a 1/10 jsou si docela blízké. Krom malé citlivosti je jejím problémem i silná tendence zrazovat.

Přirozený výběr

Uvažme, že naše strategie nejsou programy soupeřící o abstraktní body, ale živočichové soupeřící o živiny potřebné k rozmnožování. Jak si povedou jednotlivé strategie v mnohageneračním souboji o přežití? I to se již zkoušelo. Znovu cituji ze Sobeckého genu:

Axelrod vzal 63 strategií a vhodil je do počítače, čímž získal „generaci 1“ evoluční sukcese. V „generaci 1“ proto „klima“ sestávalo rovným poměrem ze všech 63 strategií. Na konci generace 1, zisky každé strategie byly vyplaceny, ne jako „peníze“ nebo „body“, ale jako potomci shodní s jejich (asexuálními) rodiči. Jak šly generace, některé strategie se stávaly vzácnějšími a nakonec vyhynuly. Jiné se staly četnějšími. Jak se měnily početní poměry, tak se v důsledku měnilo „klima“, ve kterém se odehrávaly následné tahy hry.

Jak si v takovém souboji [1] vedou naše strategie? Obrázek lepší popisu.





Barvy: černá M, červená B, zelená S, modrá O, oranžová N. Mstivá a Náhodná strategie rychle vymírají, Benevolentní strategie i zde jasně dominuje. Dokud je přítomna Mstivá, Oko za oko si vede lépe než Složitá, ovšem po vymizení M má S výhodu v podobě vyšších zisků ze soubojů s B a pomalu, ale jistě, získává navrch. Poměr zhruba 7:3 mezi B a S je nadále stabilní. V zásadě tak získáváme stejné pořadí jako v jednorázovém souboji.

Přirozený výběr s mutacemi

Napsal jsem, že Mstivá strategie by si vedla lépe, kdyby začala zrazovat později, než v pátém tahu. Což tedy hnout s hodnotami parametrů u zadaných strategií? Strategie obsahují tyto parametry:

  • (Mstivá): jeden parametr, číslo tahu, ve kterém začíná zrazovat (původně 5).
  • (Benevolentní): jeden parametr, relativní četnost soupeřovy spolupráce nutná pro spolupráci (původně 2/3).
  • (Složitá): jeden parametr, pravděpodobnost zrady v každém třetím tahu (původně 3/5).
  • (Oko za oko): žádný volný parametr.
  • (Náhodná): dva volné parametry, pravděpodobnost spolupráce po soupeřově spolupráci a zradě (původně 1/3 a 1/10).

V další simulaci stály na začátku znovu proti sobě populace našich pěti strategií, ale tentokrát nebyli všichni jedinci stejní: každý měl náhodně vybranou hodnotu svých parametrů [2]. Nyní vidíme odlišné výsledky.





Barvy: černá M, červená B, zelená S, modrá O, oranžová N. Na rozdíl od předchozího se nedaří Složité strategii, která doprovodí Náhodnou rychle do propadliště dějin. Benevolentní strategii se daří v jejich společnosti (vzpomeňme na vysoké skóre 588:875 z jejich prvního vzájemného zápasu), ale jakmile populace S vymizí, začne ji B velmi pomalu následovat, jsouc vykořisťována Mstivou strategií. Té se daří ze všech úplně nejvíc. Oko za oko si drží stabilní pozici.





Zajímavý je populační vývoj v rámci Mstivé strategie; na obrázku 1. a 10. generace. (Vodorovná osa: hodnota parametru, svislá osa: četnost.) Zcela svinské varianty, které zrazují od samého začátku (a kam patřila původní strategie s parametrem rovným pěti), rychle mizí. Dokud existují naivní strategie C a E, začátek zrazování kolem 50. tahu je zatím výhodný, což je vidět na prosperující populaci s touto hodnotou parametru na obrázku vpravo.





V pozdějším vývoji, vlivem vymizení naivních strategií, následuje posun v začátku zrazování k cca. 90. tahu. (Mutace mohou posunout řídící parametr i přes stovku; takové strategie se chovají stejně, jako kdyby byl řídící parametr roven 100). Na obrázcích 30. a 99. generace.





Populační vývoj v rámci Benevolentní strategie: 1. a 10. generace. (Vodorovná osa: hodnota parametru v procentech, svislá osa: četnost.) Žádný selekční tlak není patrný, všechny hodnoty parametru zdánlivě prosperují stejně.





Totéž, 50. a 99. generace. Množina se rozpadla na několik podpopulací, pravděpodobně z čistě náhodných příčin (srovnejte s podobným obrázkem pro strategii O, kde žádné selekční tlaky být nemohou).





Populační vývoj v rámci Složité strategie: 1. a 10. generace. (Vodorovná osa: hodnota parametru v procentech, svislá osa: četnost.) Rozhozením parametrů strategie utrpěla a rychle vymírá.





Populace prošla úzkým hrdlem v 17. generaci (vlevo), kdy přežívalo pouhých 10 jedinců. Poté následovalo období relativní prosperity, kdy populace vzrostla na maximum 58 jedinců v 52. generaci, poté následovalo rychlé vyhynutí. Zajímavé je, že nejdéle přežila podpopulace kolem nuly (tj. taková, co v každém třetím tahu vždy spolupracuje) a izolovaná populace v okolí šedesátiprocentní pravděpodobnosti, což je shodou okolností hodnota zadaná autorem. Měl autor šťastnou ruku, nebo je za tím složitá analýza?





Populační vývoj v rámci strategie Oko za oko: 1. a 99. generace. I tato strategie byla rozdělena na podpopulace s různými hodnotami parametru, ten se ale zde nijak neprojevuje. Obrázek vpravo tak představuje typický projev rozdělení parametru v případě plné absence selekčních tlaků. (Vlevo je první tah - hodnoty parametru jsou generovány rovnoměrným rozdělením na intervalu 0-100. Kdyby nebylo mutací, bylo by na místě čekat, že některé hodnoty rychle vyhynou a již nikdy se neobjeví; pravý obrázek by tak měl méně teček umístěných výš. Mutacemi vznikají shluky okupující několik vzájemně blízkých hodnot parametru.)





Rychle vymírající Náhodná strategie: 1. a 13. generace. Svisle první parametr v procentech (nahoře 0, dole 100), vodorovně druhý (vlevo 0, vpravo 100). Vymření proběhlo tak rychle, že je těžko usuzovat na to, které hodnoty parametru jsou optimální.

Jiné počáteční podmínky

Co když počáteční hodnoty parametrů nebudou rozhozeny náhodně? Níže vidíme tři různé nenáhodné počáteční situace.





Situace při „přátelských“ počátečních podmínkách: tentokráte měly všechny strategie v první generaci ty hodnoty parametrů, které nejvíc favorizují spolupráci a odpouštění. Veškerá variabilita parametrů je pouze a jen důsledkem mutací. Barvy: černá M, červená B, zelená S, modrá O, oranžová N. Vývoj je plný zvratů, nejúspěšnější jsou M a B.





Situace při „agresivních“ počátečních podmínkách — počáteční hodnoty parametrů favorizují zradu a mstivost. Zde je vývoj mnohem jednoznačnější, M, S a N velmi rychle vyhynou, v populaci zůstanou pouze B a O. Populace všech strategií dohromady by se ve skutečnosti držela mnohem níže než v předchozím případě (na zradu doplácejí všichni). Tomu jsem zabránil změnou populaci regulujícího parametru; příliš malé populace jsou příliš citlivé na náhodné fluktuace.





Poslední situace zachycuje „ideální“ počáteční podmínky, tj. hodnoty parametrů, které byly nejúspěšnější v předchozích simulacích. Mstivé strategii se dařilo nejlépe, když začínala zrazovat v 90. tahu, a tak má počáteční hodnotu parametru rovnou 90. Benevolentní si vedla dobře ve své původní podobě, a tak začíná s hodnotou 67. Složitá nejlépe přežívala, pokud se zcela vyvarovala nevyprovokovaných zrad, a tak začíná s nulou. Nejsem schopen říct, jaké hodnoty parametrů byly nejlepší pro Náhodnou strategii, ale pokud je stanovíme na 100 a 0, bude tato strategie identická se strategií Oko za oko, která si vedla vždy lépe než jakákoli verze Náhodné. (Na začátku tak budeme mít dvakrát víc jedinců typu Oko za oko, jen polovina z nich však může mutovat).

Znovu vidíme komplikovaný obrázek, ve kterém je těžko poznat, která strategie je lepší. Favorit předchozích střetnutí, Benevolentní strategie, je trochu překvapivě první a jedinou, které se „podaří“ vyhynout během tří set generací. Moc se nevede ani Náhodné strategii: mutace měnící ideání Oko za Oko na podobnou, leč částečně náhodnou strategii, nejsou výhodné, a O je tak oproti N zvýhodněná svou stabilitou vůči mutaci. Paradoxně se daří Složité strategii, která je zbavena své náhodné složky a funguje teď téměř jako dle zásady „dvě oči za oko“.

Další opakování

Chcete si také zkusit vymyslet strategii? Máte možnost. Pokud mi v reakci na tento článek mejlem dojde dostatečné množství strategií, provedu s nimi simulaci. Toto jsou pravidla pro účast:


  • Každý člověk smí nasadit do hry pouze jednu strategii.
  • Strategie může být popsána normálním jazykem, ale musí být popsána tak, aby bylo možné ji jednoznačně algoritmizovat.
  • Strategie zasílejte mejlem na koroptew zavináč seznam tečka cz, nepište je do komentářů (ostatní účastníci nesmějí znát, co proti nim soupeři chystají). Do předmětu uveďte „Strategie“.
  • Dojde-li stejná strategie od dvou nebo více lidí, bude i tak nasazena pouze jednou.
  • Autor strategie může rozhodnout, chce-li soutěžit anonymně, nebo chce-li naopak uvést své jméno.
  • Můžete poslat i strategii, která je popsána v tomto článku. Originalita se nevyžaduje.
  • Autoři zde uvedených strategií se pochopitelně mohou účastnit znovu.
  • Soutěže se automaticky účastní Plně náhodná strategie, tedy strategie, která v každém tahu zradí nebo spolupracuje s 50% pravděpodobností.
  • Strategie se utkají nejprve každá s každou podle schématu popsaného v první části článku, a poté v evolučním souboji podle pravidel popsaných v poznámce [1] (velikosti populací mohou být jiné, v závislosti na počtu podaných strategií). Platí všechna pravidla popsaná v tomto článku, s těmito změnami:

    • Zisk při oboustranné spolupráci je 5 bodů, nikoli 4 body.
    • Počet tahů v zápase je známý a roven 100.
    • Počet generací v evolučním souboji je 100, vítězem je strategie s největší populací ve sté generaci.

  • Soutěž proběhne poté, co se sejde aspoň osm strategií, ne ale dříve, než na začátku září. Již se sešlo dostatečné množství strategií, probíhá jejich závěrečné testování. Do konce srpna ještě lze posílat další strategie, poté bude soutěž uzavřena.

Pamatujte: úspěch strategie závisí na tom, kdo jsou její soupeři. Pokud se strategii dařilo v tomto článku, neznamená to, že se jí bude dařit i v opakovaném pokusu.



Poznámky:
1. Přesnější popis simulace: Na počátku bylo 200 kusů od každé strategie, celkem tedy 1 000 kusů. Ty byly náhodně spárovány do dvojic a každá dvojice absolvovala stotahový zápas. Po skončení všech zápasů se u každé ze strategií sečetly body, které získaly všechny její kopie v zápasech. Druhou generaci tvořilo znovu tisíc strategií (až na zaokrouhlovací chybu), ovšem tentokráte s četnostmi odpovídajícími poměru bodových zisků z první generace. Analogicky v dalších generacích.
2. Přesnější popis simulace: Na počátku bylo 200 kusů od každé strategie. Každému jednotlivému kusu byly náhodně nagenerovány dva parametry s hodnotami rozloženými rovnoměrně od 0 do 100 (u strategií, kde parametr má interpretaci pravděpodobnosti nebo poměru, určuje generované číslo jejich hodnotu v procentech; u strategie M určuje, v kolikátém tahu nejpozději zradí). Druhý parametr využívala prakticky pouze strategie N, strategie O ignorovala hodnotu obou parametrů. V každé generaci byly existující strategie náhodně spárovány do dvojic a každá dvojice absolvovala stotahový zápas. Poté bylo vytvořeno tolik identických kopií strategie, kolik ta získala bodů. Poté prošla každá kopie filtrem, ve kterém mohla být s určitou pravděpodobností zničena; tato pravděpodobnost byla pro všechny kopie stejná a závisela nepřímo úměrně na velikosti celkové populace. (Celková populace tedy nebyla vázána na hodnotě 1 000 jako v předchozí simulaci). Přeživší kusy byly předány do další generace s určitým rizikem mutace: s dvacetiprocentní pravděpodobností se pohnula hodnota každého z obou jeho jeho parametrů o 1 náhodným směrem.

8 komentářů:

  1. Moc zajímavý, díky. Asi ještě zkusim nějakou strategii vymyslet.

    OdpovědětVymazat
  2. Zajímavé. Zkusím něco vymyslet.

    OdpovědětVymazat
  3. Možná by Vás mohl zajímat tento článek kritizující Axelrodův přístup:
    http://www.sciencedirect.com/science/article/pii/016726819290040I

    Ve zkratce je argumentace článku následující:
    1) V Axelrodově simulaci se hrála konečná hra (Přestože účastnici nevěděli kolik kol budou hrát s daným soupeřem, výplatní matice nebyla definována pomocí sumy výplat diskontované pravděpodobností pokračovaní hry, ale jako v konečné hře s daným počtem kol).
    2) Platí, že pokud replikační dynamika konverguje, pak konverguje k Nashově rovnováze, přičemž do úvahy bereme pouze strategie, které jsou účastny na začátku hry.
    Z) Pokud je tedy přítomna strategie "vždy zraď" a hra konverguje, pak nepotřebujeme žádnou simulaci a víme, že zůstanou jen strategie, které zrazují.

    Axelrodovy výsledky jsou dány tím, že na začátku se sešly v podstatě jen slušné strategie.

    Zajímavé je, že v průběhu simulace to může vypadat, že určitá strategie téměř vyhynula, přestože ve finále převládne (Samozřejmě, pokud zaokrouhlování nezpůsobí, že zmizí úplně).

    Jsem zvědav, jestli to Vaše simulace povtrdí.

    OdpovědětVymazat
  4. Aniž jsem zatím četl odkazovaný článek:

    Pokud tvrzení Z znamená, že (v případě konečné hry, za předpokladu eliminace výhynů vlivem fluktuací) je-li přítomna "vždy zraď", jediné finální stabilní rozložení populace obsahuje pouze ji a strategie, které se v dané populaci chovají ekvivalentně, nezávisle na počátečním rozdělení populací? To mi připadá krajně podezřelé.

    Uvažujme, že v populaci jsou pouze "vždy zraď" (VZ) a "oko za oko" (OO), hraje se na 100 tahů. Zisky dle mých pravidel jsou: OO vs. OO 700:700, VZ vs. VZ 100:100, OO vs. VZ 99:106. Jsou-li VZ a OO zastoupeny v poměru A:B, je střední zisk VZ 100A + 106B, a střední zisk OO je 99A + 700B. To nám dává rovnovážný poměr A:B roven 594:1. Pokud tedy bude počáteční podíl OO v populaci vyšší, než cca. 0,17%, VZ asymptoticky vyhyne.

    (Můžete ovšem nominovat VZ do hry, jestli jí věříte.)

    OdpovědětVymazat
  5. Máte pravdu. Moje chyba, zapomněl jsem důležitý předpoklad, že potřebujeme dostatečně širokou paletu strategií, které někdy začnou zrazovat. Je to už dlouho, co jsem ten článek četl.

    Uvažujme hru, která se hraje N kol. Závěr bude platit pokud máte např. 1) strategii, která hraje OO a zrazuje v kole N; 2) strategii, která hraje OO a zrazuje v kole N-1 atd.

    Každopádně kooperace v Axelrodově simulaci vznikne v důsledku omezení množiny strategií.

    OdpovědětVymazat
  6. To je pravda.

    Navíc v předchozím mělo být, že OO vs. OO je 400:400 a rovnovážný poměr je 294:1.

    OdpovědětVymazat
  7. Nedalo mi to a poslal jsem svoji strategii. Detaily neprozradím a jsem moc zvědav, jak si povede...

    OdpovědětVymazat