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

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

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

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

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

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

Answer 7

Игра становится намного интереснее, когда вы отступаете назад и рассматриваете весь турнир. Например, несколько лет назад турнир по ПД выиграл команда из Великобритании, которая представила несколько заявок. Один из них был «хозяином», а другой - «рабом». Все они начнут играть определенную последовательность действий, которая позволит хозяевам и рабам узнавать друг друга. После распознавания ведущий будет дефектным, а подчиненный будет сотрудничать до конца итераций. Таким образом, мастер выиграл турнир, но за счет рабов.

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

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

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

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

Answer 8

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

Answer 9

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

Answer 10

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

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