Оригинал: COTW: Introduction to Game Theory 

Автор: Cangurino

Дата: 2010-07-22


Теория игр - это раздел математики, изучающий стратегические ситуации, в которых успех игрока зависит не только от его выбора, но также и от выбора других игроков. Мы используем термин "игры", несмотрря на то, что эта теория находит применение в экономике и социальных науках. Основой данной теории является "Theory of Games and Economic Behavior" (1944)} авторов J. von Neumann и O. Morgenstern.


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


Игра состоит из:

1. совокупности игроков;

2. состояния игры;

3. набора варианттов или возможных ходов каждого игрока, в зависимости от его положения;

4. функция поощрения каждого игрока, в зависимости от конечного положения.

Пример: Камень-ножницы-бумага.

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


Мы можем визуализировать различные исходы в виде матрицы:


К Б Н

К 0 - +

Б + 0 -

Н - + 0


По-вертикали - знаки первого игрока, по горизонтали - второго, ячейка на пересечении показывает исход для первого игрока.


Так как выигрыш первого игрока всегда численно равен проигрышу второго, сумма результатов всегда равна 0. Поэтому мы говорим "игра двух игроков с нулевой суммой" - описывая таким образом важный класс игр.


Пример 2: Шахматы.

Пример 3: Трехкарточный покер. Используем колоду из трех карт - туза, короля и дамы. Старшинство карт стандартное:  A>K>Q. Два игрока, А и Б, получают по одной карте. Оба игрока платя анте в $1. Игрок А ходит первым и либо делает чек, либо ставит $1. Если игрок А чекает, игрок Б тоже может чекнуть в ответ. Если А ставит, Б может сбросить или ответить. Если Б сбросит, игрок А забирает анте, иначе банк выигрывает лучшая рука.


Итак, это игра для двух игроков с нулевой суммой. Что здесь особенного, так это то, что игровое положение неизвестно обоим игрокам, так оба не знают какая карта у оппонента.Это называется игра с "неполной информацией". Шахматы - игра с полной информацией; камень-ножницы-бумага не имеет состояния как такового, так как каждый игрок знает все, т.е. ничего. [Коан, прим.перев.]


Стратегии


Стратегия игрока - это его план на игру. В нем говорится как действовать в каждой игровой ситуации. Говоря математически - это отображение (или функция) пространства игровых состояний на множество допустимых ходов. Одна из возможных стратегий для игрока А в 3-хкарточном покере может быть: рейз с тузом, рейз с королем, фолд с дамой. Одной из возможных стратегий для игрока Б может быть: колл с тузом, фолд с королем, колл с дамой.


Задав стратегии для обоих игроков мы можем определить исход для каждой комбинации карт:

(A,K): A bets, B folds, A wins $1

(A,Q): A bets, B calls, A wins $2

(K,A): A bets, B calls, B wins $2

(K,Q): A bets, B calls, A wins $2

(Q,A): A checks, B wins $1

(Q,K): A checks, B wins $1


Итак из шести возможных исходов игрок А выиграет 121-1=1, т.е. усредненный винрейт игрока А составит $0.17 за игру.


Более популярным синонимом понятия "усредненный" является "ожидаемое значение" или EV, но смысл от этого не меняется. Итак, мы утверждаем, что задав две стратегии для игроков А и Б ожидаемое значение составит +$0.17 для A, and -$0.17 для Б.


В игре камни-ножницы-бумага каждому игроку доступны только три стратегии: выбор одного из трех символов. Если бы игрок Б знал стратегию игрока А, он мог бы каждый раз корректировать свой выбор и выигрывать. Если А выбирает камень, Б должен выбрать бумагу, и таким образом выиграет.


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


(A,K): +1

(A,Q): +1

(K,A): -2

(K,Q): +1

(Q,A): -1

(Q,K): -1


Теперь игрок B выигрывает $1, или $0.17 в среднем.


Зная стратегию игрока А, у Б пояилась возможность подстроиться. Можно сказать, что Б эксплуатирует стратегию А.

Данная стратеги оппонента, или эксплутирующая стратегия, - та, что максимизирует наше EV против оппонента.

Однако теперь игрок А может подстроиться в ответ; он прекратит ставить с королем и вместо этого станет ставить с дамой; это уменьшит EV игрока Б.


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


Для упрощения мы можем определить несколько критериев, которым должна удовлетворять хорошая стратегия:

  • Б всегда должен сбрасывать даму, так она не бьет ничего
  • Б всегда должен коллить с тузом, так как он гаратировано выиграет
  • А всегда ставит с тузом. Если Б фолдит - мы ничего не теряет, а если Б отвечает, то мы зарабатываем дополнительный $1? по сравнению с чеком
  • А никогда не ставит с королем, т.к. ему ответит только туз


Итак, единственной интересной ситуацией является, когда игрок А получает даму, а игрок Б - короля.

  • Если Б коллит с королем, то игрок А не должен рейзить с дамой, так как ему всегда ответят.
  • Если А не ставит с дамой, это означает, что он ставит только с тузом, поэтому Б должен сбросить короля.
  • Если Б сбрасывает короля, то А может блефовать с дамой, так как он либо выиграет $1 (против короля), либо проиграет $2 (против туза), т.е. в среднем он потеряет $0.50, в то время как чекая он теряет $1.
  • И наконец, если А ставит с дамой, то Б должен отвечать с королем (рискуя $1 ради $3, выигрывая в половине случаев).


Если игроки эксплуатируют стратегии друг друга, мы попадаем в замкнутый круг: Б колл -> A чек -> B фолд -> A бет -> B колл.


Далее - Смешанные стратегии и балансировка.