Теория игр для ЕГЭ (информатика)

Практически все задания решаются достаточно простой программой имеющей подобный вид

1. Создаётся функция, определяющая победу/проигрыш
2. Создаётся основная функция с:
   1. Проверкой на победу через функцию
      1. При её прохождении возвращается игрок, который победил
   2. Проверка на превышение количества ходов
   3. Вызов всех возможных следующих ходов.
      1. Если ход переходит нечётному игроку, находится хотя бы один ход, при котором он выигрывает
      2. Если ход переходит чётному игроку, то ищутся случаи, когда все ходы выигрышные
3. В случае, когда игрок “поддаётся”, ищется хотя бы один выигрышный ход

---

Программа для теории игр

Условие победы

def gameOver(pile1, pile2):    
	if pile1 + pile2 >= 87:
        return True

Проверка на выигрышные ходы

# Оба игрока играют по лучшей тактике
 
def f(pile1, pile2, remaining_turns):
    if gameOver(pile1, pile2):
		return remainingё_turns % 2 == 0
    if remaining_turns == 0:
		return False
    if remaining_turns % 2 != 0:
		return f(pile1 + 1, pile2, remaining_turns - 1) or f(pile1 * 2, pile2, remaining_turns - 1) or f(pile1,pile2 + 1,remaining_turns - 1) or f(pile1, pile2 * 2, - 1)
	else:
        return f(pile1 + 1, pile2, remaining_turns - 1) and f(pile1 * 2, pile2, remaining_turns - 1) and f(pile1,pile2 + 1, remaining_turns - 1) and f(pile1, pile2 * 2, remaining_turns - 1)
        
# Первый игрок поддаётся
def f1(pile1, pile2, remaining_turns):
	if gameOver(pile1, pile2):
		return remaining_turns % 2 == 0
	if remaining_turns == 0:
		return False
	return f(pile1 + 1, pile2, remaining_turns - 1) or (pile1 * 2, pile2, remaining_turns - 1) or f(pile1, pile2 + 1, remaining_turns - 1) or f(pile1, pile2 * 2, remaining_turns - 1)

Проверка на соответствие условиям и вывод ответа

print("Первое")print("19 - ", min([s for s in range(78) if f1(9, s, 2)]))
 
print("Второе - ", min([s for s in range(78) if not f(9, s, 2) and f(9, s, 3)]))
 
print("Третье - ", min([s for s in range(78) if not f(9, s, 2) and f(9, s, 4)]))

Link to original