В комментариях к моей статье о вычислительной сложности игр и в личных беседах проявился явный интерес к поведенческим играм антагонистической природы, однако тут не всё так просто. Такие игры несут значительную вероятностную нагрузку и простые подходы к сложности неприменимы (прошу прощения за каламбур). Тем не менее многие игры такого характера также не раз становились предметом исследований, в результате которых были разработаны математические модели этих игр.
В сегодняшней статье речь пойдёт об игре, о которой я, к своему стыду, узнал всего лет пятнадцать назад, хотя она появилась ещё в 1986 году и стала достаточно популярной уже в середине 90-х. Сегодня найти человека, который ничего не знал бы об этой игре, практически невозможно. Я говорю о «Мафии».
«Мафия» — клубная командная психологическая пошаговая ролевая игра, созданная в 1986 году студентом МГУ Дмитрием Давыдовым, базируется на культурно-исторической теории советского психолога Л. С. Выготского. В Википедии достаточно подробно описана сама игра и её варианты, но существуют и классические правила.
В общем, различные варианты игры похожи, и все участники разделены на две конкурирующие фракции: красная команда — «мирные жители», чёрная команда — «мафия». Цель игры состоит в том, чтобы уничтожить группу противника. Игра состоит из двух последовательных фаз (дневной и ночной) и определённого набора действий. Члены мафии обладают определёнными фичами (знают друг друга, убивают ночью), тогда как «мирных жителей» больше. Оказывается, что относительно небольшое количество членов «мафии», т. е. пропорциональное квадратному корню из общего числа игроков, даёт равные шансы на выигрыш для обеих групп. Кроме того, игра сильно зависит от чётности общего числа игроков.
