Динамические игры с полной и совершенной информацией

Рассмотрим последовательную игру двух игроков.

• 1. Первый игрок выбирает ход а из допустимого множества А.
• 2. Второй игрок анализирует а и затем выбирает ход b из допустимого множества В.
• 3. Платежные функции игроков равны щ (а, Ь), и₂(а, Ь).

Это пример игры с полной и совершенной информацией. Для решения такой игры применяется метод обратной индукции (от конца к началу).

Ключевыми позициями в динамических играх с полной и совершенной информацией являются следующие: а) ходы осуществляются последовательно;

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

К моменту выбора хода второму игроку известен ход первого а.

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

Предположим, что для каждого выбора а существует единственное решение задачи максимизации платежной функции второго игрока. Обозначим это решение b = f (a). Но поскольку оба игрока обладают полной информацией о платежных функциях каждого, то эта же задача максимизации может быть решена и первым игроком. Тогда для него оптимальным выбором на первом шаге будет такой ход а*, который является решением задачи.

Каждое из полученных таким образом решений (a, f (a)) называется обратно-индукционным исходом для данной игры.

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

Замечание. Строго говоря, обратно-индукционный исход сам по себе не является исходом в том смысле, как мы его определили в гл. 1 (как совокупность стратегий, но одной для каждого игрока). Действительно, под f (a*) здесь понимается ход второго игрока, его реакция на ход а* первого игрока, но не его стратегия. Стратегия, напомним, подразумевает инструкцию, указывающую, как действовать игроку во всех возможных ситуациях, — это не определено в ходе f (a*). Но в литературе по теории игр за комбинацией (a*, f (a)) закрепилось понятие обратно-индукционного исхода.

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

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

Пример 3.1. Пусть задана игра в развернутой форме (рис. 3.1).

Рис. 3.1.

Для определения обратно-индукционного исхода в этой игре рассмотрим последний, третий этап. Поскольку для первого игрока более предпочтителен исход (3, 0), он выберет ход е, при котором его выигрыш равен 3. Следовательно, игрок 2 в этой ситуации получит 0. При этом важно понимать, что второй игрок может поставить себя на место первого, и поэтому он знает, что на этом этапе первый игрок сыграет е. Поэтому мы можем сократить игру до состояния, указанного на рис. 3.2.

Рис. 3.2.

Второй игрок при выборе оптимального решения на втором этапе выбирает между ходом с, при котором он получит 1, и ходом (1, при котором он получит 0. Следовательно, ход с для него оптимален. При этом исходе оба игрока получают по 1. К этому же выводу может прийти и первый игрок, поставив себя на место второго. Игру можно рассмотреть теперь в сокращенном виде (рис. 3.3).

Рис. 3.3.

На первом этапе игры первый игрок, таким образом, выбирает между ходом а, при котором он получит 2, и ходом Ь, при котором он получит 1. Для него оптимальным будет ход а.

Обратно-индукционным исходом для данной игры является выбор первым игроком хода а, после которого игра заканчивается.

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

Рассмотрим еще несколько примеров.

Пример 3.2. В игре участвуют три игрока. Сначала первый игрок выбирает xeR; затем второй игрок, зная .г, выбирает yeR) затем третий игрок, зная х и у, выбирает z е [1; 2]. Функции выигрыша имеют вид.

Какие х, у и z будут реализованы игроками при использовании ими метода обратной индукции?

Решение

Поскольку последним ходит третий игрок, то в своем выборе он руководствуется максимизацией функции по переменной z.

Условие первого порядка для экстремума:

Но поскольку , г. е. С₃ является убывающей по z.

функцией при z € [1; 2], то ее максимум достигается на левом конце: z = 1.

Причем важно понимать, что к этому выводу пришел не только третий игрок, но и первые два, поскольку могут решить за него эту задачу.

Тогда функция выигрыша второго игрока имеет вид

Условие первого порядка для экстремума:

Поскольку , то выполняется достаточное условие максимума.

Решение может получить и первый игрок и использовать знание отклика второго игрока, подставив его в свою функцию выигрыша:

Теперь нетрудно найти точку максимума функции и затем находим

Ответ:

Пример 3.3 (игра NIM). В кучке 100 камней. Игроки (Саша и Маша) по очереди берут один или два камня. Проигрывает тот, кто не может сделать ход. Первым ходит Саша. Кто выигрывает при правильной игре (использовании метода обратной индукции)?

Решение

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

Пусть теперь на столе осталось три камня. При ходе Саши поставим вопрос: Может ли Саша своим ходом поставить Машу в проигрышную позицию? Оказывается, нет. Следовательно, для него это проигрышная позиция, и мы в этом случае поставим в таблице знак «минус» — это означает, что Саша при его ходе в случае п = 3 проигрывает. То же самое можно сказать и о Маше, если у нее первый ход при трех камнях на столе:

Пусть теперь на столе осталось четыре камня. При ходе Саши поставим вопрос: Может ли Саша своим ходом поставить Машу в проигрышную позицию? Оказывается, да, может, взяв один камень (при этом ход передается Маше и на столе окажется три камня — для нес проигрышная ситуация). Следовательно, для Саши при четырех камнях и его ходе позиция выигрышная, и мы в этом случае поставим в таблице знак «плюс» — это означает, что Саша при его ходе в случае п = 4 выигрывает. То же самое можно сказать и о Маше, если ее ход при четырех камнях на столе:

Продолжая этот процесс, получим следующую последовательность строк:

Видно, что картинка повторяется через каждые три строки. Поскольку остаток от деления 100 (количества камней на столе) на 3 равен 1, то сотая строка будет содержать два плюса (как и первая). Следовательно, поскольку первым, но условию ходит Саша, то он и выиграет при правильной игре. Его выигрышная стратегия заключается в том, чтобы число камней, оставшихся после его хода, было кратным 3.

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

Пример 3.4. В кучке 100 камней. Игроки (Саша и Маша) ходят по очереди. Саша может взять один или четыре камня, Маша — два или три камня. Выигрывает тот, кто не может сделать ход. Кто выигрывает при правильной игре в двух случаях: а) первым ходит Саша; б) первой ходит Маша?

Решение

Пусть на столе остался один последний камень и ходит Саша. Тогда он проигрывает, поскольку забирает один камень и Маша не может сделать ход. Если же ходит Маша, то она выигрывает, поскольку не может сделать ход:

Пусть теперь на столе осталось два камня. При ходе Саши положение для него проигрышное. Действительно, он берет один камень, и Маша оказывается в выигрышном положении (см. строку 1). Если же ходит Маша, то она вынуждена забрать два камня, и выигрывает Саша. Значит, для Маши это тоже проигрышная ситуация:

Пусть теперь на столе осталось три камня. При ходе Саши поставим вопрос: Может ли Саша своим ходом поставить Машу в проигрышную позицию?

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

Продолжая этот процесс, получим следующую последовательность строк:

Видно, что картинка, начиная сп = 7, повторяется в каждой строке: Саша проигрывает, а Маша выигрывает. Следовательно, и при п = 100 независимо от того, кто ходит первым, выигрывает Маша.

Пример 3.5. В некой сказочной стране живут Малыш и Карлсон. И в этой сказочной стране есть сказочный календарь, в котором 10 месяцев (Л, В, С, …, У) и в каждом месяце всего 10 дней. Календарь в этой стране имеет вид, представленный на рис. 3.4.

Рис. 3.4.

Ежедневно в месяц А Малыш и Карлсон играют такую игру. Сначала Малыш называет текущую дату месяца А. Далее Карлсон называет более позднюю дату, увеличивая либо календарную дату на 1 или на 2, либо месяц на 1, но не то и другое сразу. Если, например, начальной датой было 8Л, то можно перейти к 9Л, или к ЮЛ, или к 8В. Если игрок переходит к ЮЛ, то его противник сможет в дальнейшем перейти лишь к следующим календарным датам, т. е. к 1 В, или 2 В, или к 10 В. Первый, кто доберется до 10/, выигрывает. При выборе стратегий игроки применяют метод обратной индукции.

Какова выигрышная стратегия Малыша?

Решение

Составим вспомогательную таблицу, заполняя ее от конечной даты 10/. Игрок может попасть в эту дату, находясь в ячейках 9/, 8/или 10/. Поставим в этих ячейках число 1, которое будет означать победные даты. В ячейку 7/ мы поставим нуль, означающий дату проигравшего. Действительно, какой бы ход ни сделал игрок, находясь в этой клетке, его противник на следующем ходе окажется в победной клетке с единицей (рис. 3.5).

Рис. 3.5.

Далее продолжаем процесс заполнения таблицы снизу вверх и справа налево. В результате получим заполненный календарь выигрышных (1) и проигрышных (0) дат (рис. 3.6).

Рис. 3.6.

Выигрышные даты для Малыша в месяце А — это даты 3п или 3/? — 1, где п-1,2,3.