Vězňovo dilema

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?

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:

• Kavka. Algoritmus, který nikdy nepodrazí, jedině když dojde k nějakému šumu, tak je jeho krok vnímán jako podraz. (Beránčí algoritmus)
• Podrazák. Vždy podrazí.
• Rozmar. Algoritmus, který se mezi spoluprací a podrazem rozhoduje zcela náhodně.
• Dobrý. Algoritmus se rozhoduje náhodně. Spolupracuje, ale v jednom případu ze čtyř podrazí.
• Špatný. Rozhoduje se náhodně, většinou podrazí, v jednom ze čtyř případů spolupracuje.
• TFT. Algoritmus začne spoluprací a pak opakuje poslední krok soupeře – podrazí za podraz, spolupracuje při spolupráci. (Čistící algoritmus)
• TF2T. Algoritmus, který začíná spoluprací a podrazí jen tehdy, když byl dvakrát za sebou podražen.
• Velký pes. Algoritmus, který začne spoluprací. Pokud v minulé hře oba spolupracovali, spolupracuje dál, pokud byl podražen, podrazí. Pokud v minulé hře podrazil a podraz se mu vyplatil (=soupeř spolupracoval), bude dál podrážet. Pokud podráží oba, nabídne spolupráci. (Pragmatický algoritmus)
• Malý pes. Chová se stejně jako velký pes, ale začíná podrazem.

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:

• S TFT se vyplatí spolupracovat, protože když bych ho podrazil, tak v příštím kole podrazí on mě.
• TF2T jde parádně oškubat – když ho každé druhé kolo podrazím, tak on bude pořád spolupracovat a mně se nic nestane.
• S Velkým psem je lepší spolupracovat, ale jen proto, že odměna za dvě vzájemné spolupráce (6 + 6) je větší než za jeden vzájemný a jeden jednostranný (1 + 10) podraz. V Martinově hodnocení to je zdá se naopak (za vzájemnou spolupráci je jen 5) – v tom případě by se vyplatilo tento algoritmus podrážet.
• S Malým psem to je stejné, ale vzhledem k tomu, že mě v prvním kole podrazí, tak je ho lepší podrazit taky.

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á:

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

Diskuse je zrušena z důvodu spamu.

Navigace

PHP triky

• Archiv (704), English articles
• RSS, Atom, Atom diskusí
• O autorovi, o webu, Twitter

Kupte si mou knihu

Reklama

• Hledáte-li programátora nebo naopak sami programujete a nemáte do čeho píchnout, využijte služeb portálu nezávislých profesionálů Na volné noze.

Web běží na serveru

• Váš hosting

Články podle skupin

• Dobře míněné rady (111)
• Řešení problému (170)
• Výuka (100)
• Seznámení s oblastí (102)
• Ze zákulisí (69)
• Školení (31)
• Verze PHP (8)
• Osobní (46)
• Adminer (67)

Výběr článků

• Traverzování kolem stromu prakticky
• Vlastní pořadí řádků v tabulce
• Ukázka použití indexů
• Struktura stránek
• Unikátnost návštěvníka
• Vyhledávání v JavaScriptu
• Kontrola e-mailové adresy
• Vytvoření přátelského URL
• HTTP cachování
• Atomicita operací
• Vypnutí magic_quotes_gpc
• Ukládání souborů od uživatele
• Cross Site Scripting
• AJAX
• Přihlašování uživatelů
• MySQL 4.1 – kódování
• Vzájemné propojení souborů
• Diskuse s reakcemi
• Šablony
• HTTP metody GET a POST
• Escapování
• Ukládání hesel
• Využití unikátních klíčů v databázi
• Obrana proti SQL Injection

Nejnovější články

• Adminer 4.8.1
• Adminer 4.8.0
• Adminer 4.7.9
• Vypnutí chyby při přístupu k nedefinovanému prvku pole
• Users of Adminer 3.7.1 and older might have been hacked

Normy a manuály

• PHP
• MySQL
• HTTP
• Apache
• HTML, XHTML
• JavaScript

Další projekty

• Adminer
• NotORM
• JavaScript Syntax Highlighter
• php-initialized
• Čtyřka