Автор статьи: Андрей Рогов
Введение
Теория игр — это математический метод изучения стратегических взаимодействий между участниками, принимающими решения. В информатике теория игр применяется для анализа алгоритмов, разработки искусственного интеллекта и решения оптимизационных задач.
На ЕГЭ по информатике теория игр представлена сразу тремя заданиями, которые связаны между собой. До компьютерного варианта экзамена это было одно задание, и его решение необходимо было оформлять. Сейчас достаточно найти числовые ответы.
Рассмотрим основные теоретические понятия на примере условий задания.
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить их количество в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченный запас камней. Игра завершается в тот момент, когда количество камней в куче становится не меньше 50. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу из 50 или больше камней.
Позицией будем называть текущую ситуацию в игре, т. е. определённое количество камней в куче. Выигрышная позиция — такая позиция в игре, из которой игрок, делающий ход, может гарантированно победить при правильной игре. Проигрышная позиция — это позиция, из которой в любой допустимой ситуации игрок, делающий ход, проиграет при оптимальных действиях противника. Если из текущей позиции можно перейти в проигрышную, это выигрышная позиция. Если из текущей позиции можно перейти только в выигрышные — это проигрышная позиция.
Для того чтобы определить, какие есть позиции в текущих условиях игры, мы будем использовать метод обратной индукции. Начнём с конечных позиций, — таких, в которых игра заканчивается, — и будем определять нужное нам количество промежуточных.
Конечные позиции в нашем случае — это все позиции с 50 камнями и больше, поскольку после них игра завершается. Рассмотрим позицию 49. Используя ходы + 1 и × 2, игрок может получить из числа 49 числа 50 и 98. И то и другое — конечные позиции. Это означает, что 49 — выигрышная позиция, потому что из неё есть такой ход, при котором игрок побеждает. Более того, здесь все ходы приводят к победе, проиграть просто невозможно.
Возьмём значение на единицу меньше, 48. Игрок может получить позиции 49 и 96. Если он сделает ход в 49, то проиграет, поскольку 49 — не конечная позиция, и его противник победит, поскольку 49 — выигрышная позиция. А если игрок сделает ход в 96, то он победит. Правильная игра заключается в том, чтобы умножить на два. Таким образом, 48 тоже выигрышная позиция, из неё можно гарантированно победить. К победе приводит не любой ход, но достаточно и одного.
Несложно заметить, что при меньших начальных значениях камней в куче побеждать можно, только умножая на два. Определим, при каком минимальном количестве камней можно победить.
Если в куче будет 24 камня, то победить будет нельзя, поскольку с помощью умножения на два можно набрать только 48 камней, а для победы необходимо 50. При начальном значении 25 камней победить удастся, поскольку ходом × 2 можно получить 50 камней. Следовательно, 25 — минимальное значение, при котором игрок способен победить своим первым ходом.
Обозначим все позиции с 25 до 49 как В1 — выигрышные позиции, из которых есть ход, позволяющий победить первым ходом. Для определения этих позиций можно руководствоваться «сильным» ходом — ходом, делающим наибольшее изменение количества камней.
Теперь определим проигрышные позиции, в которых игрок проиграет, сделав свой первый ход. Это такие позиции, из которых все возможные ходы ведут в В1. Подходящее значение только одно: это 24. Из 24 можно попасть в 25 и в 48, оба значения — выигрышные для противника позиции. Обозначим эту позицию П1 — проигрыш первым ходом.
Мы разобрали позиции, в которых могут оказаться игроки за один ход до окончания игры, а именно такие, из которых можно победить своим первым ходом, и такие, в которых игрок проигрывает после своего первого хода. На ЕГЭ необходимо рассмотреть позиции за два хода до окончания игры. Взглянем на нужные нам значения.
Мы уже способны определить позиции, в которых можно победить за два хода. Итак, известно, что 24 — проигрышная позиция. Если есть ход, который приведёт противника в эту позицию, игрок, делающий ход, победит. В 24 можно попасть из 23 ходом + 1 и из 12 ходом × 2. Это выигрышные позиции, но за два хода. Обозначим их В2.
И наконец, последнее, что мы определим — это проигрышные позиции, в которых потребуется один или два хода, чтобы проиграть. Такая позиция будет только одна: 22. Ходы из 22 ведут в 23 (выигрышная позиция за два хода) и в 44 (выигрышная позиция за 1 ход). Следовательно, все ходы из 22 проигрышные. Больше таких позиций нет.
Изобразим все позиции в виде таблицы.
Осталось ещё достаточно много позиций, о которых мы не знаем, проигрышные они или выигрышные. В заданиях ЕГЭ требуется рассмотреть игру на два хода для каждого игрока. Поэтому остальные позиции мы не определяем.
До этого момента мы ничего не говорили о том, какие вопросы ставятся в заданиях № 19, 20 и 21, а занимались только определением позиций. Теперь на примере задания покажем, как связаны найденные нами позиции и задания.
Задача 1. Одна куча камней, два разных хода
Аналогично тому, как мы сделали в примере, определим все позиции.
С помощью «сильного» хода можно победить начиная с позиции 61. Из позиций 58, 59 и 60 оба хода ведут в В1, следовательно они проигрышные. Попасть в позиции 58, 59 и 60 можно из 55, 56 и 57, а ходом × 5 — из 12. Все они будут выигрышными за два хода.
И наконец, из позиций 52, 53 и 54 можно сходить только в В1 и В2, т. е. выигрышные. Следовательно, это проигрышные позиции за два хода.
В вопросе задания № 19 необходимо найти позицию, в которой первый игрок не может победить своим первым ходом, но второй игрок затем побеждает. Это позиции П1, проигрышные за один ход. Наименьшей такой позицией будет 58.
В вопросе задания № 20 — позиции, в которых игрок побеждает вторым ходом. Это В2. Два наименьших значения — 12 и 55.
Для ответа на задание № 21 нужно найти позиции проигрышные, но за один или два хода. Это П2. Наименьшая такая позиция — 52.
Задача 2. Убирание камней
В этом задании камни не добавляются, а убираются. Сложность представляет только третий ход, когда количество камней уменьшается в 4 раза, поскольку происходит округление. В остальном задача решается с помощью тех же рассуждений.
Определим максимальное значение S, при котором можно выиграть первым ходом. «Сильный» ход — разделить на 4. 30 × 4 = 120, но, поскольку происходит округление в меньшую сторону, позиции 121, 122 и 123 при делении на 4 также будут давать 30 камней. Следовательно, максимальное значение, из которого можно победить первым ходом, — это 123. Все позиции с 31 до 123 обозначим В1.
Самый «слабый» ход — вычесть 3. Значит, позиции 124, 125 и 126 будут проигрышными за один ход. Это П1.
Теперь можно вычислить выигрышные позиции за два хода. Это все значения S, из которых есть ход в П1. Ходом − 3 в позиции П1 можно попасть из 127, 128 и 129. Для хода − 5 подходящими позициями будут 130 и 131. А вот ход уменьшить в 4 раза будет давать по три позиции для каждой из П1 из-за округления в меньшую сторону. Подходящими позициями будут значения с 496 до 507.
Проигрышные позиции за два хода надо искать рядом с выигрышными. Подходящими значениями S будут 132, 133, 134 и 508, 509, 510.
Ответом на задание № 19 будет 124, на задание № 20 — 127 и 128, на задание № 21 — 132.
Задача 3. Две кучи камней
В условии задания есть две кучи камней, что значительно усложняет решение. Теперь необходимо рассматривать ходы для каждой кучи. Если раньше задача, условно говоря, была одномерной (позиции можно было изобразить в виде ряда чисел), то теперь задача становится двухмерной, поскольку позиции изображаются с помощью пары чисел.
Подобные задания довольно трудны для аналитического решения. Более эффективным будет использование электронных таблиц или программирования. Тем не менее для понимания сути решения приведём разбор такой задачи.
Второе отличие этой задачи заключается в другом вопросе задания № 19. Появляется новый термин: неудачный ход.
Найдём позиции П1 (победа первым ходом) и определимся с тем, что такое неудачный ход. Для поиска позиций П1 (победа первым ходом) рассмотрим значения S, из которых можно победить при условии, что в первой куче 6 камней. Чтобы набрать в сумме 65 камней, во второй куче их должно быть как минимум 59.
«Сильный» ход — умножить на три. В 59 нельзя сделать ход, умножив число на 3, поэтому минимальным значением S, из которого можно победить, будет 20. Из позиции (6, 20) можно получить позицию (6, 60), в сумме 66. А из позиции (6, 19) можно получить только (6, 57), в сумме 63, что недостаточно для победы.
Итак, вот что можно определить как неудачный ход. Во-первых, из позиции (6, 20) игрок мог сходить в (6, 21) и победить, но сделал другой ход и затем проиграл. Очевидно, это неудачный ход. Во-вторых, из позиции (6, 7) игрок мог получить четыре разные позиции: (6, 8), (6, 21), (7, 7), (18, 7). Из них мы можем определить только одну. Позиция (6, 21) выигрышная за один ход. Таким образом, игрок из позиции (6, 7) мог сделать ход и не проиграть (во всяком случае, сразу).
Неудачным ходом было бы утроить вторую кучу и получить позицию (6, 21), поскольку противник сразу выиграл бы. В задании № 19 спрашивается о минимальном значении, при котором Ваня выигрывает сразу после первого хода Пети. Такое значение будет S = 7.
Для ответа на 20-е задание необходимо найти проигрышные позиции за один ход и выигрышные за два хода. В заданиях на две кучи камней не получится сделать так же, как и в задачах на одну: просто рассматривать все значения S по уменьшению. Рассматривая игру более чем в один ход, мы не можем не учитывать ходы, совершаемые с разными кучами.
Будем отталкиваться от позиций, которые максимально приближают к победе, но не позволяют победить. Для победы сумма камней в двух кучах должна быть 65. Рассмотрим позиции, в которых она равна 64. Например, позиция (10, 54). Она может быть получена «сильным» ходом из (10, 18). Из позиции (10, 18) нельзя победить ни одним ходом, но какой бы ход ни сделал игрок, его противник затем побеждает.
Такое свойство будет у всех позиций, из которых можно попасть в позицию с суммой камней 64, причём сделать это «сильным» ходом, т. е. утраивая бóльшую кучу. Это позиции (1, 21), (4, 20), (7, 19), (10, 18), (13, 17) и (16, 16). Нас интересуют только такие, в которые можно попасть из стартовой позиции 6, S. В позицию (7, 19) можно попасть из (6, 19). Она обладает теми же свойствами, что и позиция 10, 18. Из неё нельзя победить, но при любом ходе побеждает противник.
Это позиция П1 (проигрышная за один ход), и она может быть получена из стартовой (6, 19). Следовательно, позиция (6, 19) — выигрышная за два хода.
Из позиции (6, 10) можно попасть в (18, 10), которая аналогична позиции (10, 18), рассмотренной ранее. В другие позиции из набора (1, 21), (4, 20), (7, 19), (10, 18), (13, 17) и (16, 16) нельзя попасть из стартовой. Следовательно, мы нашли все выигрышные позиции за два хода. Это (6, 10) и (6, 19).
Ответ на задание № 20: 10 и 19. Для наглядности изобразим в виде таблицы. Позиции В1 обозначены зелёным цветом, П1 — красным, В2 — тёмно-зелёным.
Для поиска позиций П2 рассмотрим соседние от В2 позиции. Это (6, 9) и (6, 18). Из позиции (6, 9) существует ход в (7, 9) — неопределённую позицию. А вот для (6, 18) все ходы можно рассчитать.
Ходы в (18, 18) и (6, 54) сразу приводят к победе второго игрока, а из позиций (7, 18) и (6, 19) существует ход в (7, 19), что окажется проигрышной позицией (рассмотрели в задании № 20). Таким образом, позиция (6, 18) удовлетворяет всем условиям задания № 21.
Из таблицы мы видим, что такая позиция одна.
Заключение
Мы рассмотрели аналитический подход к решению заданий № 19–21 ЕГЭ по информатике. Аналитический метод показал свою эффективность при решении заданий разных уровней сложности — от простых игр с одной кучей камней до сложных с несколькими кучами и разными типами ходов.
Метод обратной индукции — универсальный инструмент для определения выигрышных и проигрышных позиций. Очень важно понимать концепции «сильного» и «слабого» хода для быстрого определения критических позиций.
Аналитический метод решения служит фундаментом для решения в электронных таблицах или путём программирования.
Рекомендуем решить подборки задач для практики
- задачи с одной кучей
- задачи с двумя кучами