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

Question

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

Для тех, кто считает это чуждым: http://en.wikipedia.org/wiki/Prisoner%27s_dilemma

Очень, очень интересный материал.

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

Answer 1

Поскольку есть только один выбор, и при отсутствии каких-либо изменяемых входных данных ваш алгоритм либо будет:

cooperate = true;

...или...

cooperate = false

Гораздо интереснее найти стратегию для Повторяющейся Дилеммы заключенного, что уже сделали многие люди.Например http://www.iterated-prisoners-dilemma.net/

Но даже в этом случае она не "разрешима", поскольку другой игрок непредсказуем.

Answer 2

Страница Википедии, похоже, дает ответы на все вопросы...что касается дилеммы одноразового заключенного, то наиболее оптимальным решением для каждого заключенного (не для обоих заключенных) является предательство.

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

Answer 3

Весь смысл дилеммы в том, что оптимальное решение (оба заключенных молчат) опасно, потому что часть проблемы находится вне вашей компетенции.Таким образом, выбор неоптимального решения, по-видимому, максимизирует ваш выигрыш, но он все равно остается неоптимальным

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

Answer 4

Я рекомендую прочитать Аксельрод "Эволюция сотрудничества".Это компьютерный эксперимент с конкурирующими стратегиями решения повторяющейся дилеммы заключенного.Когда я слышал об этом в последний раз, стратегия "око за око" была первой.Возможно, все изменилось.

Answer 5

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

Повторная версия становится более интересной, поскольку игроки могут реагировать на предыдущие варианты своих оппонентов.

Если мы заранее точно знаем, сколько раундов будет, то логичная "лучшая" стратегия по-прежнему заключается в том, чтобы всегда отступать.Это происходит потому, что всегда имеет смысл дезертировать в последний ход, поскольку нет никаких шансов на ответный удар.Конечно, наш рациональный противник будет знать это и тоже всегда будет ошибаться на последнем ходу.Это делает разумным для нас дезертировать на предпоследнем повороте, поскольку в любом случае нет шансов на сотрудничество на последнем повороте.Следуя этой логике до ее естественного завершения, мы должны отступать на каждом шагу.

Когда общее количество раундов неизвестно, все становится еще интереснее.Хорошая стратегия игры должна пытаться предугадать, что предпримет противник.Я исследовал, используя эволюционные алгоритмы и простое машинное обучение с моделированием соперника для создания стратегий игры для получения моей степени магистра.Если вы в самом деле заинтересовавшись, вы можете прочитать моя диссертация.

Как рекомендовал Юваль, вероятно, лучше всего начать с Основополагающая книга Аксельрода.Если вы правда, правда заинтересовавшись этим материалом, там был один последующая деятельность в связи с 20-летием это включало в себя множество более поздних работ по IPD (повторяющаяся дилемма заключенного) других исследователей.

Кроме того, я настоятельно рекомендовал заведение Уильяма Паундстоуна Дилемма заключенного, которая является частью биографии Джона фон Неймана и частью введения в теорию игр.

Answer 6

Что ж, насколько я понимаю, распознавание образов тоже играет огромную роль в этом.Выяснение привычки другого заключенного - как часто он молчит и когда употребляет наркотики.Вы также должны сопоставить это с вашим собственным выбором, чтобы определить, что вы сделали, чтобы заставить его отреагировать определенным образом.

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

Answer 7

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

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

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

Answer 8

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

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

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

Answer 9

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

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

Answer 10

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

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

Это это тоже было хорошо

Answer 11

Весь смысл дилеммы заключенного в том, что ваша оптимальная стратегия - предать другого заключенного.O(1)

Answer 12

Математически другие сообщения отвечают на этот вопрос, но на самом деле могут быть дополнительные варианты.Какими бы абсурдными ни были эти варианты, они приведут к дополнительным возможностям получения результата и могут увеличить шансы на личную выгоду.Например, в случае с Бэтменом это разрушило бы сюжет, но он мог бы просто убить Джокера - тем самым разрушив любые дополнительные эффекты, которые Джокер оказал бы на результат.Оставляя Джокера в живых, Бэтмен невольно дает Джокеру единственную "победу", в которой он нуждается.

Answer 13

Игра становится намного интереснее, когда вы отступаете назад и рассматриваете турнир в целом.Например, несколько лет назад турнир PD выиграла команда из Великобритании, подавшая несколько заявок.Один из них был "хозяином", а другие - "рабами".Все они начинались с выполнения определенной последовательности действий, которая позволяла ведущим и ведомым узнавать друг друга.Как только это будет распознано, ведущий отключится, а подчиненный будет сотрудничать на протяжении остальных итераций.Таким образом, хозяин выиграл турнир, но ценой гибели рабов.

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

В более общем плане, при написании программы для турнира TD вам нужно смотреть на картину в целом:

1. как присуждаются призы?
2. можете ли вы вступить в сговор с другими участниками?
3. каковы затраты на въезд?штрафы?

В противном случае, да, доминирующей стратегией является отказ от одноразового ПД.Аксельрод, как упоминали другие, показал, что "око за око" было сильным в серии турниров, но на этих турнирах никто не думал о сговоре с другими участниками.