Как доработать алгоритм?

Question

[Антон Чернышёв]

Доброго времени суток. Решил написать алгоритм для игры в ним, чтобы бот всегда выигрывал, но пристарте игры с числа 8 бот проигрывает. Как его доработать?

#алгоритм выбора числа ботом
def choize(s, nums, nums1):
    if s in nums:
        return s - 4
    elif s < 4:
        return s 
    elif s in nums1:
        return s - 8
    else: 
        return 1


nums1 = [9, 10, 11]
nums = [7, 6]
#s - количество оставшихся камней в куче
s = int(input())
a = 0
#если i = 1, ходит игрок. иначе - бот
i = 0 
while s != 0:
    if i == 1:
        a = int(input())
    elif i == 0:
        a = choize(s, nums, nums1)
#если а больше 0 и меньше 3 и s+1, ход выполняется. иначе - игрок вводит число заново, пока оно не будет корректным 
    if a > 0 and a < 4 and a < s + 1:
        s -= a
        print(a, s)
        a = 0 
#смена хода
        if i == 0:
            i = 1
        elif i == 1:
            i = 0
    else:
        print('Некорректный ход:', a)
        continue
if i == 1:
    print('ИИ выиграл!')
else:
    print('Вы выиграли!')

Comments

[Алан Гибизов]

Ты хоть откомментируй код, что ты имел ввиду этими командами?

Answer 1

[Wataru]

Это не совсем ним (где несколько кучек и за ход можно взять сколько угодно камней). Судя по коду, игроки могут брать 1,2 или 3 камня и кучка одна. Кажется, у вас выигрывает тот, кто возьмет последний камень.

Сначала немного теории игр.
Если камней 1-3, то первый игрок выигрывает (очевидно, беря все). Если камней 4, то любой ход приведет к выигрышной позиции. Значит 4 - это проигрышная позиция. Начинающий в ней ВСЕГДА проигрывает (если второй игрок, конечно, не поддается и не делает глупостей). Далее чуть чуть логики и становится понятно, что любая позиция вида 4*k проигрышная. Выигрышный ход - вычесть n%4 камня, чтобы врагу досталась пощиция с делящимся на 4 количеством камней. Что вы делаете из такой проигрышной позиции неважно.

Поэтому для 8 камней, если начинает бот, и человек действует правильно - бот всегда проиграет.

Правильная функция choize должна быть:

def choose(s):
  if s%4 == 0: return 1
  else return s%4

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

Еще по коду. Вместо if i==0 else if i ==1, можно просто делать i=1-i. а лучше вместо i=0 заведите bots_move = true и делайте bots_move = not bots_move.
Вместо s назовите переменную num_stones. Вместо a - human_move. Некоторые ваши комментарии в коде бесполезны, ибо они просто дублируют код, а не объясняют зачем или почему этот код таков.