Теория игр. Поиск выигрышной стратегии
 Скачать 274 Kb.
|
|
© К. Поляков, 2021 19-21 (повышенный уровень, время – 6 + 6 + 10 мин)Тема: Теория игр. Поиск выигрышной стратегии. Что проверяется: Умение анализировать алгоритм логической игры. Умение найти выигрышную стратегию игры. Умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию. 1.5.2. Цепочки (конечные последовательности), деревья, списки, графы, матрицы (массивы), псевдослучайные последовательности. 1.1.3. Умение строить информационные модели объектов, систем и процессов в виде алгоритмов. Что нужно знать: в простых играх можно найти выигрышную стратегию, просто перебрав все возможные варианты ходов соперников для примера рассмотрим такую игру: сначала в кучке лежит 5 спичек; два игрока убирают спички по очереди, причем за 1 ход можно убрать 1 или 2 спички; выигрывает тот, кто оставит в кучке 1 спичку первый игрок может убрать одну спичку (в этом случае их останется 4), или сразу 2 (останется 3), эти два варианта можно показать на схеме:  если первый игрок оставил 4 спички, второй может своим ходом оставить 3 или 2; а если после первого хода осталось 3 спички, второй игрок может выиграть, взяв две спички и оставив одну:  если осталось 3 или 2 спички, то 1-ый игрок (в обеих ситуациях) выиграет своим ходом:  простроенная схема называется «деревом игры», она показывает все возможные варианты, начиная с некоторого начального положения (для того, чтобы не загромождать схему, мы не рисовали другие варианты, если из какого-то положения есть выигрышный ход) в любой ситуации у игрока есть два возможных хода, поэтому от каждого узла этого дерева отходят две «ветки», такое дерево называется двоичным (если из каждого положения есть три варианта продолжения, дерево будет троичным) проанализируем эту схему; если первый игрок своим первым ходом взял две спички, то второй сразу выигрывает; если же он взял одну спичку, то своим вторым ходом он может выиграть, независимо от хода второго игрока кто же выиграет при правильной игре? для этого нужно ответить на вопросы: 1) «Может ли первый игрок выиграть, независимо от действий второго?», и 2) «Может ли второй игрок выиграть, независимо от действий первого?» ответ на первый вопрос – «да»; действительно, убрав всего одну спичку первым ходом, 1-ый игрок всегда может выиграть на следующем ходу ответ на второй вопрос – «нет», потому что если первый игрок сначала убрал одну спичку, второй всегда проиграет, если первый не ошибется таким образом, при правильной игре выиграет первый игрок; для этого ему достаточно первым ходом убрать всего одну спичку в некоторых играх, например, в рэндзю (крестики-нолики на бесконечном поле) нет выигрышной стратегии, то есть, при абсолютно правильной игре обоих противников игра бесконечна (или заканчивается ничьей); кто-то может выиграть только тогда, когда его соперник по невнимательности сделает ошибку полный перебор вариантов реально выполнить только для очень простых игр; например, в шахматах сделать это за приемлемое время не удается (дерево игры очень сильно разветвляется, порождая огромное количество вариантов) все позиции в простых играх делятся на выигрышные и проигрышные выигрышная позиция – это такая позиция, в которой игрок, делающий первый ход, может гарантированно выиграть при любой игре соперника, если не сделает ошибку; при этом говорят, что у него есть выигрышная стратегия – алгоритм выбора очередного хода, позволяющий ему выиграть если игрок начинает играть в проигрышной позиции, он обязательно проиграет, если ошибку не сделает его соперник; в этом случае говорят, что у него нет выигрышной стратегии; таким образом, общая стратегия игры состоит в том, чтобы своим ходом создать проигрышную позицию для соперника выигрышные и проигрышные позиции можно охарактеризовать так: позиция, из которой все возможные ходы ведут в выигрышные позиции – проигрышная; позиция, из которой хотя бы один из возможных ходов ведет в проигрышную позицию - выигрышная, при этом стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для соперника) позицию. Пример задания:P-00(демо-2021).Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69. Задание 19. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна. Задание 20. Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия: − Петя не может выиграть за один ход; − Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Найденные значения запишите в ответе в порядке возрастания. Задание 21 Найдите минимальное значение S, при котором одновременно выполняются два условия: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети; – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Решение Задания 19. возможно, что есть несколько значений S, которые удовлетворяют условию; нас интересует минимальное из них; при минимальном подходящем значении S общее количество камней в двух кучах увеличивается максимально быстро до значения 77 или большего; поскольку удвоение увеличивает количества камней в куче быстрее, чем добавление одного камня, можно сделать вывод, что для минимального подходящего значения S игроки своими ходами дважды удвоили бОльшую из двух куч; предположим, что бОльшая куча имеет 7 камней, и S = 7; тогда наибольшее число камней, которое можно получить после одного хода каждого игрока – 7 + 7*2*2 = 35; так как 35 < 77, игра не окончена и этот вариант не подходит; делаем вывод, что S > 7 таким образом, дважды была удвоена вторая куча; условие окончания игры 7 + S*2*2 77, откуда получаем S 17,5; это значит, что Smin = 18 Ответ: 18. Решение Задания 20. Петя своим ходом должен перевести игру в такую позицию, что Ваня не может выиграть своим первым ходом, но добавление одного камня в любую кучу позволяет выиграть Пете вторым ходом рассмотрим такие (проигрышные) позиции; при удвоении второй (бОльшей) кучи в сумме должно получаться 76 камней (недостаточно для выигрыша): (8, 34) (10, 33) (12, 32) (14,31) (16,30) … теперь подумаем, какие из них можно получить из начальной позиции (7, S) за один ход; видно, что количество камней в первой куче изменяется, то есть Петя на первом ходу работает с первой кучей; он может получить там 7 + 1 = 8 камней (и у нас есть критическая позиция (8,34)!) или 7*2=14 камней (для этого случая тоже есть критическая позиция (14,31)) поэтому условию задания удовлетворяют значения S = 31 и 34, их нужно записать в порядке возрастания Ответ: 31 34. Решение Задания 21 (благодарю за обсуждение Д. Муфаззалова и В. Бабия). определим свойства позиции, которую мы ищем: это проигрышная позиция, то есть всех возможные ходы из нее ведут в выигрышные позиции; из этой позиции есть ход в выигрышную позицию, из которой Ваня не может выиграть за один ход, но может гарантированно выиграть за два; это значит, что есть ход в позицию, определённую в решении задачи 20 или равноценную ей! для полного решения задачи построим таблицу выигрышных и проигрышных позиций; выигрышные позиции будем обозначать положительными числами, например, 2 – выигрыш в два хода; проигрышные позиции обозначаем отрицательными числами, например, «–2» – проигрыш в два хода (это значит, что при самой лучшей игре первого игрока второй выиграет по крайней мере своим вторым ходом) таблица будет прямоугольная, на вертикальной оси откладываем количество камней в первой куче, на горизонтальной – количество камней во второй куче:
пока в таблице расставлены единицы в позициях, которые ведут к выигрышу Пети на первом ходу и «–1» в позициях, которые ведут к выигрышу Вани на своем первом ходу (после любого первого хода Пети) отметим числом 2 ячейки, откуда есть ходу в серые клетки с ходом «–1»:
в верхней строке таблицы выделены жёлтым позиции (7, 31) и (7, 34), найденные при решении предыдущего задания докажем, что в верхней строке больше нет позиций с кодом 2; по определению из позиции с кодом 2 есть ход в позицию с кодом «–1»; во всех позициях с кодом «–1», не попавших в рассмотренную часть таблицы, в первой куче больше 14 камней, то есть, стартовав с первой кучей из 7 камней мы не можем получить такие позиции за один ход нам нужно найти в верхней строке позиции, из которых все ходы ведут в выигрышные позиции с кодами 1 (выигрыш за 1 ход) или 2 (выигрыш за 2 хода) сразу видны две таких позиции (выделены на следующем рисунке зелёным цветом): (7, 30) – возможные ходы в (7, 31), (8, 30) и (14, 30) с кодом 2 и (7, 60) с кодом 1 (7, 33) – возможные ходы в позиции (7, 34) и (8, 33) с кодом 2, а также (14, 33) и (7, 66) с кодом 1:
вроде бы все хорошо, и можно выбрать минимальное из двух найденных значений S (30), но кроме этих ячеек есть ещё кандидат на решение – S = 17, потому что ходом из позиции (7, 17) можно получить позицию (7, 34) с кодом 2 однако на самом деле позиция (7, 17) нам не подходит, докажем это, рассмотрев все возможных ходы Пети: (8, 17) (14, 17) (7, 18) (7, 34) здесь жёлтым фоном выделены ходы с кодом 2 – выигрышные позиции за 2 хода (из позиции (8, 17) есть ход в (8, 34) с кодом «–1») рассмотрим ход (14, 17); возможные ходы из него (15, 17) (28, 17) (14, 18) (14, 34) среди них нет ни одного хода в позицию с кодом «–1», то есть, ход Пети (14, 17) не даст Ване выиграть за 2 хода; поэтому эта позиция не подходит Ответ: 30. Решение с помощью программы (рекурсия) напишем программу на языке Python, которая для всех значений S выдаёт код позиции (про коды позиций см. выше) сначала поясним идею; пусть нужно определить код позиции (x, y); для этого мы должны предварительно определить коды позиций, куда можно попасть одним ходом из (x, y): (x+1, y) (2x, y) (x, y+1) (x, 2y) поскольку нужно выполнить ту же самую операцию, это будет рекурсивная функция итак, пусть мы нашли коды четырёх возможных следующих позиций; рассмотрим несколько примеров: пусть эти коды [1, 2, 2, 3], то есть все возможные ходы ведут в выигрышные позиции, Петя проигрывает; он заинтересован в том, чтобы проиграть за максимальное число ходов (всячески оттягивая поражение), поэтому из этих кодов нужно выбрать максимальный и записать его со знаком минус, получаем код «–3», то есть Петя проиграет за 3 хода (на 3-м ходу Ваня выиграет) пусть эти коды [1, –2, 2, –3], то есть найдены два хода в проигрышные позиции (с кодами «–2» и «–3»), и Петя может выиграть; он заинтересован в том, чтобы выиграть за наименьшее число ходов, поэтому нужно выбрать максимальное из полученных отрицательных чисел («–2»), убрать знак минус и добавить единицу (Петя добавляет новый ход); поэтому для данного случая код клетки будет равен 3 рекурсия должна заканчиваться, когда сумма x+yстала больше или равна 77; определим это значение как константу TARGET («цель»); TARGET = 77 такую позицию (когда игра завершена) будем обозначать кодом 0 и считать её проигрышной, как и позиции с отрицательным кодом запишем первую версию функции gameResult, которая принимает два параметра - количество камней в первой и второй кучах: def gameResult( x, y ): if x + y >= TARGET: return 0 # рекурсивно определяем коды всех возможных ходов nextCodes = [ gameResult(x+1, y), gameResult(x*2, y), gameResult(x, y+1), gameResult(x, y*2) ] if в nextCodes есть отрицательные или 0: res = -max(отрицательные или 0) + 1 else: res = -max(nextCodes) return res строки, выделенные красным цветом – это псевдокод, который нужно заменить на операторы Python; выделим из массива nextCodes все отрицательные числа и нули (соответствующие проигрышным позициям): negative = [c for c in nextCodes if c <= 0] тогда условный оператор if в nextCodes есть отрицательные или 0: может быть записан как if negative: res = -max(negative) + 1 else: res = -max(nextCodes) получается такая функция: def gameResult( x, y ): if x + y >= TARGET: return 0 # рекурсивно определяем коды всех возможных ходов nextCodes = [ gameResult(x+1, y), gameResult(x*2, y), gameResult(x, y+1), gameResult(x, y*2) ] negative = [c for c in nextCodes if c <= 0] if negative: res = -max(negative) + 1 else: res = -max(nextCodes) return res попробуем посчитать коды для всех возможных значений S от 69 = 77-7-1 до 1: X = 7 for S in range(TARGET-X-1,0,-1): r = gameResult( X, S ) print( "{:d} {:d}".format(S, r) ) к сожалению, обнаруживаем, что программа работает очень медленно… Дело в том, что программа много раз вычисляет значение кода для одних и тех позиций. Чтобы этого избежать, будем запоминать их в словаре results: results = {} # (1) def gameResult( x, y ): if (x,y) in results: return results[(x,y)] # (2) if x + y >= TARGET: return 0 nextCodes = [ gameResult( x+1, y ), gameResult( x*2, y ), gameResult( x, y+1 ), gameResult( x, y*2 ) ] negative = [c for c in nextCodes if c <= 0] if negative: res = -max(negative) + 1 else: res = -max(nextCodes) results[(x,y)] = res # (3) return res добавленные строчки выделены голубым фоном; в строке (1) создаётся пустой словарь (глобальная переменная), ключом в этом словаре будет кортеж, описывающий позицию (x, y); в строке (2) мы проверяем, нет ли в словаре кода для запрошенной позиции; если есть, то сразу возвращаем этот код в строке (3) добавляем в словарь новый код запрошенной позиции теперь программа отрабатывает очень быстро, и мы видим, что позиция (7, 17), которую мы хотели проверить, на самом деле выигрышная (её код 11); это значит, что ответ на вопрос задачи 21 – это 30. Ответ: 30. Решение с помощью программы (динамическое программирование, А. Сидоров) вместо рекурсии можно применить динамическое программирование, где вместо словаря results используется двухмерный массив: TARGET = 77 results = [[0]*2*TARGET for i in range(2*TARGET)] for x in range(TARGET-1,0,-1): for y in range(TARGET-x-1,0,-1): nextCodes = [ results[x+1][y], results[2*x][y], results[x][y+1], results[x][2*y]] negative = [с for с in nextCodes if с <= 0] if negative: results[x][y] = -max(negative) + 1 else: results[x][y] = -max(nextCodes) N1 = 7 for S in range(TARGET-N1-1,0,-1): print( "{:d} {:d}".format(S, results[N1][S]) ) Эта программа для каждого значения S выводит оценку позиции. Положительные значения K означают выигрыш: Петя выиграет за K ходов. Отрицательные значение (-K): Ваня гарантированно выиграет не позднее, чем своим K-м ходом. Ответ: 30. |