Теория игр
Всем ъуъ. Сегодня мы поговорим о теории игр. Это не про то, что “игрался с членом и проиграл”, а вполне себе раздел математики. Дисклеймер — чтобы что-то понимать в теории игр, было бы неплохо знать о наличии таких штук, как теория графов и теория вероятностей. Для начала хотя бы знать, понимание необязательно. Итак, поехали.
Как мы понимаем из названия, теория игр, как ни странно, относится к играм. Для начала было бы неплохо разобраться с тем, что такое игра. Честно возьму определение из педивикии: игра — в разной степени осознаваемый человеком как субъектом активности, самодеятельности и творчества (развития в целом) или даже инстинктивный способ получения и развития навыков людьми (и животными) в момент отсутствия непосредственной угрозы для жизни и развития способностей. Какое-то душное и скучное определение, поэтому мы сразу же перейдём к определению игры для нашей теории. В нашем случае игра — это процесс, в котором участвуют две и более стороны, ведущие борьбу за реализацию своих интересов. У каждой стороны есть своя цель и своя стратегия, ведущая к выигрышу или проигрышу в зависимости от поведения других игроков. С этим определением уже можно работать, этим мы и займёмся.
Итак, игра, по сути говоря, представляет из себя набор неких целей и стратегий. Целью может быть максимизация выигрыша, минимизация проигрыша — те самые “игра на победу” и “игра на ничью”. Стратегии же могут варьироваться в зависимости от целей, но такие нюансы пока что нас не интересуют. В целом уже заметно, что игру можно представить графом или матрицей. Попробуем же сделать это.
Возьмём уже классическую игру под названием “Дилемма заключённого” для двух игроков: два заключённых сидят в тюрьме по одному делу с одинаковым сроком в год, обоим предлагается сделка со следствием, если один подписывается на чистосердечное признание — второй заключённый получает 5 лет, а согласившийся освобождается, но если подписываются оба — оба и получают по 2 года. В данном случае удобно представить матрицу размером 2х2 (см. картинку), где в полях матрицы записаны результаты выбранных игроками стратегий.
Что мы видим? Если цель игрока — максимизировать выигрыш, ему выгоднее говорить, ведь в данном случае он может выиграть за счёт другого игрока. Однако, если оба игрока будут следовать этой цели, то они получат неоптимальный исход для себя. Для оптимального исхода выгодно молчать обоим, но для этого надо доверять своему оппоненту, а для этого нет оснований. Ситуация находится в некоторого рода шатком равновесии, и она получила название “равновесие Нэша” в честь одного из первых исследователей теории игр Роберта Нэша (что характерно, по закону Арнольда первым это равновесие открыл некий Курно, а Нэш показал, что оно доступно для определённого класса игр).
Между тем, мы разобрали всего лишь одну простейшую игру, при том не полностью, но при этом уже ввели кучу различных понятий. Было бы неплохо с ними разобраться, не находите? Для начала — что за матрицу мы нарисовали? Это представление нормальной формы игры, в которую входят множество игроков (в нашем случае A и B), множество стратегий одного игрока (молчит или говорит) и множество платёжных функций игрока (грубо говоря, исходы, хотя на самом деле определение сложнее). Каждую игру можно представить как подобную матрицу, но для большого количества стратегий и игроков это крайне неудобно. Теперь поговорим про исходы. Оптимальный исход — это исход, в котором суммарный выигрыш игроков максимален. В данном случае, как мы видим, (-1,-1) будет оптимальным исходом. Нет, ну если вам и вашему оппоненту внезапно доставляет сидеть в тюрьме, то вы можете сказать, что оптимальный исход (0,-5) или (-5,0), но лично мне это времяпрепровождение не нравится.
Всё это хорошо, скажете вы, а как же другие игры? Какая-нибудь дота, условно говоря. Неужели она тоже подчиняется законам теории игр? Как мы убедились в воскресенье, игра на ноль смертей не всегда приводит к победе (особенно когда дохнешь на терзателе без байбэка), но это тема для гика скорее. А в нашем случае всё зависит от требуемой точности. Почему я взял дотку — во-первых, это мемно, а во-вторых, она может помочь мне объяснить распределение игр по классам.
В первом приближении дота — это игра, в которой есть два “игрока” (Свет и Тьма, Radiant и Dire — называйте как хотите). Если мы начинаем разбираться, то выясняется, что у этих двух “игроков” (назовём их командами) есть по пять реальных игроков, которые могут договариваться внутри игры о своей стратегии на игру. Такого рода игры называются кооперативными. Окромя днотки кооперативной игрой можно назвать, к примеру, дурака 2х2. Приближаем далее и выясняем, что игроки внутри игры ходят одновременно (двигаются по карте, кидают скиллы, покупают предметы и так далее), при этом в доте реализован “туман войны” — одна команда не знает о ходах другой, пока ход не сделан. Это признак параллельной игры, в отличие от того же дурака (так называемой последовательной игры), где ходы делаются по очереди. И каждый игрок в дурака владеет всей информацией о предыдущих ходах, в отличие от доты, кстати говоря — это разделение по признаку полноты информации.
Следующий этап — это оценка ресурсов. Нет, не денег и времени, которые дота сожрала у тебя, мой дорогой читатель, и даже не ресурсов компа, с которого ты когда-то играл в эту самую доту. Я могу утверждать, что дота является так называемой “игрой с нулевой суммой”. Поясню, что имеется в виду: каждую минуту на карте появляются ресурсы на определённую сумму. Оптимальной стратегией для игроков является забрать все эти ресурсы, лишив их тем самым противника. В этом отличие доты, к примеру, от шашек: в шашках ты можешь провести дамку, тем самым увеличив суммарную ценность своих шашек, не забирая у соперника никаких ресурсов. Собственно говоря, в играх с нулевой суммой невозможна ничья, в отличие от игр с ненулевой суммой.
Итак, мы пришли к тому, что мы даже в первом приближении разработали рецепт для победы в дотке, а попутно разбили игры по классам. Я думаю, для введения в теорию игр получилось неплохо, хоть и не сильно связно. Задавайте ваши ответы. Всем обратный ъуъ.
