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>
|}
Классическая формулировка такова:
Реализация такого алгоритма через прямую эмуляцию нецелесообразна, так как в случае игры FairBot1 против FairBot2 первый вначале запустит эмуляцию второго, который запустит эмуляцию первого, который запустит эмуляцию второго и т. п. В подобной ситуации одна из программ рано или поздно исчерпает стек/память, не сумев доказать, что оппонент будет сотрудничать, и предаст его. Другая программа (которая исчерпает ресурсы позже) сможет это показать в своей эмуляции, и в ответ тоже предаст.
Однако, если FairBot реализован через математический анализ кода оппонента, то с помощью [[Теорема Лёба|теоремы Лёба]] можно доказать, что два таких алгоритма будут сотрудничать друг с другом даже при наличии различий в структуре своего кода (в отличие от CliqueBot).
=== OptimisticBot ===