Умскул учебник стремится стать лучше! Если вы наткнулись на ошибку или неточность в нашем материале - просто сообщите нам, мы будем благодарны!
Информатика

Теория игр. Программное решение

7.5.2022
4844

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

  • Как выбрать пуленепробиваемую логику решения?
  • Как будет выглядеть общая структура необходимых функций?
  • Что делать, если не выиграл первым ходом?

Чем пингвин-киборг круче самца пингвина? Вторые имеют неограниченное количество камней и придумывают разнообразные азартные игры с ними. А пингвины-киборги довольно умны, чтобы не играть в азартные игры на свои драгоценные камни, и настолько самодостаточны, что играют только с собой. 

Идея решения

В статье «Теория игр» мы подробно рассмотрели, как не проигрывать в играх с камнями или заранее знать, что проиграем. Если вы еще не знакомы с этой темой, советуем сначала заглянуть в ту статью, а потом вернуться сюда.

Итак, мы детально разбираемся в теории игр и полны решимости применять знания на практике. Пора заставить программу выполнить за нас всю работу! Но как же это сделать?

Как выбрать пуленепробиваемую логику решения?

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

1. Найти очевидные выигрышные позиции.
2. Определить самые простые проигрышные позиции.
3. Перейти к более сложным выигрышным или проигрышным позициям.

Неплохо было бы и программе дать знать, как найти и проверить выигрышные и проигрышные позиции. Здесь нам пригодятся функции из статьи «Функция и рекурсия».

  1. Одна функция будет проверять позиции на выигрыш за один ход.
  2. Другая будет проверять проигрышные позиции за один ход. Из них будут ходы в выигрышные, что мы определим с помощью первой функции.
  3. Третья сможет проверить более сложные выигрышные позиции. Они приведут в проигрышные, что мы определим с помощью второй функции.

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

Реализация решения

Для решения задачи нужно придумать саму задачу. Пусть условие будет такое:

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

В начале игры в куче лежало Х камней (1 <= X <= 202).

Как будет выглядеть общая структура необходимых функций?

Общая структура функций будет достаточно простой:
1. В аргументах функции передадим текущее количество камней в куче.
2. Ключевая часть — проверка позиции. Организуем ее с помощью логических операторов и возможных ходов.
3. Функция может сразу возвращать значение условия —  True или False — условие либо выполнилось, либо нет. Этого достаточно.

Когда мы рассмотрели общую логику решения, перейдем к более конкретным условиям для достижения победы.

Проверка выигрыша за 1 ход

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

Из каких позиций Петр выиграет первым ходом?

Позиция, выигрышная за 1 ход, — та, из которой есть хотя бы один такой ход, который даст нам выигрышное значение.

Проверяем возможные ходы. Хотя бы один из них должен дать выигрышное значение — 203 и больше. Когда нужен «хотя бы один» — используем or.

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

Итак, вид функции будет следующим:


def win1(X):
	return (X < 203 and (X + 3 >= 203 or X * 4 >= 203))

Найдем с ее помощью все позиции, выигрышные за 1 ход. Используем цикл for и переберем диапазон значений Х. Найдя подходящее, занесем его в отдельный массив. Тогда мы сразу получим все подходящие значения и без проблем узнаем любую информацию о них: количество, минимальное или максимальное значение и так далее.


def win1(X):
	return (X < 203 and (X + 3 >= 203 or X * 4 >= 203))

ans = []
for i in range(1, 203):
	if win1(i):
		ans.append(i)

print(len(ans))

_____________________________________________________________________
Вывод: 152

Здорово! Мы помогли Пете выиграть первым ходом. А что будет, если Виссарион выиграет первым ходом, как найти данные значения? Об этом мы поговорим далее.

Проверка проигрыша за 1 ход

Из каких позиций у Пети нет никаких шансов обыграть Виссариона? 

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

Проверка будет иметь несколько отличий:

  1. Выигрышную позицию проверим с помощью уже написанной функции win1 — будет ли новая позиция после нашего хода выигрышной.
  2. Так как каждый ход должен вести в выигрышную позицию, будем использовать and.
  3. Дополнительная проверка — из текущей позиции нельзя выиграть. Если из текущей позиции можно и выиграть, и проиграть — зачем проигрывать? Шансы на победу нас сейчас не интересуют.

Функция будет иметь следующий вид:


def loss1(X):
	return ((not win1(X)) and win1(X + 3) and win1(X * 4))

Поиск подходящих значений будет происходить так же, как и в предыдущей задаче — перебором подходящих значений и их сохранением в массив:


def win1(X):
	return (X < 203 and (X + 3 >= 203 or X * 4 >= 203))

def loss1(X):
	return ((not win1(X)) and win1(X + 3) and win1(X * 4))

ans = []
for i in range(1, 203):
	if loss1(i):
		ans.append(i)

print(ans)
_____________________________________________________________________
Вывод: [48, 49, 50]

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

Проверка выигрыша за 2 хода

Рассмотрим более сложную позицию.

Что делать, если не выиграл первым ходом?

При каких условиях Петр однозначно обыграет Виссариона, но не с первого своего хода, а только со второго?

Хотя бы один ход из такой позиции должен передать проигрыш нашему сопернику.

Как будем действовать?
1. «Хотя бы один ход» — используем or.
2. Для проверки используем уже написанную функцию loss1 — будет ли позиция после нашего хода проигрышной.
3. Дополнительная проверка по условию задачи — из текущей позиции нельзя выиграть за 1 ход.

Вид самой функции:


def win2(X):
	return ((not win1(X)) and (loss1(X + 3) or loss1(X * 4)))

Поиск подходящих значений с ее помощью:


def win1(X):
	return (X < 203 and (X + 3 >= 203 or X * 4 >= 203))

def loss1(X):
	return ((not win1(X)) and win1(X + 3) and win1(X * 4))

def win2(X):
	return ((not win1(X)) and (loss1(X + 3) or loss1(X * 4)))

ans = []
for i in range(1, 203):
	if win2(i):
		ans.append(i)

print(ans)
_____________________________________________________________________
Вывод: [12, 45, 46, 47]

Изучение теории игр — это замечательная возможность забрать по баллу за три задачи на ЕГЭ, с помощью практически одной и той же программы. Это номера 19, 20 и 21. 
Задание. Играют два пингвина — Петр и Виссарион. Петр будет ходить первый.
Перед ними лежит одна куча камней. На своем ходу игрок может добавить в кучу 1 камень или увеличить количество камней в куче в 2 раза. Например, если в куче находится 10 камней, игрок может увеличить это значение до 11 или до 20.Игра продолжается до тех пор, пока в куче не окажется 102 камня или больше. Выигрывает тот, кто сделает последний ход.В начальный момент в куче лежит Х камней (1 <= X <= 101).
Задание 19. Известно, что Виссарион выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Решение. Используем код, который мы обсуждали ранее. Но нам необходимо будет вывести только минимум из всех значений, а также в функции сделать проверку на то, что Виссарион хотя бы одним любым ходом может выиграть. Ранее же мы проверяли два хода.

def win1(X):
        return (X < 102 and (X + 1 >= 102 or X * 2 >= 102))

def loss1(X):
      return ((not win1(X)) and (win1(X + 1) or win1(X * 2)))

ans = []
for i in range(1, 102):
      if loss1(i):
      ans.append(i)

print(min(ans))

Задание 20. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия:— Петя не может выиграть за один ход;— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Виссарион.Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
Решение. В данном случае решение полностью аналогично тому, что мы рассмотрели при проверке выигрыша на 2 хода.

def win1(X):
        return (X < 102 and (X + 1 >= 102 or X * 2 >= 102))

def loss1(X):
        return ((not win1(X)) and win1(X + 1) and win1(X * 2))

def win2(X):
        return ((not win1(X)) and (loss1(X + 1) or loss1(X * 2)))

ans = []
for i in range(1, 102):
      if win2(i):
        ans.append(i)

print(ans)
Задание 21. Найдите минимальное значение S, при котором одновременно выполняются два условия:— у Виссариона есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;— у Виссариона нет стратегии, которая позволит ему гарантированно выиграть первым ходом.Решение. Также аналогично тому, о чем мы говорили, но рассматриваем выигрыш за 3 хода и прописываем условия, удовлетворяющие самой задаче.
def win1(X):
        return (X < 102 and (X + 1 >= 102 or X * 2 >= 102))

def loss1(X):
        return ((not win1(X)) and win1(X + 1) and win1(X * 2))

def win2(X):
        return ((not win1(X)) and (loss1(X + 1) or loss1(X * 2)))
def loss12(X):
        return win1(X+1) and win2(X*2) or win1(X*2) and win2(X+1)
ans = []
for i in range(1, 102):
      if loss12(i):
        ans.append(i)

print(min(ans))
Ответы: 19 26; 20 2549; 21 48.

Изучение теории игр — это замечательная возможность забрать по баллу за три задачи на ЕГЭ, с помощью практически одной и той же программы. Это номера 19, 20 и 21. 

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

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

Задание 19. Известно, что Виссарион выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.

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

def win1(X):
        return (X < 102 and (X + 1 >= 102 or X * 2 >= 102))
def loss1(X):
      return ((not win1(X)) and (win1(X + 1) or win1(X * 2)))
ans = []
for i in range(1, 102):
      if loss1(i):
      ans.append(i)
print(min(ans))

Задание 20. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причем одновременно выполняются два условия:— Петя не может выиграть за один ход;— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Виссарион.Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Решение. В данном случае решение полностью аналогично тому, что мы рассмотрели при проверке выигрыша на 2 хода.

def win1(X):
        return (X < 102 and (X + 1 >= 102 or X * 2 >= 102))
def loss1(X):
        return ((not win1(X)) and win1(X + 1) and win1(X * 2))
def win2(X):
        return ((not win1(X)) and (loss1(X + 1) or loss1(X * 2)))
ans = []
for i in range(1, 102):
      if win2(i):
        ans.append(i)
print(ans)

Задание 21. Найдите минимальное значение S, при котором одновременно выполняются два условия:— у Виссариона есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;— у Виссариона нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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

def win1(X):
        return (X < 102 and (X + 1 >= 102 or X * 2 >= 102))
def loss1(X):
        return ((not win1(X)) and win1(X + 1) and win1(X * 2))
def win2(X):
        return ((not win1(X)) and (loss1(X + 1) or loss1(X * 2)))
def loss12(X):
        return win1(X+1) and win2(X*2) or win1(X*2) and win2(X+1)
ans = []
for i in range(1, 102):
      if loss12(i):
        ans.append(i)
print(min(ans))

Ответы: 19 — 26; 20 — 2549; 21— 48.

Теория игр — важный аспект не только программирования, но и математики в целом. С позиций теории игр можно оценивать как законы спроса и предложения для экономических моделей, так и поведение людей с точки зрения психологии. Что общего между рекламными акциями двух крупных компаний (например, Nike и Adidas) и гонкой вооружений во время Холодной войны? И то и другое описывается концептами теории игр, на основе которых можно делать предсказания о поведении участников каждой из ситуаций. И подобные применения теории игр можно встретить в различных науках….

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

Фактчек

  • Написание функций для проверки позиций на выигрышную/проигрышную — идеальный вариант, так как так мы сможем использовать их повторно в последующих проверках.
  • Если проверяем позицию на выигрышную за два хода, нужно получить хотя бы одну проигрышную позицию. В проверке ходов используется or.
  • Если проверяем позицию на проигрышную, нужно, чтобы каждая из позиций после хода игрока была выигрышной. В проверке используем and.
  • Нельзя забывать про дополнительные условия — какие позиции не должны рассматриваться, какими позиции не должны быть.

Проверь себя

Условие задачи:

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

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

def win1(X):
        return _________

  1. (X <145 and (X + 3 >= 144 or X*8 >= 145)).
  2. (X <144 and (X + 8 >= 144 or X*3 >= 145)).
  3. (X <145 and (X + 3 >= 145 or X*3 >= 145)).
  4. (X <145 and (X + 8 >= 145 or X*3 >= 145)).

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

  1. 96
  2. 8
  3. 45
  4. 15

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

  1. 17
  2. 41
  3. 40
  4. 48

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

  1. Таких значений не существует
  2. 14
  3. 15
  4. 40

Ответ: 1. — 1; 2. — 2; 3. — 4.

Понравилась статья? Оцени:
Читайте также:

Читать статьи — хорошо, а готовиться к экзаменам
в самой крупной онлайн-школе — еще эффективнее.

50 000
Количество
учеников
1510
Количество
стобальников
>15000
Сдали на 90+
баллов