21.01 Теория игр

Решение БУ

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))