gametheoryEGE

#За один ход игрок может добавить в одну из куч один камень или
#увеличить количество камней в куче в четыре раза.
#Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 82.
#Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию,
#в которой в кучах будет 82 или больше камней.
#В начальный момент в первой куче было 4 камня, во второй куче — S камней, 1 ≤ S ≤ 77.

#Задание 19
def IsItSolutionFor19(n,s, turn):
    if n+s>=82 and turn==2: #Положительное условие выхода: на второй ход в куче оказалось нужное число камней.
        return True
    elif n+s<82 and turn==2: #Отрицательное условие выхода: на второй ход камней меньше, чем нужно.
        return False
    return IsItSolutionFor19(n+1,s,turn+1) or IsItSolutionFor19(n*4,s,turn+1) or IsItSolutionFor19(n,s+1, turn+1) or IsItSolutionFor19(n,s*4, turn+1)
    #Рекуррентный вызов в случае, если ещё не второй ход: проверится каждая ветвь дерева, если хотя бы одна верна, вернется True

#Задание 20
def IsItSolutionFor20(n,s, turn):
    if n+s>=82 and turn==3: #Положительное условие выхода: на второй ход в куче оказалось нужное число камней.
        return True
    elif n+s<82 and turn==3: #Отрицательное условие выхода: на второй ход камней меньше, чем нужно.
        return False
    elif n+s>=82 and turn<3:
        return False #Выход с отрицанием, если выиграли до 3 хода.
    if turn%2 == 0: #В ход игрока, имеющего в руках выигрышную стратегию, нам достаточно, чтобы у него одна из ветвей возвращала True (Имелся
        #хотя бы один выигрышный ход.
        return IsItSolutionFor20(n+1,s,turn+1) or IsItSolutionFor20(n*4,s,turn+1) or IsItSolutionFor20(n,s+1, turn+1) or IsItSolutionFor20(n,s*4, turn+1)
    else: #В ход проигравшего игрока все ветви должны вернуть True, иначе возможен исход, где выигрывает не наш "победитель"
        return IsItSolutionFor20(n+1,s,turn+1) and IsItSolutionFor20(n*4,s,turn+1) and IsItSolutionFor20(n,s+1, turn+1) and IsItSolutionFor20(n,s*4, turn+1)

#Задание 21
def IsItSolutionFor21(n,s, turn):
    if n+s>=82 and (turn==4 or turn==2): #Если при данном s игра выигрывается на 2 или 4 ходе, получаем True.
        return True
    elif n+s<82 and turn==4: #Если не доиграли до 4, получаем False.
        return False
    elif n+s>=82 and turn<4: #Важно: эта проверка сработает только в том случае, если сейчас первый или третий ход.
        return False
    if turn%2 == 1: #Далее по аналогии с 20 заданием: ходы победителя с or, проигравшего с and
        return IsItSolutionFor21(n+1,s,turn+1) or IsItSolutionFor21(n*4,s,turn+1) or IsItSolutionFor21(n,s+1, turn+1) or IsItSolutionFor21(n,s*4, turn+1)
    else:
        return IsItSolutionFor21(n+1,s,turn+1) and IsItSolutionFor21(n*4,s,turn+1) and IsItSolutionFor21(n,s+1, turn+1) and IsItSolutionFor21(n,s*4, turn+1)

def CheckWinTurn2(n,s, turn): #Дополнение: так как имеем условие, что игрок не должен гарантированно победить на втором
                              #ходу, делаем проверку на гарантированную победу вторым ходом.
    if n+s>=82 and turn==2:
        return True
    elif n+s<82 and turn==2:
        return False
    if turn%2 == 1:
        return CheckWinTurn2(n+1,s,turn+1) or CheckWinTurn2(n*4,s,turn+1) or CheckWinTurn2(n,s+1, turn+1) or CheckWinTurn2(n,s*4, turn+1)
    else:
        return CheckWinTurn2(n+1,s,turn+1) and CheckWinTurn2(n*4,s,turn+1) and CheckWinTurn2(n,s+1, turn+1) and CheckWinTurn2(n,s*4, turn+1)



for i in range(1,77):
    if IsItSolutionFor19(4,i,0):
        print('its answr for 19:', i)
        break

print('its answrs for 20:')
for i in range(1,77):
    if IsItSolutionFor20(4,i,0):
        print(i)

for i in range(1,77):
    if IsItSolutionFor21(4,i,0) and not CheckWinTurn2(4,i,0):
        print('its answr for 21:',i)