Vězňovo dilema

Školení, která pořádám

Martin Malý zveřejnil sérii svých starších článků o tzv. Vězňově dilematu. Rád jsem si tuto úlohu připomněl. O co jde?

Představte si, že jste uvězněn spolu s vaším komplicem, jste držen každý zvlášť a jste zvlášť vyslýcháni. Máte možnost vypovídat proti tomu druhému nebo mlčet. Policie na vás skoro nic nemá a pokud se oba svorně rozhodnete mlčet, dostanete oba tak akorát podmínku. Pokud však pomůžete vašeho kolegu usvědčit, půjde on sedět na deset let a vy vyváznete bez trestu. Totéž platí i v opačném případě. A pokud se rozhodnete oba vypovídat proti tomu druhému, půjdete sedět na pět let oba. Jak se rozhodnete?

já / protihráčpodrazspolupráce
podraz110
spolupráce-106

Hra na toto téma spočívá v tom, že se proti sobě postaví dva algoritmy na předem neznámý počet kol a mají hrát tak, aby maximalizovaly svůj zisk při nějakém bodovém ohodnocení jednotlivých tahů.

Martin problém popisuje ve vztahu ke komunitám, do hry vnesl šum a mutování algoritmů a celé jeho dílo určitě stojí za přečtení. Mně problém přijde zajímavý z jiného pohledu.

Původní algoritmy

Martin použil v simulacích tyto algoritmy:

Naprogramovat by se daly takhle:

<?php
// true je spolupráce, false je podraz

function kavka($history) {
    return true;
}

function podrazak($history) {
    return false;
}

function rozmar($history) {
    return (mt_rand(0, 1) == 0);
}

function dobry($history) {
    return (mt_rand(0, 3) != 0);
}

function spatny($history) {
    return (mt_rand(0, 3) == 0);
}

function tft($history) {
    return (!$history || array_pop($history));
}

function tf2t($history) {
    return (count($history) < 2 || array_pop($history) || array_pop($history));
}

function velky_pes($history) {
    $return = true;
    foreach ($history as $play) {
        if (!$play) {
            $return = !$return;
        }
    }
    return $return;
}

function maly_pes($history) {
    $return = false;
    foreach ($history as $play) {
        if (!$play) {
            $return = !$return;
        }
    }
    return $return;
}
?>

Optimální algoritmus

Všechny algoritmy jsou dost primitivní – do historie se buď vůbec nedívají nebo se dívají jen jeden, maximálně dva kroky zpět. Pro Martinovy účely to úplně stačí a závěry z toho vyvodil zajímavé. Ale já jsem si řekl – jak by vypadal algoritmus, který by chtěl maximalizovat svůj zisk s využitím všech dostupných znalostí? Pokud by věděl, kdo proti němu stojí, tak má situaci docela jednoduchou:

<?php
function optimalni($history, $opponent) {
    switch ($opponent) {
        case 'kavka': return false;
        case 'podrazak': return false;
        case 'rozmar': return false;
        case 'dobry': return false;
        case 'spatny': return false;
        case 'tft': return true;
        case 'tf2t': return (count($history) % 2 != 0);
        case 'velky_pes': return true;
        case 'maly_pes': return (bool)$history;
    }
    return true;
}
?>

Netriviální protihráči:

Pokud by se hra hrála na předem známý počet kol, tak by se také vyplatilo v posledním kole každého podrazit.

Učící se algoritmus

A teď řekněme, že nevíme, kdo proti nám stojí – jak z předešlých tahů odvodit, kdo to je? Kvůli náhodným algoritmům je to ještě o něco těžší – nikdy nemůžeme mít jistotu. Vyplatí se zariskovat a v jednom tahu nabídnout spolupráci jen proto, abych zjistil, kdo proti mně stojí v příštím kole? Vyplatí se na to vůbec sestavovat pravidla nebo by bylo lepší vyzkoušet všechny možnosti a optimální strategii vypočítat? Já jsem sestavil pravidla začínající podrazem a spoluprací, náhodné algoritmy jsem nezohlednil:

<?php
function ucici($history) {
    $opening = array(false, true); // v prvních dvou kolech vyzkoušíme reakce na podraz a spolupráci
    if (count($history) < count($opening)) {
        return $opening[count($history)];
    }
    
    if (!$history[0]) { // podraz v prvním kole: Podrazák nebo Malý pes
        return $history[1]; // když v druhém kole spolupracoval, je to Malý pes a vyplatí se spolupracovat, jinak je to Podrazák
    }
    
    if (!$history[1]) { // podraz v druhém kole: TFT nebo Velký pes
        if (count($history) < 3) {
            return false; // ve třetím kole musíme Velkého psa naučit, že se mu nevyplatí podrážet
        }
        return true;
    }
    
    // TF2T nebo Kavka
    if (count($history) < 4) {
        return false; // ve třetím kole se vyplatí podrazit, ve čtvrtém vyzkoušíme, jestli to je TF2T
    }
    if (count($history) < 5) {
        return true; // v pátém kole TF2T naznačíme, že s ním můžeme spolupracovat, zisk z Kavky oželíme
    }
    if (!$history[4]) { // když v pátém kole podrazil, je to TF2T
        return (count($history) % 2 == 0); // v lichých kolech se vyplatí spolupracovat
    }
    return false; // jinak to je Kavka
}
?>

Při jiném zahájení by pravidla samozřejmě vypadala jinak. Algoritmus není tak dobrý jako optimální (který ovšem podvádí) a v některých případech ani jako některé primitivní algoritmy, s velkým počtem kol se jim ale přibližuje. V součtu proti všem drtivě vyhrává:

ziskKavkaPodrazákTFTTF2TVelký pesMalý pescelkem
Kavka1200-2000120012001200-2000800
Podrazák2000200218236110011004854
TFT1200178120012001200465024
TF2T1200156120012001200-4504506
Velký pes1200-90012001200120011585058
Malý pes2000-90086550119811904124
Optimální200020012001600120011907390
Učící198417811521576116611907246

Neznámý protihráč

A co kdybych nevěděl, kdo proti mně stojí, ale ani bych nevěděl, jaké algoritmy existují? Co kdybych vypustil stádo divokých algoritmů do arény a nechal přežít ten nejlepší? Jak by takový algoritmus vypadal?

Pokud s tím někdo chce experimentovat, zde je program, který jsem použil pro testování algoritmů:

<?php
function veznovo_dilema($algos, $prices) {
    $profits = array_fill_keys($algos, array_fill_keys($algos, 0));
    foreach ($algos as $home) {
        foreach ($algos as $away) {
            $home_history = array();
            $away_history = array();
            for ($i = 0; $i < 100; $i++) {
                $home_play = $home($away_history, $away);
                $away_play = $away($home_history, $home);
                $home_history[] = $home_play;
                $away_history[] = $away_play;
                $profits[$home][$away] += $prices[$away_play][$home_play];
                $profits[$away][$home] += $prices[$home_play][$away_play];
            }
        }
    }
    return $profits;
}

$algos = array('kavka', 'podrazak', 'tft', 'tf2t', 'velky_pes', 'maly_pes', 'optimalni', 'ucici');
$prices = array(
    false => array(false => 1, true => -10),
    true => array(false => 10, true => 6),
);

foreach (veznovo_dilema($algos, $prices) as $algo => $val) {
    echo "$algo\t" . implode("\t", $val) . "\t" . array_sum($val) . "\n";
}
?>

Závěr

Ve skutečném světě taky pracujeme s delší historií, pamatujeme si křivdy z minula a při svém rozhodování je chtě nechtě zohledňujeme. Co se algoritmizuje těžko, je první dojem – pokud se nám někdo nezdá, tak se k němu chováme jinak, než pokud je nám sympatický.

Jakub Vrána, Řešení problému, 8.2.2013, diskuse: 8 (nové: 0)

Diskuse

lopata:

"Ale já jsem si řekl – jak by vypadal algoritmus, který by chtěl maximalizovat svůj zisk s využitím všech dostupných znalostí?"

Tak přesně tyhle věci - využívat algoritmy na věci, které mohou zásadně ovlivnit lidské životy, už jednou (2008) málem poslaly svět ke dnu. A děje se to dále, viz. high speed trading nebo jak se to jmenuje atd. Jako akademické hraní OK, ale do reálného světa ne, a když už tak regulovat a zdanit.

v6ak:

Souhlasím, že na některé věci, včetně obchodování na burze, není vhodné se spoléhat čistě na algoritmy. Ty mohou být nápomocné (co jiného ostatně dělám, když si hledám fulltextem informace, které sám dál použiju), ale u komplexnějších problémů těžko někdy (aspoň v dohledné době) zcela nahradí lidský úsudek.

Ale nemyslím si, že by to byl problém v USA v roce 2008. Tehdy, pokud si dobře pamatuju, šlo o subprime hypotéky, které banky poskytovaly právě kvůli regulacím.

Pokud jede člověk za sebe, rozmyslí si, jestli se bude chovat *výhradně* podle algoritmů. (A neříkám, že to chování nemůže být za žádnou cenu úspěšné. Záleží, jak složitý systém se snaží ty algoritmy pochytit a případně jak jsou sofistikované.) Musí ale platit tyto dvě podmínky:

1) Rizika nese člověk sám, případně je sdílí s někým, kdo s tím (za stanovených podmínek) souhlasí. V případě burzy jde o riziko ztráty. Důležité je, že v případě neúspěchu nenastane bailout.
2) O svém chování se rozhoduje každý sám, nikdo není regulací tlačen např. do poskytování hypoték i méně majetným vrstvám.

ikona Jakub Vrána OpenID:

Karel Janeček by nesouhlasil: http://cs.wikipedia.org/wiki/Karel_Jane%C4%….C3.A1n.C3.AD

v6ak:

On ani Karel Janeček se nespoléhá čistě na algoritmy, byť se do toho pustil v poněkud větší míře, než bych se do toho pouštěl já. (Zvažuju, že se pokusím takto trošku stabilizovat BitCoin, kde se kurz zatím dost hýbe. No, moc kapitálu nemám, ale mělo by to být dost na to, aby se tím mělo smysl zabývat.) On, pokud vím, algoritmy postupně upravuje podle změn na trhu.

Franta:

Pán bude asi komunista, že? Přezdívka by i odpovídala.

Co se týče obchodování (nebo spíš gamblerství) na burze nebo jinde – může se ti to nelíbit, můžeš to považovat za nemorální či nesmyslné, ale to je tak asi všechno – když chce jeden prodávat a druhý nakupovat, tak si k sobě vždycky nějak najdou cestu. A je naopak nemorální jim v tom bránit – je to jejich majetek a jejich peníze – nemáš právo jim mluvit do toho, co s nimi udělají.

Co se týče krize – daleko horší je ztráta materiálu, energií a lidské práce, které se vyplýtvaly na válku běžící od roku 2001 – tyhle zdroje v hospodářství chybí a to se musí nutně někde projevit. Svádět to na nějaké gamblery je velice hloupé – pak se třeba zakáže gambling, lidi budou mít pocit, že vyřešili problém, ale nevyřešili vůbec nic… ale to je na jinou diskusi :-)

P.S. Osobně taky tomu obchodování na burze moc nefandím a nepovažuji to za moc smysluplně strávený život – ale když to někdo chce dělat, tak ať si obchoduje.

zde:

> Pokud by se hra hrála na předem známý počet kol, tak by se také vyplatilo v posledním kole každého podrazit.

Jistě. A když vím že protihráč v posledním kole podrazí, vyplatí se ho podrazit v předposledním kole.  Indukce pak vede k závěru že se vyplatí podrazit vždy.

> proti sobě postaví dva algoritmy na předem neznámý počet kol
> ..

Jestli je kol 10 nebo 100 nemá na rozhodování žádný vliv.

Martin Malý :

Ne, počet kol vliv nemá. Vliv má ale to,že nevíme, kolik kol budeme ještě hrát!

Milsa:

Treba počítať aj so štatistikou pravdepodobnosti, že na aký algoritmus natrafime.

Vložit příspěvek

Používejte diakritiku. Vstup se chápe jako čistý text, ale URL budou převedeny na odkazy a PHP kód uzavřený do <?php ?> bude zvýrazněn. Pokud máte dotaz, který nesouvisí s článkem, zkuste raději diskusi o PHP, zde se odpovědi pravděpodobně nedočkáte.

Jméno: URL:

avatar © 2005-2016 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.