[CZ] Vězňovo dilema II - simulace a evoluce

Minule jste si všichni naprogramovali svoji strategii pro vězňovo dilema, dneska si s vašimi strategiemi trošku pohrajeme. Zkusíme si nasimulovat život strategií, stejně jako to dělal Axelrod, a také si zkusíme vyvinout strategii proti nějaké skupině jiných strategií.

Pří dnešních cvičeních budete potřebovat strategie z minula a také vstupní soubory. Oboje je zabaleno v jednom archivu zde.(Archiv obsahuje i letošní verze souborů input-evolution.txtinput-sumulation.txt, které dejte do adresáře resources).

Simulace života strategií

Představme si, že máme populaci jedinců, kteří mezi sebou opakovaně hrají vězňovo dilema a na základě získaných bodů mají možnost se rozmnožit a přežít do další generace.

V takové simulaci můžeme objevit různé zajímavé věci. Například, existuje strategie, která ve všech případech přežije? Existuje nějaká skupina strategií, kterou nelze napadnout tím, že se objeví nová strategie?

Vezměme si například populaci, ve které všichni jedinci hrají podle strategie Always Cooperate (AC). Co se stane, když se najedou v populaci objeví jedinec, který bude hrát Always Deceive (AD)? Všichni AC strategie proti sobě vždy získají 3 body za každý tah. Nově příchozí AD získá ale za každý tah proti AC 5 bodů. Protože je AD jedna a AC je hodně, tak se stane to, že AD bude mít více bodů než AC a začne se v populaci množit. Zastaví se někdy množení AD nebo AD ovládne celou populaci? Co by se stalo, kdyby v populaci místo AC byly Tit-for-tat?

Simulaci života strategií máme implementovanou v package evolution.prisoner.simulation. Používá se k tomu framework evolučních algoritmů (ale bez operátorů). Každý jedinec je číslo, které ukazuje do tabulky strategií a určuje, jakou strategii bude hrát. Během jedné generace se potká s 10 (dá se nastavit v ga-prisoner-simulation.properties) náhodnými jinými jedinci a hrají spolu iterované vězňovo dilema. Jako fitness je každému přidělen součet získaných počtů bodů ze všech her. Nakonec se provede ruletová selekce a tím vznikne nová populace. Program postupně vypisuje, jaká strategie kdy vymřela, a nakonec vypíše počet jedinců strategií, které přežily. Počet jedinců hrajících jednotlivé strategie v počáteční populaci se dá nastavit v souboru input-simulation.txt.

Evoluce strategie

Mohlo by nás taky zajímat, jestli je možné najít strategii, která porazí libovolnou jinou skupinku strategií. Na tohle sice odpověď nenajdeme, ale můžeme se pokusit takovou strategii najít pomocí evolučních algoritmů.

V package evolution.prisoner.evolution máme připravené zdrojáky, které se o podobnou věc snaží. Je dost těžké vymyslet kódování jedince, který má reprezentovat strategii pro vězňovo dilema. V našem případě je jedinec kódovaný binárně a pamatuje si vždy svoje a oponentovy tři poslední tahy. Na základě těchto tahů se rozhoduje, jestli v následujícím kole bude spolupracovat, nebo jestli zradí. Je to tedy vektor 64 (2^6) binárních hodnot, na který se používají přístupy z prvního cvičení.

Samozřejmě se dá evoluce udělat i jinak, nejjednodušším způsobem může být využití evoluce k ladění nějakých parametrů libovolné strategie (třeba jak moc toleruji cizí zradu, nebo kolikrát zradím, když mě někdo jiný zradí).

Skupina strategií, proti kterým se snažíme vyvinout novou strategii, se dá nastavit v souboru resources/input-evolution.txt.

Last modified: Tuesday, 30 October 2018, 1:45 AM