Теория игр. История создания и применение

в 10:53, , рубрики: game development, Gamedev, vircities, анализ, Анализ и проектирование систем, Блог компании IlkFinKom, история, математика, проектирование, социальное взаимодействие, теория игр, метки:

Знакомьтесь, перед вами праотцы всего современного геймдева.

image

Именно этим великим учёным игровая индустрия обязана самим фактом своего существования в современном виде. Они создали знаменитую «Теорию игр»: методологическую концепцию принятия решений участником любой игры. Как работа Денниса Ритчи, создателя языка программирования С, повлияла на весь дальнейший ход развития IT, так и описание теории игр определило вектор развития индустрии и появление профессии геймдизайнера.

История появления

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

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

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

В 1944 году за авторством Моргенштерна и фон Неймана была опубликована книга «Теория игр и экономическое поведение», в которой:

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

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

Но это только начало. Спустя 5 лет, в 1949 году, Джон Нэш в своей диссертации значительно расширил теорию игр, допустив ситуации, когда игроки не конкурируют между собой, а кооперируются для достижения общей цели (кооперативные игры). Более того, Нэш также ввёл понятие «игр с ненулевой суммой», в которых выигрыш был не константой (игры с нулевой суммой), а мог изменяться от действий игроков. Для своего времени это был настоящий прорыв в изучении игрового взаимодействия, наглядно показавший всю ветхость «классического» понятия о конкуренции (когда каждый сам за себя). За эту диссертацию Джон Нэш даже получил нобелевскую премию (единственный из этих троих, кстати).

А дальше уже пошло-поехало. Теория игр стала Граалем для мирового научного сообщества, ибо она прекрасно описывала не только поведение игроков во время игры, но и поведение любого мыслящего существа. В последующие годы выходит множество основанных на теории игр научных работ в самых разных областях:

  • политология;
  • психология;
  • конфликтология;
  • юриспруденция;
  • биология (теория эволюции);
  • кибернетика (создание искуственного интеллекта) и т.д.

Так что же это такое

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

Применяется теория игр так:

  1. Геймдизайнер задаёт ситуацию, определяя правила игры и игроков в ней (через эти самые формулы, параметры и показатели).
  2. Исследуя поведение тех или иных игроков, он получает (составляет) комбинаторное уравнение.
  3. Решая это уравнение, геймдизайнер понимает, как исследуемые игроки будут действовать заданной ситуации.
  4. ?????
  5. PROFIT!!!

Вы спросите: «Так где же здесь теория игр?». А она здесь в чертогах разума геймдизайнера. Знание и понимание теории игр как раз и позволяет задавать ситуации и прогнозировать поведение игроков.

Альфа и Омега

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

Равновесие по Нэшу:

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

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

Равновесие по Парето:

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

Иными словами, при стратегии «каждый сам за себя» игроки рано или поздно придут к равновесию по Нэшу, а при стратегии «кооперируемся» — максимизируют общий выигрыш и приходят к равновесию по Парето.

Наглядный пример

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

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

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

Клиентура, пребывая в восторге от снижения цен на выпивку, ринулась обратно к этим двоим. Разумеется, хозяин первого бара, видя это, тоже снижает цену, а потом ещё, ещё и ещё. Рано или поздно все три бармена окажутся в ситуации, когда цена продажи рома сравняется с ценой его закупки, то есть дальше её снижать будет попросту некуда. Все игроки находятся в одинаково плохих условиях, но ничего не могут с этим сделать: уменьшать цену нельзя, увеличивать тоже, потому что никто не будет покупать. Это и есть равновесие по Нэшу.

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

Кончились радужные деньки для пассажиров, цена на самый ликвидный в морском круизе товар взлетела до небес, причём у всех троих одновременно. А что поделать — монополия. Теперь уже начинается другая игра: бары всё выше поднимают цены на ром и смотрят, сколько людей продолжают покупать его. Объемы продаж падают, но маржа растёт.

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

Цена является возрастающей функцией от времени, количество покупателей — убывающей функцией от цены, функция дохода от времени равна произведению этих двух функций, а её максимум — и есть равновесие по Парето:

image

Произведение функций:

image

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

Область применения

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

Конкретные случаи применения зависят от конкретных задач:

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

Вместо эпилога

Для нас, в ходе разработки VirCities, использование теории игр было не прихотью, а необходимостью. Разрабатывая социально-экономическую игру перед геймдизайнером, фактически, ставится задача создать максимально сбалансированный и продуманный полигон подтверждения механизмов, описанных Моргенштерном, фон Нейманом и Нэшем. В реальности рынок является саморегулирующимся механизмом, однако, разработчик выступает своего рода «регулятором», который определяет «правила» игры и инструментарий. Огромное внимание было уделено достаточной гибкости, для того, чтобы теория игр отрабатывала в рамках игры корректно. К сожалению, ошибки в проектировании и анализе необходимых для стабильного существования всей системы механизмов часто приводят проекты, подобные нашему, к полному краху с течением времени.

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

Надеюсь, было интересно. Спасибо за внимание.

image

Автор: leooverlight

Источник

Поделиться

* - обязательные к заполнению поля