Генетический Алгоритм для Дилеммы Заключенного

В комментариях к посту об архетипе “Эскалация”, Антон Чаплыгин совершенно правильно заметил, что оптимальной стратегией для игры “Дилемма Заключенного” является сотрудничество: “не нападать первым, но быть готовым дать адекватный отпор (но не превышающий действий противника, обязательно с явным указанием в ответ на что были предприняты эти действия), прощать и не завидовать результатам оппонента”. В этой заметке я хочу пояснить, что это за игра такая и каким образом можно смоделировать оптимальную стратегию при помощи генетических алгоритмов.

Итак, в чем суть дилеммы заключенного? Представим, что полиция задержала 2х подозреваемых в преступлении: Аню и Ваню, которых посадили в разные камеры без возможности общаться друг с другом.  Ане предлагают следующее:

• Если она даст показания против Вани, то ее отпустят, а Ваню посадят на 5 лет;
• Но если и Ваня даст показания против нее, то каждому “влепят” по 4 года;
• Но если ни Аня, ни Ваня не дадут показания против друг друга, то каждого из них посадят лишь на 2 года.

Как же поступить Ане? Давать ли показания против Вани? Сотрудничать (то есть не давать показания против Вани, надеясь на это же с его стороны) или защищаться (то есть дать показания и в худшем случае сесть на 4 года, но и Ваня сядет в этом случае – “собака на сене”). По идее,  Ане выгоднее защищаться. Но дилемма в том, что если ситуация – симметрична (Ване тоже выгоднее защищаться), но если оба будут защищаться – то результат будет хуже, чем если они будут сотрудничать.

А что если эту игру повторять вновь и вновь? Этот вопрос настолько занял Роберта Аксельрода (Axelrod), что он решил устроить соревнования (и даже дважды). Ученые со всего мира прислали свои стратегии, в их числе был и математик Анатолий Раппорорт. Стратегия Анатолия была на удивление простой и называлась “TIT FOR TAT”. Причем, она победила в обоих турнирах.  Суть стратегии заключается в следующем:

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

Вот уж, гениальное – просто! Аксельрод был удивлен результатами соревнований и задался вопросом: а можно ли вывести оптимальную стратегию при помощи генетического алгоритма? Как оказалось, вполне! Вот как это выглядело:

• Каждая стратегия – это решение о том, что выбрать в следующем ходу (C – сотрудничество или D – защита) в ответ на 4 возможных исхода в предыдущем ходе: 1) СС – в прошлом ходу оба игрока выбрали сотрудничество; 2) CD – первый игрок выбрал сотрудничество, в то время как второй – защиту; 3) DC – первый игрок выбрал защиту, а второй – сотрудничество;  4)  DD – оба игрока выбрали защиту.

Таким образом, стратегия – это строка из 4х букв, которая определяет что выбрать. Например, вышеупомянутая стратегия TIT FOR TAT для первого игрока представляется в виде: “CDCD” (сотрудничать, если противник сотрудничал, защищаться – если противник защищался).

• Приспособленность каждой стратегии (fitness) Аксельродом определялась следующим образом: каждая стратегия играла с каждой другой стратегией из своей популяции; лучшие из них выбирались для создания потомков и опять играли друг с другом.
• Поначалу стратегии сотрудничества (наподобие TIT FOR TAT) набирали гораздо меньше очков (были менее приспособлены), чем стратегии, поощрявшие защиту. Но после 10-20 поколений этот тренд менялся в обратную сторону и стратегии,  поощрявшие сотрудничество и наказывавшие защиту, выживали и в итоге представляли основную популяцию.

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

Кстати, а кто догадается почему стратегия называется TIT FOR TAT?

3 отзывов

• 

  By Владимир Мельников, August 9, 2009 @ 5:54 pm

  зуб за зуб — он тебя и ты его ))

  Ответить

  

  Bayram Annakov Ответ:
  August 9th, 2009 at 6:05 pm

  Володя, совершенно верно!

  Ответить

Ссылки на эту статью

1. Дан Воронов — Сотрудничество лучше соперничества (всегда!) — January 22, 2010 @ 1:36 pm

Оставить отзыв