20. Теория игр

Решение БУ

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 + 2, second_heap), game(first_heap, second_heap + 2), game(first_heap * 2, second_heap),
             game(first_heap, second_heap * 2), game(first_heap + 1, second_heap), game(first_heap, second_heap + 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,40):
    if game(7,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)
        break

Решение АР

from functools import lru_cache

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

@lru_cache(None)
def game(heap):
    if sum(heap) >= 47:
        return ’END’
    elif any(game(x) == ’END’ for x in moves(heap)):
        return ’P1’
    elif all(game(x) == ’P1’ for x in moves(heap)):
        return ’V1’
    elif any(game(x) == ’V1’ for x in moves(heap)):
        return ’P2’
    elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)):
        return ’V2’

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

from functools import lru_cache


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


for i in range(1, 100):
    if f(25, i) == 2:
        print(i)
        break

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if (a + b) <= 75:
        return 0
    moves = []
    if a - 3 >= 0:
        moves.append(f(a - 3, b))
    if b - 3 >= 0:
        moves.append(f(a, b - 3))
    if a > 0:
        moves.append(f(a // 5, b))
    if b > 0:
        moves.append(f(a, b // 5))
    petya_win = [i for i in moves if i <= 0]
    if petya_win:
        return -max(petya_win) + 1
    return -max(moves)


for i in range(50, 101):
    if f(100, i) == 2:
        print(i)

from functools import lru_cache


@lru_cache(None)
def f(a, b, c):
    if a + b >= 199:
        return 0
    moves = [f(a, b * 2, c)]
    if c == 0:
        moves.append(f(b, a, 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, 100):
    if f(99, i, 0) == 2:
        print(i)
        break

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 199:  # Если камней в куче стало больше 198
        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),
             game(first_heap + first_heap - 1, second_heap), game(first_heap, second_heap + second_heap - 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(2,98):
    if game(97,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)
        break

Решение АР

from functools import lru_cache

def moves(h):
    a, b = h
    return (a + 1, b), (a, b + 1), (a + 2, b), (a, b + 2), (a + a - 1, b), (a, b + b - 1)

@lru_cache(None)
def f(h):
    if sum(h) >= 199:
        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) == "P2" or f(x) == "P1") for x in moves(h)):
        return "V2"

for s in range(97, 1, -1):
    h = 97, s
    if f(h) == "P2":
        print(s, "P2")

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

from functools import lru_cache


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

    # Если суммарное кол-во камней в кучах стало более 70
    if first_heap + second_heap > 70:
        # Возвращаем 1,
        # которая преобразуется в победу Вани первым ходом из-за "плохого" хода Пети
        return 1

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

    # Прописываем возможные ходы в партии
    moves = [
        game(first_heap + 1, second_heap),
        game(first_heap * 2, second_heap),
        game(first_heap, second_heap + 1),
        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 S in range(1, 29 + 1):
    # Если в данной позиции Петя гарантированно выигрывает своим вторым ходом
    if game(20, S) == 2:
        print(S)
        break  # Первое выведенное значение будет минимальным

from functools import lru_cache


@lru_cache(None)
def f(first_heap, second_heap, third_heap):
    if first_heap + second_heap + third_heap >= 70:
        return 0
    moves = [f(first_heap + 1, second_heap, third_heap), f(first_heap, second_heap + 1, third_heap),
             f(first_heap, second_heap, third_heap + 1),
             f(first_heap * 2, second_heap, third_heap), f(first_heap, second_heap * 2, third_heap),
             f(first_heap, second_heap, third_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, 40):
    if f(20, 10, i) == 2:
        print(i)
        break

from functools import lru_cache


@lru_cache(None)
def f(first_heap, second_heap, third_heap, fourth_heap):
    if first_heap + second_heap + third_heap + fourth_heap >= 70:
        return 0
    moves = [f(first_heap + 2, second_heap, third_heap, fourth_heap),
             f(first_heap, second_heap + 2, third_heap, fourth_heap),
             f(first_heap, second_heap, third_heap + 2, fourth_heap),
             f(first_heap, second_heap, third_heap, fourth_heap + 2),
             f(first_heap * 3, second_heap, third_heap, fourth_heap),
             f(first_heap, second_heap * 3, third_heap, fourth_heap),
             f(first_heap, second_heap, third_heap * 3, fourth_heap),
             f(first_heap, second_heap, third_heap, fourth_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, 40):
    if f(9, 6, 8, i) == 2:
        print(i)
        break

Решение БУ

from functools import lru_cache


@lru_cache(None)
def game(heap_1, heap_2, heap_3, heap_4):  # Функция игры

    # Если суммарное кол-во камней в кучах стало более 80
    if heap_1 + heap_2 + heap_3 + heap_4 > 80:
        # Возвращаем 1,
        # которая преобразуется в победу Вани первым ходом из-за "плохого" хода Пети
        return 1

    # Если суммарное кол-во камней в кучах стало не менее 60
    if heap_1 + heap_2 + heap_3 + heap_4 >= 60:
        return 0  # Прекращаем игру

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

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

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


for S in range(1, 29 + 1):
    # Если в данной позиции Петя гарантированно выигрывает своим вторым ходом
    if game(10, 10, 10, S) == 2:
        print(S)
        break  # Первое выведенное значение будет минимальным

Решение АР

from functools import lru_cache

def moves(h):
    a, b, c, d = h
    return (a + 2, b, c, d), (a, b + 2, c, d), (a, b, c + 2, d),
    (a, b, c, d + 2), (a * 3, b, c, d), (a, b * 3, c, d),
    (a, b, c * 3, d), (a, b, c, d * 3)

@lru_cache(None)
def f(h):
    if sum(h) > 80:
        return "V0"
    if sum(h) >= 60:
        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) == "P2" or f(x) == "P1" or f(x) == "V0") for x in moves(h)):
        return "V2"

for s in range(29, 0, -1):
    h = 10, 10, 10, s
    if f(h) == "P2":
        print(s, "P2")

from functools import lru_cache


@lru_cache(None)
def f(x_coord, y_coord):
    if (x_coord ** 2 + y_coord ** 2) ** 0.5 > 20:
        return 0
    moves = [f(x_coord + 1, y_coord + 2), f(x_coord, y_coord + 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, 18):
    if f(10, i) == 2:
        print(i)
        break

from functools import lru_cache


@lru_cache(None)
def f(x_coord, y_coord):
    if (x_coord ** 2 + y_coord ** 2) ** 0.5 > 30:
        return 0
    moves = [f(x_coord + 1, y_coord + 2), f(x_coord, y_coord + 1), f(x_coord + 10, y_coord + 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, 26):
    if f(15, i) == 2:
        print(i)
        break

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 43:  # Если камней в куче стало больше 42
        return 0  # Прекращаем игру
    moves = [game(first_heap + 2, second_heap), game(first_heap, second_heap + 2), 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,35):
    if game(8+2,i) == 1 or game(8*2,i) == 1 or game(8,i+2) == 1 or game(8,i*2) == 1: # если в данной позиции после неудачного хода Пети возможен выигрыш Вани
        print(i)
        break

Решение АР

from functools import lru_cache


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


@lru_cache(None)
def f(h):
    if sum(h) >= 43:
        return ’END’
    if any(f(x) == ’END’ for x in moves(h)):
        return ’WIN1’
    if any(f(x) == ’WIN1’ for x in moves(h)):
        return ’LOSE1’


for i in range(1, 35):
    h = 8, i
    if f(h) == ’LOSE1’:
        print(i)
        break

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap, second_heap):  # Функция игры
    if first_heap + second_heap >= 57:  # Если камней в куче стало больше 56
        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,52):
    if game(5,i) == 2: # если в данной позиции возможен выигрыш Пети вторым ходом
        print(i)

Решение АР

from functools import lru_cache


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


@lru_cache(None)
def f(h):
    if (sum(h) >= 57):
        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’


for s in range(1, 52):
    h = 5, s
    if f(h) == ’P2’:
        print(s, end=’’)

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

Из предыдущей задачи мы знаем, что в отрезке [61;70] Петя гарантированно выигрывает своим первым ходом. В значении 60 Ваня гарантированно выигрывает своим первым ходом после любого хода Пети. Значит, что если после первого хода Пети в куче станет 60 камней, значит, он гарантированно выиграет в партии своим вторым ходом. Распишем из каких значений за один ход можно попасть в 60:

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 71: # если камней в куче стало больше 70
        return 0 # прекращаем игру
    moves = [game(first_heap+1),game(first_heap+10)] # прописываем ходы возможные в партии
    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,71):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)

Решение 1

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

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

 

Решение 2

from functools import lru_cache


@lru_cache(None)
def f(a, b):
    if a + b <= 40:
        return 0
    moves = []
    if a > 0:
        moves.append(f(a - 1, b))
        if a > 1:
            moves.append(f(a // 2 + (a % 2), b))
    if b > 0:
        moves.append(f(a, b - 1))
        if b > 1:
            moves.append(f(a, b // 2 + (b % 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(20, 100):
    if f(20, i) == 2:
        print(i)

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

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

Возможные значения В этих случаях Петя не может выиграть первым ходом. Однако он может получить кучу из камней (при он добавляет камня; при — камень). Тогда после первого хода Ваня в куче будет , или камней. Во всех случаях Петя увеличивает количество камней в раза и выигрывает в один ход.

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 39: # если камней в куче стало больше 38
        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)

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

Из предыдущей задачи мы знаем, что при значениях и Ваня гарантированно победит своим первым ходом. Если после первого хода Пети в куче будет или камней, значит, в этой позиции Петя гарантированно победит вторым ходом. Распишем значения и стратегии, при которых Петя победит своим вторым ходом: При Петя может перейти в позицию ходом и гарантированно после хода Вани выиграет партию своим вторым ходом.

При Петя может перейти в позицию ходом и гарантированно после хода Вани выиграет партию своим вторым ходом.

При Петя может перейти в позицию ходом и гарантированно после хода Вани выиграет партию своим вторым ходом.

При Петя может перейти в позицию ходом и гарантированно после хода Вани выиграет партию своим вторым ходом.

При Петя может перейти в позицию ходом и гарантированно после хода Вани выиграет партию своим вторым ходом.

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 55: # если камней в куче стало больше 54
        return 0 # прекращаем игру
    moves = [game(first_heap+2),game(first_heap+4),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)

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

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

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

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

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

После того как мы определили значения, при которых Ваня побеждает первым ходом мы можем определить значения, в которых Петя побеждает своим вторым ходом. Значение, из которого ХОТЯ БЫ ОДИН ход ведёт в или – это значение, в котором Петя побеждает своим вторым ходом. Распишем значения и стратегии, при которых Петя побеждает своим вторым ходом:

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

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

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

Решение БУ

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 27: # если камней в куче стало больше 26
        return 0 # прекращаем игру
    moves = [game(first_heap+2),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)

for i in range(1,27):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        print(i)

Решение АР

from functools import lru_cache
def moves(h):
    return (h+2), (h*3)
@lru_cache(None)
def game(h):
    if h >= 27:
        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, 27):
    if game(s) == ’WIN2’:
        print(s)

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

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

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

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

После того как мы определили значения, в которых Ваня побеждает своим первым ходом мы можем определить значения, в которых Петя побеждает своим вторым ходом. Значение, из которого ХОТЯ БЫ ОДИН ход ведёт в или – это значение, в котором Петя побеждает своим вторым ходом. Распишем значения и стратегии, при которых Петя победит вторым ходом:

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

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

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

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

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

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

from functools import lru_cache
@lru_cache(None)
def game(first_heap): # функция игры
    if first_heap >= 31: # если камней в куче стало больше 30
        return 0 # прекращаем игру
    moves = [game(first_heap+2),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)
count = 0
for i in range(1,31):
    if game(i) == 2: # если в данной позиции Петя побеждает вторым ходом
        count += 1
print(count)

Решение БУ

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)