егэ. Теория игр. Поиск выигрышной стратегии
 Скачать 0.79 Mb.
|
Пример задания:P-02(демо-2023).Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 129. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 129 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 128. Задание 19. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Задание 20. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания. Задание 21 Найдите значение S, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Решение (программа, автор разбора А. Кабанов, идея – И. Воропаев, доработка – А. Кабанов и К. Поляков). Напишем функцию, которая определяет существование выигрышной стратегии не более чем за m ходов обоих игроков. Функция имеет два параметра: количество камней S и наибольшее возможное количество ходов m. С каждым ходом значение m уменьшается на 1, показывая тем самым оставшееся число ходов до необходимого окончания игры: def f(s,m): if s>=129: return m%2==0 #1 if m==0: return 0 #2 if m%2!=0: return f(s+1,m-1) or f(s*2,m-1) #3 else: return f(s+1,m-1) and f(s*2,m-1) #4 При завершении игры функция отмечает победными такие варианты игры, в которых игра закончилась ровно за m ходов или менее, но тем же игроком (оставшееся значение m чётно) (#1). Варианты, требующие большей глубины, чем m, отбрасываются (#2). Если оставшееся число ходов нечётно, то для победы достаточно существования стратегии в одном из следующих ходов (#3). В противном случае стратегия должна быть во всех ходах (#4). Так происходит, потому что нечётное количество ходов подразумевает победу игрока, выполняющего ход из этой позиции. Тогда как чётное количество ходов подразумевает гарантированную победу его противника. Для нахождения ответа на 19 задание найдём значение S, для которого существует выигрышная стратегия за 2 хода print( '19)', *[s for s in range(1,129) if f(s,2)] ) Для нахождения ответа на 20 задание найдём значения S, для которых не существует выигрышной стратегии за 1 ход, но существует за 3 хода. print( '20)', *[s for s in range(1,129) if not f(s,1) and f(s,3)] ) Для нахождения ответа на 21 задание найдём значение S, для которого не существует выигрышной стратегии за 2 хода, но существует за 4 хода. print( '21)', *[s for s in range(1,129) if not f(s,2) and f(s,4)] ) Ответ: 19) 64 20) 32 63 21) 62 Ещё пример задания:P-01(демо-2022).Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 29 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 28. Задание 19. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Задание 20. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания. Задание 21 Найдите значение S, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Решение (построение таблицы). задачи с одной кучей просто решаются с помощью таблицы (массива); будем записывать в ячейках таблицы числовую оценку позиции: положительное число N означает выигрыш за Nходов, отрицательное число (–N) – проигрыш за N ходов очевидно, что при всех S ≥ 15 Петя выигрывает свои первым ходом, увеличив количество камней в куче вдвое; это позиции с оценкой 1 (выигрыш в один ход):
все возможные ходы из позиции 14 (это 15 и 28) ведут в позиции с оценкой 1, то есть 14 – проигрышная позиция с оценкой –1: проигрыш за один ход (Петя, начинающий игру, может ходить любым способом, но Ваня своим первым ходом сразу сможет выиграть):
гарантированный выигрыш за 2 хода возможен для тех позиций, из которых есть ход в позицию с оценкой –1, то есть, из позиций 13 и 7; оценка этих позиций – 2:
дальше определяем все позиции, откуда все ходы ведут в позиции с оценкой 1 или 2 (все они уже заполнены в таблице); определяем, что это только позиция 12 (возможные ходы – 13 с оценкой 2 и 24 с оценкой 1):
оценка позиции 12 равна (–2) Решение Задания 19. Ответ: 14 (позиция с оценкой –1). Решение Задания 20. Ответ: 7 и 13 (позиции с оценкой 2).; Решение Задания 21. Ответ: 12 (позиция с оценкой –2). Решение (программа, А. Кабанов) Напишем функцию, которая определяет существование выигрышной стратегии не более чем за moveWin ходов обоих игроков. Функция имеет три параметра: количество камней S, число совершённых ходов prevMoves и наибольшее возможное количество ходов moveWin. def f( S, prevMoves, moveWin ): if S >= 29: return prevMoves % 2 == moveWin % 2 # 1 if prevMoves == moveWin: return 0 # 2 if (prevMoves+1) % 2 == moveWin % 2: # 3 return f(S+1, prevMoves+1, moveWin) or \ f(S*2, prevMoves+1, moveWin) else: return f(S+1, prevMoves+1, moveWin) and \ # 4 f(S*2, prevMoves+1, moveWin) При завершении игры функция отмечает победными такие варианты игры, в которых игра закончилась за количество ходов той же чётности что и moveWin (за moveWin ходов или менее, но того же игрока) (метка #1). Варианты, требующие большей глубины, чем moveWin, отбрасываются (метка #2). Если moveWin нечётное, то проверяется возможность победы первого игрока, для чётных победа второго игрока. При анализе следующих ходов мы исходим из принципа, что если их чётность совпадает с moveWin, то достаточно победы в одном из них (метка #3). В противном случае победа должна быть во всех случаях (метка #4). Для нахождения ответа на 19 задание найдём значение S, для которого существует выигрышная стратегия за 2 хода. print( '19)', *[s for s in range(1,29) if f(s,0,2)] ) Для нахождения ответа на 20 задание найдём значения S, для которых не существует выигрышной стратегии за 1 ход, но существует за 3 хода. print( '20)', *[s for s in range(1,29) if not f(s,0,1) and f(s,0,3)] ) Для нахождения ответа на 21 задание найдём значение S, для которого не существует выигрышной стратегии за 2 хода, но существует за 4 хода. print( '21)', *[s for s in range(1,29) if not f(s,0,2) and f(s,0,4)] ) Ответ: 19) 14 20) 7 13 21) 12 Решение (программа) напишем, как и в разборе задачи Р00 (см. ниже), функцию, определяющую оценку позиции в виде числа: TARGET = 29 def gameResult( S ): ... Константа TARGET обозначает количество камней, при котором игра заканчивается. условие окончания игры (проигрыш того, кто получил такую позицию, оценка 0): if S >= TARGET: return 0 определяем рекурсивно оценки всех возможных ходов: nextCodes = [ gameResult(S+1), gameResult(S*2)] определяем, нет ли среди возможных ходов хода в проигрышную позицию: negative = [c for c in nextCodes if c <= 0] если среди возможных ходов есть ход в проигрышную позицию, строим положительную оценку позиции (она выигрышная), добавляя 1 к модулю оценки: if negative: res = -max(negative) + 1 иначе (если все ходы ведут в выигрышные позиции с положительной оценкой) строим отрицательную оценку позиции (она проигрышная): else: res = -max(nextCodes) вот полная функция TARGET = 29 def gameResult( S ): if S >= TARGET: return 0 # рекурсивно определяем коды всех возможных ходов nextCodes = [ gameResult(S+1), gameResult(S*2) ] negative = [c for c in nextCodes if c <= 0] if negative: res = -max(negative) + 1 else: res = -max(nextCodes) return res и основная программа, которая ее вызывает: results = [(S,gameResult(S)) for S in range(1,TARGET)] print( '19:', [S for S, R in results if R == -1] ) print( '20:', [S for S, R in results if R == 2] ) print( '21:', [S for S, R in results if R == -2] ) Здесь сначала определяются оценки позиции для всех возможных начальных значений S; они сохраняются в массиве кортежей (S,оценка). Затем выбираются результаты с оценкой –1 (решение задачи 19) , 2 (решение задачи 20) и –2 (решение задачи 21). |