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

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

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

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

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

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

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

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

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

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

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

Кроме того, я полностью рекомендовал Дилемму Заключенного William Poundstone, которая является биографией части John von Neumann и введения части в теорию игр.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В более общем плане при записи программы для турнира TD необходимо посмотреть на большее изображение:

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

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

Mathemaically другие сообщения отвечают на вопрос, но в действительности, может быть дополнительными опциями. Однако абсурдный эти опции, они приведут к дополнительным возможностям результата, и они могут привести к увеличенному шансу личной выгоды. Например, в случае Batman's, это разрушило бы график, но он, возможно, просто уничтожил Шутника - таким образом разрушающий любые дополнительные эффекты, которые Шутник будет иметь на результат. Позволяя Шутнику жить, Batman невольно позволяет Шутнику единственную "победу", в которой он нуждается.