Архетипы стратегий охоты на оленя

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

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

Белый рыцарь и Черный рыцарь

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

Белый рыцарь - это идеалист, верящий в то, что олень является очевидным выбором: “Ну как можно выбирать кролика? Вы только посмотрите на цифры!” Обычно у Белого рыцаря на руках достаточно ресурсов для того, чтобы лично он не воспринимал плату за участие в охоте на оленя сколько-нибудь рискованной. Либо же у него есть какая-то еще мотивация делать именно такой выбор (например, ему глубоко небезразличен именно этот конкретный проект).

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

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

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

И хотя в чем-то Черный рыцарь явно мудрее Белого, он сам - тоже не без серьезного изъяна. Общего знания о том, что все члены племени непременно пойдут охотиться на оленя, чрезвычайно трудно добиться, а значит он никогда не будет к ней присоединяться. Более того, он вообще никак не будет пытаться решить эту проблему, даже когда олень действительно стоит того. Порой Черный рыцарь будет тем единственным твердолобым пессимистом, кто не присоединился к охоте на оленя, когда всё племя все-таки рискнуло собраться.

В поисках мудрого Серого рыцаря

Нетрудно провести параллель между этими двумя стратегиями и стратегиями, описанных для разных вариантов дилеммы заключенного. Среди таковых известны CooperateBot (игрок, который всегда сотрудничает) и DefectBot (игрок, который всегда предает) - их аналогами и являются Белый и Черный рыцари соответственно.

Понятно теперь, откуда берутся их недостатки: оба они имеют фиксированную стратегию и неспособны адаптироваться по мере поступления новых свидетельств о характере стратегий оппонентов. Белый рыцарь будет игнорировать то, что его соплеменники хотят избегать рисков; Черный рыцарь - игнорировать ситуацию, в которой соплеменники готовы рискнуть.

Нетрудно понять, как играть вместе с ними. Если все остальные члены вашего племени - Белые рыцари, то вы можете спокойно охотиться на оленя. Если в племени есть хотя бы один Черный рыцарь, и по крайней мере один участник, про которого нет общего знания, что он является Белым рыцарем - выбирайте охоту на кролика: Черный рыцарь непременно испортит всю малину (т.к. решит, что тот второй непременно сделает выбор Шеллинга). Впрочем, если уж вопрос выбора стратегии вообще стоит - значит вы точно не Белый рыцарь, и Черному рыцарю хватит одного лишь вашего присутствия, чтобы выбрать кролика.

Вероятно, сами мы не хотим придерживаться стратегии ни Белого рыцаря, ни Черного - слишком уж велики их недостатки. К счастью, в реальной жизни мы редко встречаемся с охотой на оленя в ее базовом варианте (для которой сложно придумать что-то умнее этих двух архетипов) - обычно присутствуют дополнительные факторы. И для таких более сложных игр существуют более интересные стратегии, которые мы могли бы использовать.

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

Рыцарь-конформист

Для начала рассмотрим стратегии из итерированной дилеммы заключенного; это будет полезно, разумеется для итерированной же охоты на оленя. Последняя может иметь место, если вы в одном “племени” либо пытаетесь реализовать несколько проектов, либо один проект несколько раз подряд. Конечно, итерированная игра подразумевает некоторый запас ресурсов (вы не будете на голодном пайке в первой же итерации), но все же далеко не бесконечный (и транжирить их направо и налево было бы глупо).

По опыту турниров компьютерных программ по итерированной дилемме заключенного можно сказать, что очень хорошо себя показывает стратегия Tit-for-tat (”Око за око”): на первом ходу кооперируйте , а на последующих - повторяйте ход вашего оппонента. Если он сотрудничал с вами на прошлом ходу - вознаградите его кооперацией на этом ходу. Если он предал вас на прошлом ходу - накажите его предательством на этом.

В терминах охоты на оленя ее аналог может звучать так. Во время первой охоты дайте шанс своим соплеменникам - выберите S (stag, олень), а далее смотрите на их действия и подстраивайтесь под них. Если во время прошлой охоты большинство участников выбрало S - в этот раз вам, вероятно, стоит попробовать тоже выбрать S. Если же большинство выбрало R (rabbit, кролик) - на этот раз тоже предпочитайте R. Если все будут придерживаться подобной мета-стратегии, то довольно скоро племя будет стабильно оказываться в одном из равновесных состояний.

Данная мета-стратегия частично свободна от недостатков Белого и Черного рыцарей - она позволяет адаптироваться под окружающих. При самом удачном стечении обстоятельств племя начнет стабильно успешно охотиться на оленя; в сценарии похуже - хотя бы не будет впустую тратить ресурсы. Фактически племя Рыцарей-конформистов со временем превращается либо в племя Белых рыцарей, либо в племя Черных рыцарей.

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

Похожую проблему (когда из-за ошибки - зашумленности канала обратной связи или “рука соскользнула” два Tit-for-tat бота проваливаются в бесконечный цикл CD-DC-CD-… или и вовсе бесконечное DD) решают возможностью прощать, и в ответ на предательство с небольшой долей вероятности все же кооперировать.

Подобную модификацию можно внести и в стратегию Рыцаря-конформиста. Так, если большинство членов племени выбрало S - будем выбирать S; если большинство выбрало R - чаще всего будем выбирать R, но иногда все же выбирать S. Рано или поздно больше половины соплеменников выберет S - и тогда всё племя разом превратится в Белых рыцарей.

К сожалению, хорошо это будет работать только в племени из одних только Рыцарей-конформистов (возможно, разбавленных Белыми рыцарями). При наличии некоторых других типов соплеменников (тех же Черных рыцарей) эта мета-стратегия может обернуться сплошным разочарованием: вполне возможна ситуация, когда почти всё племя упорно пытается пойти на оленя, но единственный упёртый пессимист начисто всё портит. В реальности, конечно, мы довольно быстро заметим закономерность, и сможем либо что-то сделать с “неправильным” игроком, либо со своей стратегией.

Рыцарь Лапласа

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

В подобной вариации дилеммы заключенного есть ряд интересных стратегий. Простейшая из них - CliqueBot, кооперирующая со своими точными копиями и предающая всех остальных. Основной недостаток ее в том, что даже при наличии несущественных различий между двумя вариациями CliqueBot (даже если в их коде просто различаются названия переменных) они будут взаимно предавать друг друга. Конечно, кооперировать со своими FDT-копиями (например, с некоторыми оговорками про одинаковые условия - между “я сегодняшний” и “я завтрашний”) при установлении полезной привычки - уже довольно неплохо; но хотелось бы чего-то большего.

То самое “большее” предлагают нам FairBot и PrudentBot. FairBot пытается доказать по коду оппонента, что тот будет с ним сотрудничать, и если успешно доказывает - сам сотрудничает с ним; если же доказать этого он не может (либо потому, что оппонент и в самом деле не будет сотрудничать, либо из-за ограниченности своих возможностей получать доказательства), то предает.

Известно, что FairBot (как, впрочем, и CliqueBot) нельзя эксплуатировать (т.е. получить ситуацию, когда он кооперирует, а его оппонент предает), и что сам с собой он кооперирует. Недостаток FairBot (которого лишен PrudentBot) для дилеммы заключенного состоит в том, что он не в состоянии эксплуатировать CooperateBot (т.е. теряет прибыль на том, что относится “справедливо” даже к бездушным законам природы, которым на самом деле всё равно). Впрочем, для охоты на оленя это не актуально: если все остальные члены племени - Белые рыцари, то мы и сами захотим охотиться на оленя вместе с ними.

Возвращаясь к охоте на оленя, назовем Рыцарем Лапласа (в честь Демона Лапласа) такого агента, который пытается доказать, что все его оппоненты (которым тоже доступен исходный код всех прочих) идут на оленя; если у него это получается, то он тоже идет на оленя; если нет - идет на кролика.

Вообще-то, такое поведение немного похоже на Черного рыцаря из базовой вариации нашей игры. Однако, поскольку мы не определяли того достаточно формально, позволим здесь себе вольность и будем считать, что Черный рыцарь в охоте на оленя с доступом к исходному коду - это тот, кто идет охотиться на кролика всегда (аналог DefectBot), а Рыцарь Лапласа - тот, кто по-честному пытается проверить, действительно ли остальные согласятся идти на оленя.

Посмотрим, как конкретно поведет себя такой агент при игре с разными типами оппонентов. Понятно, что в окружении одних лишь Белых рыцарей он выбирает охоту на оленя, а при наличии хотя бы одного Черного рыцаря - охоту на кролика. Теорема 3.1 из приведенной выше работы показывает с помощью теоремы Лёба, что два FairBot, пользующиеся одной лишь арифметикой Пеано, кооперируют друг с другом. Воспроизведя ее доказательство дословно, мы легко можем показать, что племя из двух Рыцарей Лапласа успешно ловит оленя. По аналогии несложно также доказать такой же результат и для племени из любого числа Рыцарей Лапласа. Добавление к племени произвольного числа Белых рыцарей, конечно, не меняет ситуацию.

Конечно, подход “перед тем, как выбирать, участвовать ли в проекте, обменяйтесь со своими потенциальными коллегами всеми своими соображениями, пожеланиями и идеями, и затем постарайтесь понять, совместимы ли они с таковыми у оппонентов” является довольно ресурсоемким, но зато дает отличные результаты (по крайней мере, для формально заданных агентов, хорошо умеющих доказывать теоремы).

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

Мета-стратегии лучше простых стратегий

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

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

Эта статья в моем телеграм-канале: https://t.me/bayesian_little_list/23