Теория игр: задачи 19-21 ЕГЭ по информатике. Решение на питоне.

 

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне

 

Честно говоря, задачи 19-21 можно решать в уме - по крайней мере, в том виде, в котором они предлагались в 2023 г. Но при небольшом усложнении условий это будет гораздо труднее. Поэтому ниже я расскажу про программный способ их решения. В данном способе одной программой можно решить все три задачи "одним махом" (и заработать три первичных балла, что само по себе приятно).

Хотя в интернете много программ для решения данной задачи, но у всех, которые я видел, есть существенный недостаток. Они мало понятны, и, как правило, никаких пояснений к ним не прилагается. Поэтому я стремился написать такое решение, которое будет как можно более прозрачно, которое можно легко изменять в соответствии с условиями задачи, а также максимально подробно его прокомментировал.

Задачи 19-21 достаточно однотипны: есть игра с простыми правилами, в которую играют двое. Игроки делают ходы по очереди. Обычно это что-то вроде того, что есть куча камней, и каждый игрок может добавить в эту кучу либо два камня, либо три, либо утроить число камней в куче. Победителем считается тот игрок, который сделает число камней больше некоторого порога.  

В задаче 19 есть два варианта вопроса. Первый: первый игрок делает неудачный ход, и второй тут же выигрывает. При каком минимальном числе камней в куче это возможно? Второй: при каком минимальном числе вамней в куче первый игрок выиграть своим первым ходом не может, но второй может выиграть свим первым ходом после любого хода первого? (Вначале мы будем рассматривать именно второй вариант, но потом опишем и способ решения для первого.)

В задаче 20 вопрос стандартный: при каких начальных числах камней в куче первый игрок своим первым ходом выиграть не может, но своим вторым ходом выиграет, что бы ни делал второй игрок? 

Задача 21 также стандартна: при каких начальных числах камней в куче второй игрок может выиграть своим первым или вторым ходом при любых ходах первого игрока?

В качестве примера возьмём задачи из демо-варианта ЕГЭ по информатике 2024 г. В них правила следующие: каждый игрок может либо добавить в кучу один камень, либо удвоить число камней в куче. Игра заканчивается, когда число камней в куче становится не менее 129, и победитель - тот, кто сумел этого достичь. Начальное число камней в куче s лежит в пределах 1<=s<=128.  

Вопрос задачи 19: при каком начальном значении s второй игрок может выиграть своим первым ходом при любых ходах первого игрока? (Т.е. второй вариант задачи 19.)

Вопрос задачи 20: при каких двух наименьших значениях s первый игрок не может выиграть своим первым ходом, но модкт выиграть своим вторым ходом при любых ходах второго игрока?

Вопрос задачи 21: при каком минимальном s второй игрок может выиграть своим первым или вторым ходом при любых ходах первого?

Чуть-чуть рассуждений (достаточно очевидных)

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

Если же при любом ходе игрока выигрывает его противник, то ситуация, очевидно, безнадёжна для текущего игрока. Впору сказать "Сдаюсь" и не тратить время впустую.

Вот, собственно, центральная идея нашей программы.

Пора писать программу.

Основа программы - это функция move (рекурсивная), анализирующая текущую игровую ситуацию. Она будет возвращать одно из трех значений: 1 - в данной ситуации побеждает первый игрок, 2 - второй, 0 - победитель не определён.

У функции move(n,lim,s) три параметра: номер хода n, ограничение на число ходов lim и число камней в куче s. 

Вначале определим, кто на данном ходе текущий игрок (player), а кто - его противник (rival). Нечётные ходы делает первый игрок, а чётные - аторой. Пожалуй, наиболее простые формулы следующие:

player=2-n%2
rival=3-player

Первое, что нужно сделать - проверить, а не закончилась ли игра. Если число камней превысило 128, то игра закончена. А кто же победитель? Вообще-то не текущий игрок - он ещё не сделал свой ход. (Если ваша очередь ходить и вы видите, что в куче уже, скажем, 130 камней, то вам должно быть ясно, что ваш противник только что сделал выигрышный ход и он-то и является победителем.)

if s>128:
    return rival

Теперь нужно проверить, а не превышен ли лимит ходов. Если да, то делать дальнейшие ходы мы не имеем права, и победитель не определён:

if n>lim:
    return 0

Вот теперь-то и начинается настоящая игра.

Составим список позиций, которые возможны после хода текущего игрока:

pos=[s+1,s*2]

Теперь получим список результатов игры для каждой позиции в этом списке:

res=[move(n+1,lim,x) for x in pos]

Возможны три случая.

Во-первых, в списке результатов есть хотя бы один ход, выинрышный для текущего игрока:

if any([x==player for x in res]):
    return player

Во-вторых, все ходы в списке - проигрышные:

if all([x==rival for x in res]):
    return rival

Если же неверно ни одно, ни другое, то победитель не определён:

return 0

Приведём функцию целиком:

def move(n,lim,s):
    # n - номер хода, lim - ограничение числа ходов, s - число камней
    # Результат: 1 - победа первого игрока, 2 - второго, 0 - победитель не определён
    player=2-n%2 # текущий игрок
    rival=3-player # противник
    if s>128: # Игра окончена?
        return rival # Да, победил противник
    if n>lim: # Превышен лимит ходов?
        return 0 # Да, победитель не определён
    pos=[s+1,s*2] # Список поэиций после хода игрока
    res=[move(n+1,lim,x) for x in pos] # Список результатов ходов
    if any([x==player for x in res]): # Есть выигрышный ход?
        return player # Да, победил текущий игрок
    if all([x==rival for x in res]): # Все ходы проигрышные?
        return rival # Да, победил противник
    return 0 # Победитель не определён

Функцию мы написали, пора её вызывать.

Для ответа на вопрос задачи 19 получим и напечатаем список значений s, для которых при игре в два хода побеждает второй игрок. В задаче 20 требуются такие значения s, при которых в игре в один ход победителя нет, а при игре в три хода побеждает первый. Наконец, в задаче 21 требуются такие значения s, что при игре в два хода не выигрывает никто, а при игре в четыре хода побеждает второй.

Вот соответствующий код:

print('#19:',*[s for s in range(1,129) if move(1,2,s)==2])
print('#20:',*[s for s in range(1,129) if move(1,1,s)==0 and move(1,3,s)==1])
print('#21:',*[s for s in range(1,129) if move(1,2,s)==0 and move(1,4,s)==2])

Выполняем его и получаем ответ на три задачи сразу:

#19: 64
#20: 32 63
#21: 62

Одним выстрелом - трёх зайцев. Неплохо.

Если Петя глуповат...

Предыдущая программа решает 19-ю задачу во втором её варианте: при каких s первый игрок не может выиграть своим первым ходом, а второй выиграет при любом ходе первого. 

А что делать, если в задаче требуется узнать, при каком минимальном значении s возможна ситуация, когда первый игрок делает неудачный ход, после которго второй немедленно выигрывает?

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

В строке 

if all([x==rival for x in res]):

меняем функцию all на any и выполняем вызов (точно такой же, как и в предыдущем случае):

print('#19:',*[s for s in range(1,129) if move(1,2,s)==2])

Получаем следующий длинный список значений s:

#19: 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

Для каждого из этих значений у первого игрока есть по крайней мере один ход, после которого у второго игрока есть возможность выиграть. Минимальное число - 33. 

В самом деле, если первый игрок удвоит 33 и получит 66, то второй тоже удвоит это число, получит 132 и выиграет. Если же у первого игрока будет хотя бы на один камень меньше, то такая ситуация невозможна (32*2=64, 64*2=128, для выигрыша второму игроку не хватает одного камня).

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

А как быть с двумя кучами?

Ну хорошо, задачу с одной кучей мы решили. А что, если куч будет две?

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

Решим одну из таких задач. В ней игроки имеют право добавлять в меньшую из двух куч один или два камня или удваивать количество камней в ней. Изменять большую кучу запрещается. (В условии ничего не сказано про случай, когда число камней в кучах одинаковое. В этом случае, видимо, можно изменять любую кучу. Мы будем изменять вторую.) Игра заканчивается, когда суммарное число камней в кучах станет более 80, и победитель - игрок, который своим ходом получил такое число. Сначала в первой куче 12 камней, во второй - произвольное число.

Изменения в программе минимальные. Во-первых, параметр s теперь - это кортеж из двух чисел. Мы распакуем его в переменные s1 и s2.

Формирование списка позиций теперь будет выглядеть так:

s1,s2=s
pos=[(s1+1,s2),(s1+2,s2),(s1*2,s2)] if s1<s2 else [(s1,s2+1),(s1,s2+2),(s1,s2*2)]

Кроме того, нужно будет изменить условие завершения игры:

if sum(s)>80:

Больше никаких изменений в функции не требуется. А вызовы функции, разумеется, придется поменять - ведь параметр s теперь кортеж.

Вот полная программа решения этой задачи:

 

def move(n,lim,s):
    # n - номер хода, lim - ограничение числа ходов, s - числа камней (кортеж)
    # Результат: 1 - победа первого игрока, 2 - второго, 0 - победитель не определён
    player=2-n%2 # текущий игрок
    rival=3-player # противник
    if sum(s)>80: # Игра окончена?
        return rival # Да, победил противник
    if n>lim: # Превышен лимит ходов?
        return 0 # Да, победитель не определён
    s1,s2=s # Распаковка позиции, формирование списка
    pos=[(s1+1,s2),(s1+2,s2),(s1*2,s2)] if s1<s2 else [(s1,s2+1),(s1,s2+2),(s1,s2*2)]
    res=[move(n+1,lim,x) for x in pos] # Список результатов ходов
    if any([x==player for x in res]): # Есть выигрышный ход?
        return player # Да, победил текущий игрок
    if all([x==rival for x in res]): # Все ходы проигрышные?
        return rival # Да, победил противник
    return 0 # Победитель не определён
    
print('#19:',*[s for s in range(1,69) if move(1,2,(12,s))==2])
print('#20:',*[s for s in range(1,69) if move(1,1,(12,s))==0 and move(1,3,(12,s))==1])
print('#21:',*[s for s in range(1,69) if move(1,2,(12,s))==0 and move(1,4,(12,s))==2])

 

Вот, собственно, и всё.  Почти. Но есть ещё кое-что.

А если нельзя повторять ходы?

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

Как быть? А очень просто. Надо добавить в нашу функцию ещё один параметр: список сделанных ходов. На основе этого списка можно удалить из списка позиций те ходы, которые делать запрещено, чтобы программа их не рассматривала.

Возьмём для примера следующую задачу.

Игра - с одной кучей камней. Каждый игрок может добавить в кучу либо один камень, либо два, дибо удвоить число камней в куче. При этом запрещается повторять свой последний ход. Игра заканчивается, когда число камней в куче станет не менее 21. В данной задаче также немного иные вопросы. В задаче 19 справшивается, при каком наименьшем значении S первый игрок не может выиграть первым ходом, но обязательно выиграет вторым. В задаче 20 - при каких двух значениях S второй игрок выиграет своим вторым ходом, но выигрыш первым ходом не гарантирован. В задаче 21 - при каком наибольшем S первый игрок не может выиграть своим вторым ходом, но всегда может выиграть третьим. (Иными словами, здесь задачи 19 и 20 - это задачи 20 и 21 из традиционных вариантов. К слову, это задача 46977 с сайта "Решу ЕГЭ".)

В список позиций будем заносить не просто количества камней в куче, а кортежи, в которых первый элемент - это число камней, а второй - условный номер хода: 0 - добавить один камень, 1 - добавить два камня, 2 - удвоить число камней.

После этого проверим, что длина списка ходов более одного (т.е. имеется предыдущий ход текущего игрока). Если это так - удалим соответствующий элемент из списка позиций. При вызове функции  возьмем первый элемент кортежа как количество камней в куче, а второй присоединим к списку ходов. Далее всё как прежде.

При первом вызове функции список ходов, естественно, пустой.

Вот полный текст программы:

def move(n,lim,s,t):
    player=2-n%2
    rival=3-player
    if s>=21: return rival
    if n>lim: return 0
    pos=[(s+1,0),(s+2,1),(s*2,2)]
    if len(t)>1: del pos[t[-2]]
    res=[move(n+1,lim,x[0],t+[x[1]]) for x in pos]
    if any([x==player for x in res]): return player
    if all([x==rival for x in res]): return rival
    return 0

print('#19:',*[s for s in range(1,21) if move(1,1,s,[])==0 and move(1,3,s,[])==1])
print('#20:',*[s for s in range(1,21) if move(1,2,s,[])==0 and move(1,4,s,[])==2])
print('#21:',*[s for s in range(1,21) if move(1,3,s,[])==0 and move(1,5,s,[])==1])

Ответ программы:

#19: 8 9
#20: 6 7
#21: 3 5

(На сайте "Решу ЕГЭ" даны программные решения задач. Для каждой задачи - своя программа, при этом программа для задачи 21 содержит примерно 80 строк. Не программа, а сценарий ужастика.)

Если запрещается повторять ход предыдущего игрока, то строку 

if len(t)>1: del pos[t[-2]]

следует заменить на 

if len(t)>0: del pos[t[-1]]

(c) Ю.Д.Красильников, 2024 г.