20.01 Теория игр

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

Из предыдущего задания мы знаем, что в отрезке [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))