14
правок
Изменения
→Классическая дилемма заключенного: добавил матрицу игры
== Классическая дилемма заключенного ==
{| class="wikitable" style="text-align:center; float:right; margin-left:0.8em; clear:right;"
|+ Матрица исходной игры
|-
! !! <span style="color:#20B2AA">Заключённый Б</span> молчит !! <span style="color:#20B2AA">Заключённый Б</span> предаёт
|-
! <span style="color:#A81C07">Заключённый А</span> молчит
| <span style="color:#A81C07">0.5</span>/<span style="color:#20B2AA">0.5</span>|| <span style="color:#A81C07">10</span>/<span style="color:#20B2AA">0</span>
|-
! <span style="color:#A81C07">Заключённый А</span> предаёт
| <span style="color:#A81C07">0</span>/<span style="color:#20B2AA">10</span> || <span style="color:#A81C07">2</span>/<span style="color:#20B2AA">2</span>
|}
Классическая формулировка такова:
Другая формулировка дилеммы заключенного с аналогичными выводами: «Некий меценат предлагает двум соседям (каждому независимо от другого) выбор: взять один миллион долларов самому или передать два миллиона долларов другому».
== Способы разрешения классической дилеммы заключенного==
Если между двумя агентами существует [[общее знание]] о том, что они достаточно похожи друг на друга (настолько, что придут к одинаковым выводам и выберут одинаковую стратегию), то есть реализуется либо исход CC, либо DD, но не CD и не DC, то делая выбор между миром, в котором оба выбрали кооперацию, и миром, в котором оба выбрали предательство, они оба предпочтут сделать ход C.
В повторяющейся дилемме заключенного агент может получить косвенные данные о стратегии оппонента по его прошлым ходам. Развитие этой идеи — возможность получить полную информацию о стратегии оппонента через анализ его полного исходного кода. В соответствующем гипотетическом турнире компьютерных программ все они играют друг с другом попарно по одному разу, и каждой на вход дается исходный код оппонента.
Программу, которая всегда сотрудничает, называют '''CooperateBot'''; программу, которая всегда предает, называют '''DefectBot'''.
Основное качество, которым должна обладать хорошая программа — не быть эксплуатируемой (то есть предотвращать ситуации, когда она сотрудничает с оппонентом, который предает ее). Большинство описанных ниже программ обладают этим качеством.
Реализация такого алгоритма через прямую эмуляцию нецелесообразна, так как в случае игры FairBot1 против FairBot2 первый вначале запустит эмуляцию второго, который запустит эмуляцию первого, который запустит эмуляцию второго и т. п. В подобной ситуации одна из программ рано или поздно исчерпает стек/память, не сумев доказать, что оппонент будет сотрудничать, и предаст его. Другая программа (которая исчерпает ресурсы позже) сможет это показать в своей эмуляции, и в ответ тоже предаст.
Однако, если FairBot реализован через математический анализ кода оппонента, то с помощью [[Теорема Лёба|теоремы Лёба]] можно доказать, что два таких алгоритма будут сотрудничать друг с другом даже при наличии различий в структуре своего кода (в отличие от CliqueBot).
=== OptimisticBot ===
* [[Охота на оленя]]
[[Категория:ПонятиеПонятия]]
[[Категория:Теория игр]]