Теория игр

Что проверяют эти номера

№19, №20 и №21 это три вопроса про одну и ту же игру. Условие у них общее, функция общая, меняется только последняя строка. Поэтому учим их вместе: разобрался с одним, считай, разобрался со всеми.

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

Два игрока, Петя ходит первым. Ход меняет кучу (или кучи) камней. Игра кончается, когда набран порог. Выигрывает тот, кто сделал последний ход. Надо найти начальные значения S, при которых выполняется условие про выигрыш за один, два, три или четыре хода.

Простыми словами

В игре есть двое, и код всегда считает за одного игрока: за того, кто должен выиграть. Назовём его «наш». Вся логика укладывается в два правила:

• Ходит наш. Он умный и выберет лучший ход. Значит, достаточно, чтобы хотя бы один ход вёл к победе. Это any, то есть «хотя бы один».
• Ходит соперник. Мы не знаем, что он выберет. Значит, победа должна быть после любого его хода. Это all, то есть «все».

Число m это сколько ходов осталось сделать обоим вместе. В №19 первым ходит Петя, а выиграть должен Ваня, поэтому m = 2: ход Пети, затем ход Вани.

Сразу запомни, как считать ходы: Петя, Ваня, Петя, Ваня. Первый ход Пети это 1, первый ход Вани это 2, второй ход Пети это 3, второй ход Вани это 4.

Общее решение: функция f(s, m)

s это камни, а m это сколько ходов осталось. На ходу того, кто должен выиграть, хватает одного удачного варианта, поэтому any. На ходу соперника выигрыш должен быть при любом его ответе, поэтому all.

m — количество ходов (полуходов, то есть ходов обоих игроков), s — количество камней.

def f(s, m):
    if s >= 39:                       # игра закончилась
        return m % 2 == 0
    if m == 0:
        return 0
    h = [f(s + 1, m - 1), f(s + 3, m - 1), f(s * 2, m - 1)]    # ходы
    return any(h) if m % 2 != 0 else all(h)

print([s for s in range(1, 39) if f(s, 2)])                         # №19
print([s for s in range(1, 39) if not f(s, 1) and f(s, 3)])        # №20
print([s for s in range(1, 39) if not f(s, 2) and f(s, 4)])        # №21

Как это читать:

• Нечётное m: ходит игрок, за которого мы считаем (ему достаточно одного хода: any(h)).
• Чётное m: ходит противник, ему подходят все ходы (all(h)): проверяем, что выигрыш есть при любом его ходе.
• Если игра кончилась раньше, победил тот, кто сделал последний ход: m % 2 == 0 — выиграл «наш» (он ходил последним), иначе противник.
• Вызовы: №19 — f(s, 2), №20 — not f(s, 1) and f(s, 3), №21 — not f(s, 2) and f(s, 4).

Разбор игры руками

Одна куча, ходы «+1» и «×2», конец при 30 камнях. Возьмём S = 14.

Петя может сделать 15 или 28. Из 15 Ваня удваивает и получает 30. Из 28 Ваня тоже удваивает и получает 56. Как бы ни сходил Петя, Ваня выигрывает первым ходом. Это и проверяет f(14, 2).

№19: Ваня выигрывает первым ходом

Три вызова внизу дают ответы сразу на все три номера. На экзамене код пишешь один раз и получаешь три ответа.

Ходы +2, +4, ×2, порог 125:

def f(s, m):
    if s >= 125:
        return m % 2 == 0
    if m == 0:
        return 0
    h = [f(s + 2, m - 1), f(s + 4, m - 1), f(s * 2, m - 1)]
    return any(h) if m % 2 != 0 else all(h)

print([s for s in range(1, 125) if f(s, 2)])                          # [61, 62]
print([s for s in range(1, 125) if not f(s, 1) and f(s, 3)])         # [31, 57, 58, 59, 60]
print([s for s in range(1, 125) if not f(s, 2) and f(s, 4)])         # [55, 56]

# пиши решение здесь

№20: Петя выигрывает вторым ходом

Петя ходит первым. Его второй ход по общему счёту третий: Петя, Ваня, Петя. Поэтому нам нужно f(s, 3).

Но есть подвох: f(s, 3) считает и те случаи, где Петя мог выиграть сразу, первым ходом. В условии просят именно второй ход, поэтому такие начальные значения убираем условием not f(s, 1). Читается так: «первым ходом гарантированно не выиграть, а вторым можно».

Разбор руками

Та же игра с порогом 30. S = 7: Петя делает 14. Из 14 Ваня может получить 15 или 28, и оба раза Петя удваивает и заканчивает игру. Первым ходом Петя выиграть не мог: из 7 получается только 8 или 14. Поэтому S = 7 подходит.

# пиши решение здесь

# пиши решение здесь

№21: Ваня выигрывает первым или вторым ходом

Теперь выиграть должен Ваня, первым или вторым своим ходом. Его ходы по общему счёту второй и четвёртый: Петя, Ваня, Петя, Ваня. Поэтому f(s, 4).

Условие not f(s, 2) убирает начальные значения, где Ваня всегда побеждал бы первым ходом. Смысл такой: Петя может сыграть так, что сразу выиграть не выйдет, но Ваня всё равно победит не позже второго хода.

Разбор руками

Порог 30. S = 12: Петя делает 13 или 24. Из 24 Ваня сразу удваивает и выигрывает. Из 13 он идёт в 14, а это уже проигрышная для Пети позиция, и Ваня выигрывает следующим ходом. Гарантировать победу первым ходом он не может, потому что из 13 сразу до 30 не дойти.

# пиши решение здесь

# пиши решение здесь

Две кучи

Функция та же, только теперь у неё два числа и по каждой команде два варианта хода, в первую кучу и во вторую. Условие конца обычно про сумму.

Функция получает две кучи a и b, порог на сумму:

def f(a, b, m):
    if a + b >= 90:
        return m % 2 == 0
    if m == 0:
        return 0
    h = [f(a + 3, b, m - 1), f(a, b + 3, m - 1), f(a * 2, b, m - 1), f(a, b * 2, m - 1)]
    return any(h) if m % 2 != 0 else all(h)

print([s for s in range(1, 78) if f(12, s, 2)])     # Ваня выигрывает при любом ходе Пети

Первая куча известна (12), вторая S — перебираем.

Для двух куч общая функция тоже одна, и она сразу отвечает на все три вопроса:

def f(a, b, m):
    if a + b >= 90:
        return m % 2 == 0
    if m == 0:
        return 0
    h = [f(a + 3, b, m - 1), f(a, b + 3, m - 1), f(a * 2, b, m - 1), f(a, b * 2, m - 1)]
    return any(h) if m % 2 != 0 else all(h)

print([s for s in range(1, 78) if f(12, s, 2)])                          # №19
print([s for s in range(1, 78) if not f(12, s, 1) and f(12, s, 3)])     # №20
print([s for s in range(1, 78) if not f(12, s, 2) and f(12, s, 4)])     # №21

Если условие просит два наименьших значения, бери первые два числа из списка.

Неудачный ход Пети

Если в условии «после неудачного хода Пети» (Петя ходит как угодно, лишь бы не закончил игру), в конце ставим any для обоих игроков:

    return any(h) if m % 2 != 0 else any(h)         # или просто return any(h)

Вызов остаётся тем же, меняется только последняя строка функции.

Дополнительное условие

Если у игры есть особая зона, дописываем её ПЕРЕД обычной проверкой конца:

def f(s, m):
    if 50 <= s <= 119:
        return m % 2 == 0
    if s > 119:
        return m % 2 != 0
    if m == 0:
        return 0
    h = [f(s + 1, m - 1), f(s + 3, m - 1), f(s * 2, m - 1)]
    return any(h) if m % 2 != 0 else all(h)

# пиши решение здесь

# пиши решение здесь

Игры «минус»

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

def f(a, b, m):
    if a + b <= 30:
        return m % 2 == 0
    if m == 0:
        return 0
    h = [f(a - 1, b, m - 1), f(a, b - 1, m - 1), f(a // 2, b, m - 1), f(a, b // 2, m - 1)]
    return any(h) if m % 2 != 0 else all(h)

print([s for s in range(21, 500) if f(10, s, 2)])                          # №19
r = [s for s in range(21, 500) if not f(10, s, 1) and f(10, s, 3)]         # №20
print(r[0], r[-1])
print(min(s for s in range(21, 500) if not f(10, s, 2) and f(10, s, 4)))   # №21

# пиши решение здесь

Необычные игры

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

Произведение камней вместо суммы:

def f(a, b, m):
    if a * b >= 516:
        return m % 2 == 0
    if m == 0:
        return 0
    h = [f(a + 3, b, m - 1), f(a, b + 3, m - 1)]
    return any(h) if m % 2 != 0 else all(h)

print([s for s in range(1, 74) if f(7, s, 2)])

Нельзя повторять последний ход (запоминаем его в hist):

def f(s, m, hist=''):
    if s >= 60:
        return m % 2 == 0
    if m == 0:
        return 0
    h = []
    if hist[-1:] != '1':
        h.append(f(s + 3, m - 1, hist + '1'))
    if hist[-1:] != '2':
        h.append(f(s + 6, m - 1, hist + '2'))
    return any(h) if m % 2 != 0 else all(h)

hist[-1:] (срез) вместо hist[-1], чтобы не падало на пустой строке.

Запоминаем последний и предпоследний ход:

def f(s, m, k='', k2=''):
    if s > 40:
        return m % 2 == 0
    if m == 0:
        return 0
    h = []
    if k2 != '+1':
        h.append(f(s + 1, m - 1, '+1', k))
    if k2 != '+2':
        h.append(f(s + 2, m - 1, '+2', k))
    if k2 != '*2':
        h.append(f(s * 2, m - 1, '*2', k))
    return any(h) if m % 2 != 0 else all(h)

Как решать

Весь порядок действий на экзамене укладывается в несколько минут.

1. Определи: одна куча или две, порог >= или <=.
2. Перепиши ходы в список h.
3. Для «минус» игр условие конца a + b <= T, ходы например a - 1, a // 2.
4. Вызов по номеру: №19 f(…, 2) (при неудачном ходе Пети any в обеих ветках), №20 not f(…, 1) and f(…, 3), №21 not f(…, 2) and f(…, 4).
5. Диапазон S с запасом (в играх «минус» берём до 1500).

# пиши решение здесь

Ловушки