TheLazy.Dev
Portfolio GitHub

Blog

Теория игр в 19-21 задачах КЕГЭ 2021

purplewhiteslive

Danila White

Posted on April 3, 2021

Теория игр в 19-21 задачах КЕГЭ 2021

Введение

Привет друг! Проблемы с теорией игр? В этой статье мы разберем код, который решает любые прототипы стандартных 19-21 задач из КЕГЭ. Чтобы максимально понять ниже описанный код, я крайне рекомендую сначала научиться решать эти задачи ручками.

Условие

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в четыре раза.
В начальный момент в первой куче было 3 камня, во второй куче — S камней, 1 ≤ S ≤ 57. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 61. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 61 или больше камней.

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

  2. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

    • Петя не может выиграть за один ход;
    • Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

  3. Найдите минимальное значение S, при котором одновременно выполняются два условия:

    • у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
    • у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение

Winpos

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

Обозначим переменные count1 и count2 как количество камней в 1 и 2 куче соответственно.
Если изначально суммарное количество камней в кучах меньше 61

if (count1 + count2 < 61)
Enter fullscreen mode Exit fullscreen mode

и при любом следующем ходе оно становиться больше либо равно 61

((count1 + count2 + 1 >= 61) or
(count1 * 4 + count2 >= 61) or 
(count1 + count2 * 4 >= 61))
Enter fullscreen mode Exit fullscreen mode

то мы возвращаем True, что означает что игрок находиться в выигрышной позиции.
Иначе мы возвращаем False, что означает что игрок не находиться в выигрышной позиции.

def winpos(count1, count2):
    if (count1 + count2 < 61) and ((count1 + count2 + 1 >= 61) or
       (count1 * 4 + count2 >= 61) or (count1 + count2 * 4 >= 61)):
        return True
    else:
        return False
Enter fullscreen mode Exit fullscreen mode

Первая функция готова, приступим к написанию следующей.

Losspos

Теперь нам надо написать функцию, которая будет возвращать True если игрок находится в проигрышной позиции и False если игрок не находится в проигрышной позиции.

Если изначально игрок не находиться в выигрышной позиции

if not winpos(count1, count2)
Enter fullscreen mode Exit fullscreen mode

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

(winpos(count1 + 1, count2) and winpos(count1, count2 + 1) and
 winpos(count1 * 4, count2) and winpos(count1, count2 * 4))
Enter fullscreen mode Exit fullscreen mode

то мы возвращаем True, что означает что игрок находиться в проигрышной позиции.
Иначе, мы возвращаем False, что означает что игрок не находиться в проигрышной позиции.

def losspos(count1, count2):
    if not winpos(count1, count2) and (winpos(count1 + 1, count2) and
        winpos(count1, count2 + 1) and winpos(count1 * 4, count2) and
        winpos(count1, count2 * 4)):
        return True
    else:
        return False
Enter fullscreen mode Exit fullscreen mode

Вторая функция готова, осталась еще одна.

Prewinpos

Последняя функция должна возвращать True если игрок находится в предвыигрышной позиции и False если игрок не находится в предвыигрышной позиции.

Если изначально игрок не находится в выигрышной позиции

if not winpos(count1, count2)
Enter fullscreen mode Exit fullscreen mode

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

(losspos(count1 + 1, count2) or losspos(count1, count2 + 1) or
 losspos(count1 * 4, count2) or losspos(count1, count2 * 4)):
Enter fullscreen mode Exit fullscreen mode

то мы возвращаем True, что означает что игрок находится в предвыигрышной позциии.
Иначе, мы возвращаем False, что означает что игрок не находиться в предвыигрышной позциии.

def prewinpos(count1, count2):
    if not winpos(count1, count2) and (losspos(count1 + 1, count2) or
        losspos(count1, count2 + 1) or losspos(count1 * 4, count2) or
        losspos(count1, count2 * 4)):
        return True
    else:
        return False
Enter fullscreen mode Exit fullscreen mode

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

1 Задача

Условие задачи можно воспринимать так: "Ваня находиться в выигрышной позиции(выигрывает за один ход)".

Изначально в первой куче 3 камня

count1 = 3
Enter fullscreen mode Exit fullscreen mode

а во второй куче S камней, 1 ≤ S ≤ 57

for s in range(1, 58):
Enter fullscreen mode Exit fullscreen mode

Перебираем все возможные комбинации с S, при которых игрок находится в выигрышной позиции

if winpos(count1 + 1, s) or winpos(count1, s + 1) or
   winpos(count1 * 4, s) or winpos(count1, s * 4):
Enter fullscreen mode Exit fullscreen mode

и если хоть одна такая комбинация существует, то мы выводим S на экран и прерываем цикл.

print("19:", s)
break
Enter fullscreen mode Exit fullscreen mode

Получается следующий код, который решает эту задачу

count1 = 3
for i in range(1, 58):
    if winpos(count1 + 1, i) or winpos(count1, i + 1) or
        winpos(count1 * 4, i) or winpos(count1, i * 4):
        print("19:", i)
        break
Enter fullscreen mode Exit fullscreen mode

2 Задача

Условие задачи можно воспринимать так: "Ваня находится в проигрышной позиции".

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

for i in range(1, 58):
    if losspos(count1 + 1, i) or losspos(count1, i + 1) or
        losspos(count1 * 4, i) or losspos(count1, i * 4):
        print("20:", i)
Enter fullscreen mode Exit fullscreen mode

3 Задача

Условие задачи можно воспринимать так: "Ваня находиться или в выигрышной или в предвыигрышной позиции"

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

if (winpos(count1 + 1, i) or predwinpos(count1 + 1, i)) and 
   (winpos(count1, i + 1) or predwinpos(count1, i + 1)) and 
   (winpos(count1 * 4, i) or predwinpos(count1 * 4, i)) and 
   (winpos(count1, i * 4) or predwinpos(count1, i * 4)):
   print("21:", i)
Enter fullscreen mode Exit fullscreen mode

2 Способ

Подробней с этим методом решения теории игр вы можете ознакомится на канале Алексея Кабанова

Мемоизация

Для оптимизации рекурсии подключим декоратор cache из модуля functools.

from functools import cache
Enter fullscreen mode Exit fullscreen mode

Moves

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

def moves(heap):
    a, b = heap
    return (a + 1, b), (a * 4, b), (a, b + 1), (a, b * 4)
Enter fullscreen mode Exit fullscreen mode

Game

Напишем функцию game, которая рекурсивно описывает игру.

@cache
def game(heap):
    if sum(heap) >= 61:
        return 0
    steps = [game(x) for x in moves(heap)]
    if any(x % 2 == 0 for x in steps):
        return min(x for x in steps if x % 2 == 0) + 1
    else:
        return max(steps) + 1
Enter fullscreen mode Exit fullscreen mode

1-3 задача

Перебираем все значения s и выводим на экран необходимые данные.

for s in range(57, 0, -1):
    print(s, ": ", game((3, s)), " | ", [game(x) for x in moves((3, s))])
Enter fullscreen mode Exit fullscreen mode

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

💖 💪 🙅 🚩
purplewhiteslive
Danila White

Posted on April 3, 2021

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

What was your win this week?
weeklyretro What was your win this week?

November 29, 2024

If you're a beginner, definitely check this open source guide. I've explained almost everything you need to know.
undefined If you're a beginner, definitely check this open source guide. I've explained almost everything you need to know.

November 28, 2024

Exploring Typesafe design tokens in Tailwind 4
tailwindcss Exploring Typesafe design tokens in Tailwind 4

November 29, 2024

Where GitOps Meets ClickOps
devops Where GitOps Meets ClickOps

November 29, 2024

The best way to get better at writing code is...
development The best way to get better at writing code is...

November 28, 2024