DEV Community

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

Posted on • Edited on

Теория игр в 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

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

Top comments (6)

Collapse
 
tomford profile image
tomford51 •

Світ технологій швидко змінюється, і 2021 рік запам'ятався багатьма новими інноваціями в IT-сфері. Якщо ви шукаєте розваги та нові можливості для відпочинку, зверніть увагу на vbet, який пропонує багато цікавих опцій для дозвілля в казіно Крім того, завжди варто оновлювати свої знання та навички, особливо в таких мінливих галузях, як програмування. Нові технології відкривають багато можливостей для особистого розвитку та кар'єрного зростання

Collapse
 
__03f3f898142e5 profile image
I am Diana •

Привет, ребята! Я уже несколько лет увлекаюсь онлайн-казино и могу точно сказать, что изучение рейтингов и обзоров - это один из ключевых факторов успеха. Когда я наткнулась на сайт про naukaspb.info/slots-sms/igry-na-re... азартные игры на реальные деньги с выводом на карту, я была приятно удивлена, насколько детально там описаны лучшие игровые автоматы и казино. Рейтинги помогают понять, какие казино имеют лицензии, какие разработчики предлагают самые надежные слоты, и какие бонусы можно получить. Также важно учитывать волатильность и RTP, чтобы выбрать автоматы с наилучшими шансами на выигрыш. Благодаря таким рейтингам и обзорам я всегда уверен в своем выборе и могу наслаждаться игрой без лишних переживаний. Как вы находите честные слоты?

Collapse
 
trasatorn profile image
Trace • • Edited

Теория игр – очень интересная и полезная тема, особенно если ты увлекаешься стратегическими играми или ставками на спорт. Задачи, подобные тем, что рассматриваются в "Теория игр в 19-21 задачах КЕГЭ 2021", помогают развить аналитическое мышление и лучше понимать, как работает стратегия в реальной жизни. Это может пригодиться не только в учебе, но и в хобби, например, когда ты ищешь эффективные стратегии на спортивных платформах вроде 1winkazino-az.com/. Развивая стратегическое мышление, можно научиться принимать более обоснованные решения в играх и спорте.

Collapse
 
rinkton profile image
Rinkton •

Sorry, non-russian guy. This post is occupated by Russian

Collapse
 
purplewhiteslive profile image
Danila White •

lmao

Some comments may only be visible to logged-in visitors. Sign in to view all comments.

Read next

saumyashah40 profile image

How Pod Creation Happens in Kubernetes? Understand Full K8s Workflow

Saumya Shah -

grantdotdev profile image

Advent of Code 2024 - Day 20: Race Condition

Grant Riordan -

arber profile image

Proposal: Standard Communication API Channels for AI Agents (AI Generated)

Arber -

talonx profile image

How to Configure a Remote Data Store for Prometheus

Hrish B -