Пользователь
0,0
рейтинг
1 мая 2013 в 00:34

Разработка → Дилемма заключенных: you are (not) alone


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

Если построить дерево решений, то получится следующая схема:

где Я и ОН это заключенные
красные линии означают дачу показаний против другого заключенного
зеленые линии молчание
A, B, C, D — четыре возможных исхода
А — оба дают показания
B — я даю показания, он молчит
C — я молчу, он дает показания
D — мы оба молчим

Теперь зададим функцию выигрышей:
Для меня функция будет равняться f1 = -m
Для него будет равняться f2 = -n

где m и n — количество получаемый лет заключения, мои и его соответственно, функции взяты с отрицанием, так как мы хотим сидеть за решеткой меньше
здесь m и n не зависимые переменные, так как у нас игра с не нулевой суммой, иначе функции выглядели бы так:
Для меня f1 = -m
Для него f2 = m
здесь второй заключенный стремится чтобы мы сидели дольше и пытается минимизировать m.

Возьмем для примера данные с вики про возможные исходы, тогда:
A = -2;- 2
B = 0;- 10
C = -10; 0
D = -1; -1
где первое и второе число, выигрыш мой и его соответственно
Получим следующую схему, которую нам нужно решить:


Теперь попробуем разрешить данную проблему и решить какой ход нам сделать. Сначала попробуем алгоритм minimax, который в нашем случае будет в виде maximax, так как оба игрока пытаются максимизировать свой выигрыш. Получаем следующий результат:

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


Данный алгоритм максимакс плохо работает в реальном мире, так как всегда настроен на плохой исход. В таких ситуациях значительно лучше себя показывает алгоритм ожидаемого максимума(expectimax). Этот алгоритм учитывает, что игроки могут выбирать не самые выгодные для себя ходы.
Допустим, что ОН предает в 50% случаев, тогда:
выигрыш нашего предательства будет равен 0.5*(-2) + 0.5*(0) = -1
выигрыш нашего молчания 0.5*(-10) + 0.5*(-1) = -5.5
или тоже самое на схеме:


Как видно, даже с более подходящим алгоритмом чуда не произошло и нам все также выгоднее предавать. Даже если вероятность ЕГО молчания увеличится все равно при данных условиях выгоднее предавать. Если мы будем знать что ОН всегда будет молчать мы выберем предательство.

Почему так? Где мы просчитались?
Мы забыли рассмотреть одну очень важную деталь — функцию выигрышей. А что если нам не безразлична ЕГО судьба, а ему не безразлична НАША? Тогда функции выигрышей будут такими:
f1 = -m -n
f2 = -m -n
где m и n — количество получаемый лет заключения, мои и его соответственно
Тогда получаем следующую схему, но это уже будет не классическая задача, так как одно из условий не будет выполнятся:

и теперь все кардинально меняется, для максимакса решение для МЕНЯ получится молчать, так как Я буду выбирать между -4;-4 слева(предательство) и -2;-2 справа(молчание)
а для ожидаемого максимума с 50% ЕГО предательства получится:
для моего предательства выигрыш -7
для моего молчания выигрыш -6
Следовательно — молчим.
Внимательный хабраюзер заметит, что если вероятность ЕГО предательства будет возрастать, то для МЕНЯ будет уже выгоднее предавать.

Как же узнать эти вероятности? Их можно найти на основе предыдущего опыта.
Допустим ОН раньше в 9 случаях из 10 молчал, следовательно ставим ему вероятность предательства 10%
Правда в реальном мире эти вероятности зависят от большого количества факторов и найти их является одной из основных проблем.

Так же стоит помнить, что функции выигрышей могут иметь другой вид, более эгоистичный для МЕНЯ, например:
f1 = -m/2 — n
здесь мы помним про НЕГО, но все равно если будет выбор между ЕМУ сидеть 2 года или МНЕ 1, Я предпочту второй вариант.
Эту функцию тоже сложно найти.

Вывод:


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

Я считаю что дилемма заключенных это дилемма недостаточных входных данных. Если мы будем знать с какой вероятностью ОН предаст, как МЫ эгоистичны и как эгоистичен ОН, то сможем принять решение очень близкое к верному.
@overmes
карма
56,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (18)

  • +1
    — Если мы будем знать с какой вероятностью ОН предаст
    А если таки не будем?
    • +3
      тогда наша модель будет плохо соответствовать действительности и вероятность ошибиться возрастает
  • +8
    Почему-то никто не упомянул о такой замечательной модификации игры, как игра с фиксированным количеством раундов (например, рассмотрим N раундов).

    Тогда, максимизируя свой выигрыш, мы обязаны на последнем N-ом раунде выставлять всегда «предательство», так как независимо от нашей предыдущей стратегии и стратегии противника это будет всегда выгоднее, чем «сотрудничество» (нет возможности «отомстить»). Предполагая, что противник умный и тоже заметил это обстоятельство, мы знаем, что на последнем раунде он тоже должен выставить «предательство» для максимизации своей выгоды. Значит, оптимальная стратегия шага N полностью определёна.

    Определим стратегию шага N-1. Если на шаге N игроки выставляют предательство, то игра сводится в ведению N-1 шагов. По индукции определяем оптимальную стратегию — всегда выставлять «предательство»

    зы. плюс поставил только за заголовок.
    • +2
      Но почему же оказывается, что оптимальная стратегия хуже, чем «сотрудничество»?
      Предательство даст нам -1 в худшем случае и +100 в лучшем.
      Сотрудничество даст -100 в худшем и +1 в лучшем.
      Но "+100 в лучшем" в реальности выглядит как тарифный план «до 100 мбит» у провайдера.
      В реальности при использовании «предательства» мы получаем свои гарантированные -1, когда могли бы сойтись на +1.

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

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

        как мне кажется задача значительно упращается
        • +2
          Эквилибриум неша — вариант А в ваше игре. тк у игроков нет данных о действиях противника они просто теоритезируют и простой расчет показывает что предательство всегда дает лучший результат чем сотрудничество.
          • 0
            если функции выигрышей полностью эгоистичные, тогда да, но если нет, то может выиграть и молчание
    • 0
      deleted
  • 0
    На мой взгляд тут явно не хватает функции «позелности» вокруг n и m. Ведь разница между результатом один год и два года гораздо меньше, чем разница между годом и оправданием. Именно поэтому зек скорее всего будет сотрудничать. А еще нужно как-то учесть, что у каждого из них эта функция будет своя.
    • 0
      можно просто сделать функцию не линейной
  • +1
    А что если нам не безразлична ЕГО судьба, а ему не безразлична НАША?

    Другая сторона: братки просто так не оставят предателя.
  • +5
    > согласен с написанным и считаю, что это хорошая работа, особенно учитывая, что автор школьник.
    Шикарная фраза, надо запомнить
    • +5
      убрал. я пытался похвалить, но получилось плохо
  • 0
    Однако это не учитывает российские реалии, у нас лучше молчать в любом случае :)
    • +4
      пока в дело не вмешается паяльник. В формулах можно записать любые реалии.
  • 0
    > Я считаю что дилемма заключенных это дилемма недостаточных входных данных. Если мы будем знать с какой вероятностью ОН предаст, как МЫ эгоистичны и как эгоистичен ОН, то сможем принять решение очень близкое к верному.
    Именно так и есть. А входные данные это: личный опыт, религия, культура, воспитание и т.д.
  • 0
    дилемма заключенного вики:
    ru.wikipedia.org/wiki/%D0%94%D0%B8%D0%BB%D0%B5%D0%BC%D0%BC%D0%B0_%D0%B7%D0%B0%D0%BA%D0%BB%D1%8E%D1%87%D1%91%D0%BD%D0%BD%D0%BE%D0%B3%D0%BE
    Хотя стратегия «око за око» считалась самой удачной простой стратегией, команда Университета Саутгемптона из Англии (под руководством профессора Николаса Дженнингса[6]) представила новую стратегию на 20-ю годовщину Чемпионата по ПДЗ. Эта стратегия оказалась более успешной, чем «око за око». Она основывалась на взаимодействии между программами, чтобы получить максимальный счёт для одной из них. Университет выставил на чемпионат 60 программ, которые РАСПОЗНАВАЛИ ДРУГ ДРУГА ПО РЯДУ ДЕЙСТВИЙ (КАК???) на первых 5-10 ходах. УЗНАВ ДРУГУЮ (КАК???), одна программа всегда сотрудничала, а другая предавала, что давало максимум очков предателю. Если программа понимала, что оппонент — не саутгемптонский, она дальше всё время предавала его, чтобы минимизировать результат соперника. В результате[7] эта стратегия заняла первые три места в соревновании, как и несколько мест подряд ниже.

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

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