21. Теория игр

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 49:  # Если камней в куче стало больше 48
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,44):
    # если в данной позиции возможен выигрыш Вани вторым ходом
    if game(5,i) == -2:
        print(i)

Аналитическое решение:

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

 

Программное решение:

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if a + b <= 34:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1, b))
        moves.append(f(a // 2, b))
    if b > 0:
        moves.append(f(a, b - 1))
        moves.append(f(a, b // 2))
    pinki_win = [i for i in moves if i <= 0]
    if pinki_win:
        return -max(pinki_win) + 1
    else:
        return -max(moves)


for i in range(12, 100):
    if f(22, i) == -2:
        print(i)

Решение руками

Из предыдущих заданий мы знаем, что в значениях , , Петя гарантированно побеждает своим вторым ходом и в отрезке значений [17;32] Петя гарантированно побеждает своим первым ходом. Значение, из которого ВСЕ ходы ведут в вышеописанные значения – это значение, в котором Ваня побеждает своим вторым ходом или первым ходом при неудачной игре Пети. Распишем значения и стратегии, при которых Ваня побеждает вторым или первым ходом:

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

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

В ответ нужно указать минимальное значение S. Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 33: # если камней в куче стало больше 32
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+3),game(first_heap*2)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,33):
    if game(i) == -2: # если в данной позиции возможен выигрыш Вани вторым ходом
        print(i)

Решение АР

from functools import lru_cache

def moves(h):
    return (h + 1), (h + 3), (h * 2)

@lru_cache(None)
def game(h):
    if h >= 33:
        return "END"
    elif any(game(x) == "END" for x in moves(h)):
        return "WIN1"
    elif all(game(x) == "WIN1" for x in moves(h)):
        return "LOSE1"
    elif any(game(x) == "LOSE1" for x in moves(h)):
        return "WIN2"
    elif all(game(x) == "WIN2" or game(x) == "WIN1" for x in moves(h)):
        return "LOSE2"

for s in range(1, 33):
    if game(s) == "LOSE2":
        print(s)

Решение руками:

Из предыдущих заданий мы знаем, что в значениях , Петя гарантированно побеждает своим вторым ходом и в отрезке значений [23;45] Петя побеждает гарантированно своим первым ходом. Значение, из которого ВСЕ первые ходы ведут в вышеописанные значения – это значение, в котором Ваня гарантированно побеждает вторым ходом или первым при неудачной игре Пети. Распишем значение и стратегии, при которых Ваня побеждает вторым или первым ходом:

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

Ответ:

Решение программой:

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 46: # если камней в куче стало больше 45
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap*2)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,45):
    if game(i) == -2: # если в данной позиции возможен выигрыш Вани вторым ходом
        print(i)

Решение руками

Из предыдущих заданий мы знаем, что в значениях , , Петя гарантированно побеждает своим вторым ходом и в отрезке значений [19;37] Петя побеждает гарантированно своим первым ходом. Значение, из которого ВСЕ первые ходы ведут в вышеописанные значения – это значение, в котором Ваня гарантированно побеждает вторым ходом или первым при неудачной игре Пети. Распишем значение и стратегии, при которых Ваня побеждает вторым или первым ходом:

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

Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 38: # если камней в куче стало больше 37
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+2),game(first_heap*2)] # прописываем ходы возможные в партии
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,38):
    if game(i) == -2: # если в данной позиции возможен выигрыш Вани вторым ходом
        print(i)

Решение АР

from functools import lru_cache
def moves(heap):
    return heap + 1, heap + 2, heap * 2
@lru_cache(None)
def game(heap):
    if heap >= 38:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(1, 38):
    print(s, game(s))

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 77:  # Если камней в куче стало больше 76
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,70):
    # если в данной позиции возможен выигрыш Вани вторым ходом
    if game(7,i) == -2:
        print(i)
        break

Решение АР

from functools import lru_cache

def moves(heap):
    a, b = heap
    return (a + 1, b), (a * 2, b), (a, b + 1), (a, b * 2)

@lru_cache(None)
def game(heap):
    if sum(heap) >= 77:
        return "END"
    elif any(game(x) == "END" for x in moves(heap)):
        return "WIN1"
    elif all(game(x) == "WIN1" for x in moves(heap)):
        return "LOSE1"
    elif any(game(x) == "LOSE1" for x in moves(heap)):
        return "WIN2"
    elif all(game(x) == "WIN1" or game(x) == "WIN2" for x in moves(heap)):
        return "LOSE2"

for s in range(1, 70):
    print(s, game((7, s)))

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 82:  # Если камней в куче стало больше 81
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 4, second_heap),
             game(first_heap, second_heap * 4)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,78):
    # если в данной позиции возможен выигрыш Вани вторым ходом
    if game(4,i) == -2:
        print(i)

Решение АР

from functools import lru_cache

def moves(heap):
    a, b = heap
    return (a + 1, b), (a * 4, b), (a, b + 1), (a, b * 4)

@lru_cache(None)
def game(heap):
    if sum(heap) >= 82:
        return "END"
    elif any(game(x) == "END" for x in moves(heap)):
        return "WIN1"
    elif all(game(x) == "WIN1" for x in moves(heap)):
        return "LOSE1"
    elif any(game(x) == "LOSE1" for x in moves(heap)):
        return "WIN2"
    elif all(game(x) == "WIN1" or game(x) == "WIN2" for x in moves(heap)):
        return "LOSE2"

for s in range(1, 77):
    h = 4, s
    print(s, game(h))

from functools import lru_cache


@lru_cache(None)
def f(a):
    if a <= 11:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1))
    if a > 2:
        moves.append(f(a - 3))
    pupsen_win = [i for i in moves if i <= 0]
    if pupsen_win:
        return -max(pupsen_win) + 1
    return -max(moves)


for i in range(12, 50):
    if f(i) == -2:
        print(i)

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 66:  # Если камней в куче стало больше 65
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,55):
    # если в данной позиции возможен выигрыш Вани вторым ходом
    if game(11,i) == -2:
        print(i)

# Таких значений нет - записываем в ответ 0

Решение АР

from functools import lru_cache
def moves(heap):
    a, b = heap
    return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2)
@lru_cache(None)
def game(heap):
    if sum(heap) >= 66:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(1, 55):
    print(s, game((11, s)))

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 88:  # Если камней в куче стало больше 87
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 3, second_heap),
             game(first_heap, second_heap * 3)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,79):
    # если в данной позиции возможен выигрыш Вани вторым ходом
    if game(9,i) == -2:
        print(i)

Решение АР

from functools import lru_cache
def moves(heap):
    a, b = heap
    return (a + 2, b), (a, b + 2), (a * 3, b), (a, b * 3)
@lru_cache(None)
def game(heap):
    if sum(heap) >= 88:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(1, 79):
    print(s, game((9, s)))

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 83:  # Если камней в куче стало больше 82
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 4, second_heap),
             game(first_heap, second_heap * 4)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,78):
    # если в данной позиции возможен выигрыш Вани вторым ходом
    if game(5,i) == -2:
        print(i)

Решение АР

from functools import lru_cache
def moves(heap):
    a, b = heap
    return (a + 1, b), (a, b + 1), (a * 4, b), (a, b * 4)
@lru_cache(None)
def game(heap):
    if sum(heap) >= 83:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(1, 78):
    print(s, game((5, s)))

Решение программой

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 55:  # Если камней в куче стало больше 54
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap), game(first_heap, second_heap + 1), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

for i in range(1,45):
    # если в данной позиции возможен выигрыш Вани вторым ходом
    if game(10,i) == -2:
        print(i)
# Таких значений нет - в ответ записываем 0

Альтернативное решение программой

from functools import lru_cache
def moves(heap):
    a, b = heap
    return (a + 1, b), (a, b + 1), (a * 2, b), (a, b * 2)
@lru_cache(None)
def game(heap):
    if sum(heap) >= 55:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
for s in range(1, 45):
    print(s, game((10, s)))

from functools import lru_cache


@lru_cache(None)
def f(first_heap, second_heap, third_heap, c=0):
    if first_heap + second_heap + third_heap <= 32:
        return 0
    if c > 4:
        return 123123
    moves = []
    if first_heap > 1:
        moves.append(f(first_heap - 1, second_heap, third_heap, c + 1))
        moves.append(f((first_heap + 1) // 2, second_heap, third_heap, c + 1))
    if second_heap > 1:
        moves.append(f(first_heap, second_heap - 1, third_heap, c + 1))
        moves.append(f(first_heap, (second_heap + 1) // 2, third_heap, c + 1))
    if third_heap > 1:
        moves.append(f(first_heap, second_heap, third_heap - 1, c + 1))
        moves.append(f(first_heap, second_heap, (third_heap + 1) // 2, c + 1))

    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1
    else:
        return -max(moves)


for i in range(11, 100):
    if f(11, 11, i) == -2:
        print(i)

Решение руками

Из предыдущих заданий мы знаем, что Петя побеждает своим первым ходом при нечётных значениях в отрезке [17;49] и значениях 48,50, а также, что Петя побеждает своим вторым ходом в значениях: (3, 4, 5, 6, 8, 10, 12, 14). Значение, из которого ВСЕ первые ходы ведут в вышеописанные значения – это значение, в котором Ваня гарантированно побеждает вторым ходом или первым при неудачной игре Пети. Распишем значение и стратегии, при которых Ваня побеждает вторым или первым ходом:

. Петя может увеличить количество камней только до ходом .

. Петя может увеличить количество камней до ходом или до ходом .

В ответ нужно указать количество значений S. Ответ:

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 51: # если камней в куче стало больше 50
        return 0 # прекращаем игру
    moves = [] # cписок всех возможных ходов в партии
    if first_heap % 2 == 0: # если количество камней в куче является чётным
        # то можем совершить только +1, +3 ходы, так как чётное+нечётное = нечётное
        moves = [game(first_heap+1),game(first_heap+3)]
    else: # если количество камней в куче является нечётным
        # то можем совершить только *3 ход, так как нечётное*нечётное = нечётное
        moves = [game(first_heap*3)]
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # проверяем есть ли выигрыш Пети в данной позиции
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)
count = 0
for i in range(1,51):
    # если в данной позиции возможен выигрыш Вани вторым ходом
    if game(i) == -2:
        count += 1
print(count)

Решение АР

from functools import lru_cache

def moves(heap):
    m = []
    if (heap * 3) % 2 != 0:
        m += [heap * 3]
    if (heap + 1) % 2 != 0:
        m += [heap + 1]
    if (heap + 3) % 2 != 0:
        m += [heap + 3]
    return m

@lru_cache(None)
def game(heap):
    if heap >= 51:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’

count = 0
for s in range(1, 51):
    count += (game(s) == ’LOSE2’)
print(count)

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(heap):  # Функция игры

    # Если кол-во таблеток в куче стало более 112
    if heap > 112:
        # Возвращаем 1,
        # которая преобразуется в победу Тринити первым ходом из-за "плохого" хода Нео
        return 1

    # Если кол-во таблеток в куче стало не менее 45
    if heap >= 45:
        return 0  # Прекращаем игру

    # Прописываем возможные ходы в партии
    moves = [game(heap + 2), game(heap * 3)]

    # Находим значения, через которые может победить Нео
    neo_win = [i for i in moves if i <= 0]

    if neo_win:  # Если такие значения нашлись и список не пуст
        return -max(neo_win) + 1
    else:  # Иначе побеждает Тринити максимальным ходом
        return -max(moves)


# Нео - первый игрок
# Тринити - второй игрок
for S in range(1, 44 + 1):
    # Если в данной позиции Тринити гарантированно выигрывает своим вторым ходом
    if game(S) == -2:
        print(S)  # В ответ берём последнее выведенное значение

Решение АР

from functools import lru_cache

def moves(heap):
    return heap + 2, heap * 3

@lru_cache(None)
def game(heap):
    if 45 <= heap <= 112:
        return ’END’
    elif heap > 112:
        return ’WIN1’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’

for s in range(44, 0, -1):
    if game(s) == ’LOSE2’:
        print(s)
        break

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(heap):  # Функция игры

    # Если кол-во морковок в куче стало более 100
    if heap > 100:
        # Возвращаем 1,
        # которая преобразуется в победу Свена первым ходом из-за "плохого" хода Олафа
        return 1

    # Если кол-во морковок в куче стало не менее 50
    if heap >= 50:
        return 0  # Прекращаем игру

    # Прописываем возможные ходы в партии
    moves = [game(heap + 1), game(heap + 2), game(heap + 3), game(heap * 3)]

    # Находим значения, через которые может победить Олаф
    olaf_win = [i for i in moves if i <= 0]

    if olaf_win:  # Если такие значения нашлись и список не пуст
        return -max(olaf_win) + 1
    else:  # Иначе побеждает Свен максимальным ходом
        return -max(moves)


# Олаф - первый игрок
# Свен - второй игрок
if game(12) > 0:  # Если значение положительное - побеждает Олаф
    print("о")
elif game(12) < 0:  # Если отрицательное - Свен
    print("с")

Решение АР

from functools import lru_cache

def moves(heap):
    return heap + 1, heap + 2, heap + 3, heap * 3

@lru_cache(None)
def game(heap):
    if 50 <= heap <= 100:
        return ’END’
    elif heap > 100:
        return ’WIN1’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’WIN1’
    elif all(game(x) == ’WIN1’ for x in moves(heap)):
        return ’LOSE1’
    elif any(game(x) == ’LOSE1’ for x in moves(heap)):
        return ’WIN2’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)):
        return ’LOSE2’
    elif any(game(x) == ’LOSE2’ for x in moves(heap)):
        return ’WIN3’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ or game(x) == ’WIN3’ for x in moves(heap)):
        return ’LOSE3’
    elif any(game(x) == ’LOSE3’ for x in moves(heap)):
        return ’WIN4’
    elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ or game(x) == ’WIN3’ or game(x) == ’WIN4’ for x in moves(heap)):
        return ’LOSE4’

print(game(12))

Аналитическое решение:

В данной задаче требуется найти максимальную позиции типа . Таких позиций две. Это позиции и Максимальная из них это

 

Программное решение:

from functools import lru_cache


@lru_cache(None)
def f(a):
    if a >= 42:
        return 0
    moves = [f(a + 2), f(a * 3)]
    rick_win = [i for i in moves if i <= 0]
    if rick_win:
        return -max(rick_win) + 1
    return -max(moves)


for i in range(1, 42):
    if f(i) == -2:
        print(i)

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if a + b >= 100:
        return 0
    moves = [f(a + 1, b), f(a * 3, b), f(a, b + 1), f(a, b * 3)]
    anya_win = [i for i in moves if i <= 0]
    if anya_win:
        return -max(anya_win) + 1
    return -max(moves)


for i in range(1, 93):
    if f(7, i) == -2:
        print(i)

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 47:  # Если камней в куче стало больше 46
        return 0  # Прекращаем игру
    moves = [game(first_heap + 1, second_heap+2), game(first_heap+2, second_heap + 1),
             game(first_heap * 2, second_heap),game(first_heap, second_heap * 2)]  # Генерация всех возможных ходов
    petya_win = [i for i in moves if i <= 0]
    if petya_win: # если в данной позиции есть выигрыш Пети
        return -max(petya_win) + 1
    else: # если в данной позиции выигрыш Вани
        return -max(moves)

print(game(10,13)) # -2, значит, имя победителя - ВАНЯ

Решение АР

from functools import lru_cache
def moves(h):
    a, b = h
    return (a + 1, b + 2), (a + 2, b + 1), (a * 2, b), (a, b * 2)
@lru_cache(None)
def f(h):
    if sum(h) >= 47:
        return ’END’
    if(any(f(x) == ’END’ for x in moves(h))):
        return ’P1’
    if(all(f(x) == ’P1’ for x in moves(h))):
        return ’V1’
    if (any(f(x) == ’V1’ for x in moves(h))):
        return ’P2’
    if (all(f(x) == ’P1’ or f(x) == ’P2’ for x in moves(h))):
        return ’V2’
h = 10, 13
print(f(h))

from functools import lru_cache


@lru_cache(None)
def f(a, b, c=0):
    if a * b >= 1056:
        return 0
    if c > 4:
        return -10 ** 10
    moves = [f(a + 1, b, c + 1), f(a * 4, b, c + 1), f(a, b + 1, c + 1), f(a, b * 4, c + 1)]
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1
    else:
        return -max(moves)


for i in range(1, 132):
    if f(8, i) == -2:
        print(i)