Теория игр

На этой странице вы узнаете

• Как  просчитать, выиграете вы или проиграете?
• Как использовать то, что мы уже знаем, чтобы узнать еще больше?
• Что делать с дробным количеством камней?

Почему камушки — это любовь?

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

Постановка задачи и основные понятия

Теория игр — раздел математики, который занимается решением проблем, связанных с разработкой и анализом стратегии в играх.

Самый простой и классический пример игры — игра с камнями:

1. Перед игроками лежит куча камней (или несколько).
2. Игрокам доступны заранее определенные действия с этой кучей. Например, добавить в нее определенное количество камней, увеличить кучу во сколько-то раз и т.д.
3. Игроки ходят строго по очереди, заранее известно, кто ходит первый.
4. Цель игры — достичь определенного состояния кучи, например, чтобы в ней было заданное количество камней.

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

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

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

Конкретнее:

• выигрышная позиция — та, играя из которой игрок гарантированно побеждает;
• проигрышная позиция — та, из которой игрок гарантированно проиграет.

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

Разбор игры

И как все-таки не проиграть?

Чтобы было с чем работать, давайте определим конкретные условия нашей игры:

1. Играют два пингвина — Петр и Виссарион. Петр будет ходить первый.
2. Перед ними лежит одна куча камней. На своем ходу игрок может добавить в кучу 1 камень или увеличить количество камней в куче в 2 раза. Например, если в куче находится 10 камней, игрок может увеличить это значение до 11 или до 20.
3. Игра продолжается до тех пор, пока в куче не окажется 52 камня или больше. Выигрывает тот, кто сделает последний ход, то есть получит 52 камня или больше.

Заметьте — в условии не сказано, сколько в куче камней изначально. И это не ошибка. Сейчас мы будем анализировать игру и предсказывать ее исходы при различных начальных позициях. Чтобы было проще, давайте скажем, что изначально в куче было Х камней. Единственное наше ограничение — Х должно быть меньше 52, так как при 52 и более игра уже заканчивается.

Петя — хороший пингвин. Давайте поможем Пете выиграть.

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

Рассмотрим, каким образом мы можем получить победное значение:

• Первый наш возможный ход — добавить в кучу один камень:

1. Х + 1 >= 52;
2. Х >= 51.

51 — первое начальное значение, из которого Петя выиграет первым ходом.

• Второй наш возможный ход — увеличить кучу в два раза:

1. Х * 2 >= 52;
2. Х >= 26.

Здесь мы получили побольше ответов — при любом Х от 26 до 51 Петя может выиграть первым ходом.

Все Х от 26 до 51 — выигрышные позиции. Любое из этих значений можно умножить на 2 и получить нужный результат. Это стоит запомнить.

Мы можем конкретизировать определение выигрышной позиции:

Выигрышная позиция — та, из которой есть ход к финальному значению.

Что, если есть такая позиция, из которой Петя никак не сможет выиграть? Есть ли такое Х, при котором Виссарион выиграет своим первым ходом после любого хода Пети?

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

Из начального Х Петя сможет получить либо Х + 1, либо Х * 2. Проверим, чтобы эти ходы не дали Пете победу, а Виссарион после каждого из этих ходов смог выиграть. При этом за ход Виссариона предлагаем рассмотреть только умножение на два. Добавить в кучу 1 камень звучит слабо, умножение явно даст более продуктивный результат как самый сильный ход.

Тогда надо решить систему неравенств:

1. Ходы Пети не набирают нужное количество.
2. Ходы Виссариона — набирают

Чтобы найти решение, можем занести все результаты на числовую прямую и выбрать на ней участок, на котором пересекаются все значения X :

Получается, что в данном случае 25 — единственное значение Х, при любой игре из которого Петя проиграет, а Виссарион выиграет на своем первом ходу.

25 — проигрышная позиция: тот, кто из нее будет ходить, однозначно проиграет. Но давайте разберемся поподробнее, что именно делает позицию 25 проигрышной?

Петя на своем ходу может получить либо 25 + 1 = 26, либо 25 * 2 = 50. Вспомним, что мы уже выяснили: все числа из диапазона [25, 51] — это выигрышные позиции. То есть получается, что Петя дарит своим ходом Виссариону выигрышную позицию, из которой тот играет и, соответственно, выигрывает.

Уточним определение проигрышной позиции:

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

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

Давайте попробуем построить дерево вариантов такой игры. Так как мы еще не знаем, какой первый ход должен сделать Петя, запишем, что из значения Х он получит значение S. Потом выясним, как именно: S = X + 1 или S = X * 2.

Как использовать то, что мы уже знаем, чтобы узнать еще больше? Выделенный блок ничего вам не напоминает?Дерево такой же формы мы строили, когда нашли проигрышную позицию 25. Значит ли это, что если позиция, из которой будет ходить Виссарион, будет проигрышной, то Петя выиграет? Конечно. Проигрышная позиция на то и есть проигрышная: кто бы из нее ни играл, он не выиграет. Значит, в качестве S можно брать известное значение проигрышной позиции, и S = 25. Как же мы можем получить это S из Х? 1. 25 = Х + 1 —> Х = 24; 2. 25 = Х * 2 —> Х = 12,5.

К Х = 24 нет вопросов. Можем даже проверить, построив для него дерево вариантов:

Как видите, любой второй ход Пети — выигрышный при любой игре Виссариона.

Что делать с дробным количеством камней? Если при таком алгоритме мы нашли целое число, оно точно будет подходящим. А дробным ответ быть не может, так как количество камней — это целое число. Но просто так исключать дробные значения не стоит. Иногда необходимо округлить дробное значение вниз и проверить его. Тогда мы проверим не только найденное S, но и близкое к нему значение. Округлять вверх нельзя, так как найденное нами S — граничное значение. Если получим больше, то пойдем в обход алгоритма и получим не тот результат.

Близкое к S = 25 значение из Х = 12 мы можем получить 24. Проверим этот ход:

Гарантии выигрыша за 2 хода нет, так что это значение нам не подходит.

А вот Х = 24 подошло. Из этой позиции есть стратегия, которая гарантирует выигрыш за 2 хода, значит, 24 — выигрышная позиция. Но если вспомнить, как именно мы нашли это значение, можно добавить еще одно определение этой позиции:

Выигрышная позиция — та, из которой есть хотя бы один ход, ведущий в проигрышную.

Теперь, зная, что такое выигрышная и проигрышная стратегия, а также умея строить стратегия, мы готовы переиграть любого пингвина.

Потренируемся применять полученные навыки на примере задачи 19 номера ЕГЭ.

Задание. Играют два пингвина — Петр и Виссарион. Петр будет ходить первый.

1. Перед ними лежит одна куча камней. На своем ходу игрок может добавить в кучу 1 камень или увеличить количество камней в куче в 2 раза. Например, если в куче находится 10 камней, игрок может увеличить это значение до 11 или до 20.
2. Игра продолжается до тех пор, пока в куче не окажется 102 камня или больше. Выигрывает тот, кто сделает последний ход.
3. В начальный момент в куче лежит Х камней (1 <= X <= 101).

Укажите такое Х, при котором Виссарион выиграет своим первым ходом после любого хода Пети.

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

Тогда надо решить систему неравенств:
1. Ходы Пети не набирают нужное количество.
2. Ходы Виссариона — набирают.

Тогда имеем:

Если решим каждое из них, получим:

Нанесем эти значения на числовую прямую и найдем решение.

Находим, что единственное значение, подходящее под условия — 50. Это и будет ответом.

Ответ: 50

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

Фактчек

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

Проверь себя

Задание 1.
Что такое теория игр?

1. Любое развлечение, в котором можно выиграть призы.
2. Модель, изучающая анализ игр и поиск стратегий.
3. Вид спорта, включающий соревнование между командами.
4. Вид спектакля в театре.

Для заданий ниже предложена задача. Условие:

1. Играют два пингвина — Петр и Виссарион. Петр будет ходить первый.
2. Перед ними лежит одна куча камней. На своем ходу игрок может добавить в кучу 2 камня или увеличить количество камней в куче в 3 раза. Например, если в куче находится 10 камней, игрок может увеличить это значение до 12 или до 30.
3. Игра продолжается до тех пор, пока в куче не окажется 90 камней или больше. Выигрывает тот, кто сделает последний ход.
4. В начальный момент в куче лежит Х камней (1 <= X <= 89).

Задание 2.
Выберите, какие из предложенных значений Х дадут выигрыш Пете первым же его ходом?

1. 10
2. 20
3. 30
4. 40

Задание 3.
Выберите значения Х, при котором Виссарион выиграет своим первым ходом после любого хода Пети:

1. 27
2. 28
3. 29
4. 30

Задание 4.
Из предложенных, выберите значение Х, при котором Петя не может выиграть первым ходом, но у него есть стратегия, позволяющая ему выиграть вторым своим ходом после любого хода Виссариона:

1. 9
2. 10
3. 14
4. 26

Ответы:  1. – 2; 2. – 34; 3. – 23; 4. – 4.