úterý 6. září 2011

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 Es = 5p - 7 a Ez = 6p - 6. Spolupracuji s pravděpodobností exp Es / (exp Es + exp Ez).

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í.

19 komentářů:

  1. Tak aký názov to mala tá kapitola v Dawkinsovej knihe? "Komplikované stratégie skončia posledné"? :D

    Hynek: "Házení kostkou do optimálního rozhodování nepatří."
    S tým sa samozrejme dá polemizovať. Že v deterministickom prostredí sú lepšie deterministické stratégie tomu verím. Môžeme si však predstaviť probabilistickú VD, v ktorej na jednej strane správanie má určitú nedeterministickú efektivitu napr. 90 %, teda v 10 % sa agentovi v priemere nepodarí spolupracovať/zradiť. Na druhej strane agenti nemusia rozoznať čo druhí agenti robia,napr. keď agent zaznamená spoluprácu ako zradu (a naopak) v 10 % z prípadov. Takéto probabilistické prostredie samozrejme lepšie zodpovedá reálnemu prostrediu, kde sá takéto omyli dejú.

    OdpovědětVymazat
  2. Proč se domníváte, že v prostředí se šumem jsou deterministické strategie nevhodné? Nedeterminismus prostředí samozřejmě snižuje efektivitu strategií, není důvod se domnívat, že přidáním dalšího nedeterminismu do strategií samotných to vykompenzuje. Právě naopak.

    Do prostředí s desetiprocentním šumem bych nasadil třeba tohle: Pokud soupeř spolupracoval, spolupracuj, pokud zradil a nestalo se to v posledních n tazích víc než n/10+1 krát (pro všechna n), spolupracuj, jinak zraď. Je to deterministické, umí to odpouštět náhodné zrady, mělo by do slušně fungovat.

    Ale asi budu muset ještě někdy udělat turnaj se šumem.

    OdpovědětVymazat
  3. Aha tak to som zvrat "hádzanie kockou" trochu inak pochopil. Nevadí, lebo ani s predstavou, že hádzanie kockou pri tvorbe správania sa neoplatí nesúhlasím. Aj keď z iných dôvodov. Kritickým faktorom je tu skôr či sa moja stratégia učí alebo nie. Variabilita vo vlastnom správaní umožní stratégii nadobudnúť bohatšie skúsenosti a na základe týchto vylepšiť svoju stratégiu. Napríklad môže byť pre moju stratégiu optimálne spolupracovať, lebo v doterajšej historii protivník vždy spolupracoval. Avšak je možné že súper spolupracuje vždy aj keď ja zradím. Náhoda vo vlastnom správaní mi to umožní odhaliť.
    Dalšia nevýhoda deterministických stratégii je že sa ľahko dajú parazitovať keďže sú predvídateľné, akurát v prípade komplexnejších stratégii by som potreboval viacej pozorovaní (najlepšie naprieč fylogenézou), aby som mohol súpera modelovať. Koniec-koncov to jeden z dôvodov prečo evolúcia hádže kockou a prečo je pri hre kameň, papier, nožnice náhodny výber najoptimálnejšia stratégiou.

    OdpovědětVymazat
  4. Strategie může občas hodit experimentální zradu podle deterministického algoritmu a učit se tak deterministicky. (Na hraně hnidopišství je pak námitka, že pseudonáhodný generátor je ve skutečnosti deterministický algoritmus.) Je faktem, že předvídatelnost je nevýhodou jednoduchých deterministických strategií. Ne tak už u složitějších; např. deterministická strategie, která se sama učí, musí vypadat zvnějšku velmi nedeterministicky.

    Taktéž zůstává sporné, zda náklady na učení se nejsou vyšší než zisky z nabytých vědomostí. V této soutěži tomu tak jednoznačně bylo, kdyby ale existovala paměť napříč generacemi nebo přístup k výsledkům ostatních zápasů, mohlo by to situaci změnit. Přístup k datům z jiných zápasů ale zvýhodňuje strategie, které přenechají experminetování ostatním a samy poučeny se z jejich chyb jdou deterministicky cestou maximálního zisku.

    Nicméně máte asi pravdu, že někdy se může náhodnost vyplatit.

    OdpovědětVymazat
  5. dovoluji si upozornit na nasledujici, velmi zajimavy clanek

    http://www.pnas.org/content/early/2012/05/16/1206569109.full.pdf+html

    "Here, we
    show that such strategies unexpectedly do exist. In particular,
    a player X who is witting of these strategies can (i) deterministically set her opponent Y’s score, independently of his strategy or
    response, or (ii) enforce an extortionate linear relation between
    her and his scores. Against such a player, an evolutionary player’s
    best response is to accede to the extortion. Only a player with
    a theory of mind about his opponent can do better, in which case
    Iterated Prisoner’s Dilemma is an Ultimatum Game."

    OdpovědětVymazat
  6. Weights and resistance coaching are excellent solutions for losing fat.


    My blog post: just click the following internet site

    OdpovědětVymazat
  7. Electric power Rod and Spiraflex technology provide
    enjoyable added benefits and prospects for rookie and intermediate fat lifters.


    Here is my website ... http://www.getfitnstrong.com/bowflex-dumbbells/3-reasons-bowflex-selecttech-552-dumbbells/

    OdpovědětVymazat
  8. They are really tested to carve excellent bodies and they
    are excellent for growing power.

    My blog post :: adjustable dumbbell set

    OdpovědětVymazat
  9. Set a 'bed time' along with a 'wake time' for the
    little ones which is not less than 9 hours a component.


    Feel free to visit my webpage; hex dumbbells cheap

    OdpovědětVymazat
  10. The market is filled with may perhaps manufacturers, nevertheless, not all are classified as
    the same in quality and function, and every model has its have pros and
    cons.

    my webpage: just click the up coming document

    OdpovědětVymazat
  11. But if you are attempting to replicate a similar physical exercise with these
    bands, it will be much more complicated.

    my weblog - Share Group

    OdpovědětVymazat
  12. Most regular dumbbells will not help you assemble up your arm muscle tissue, which
    must be an element of a critical cardio work out.

    my blog post :: bowflex selecttech 552 dumbbells used

    OdpovědětVymazat
  13. The exhibit wordings have spaces amongst them.


    Here is my homepage adjustable dumbbells

    OdpovědětVymazat
  14. The 60" treadbelt is generous and ideal for those wanting to strengthen stride length as well as the motor is powerful adequate to very last the study course.

    Feel free to surf to my weblog ... http://www.getfitnstrong.com/adjustable-dumbbells/adjustable-dumbbells/

    OdpovědětVymazat
  15. For your much better invest in, opt for the one containing an exceedingly high quality but will come at a quite cheap selling price.


    Check out my web site; dumbbell sets

    OdpovědětVymazat
  16. The cords are available in handy simply because you can wrap the cord all around
    your pull up bar and bit by bit start off creating your again
    muscle tissues up.

    my web-site :: bowflex dumbbells 552

    OdpovědětVymazat
  17. Carbohydrates ought to be a part of any healthful body weight loss approach.


    my blog ... helpful hints

    OdpovědětVymazat
  18. Though not affordable, the Revolution features ninety higher superior exercise routines with out all of the bulky and significant weights from the gym.


    Stop by my site :: cheap free weights for sale

    OdpovědětVymazat
  19. By simply just turning a knob you cango from five to in excess
    of fifty kilos.

    Also visit my web blog Recommended Site

    OdpovědětVymazat