Алгоритм дилеммы заключенного

Question

После просмотра Темного Рыцаря я довольно увлекся концепцией Дилеммы Заключенного. должен быть алгоритмом, который максимизирует собственный выигрыш в данной ситуации.

Для тех, кто находит этот иностранный: http://en.wikipedia.org/wiki/Prisoner%27s_dilemma

Очень, очень интересные вещи.

Редактировать: Вопрос в том, , что является, если таковой имеется, самый эффективный алгоритм, который существует для дилеммы заключенного?

Answer 1

Кроме того, в повторной игре заключенных оптимальная стратегия зависит от других стратегий в игре.

В серии против игрока, у которого ВСЕГДА дефекты всегда есть, это лучшая стратегия. При игре против игрока, который может сотрудничать, стратегия, которая наносит ответный удар, но иногда прощает, вероятно, будет лучшей.

Я должен добавить, что это применимо только к игре неизвестной длины. Любая игра известной длины идентична одиночной игре.

Answer 2

Нет, поскольку вы не можете однозначно предсказать поведение второго заключенного.

Существуют всевозможные «решения», которые делают основополагающие, но очень ограничительные предположения о поведении второго заключенного, но они мало что могут сказать о непринужденной проблеме (вот что делает ее такой непреодолимой дилеммой).

Мои два цента, учитывая, что вы не можете полагаться на поведение второго заключенного, сводятся к следующему: вы оптимист или циник? Собираются ли два заключенных держаться вместе (честь среди воров), или они собираются сдать друг друга при первой возможности спасти свое горло ...?

Answer 3

Ах да. Это заставило меня вспомнить эту старую статью о Дилемма узника в разработке программного обеспечения

Для алгоритмического соревнования PD посмотрите здесь

Этот тоже был хорошим