Для всех учителей из 37 347 образовательных учреждений по всей стране

Скидка до 75% на все 778 курсов

Выбрать курс
Получите деньги за публикацию своих
разработок в библиотеке «Инфоурок»
Добавить авторскую разработку
и получить бесплатное свидетельство о размещении материала на сайте infourok.ru
Инфоурок Информатика Другие методич. материалыМетодические материалы к теме Решение игровых задач(Задача 26 Подготовка к ЕГЭ)

Методические материалы к теме Решение игровых задач(Задача 26 Подготовка к ЕГЭ)

библиотека
материалов

Задача №26. Построение дерева игры. Поиск выигрышной стратегии

Автор материалов – Герасимов Н.А.

  1. Формализация игровой ситуации

  2. Определение выигрышной стратегии для игры двух игроков.

  3. Определение выигрышной стратегии для произвольной ситуации

  4. Вопросы для самопроверки

Литература и источники:



  1. Формализация игровой ситуации

Под «игрой» будем понимать многоходовый процесс, в котором участвуют 2 и более игроков, каждый из которых на каждом шаге игры может сделать выбор (ход), изменяющий игровую ситуацию. Игроками выбор делается из конечной альтернативы вариантов действий. Такие игры называют играми «с полной информацией»

Примерами игр «с полной информацией» являются игры «крестики-нолики», шашки, шахматы и другие. Начинается игра с определенной позиции (или начальной ситуации S0), которая как правило, создает равные условия для каждого игрока.

Игра развивается по шагам. На каждом шаге игры каждый игрок имеет возможность выбрать альтернативу из конечного набора действий ( множество альтернатив D={a,b, …} на каждом шаге игры постоянно).

После сделанных ходов всеми игроками в игре возникает новая ситуация (Si), которая оценивается игроками. Каждый игрок оценивает свою позицию, относительно цели игры и принимает решение о качестве ситуации и какое действие выбрать на следующем шаге игры..

Конечной ситуацией (Sn) в игре является та, в которой один из игроков достигает конечной цели игры первым.

Последовательность ходов (выборов) игроком, приводящих его из начальной ситуации (S0) в конечную (Sn) называется – траекторией игрока (или его стратегией).

Очевидно, что у каждого игрока возможны различные варианты стратегий. Одни стратегии приводят игрока к выигрышу (выигрышная стратегия), другие - нет.

В простых играх, у которых исходная ситуация описывается малым количеством вариаций, количество игроков невелико (2 или 3 игрока), и количество альтернатив действий так же невелик - все множество стратегий игроков можно отобразить графом (обычно графом типа «дерево»).

Пример простой игры можно представить так. Имеется исходная ситуация: ящик, в котором 2 яблока. Имеются два игрока, которые могут добавить в этот ящик яблоки двумя способами: способ а) +2 яблока, или способ б) удвоить количество яблок в ящике. Выигрывает тот, кто первым получит заданное количество яблок в ящике (например 7 яблок).

Граф, отображающий возможные варианты количества яблок в корзине на каждом шаге игры показан ниже.

hello_html_m7c9193c6.png

Рис.1. Вариант графа, отражающий все ситуации в простой игре двух игроков

Анализ графа. Из графа на Рис.1. видно, что какое бы действие не принял первый игрок (+2 или х2), второй игрок всегда может закончить игру на 2-м шаге. В этом случае можно говорить, что второй игрок имеет очевидную выигрышную стратегию.

Но если 2-й игрок упустит такую возможность, то игра закончится на 3-м шаге победой 1-го игрока.

Таким образом, стратегия на графе отображается последовательностью дуг графа (маршрутом на графе), которая приводит игрока из начальной ситуации в конечную.

Если у игрока имеется четкая стратегия, которая однозначно приводит его из некоторой позиции (Si) в к выигрышу, то говорят, что игрок «имеет выигрышную позицию» в позиции (Si).



  1. Определение выигрышной стратегии для игры двух игроков.

Существует класс простых игр, в которых выигрышную позицию имеет игрок, который начинает игру первый. И если он выберет правильное решение на первом ходу, то он может получить гарантированный выигрыш не зависимо от выборов других игроков.

Проигрышная позиция – это такая позиция, при которой игрок, делающий первый ход, проигрывает независимо от выбора очередного хода.

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

Рассмотрим варианты задач, в которых имеется выигрышная стратегия для первого игрока

Пример 1.

Описание игры. Перед игроками стоят две емкости, в которых лежат камни. В первой емкости находятся 3 камня, а во второй – 6 . У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то емкости, или добавляет 2 камня в какую-то емкость. Выигрывает игрок, после хода которого общее число камней в двухемкостях становится не менее 24 камней.

Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Докажите, что у первого игрока имеется или отсутствует выигрышная стратегия? Ответ обоснуйте.

Решение:

Для доказательства построим граф, охватывающий все стратегии как 1-го игрока, так и 2-го.

Начальная ситуация игры: в емкостях лежит (3 и 6) камней или всего 9. Ситуация S0.

1-й Шаг игры. Ход 1-го игрока. Он может перевести ситуацию S0 в 4-ре новых ситуации:

S11= (3+2,6)= (5,6); S12= (3х2,6)= (6,6); S13= (3,6+2)= (3,8); S14= (3,6х2)= (5,12);

2-й Шаг игры. Ход 2-го игрока. Он может перевести любую из 4-х ситуаций S11, S12, S13 и S14, в 4-ре новых ситуации.

Например, рассмотрим изменение ситуации S11:

S111=(5+2,6)=(7,6); S112=(5х2,6)=(10,6); S113=(5,6+2)=(5,8); S114=(5,6х2)=(5,12);

Анализ: на один из вариантов не дает окончания игры, т.к. во всех ситуациях сумма камней меньше 24.

И так далее, можно рассмотреть все возможные исходы из других ситуаций и принять правильную стратегию для следующего хода.

3-й Шаг игры. Снова ход 1-го игрока. Он уже исходит из сложившейся конкретной ситуации.

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

hello_html_m748b7e0e.png

Рис.1. Граф отображающий все множество стратегий в игре Примера 1.
(красные вершины – отражают выигрыш игрока)

Из анализа Графа стратегий видно, что только одна стратегия гарантирует 1-му игроку выигрыш вне зависимости ходов 2-го игрока. Это стратегия S11= (3+2,6)= (5,6), которая переводит игру из ситуации S0(3,6) в ситуацию S11= (5,6). (синий круг на рис.1).

Не зависимо от выбора 2-го игрока у 1-го имеется однозначная возможность достичь выигрышной ситуации ( «сумма камней больше или равна 24») первым.

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

Таким образом 1-й игрок на первом ходу обязательно должен добавить 2 камня к первой емкости (т.е. 3+2=5).

Ответ: Выигрывает первый игрок. Своим первым ходом он должен добавить 2 камня в первую кучу.



  1. Определение выигрышной стратегии для произвольной ситуации

Пример 2.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (6, 34), (7, 33), (9, 32) выигрышная стратегия есть у Пети. Чтобы выиграть, ему достаточно удвоить количество камней во второй куче.

Задание 1. Для каждой из начальных позиций (6, 33), (8, 32) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2. Для каждой из начальных позиций (6, 32), (7, 32), (8, 31) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3. Для начальной позиции (7, 31) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной Вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

 

Решение:

Задание 1. В начальных позициях (6, 33), (8, 32) выигрышная стратегия есть у Вани. При начальной позиции (6, 33) после первого хода Пети может получиться одна из следующих четырёх позиций: (7, 33), (12, 33), (6, 34), (6, 66). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Для позиции (8, 32) после первого хода Пети может получиться одна из следующих четырёх позиций: (9, 32), (16, 32), (8, 33), (8, 64). Каждая из этих позиций содержит менее 73 камней. При этом из любой из этих позиций Ваня может получить позицию, содержащую не менее 73 камней, удвоив количество камней во второй куче. Таким образом, Ваня при любом ходе Пети выигрывает своим первым ходом.

Задание 2. В начальных позициях (6, 32), (7, 32) и (8, 31) выигрышная стратегия есть у Пети. При начальной позиции (6, 32) он должен первым ходом получить позицию (6, 33), из начальных позиций (7, 32) и (8, 31) Петя после первого хода должен получить позицию (8, 32). Позиции (6, 33) и (8, 32) рассмотрены при разборе задания 1. В этих позициях выигрышная стратегия есть у игрока, который будет ходить вторым (теперь это Петя). Эта стратегия описана при разборе задания 1. Таким образом, Петя при любой игре Вани выигрывает своим вторым ходом.

Задание 3. В начальной позиции (7, 31) выигрышная стратегия есть у Вани. После первого хода Пети может возникнуть одна из четырёх позиций: (8, 31), (7, 32), (14, 31) и (7, 62). В позициях (14, 31) и (7, 62) Ваня может выиграть одним ходом, удвоив количество камней во второй куче. Позиции (8, 31) и (7, 32) были рассмотрены при разборе задания 2. В этих позициях у игрока, который должен сделать ход (теперь это Ваня), есть выигрышная стратегия. Эта стратегия описана при разборе задания 2. Таким образом, в зависимости от игры Пети Ваня выигрывает на первом или втором ходу.

 hello_html_m340f3ac9.png

Ответ:

Задание 1. Ваня выигрывает своим первым ходом.

Задание 2. Петя выигрывает своим вторым ходом.

Задание 3. Ваня выигрывает первым или вторым ходом.

Определение начальной позиции, обеспечивающей выигрыш того или иного игрока

Пример 3.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

 Игра завершается в тот момент, когда количество камней в куче становится не менее 48. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 48 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 47.

 

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

 

  1. Вопросы для самопроверки

Выполните следующие задания. Во всех случаях обосновывайте свой ответ.

1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающий ход для каждого указанного значения S.

б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.

 

2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть за один ход и (б) Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети.

3. Укажите значение S, при котором:

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

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

 

Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.

 

Решение:

1. а) Петя может выиграть, если 16, ..., 47. Во всех этих случаях достаточно утроить количество камней. При меньших значениях S за один ход нельзя получить кучу, в которой больше 47 камней.

б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 15 камней. Тогда после первого хода Петя в куче будет 16 или 45 камней. В обоих случаях Ваня утраивает количество камней и выигрывает в один ход.

2. Возможные значения S: 5 и 14. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 15 камней: в первом случае утроением, во втором добавлением одного камня. Эта позиция разобрана в п. 16. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.

3. Возможное значение S: 13. После первого хода Пети в куче будет 14 или 39 камней. Если в куче станет 39 камней. Ваня утроит количество камней н выиграет первым ходом. Ситуация, когда в куче 14 камней, уже разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.

На рисунке изображено дерево игры. Выигрышные позиции подчеркнуты.

hello_html_m36914c56.png

Ответ:

1.   а) S от16 до 47

б) S = 15

2. S = 5 и S = 14

3. S = 13



  1. Вопросы для самопроверки

  1. Определите формально правила игры (приведите пример игры по правилам)

  2. Как с помощью графа можно отобразить изменения в состоянии игровой ситуации (приведите пример графа простой игры двух игроков)

  3. Что отображает путь на графе от исходной ситуации (S0) до конечной ситуации (Sn) для игрока.

  4. Как можно рассчитать количество выигрышных ситуаций для игрока (какой метод вам удобнее графом или таблицей)



Литература и источники:

  1. Станкевич А. Игры на графах - https://ejudge.lksh.ru/archive/2014/08/A/games.pdf

  2. Построение графической схемы алгоритма - https://megapredmet.ru/1-3657.html

  3. Основные комбинаторные ситуации - https://cyberpedia.su/16x3e61.html

  4. https://ege-study.ru/ru/ege/materialy/informatika/zadanie-26/

Курс повышения квалификации
Курс профессиональной переподготовки
Учитель математики и информатики
Найдите материал к любому уроку,
указав свой предмет (категорию), класс, учебник и тему:
также Вы можете выбрать тип материала:
Краткое описание документа:

Методический материал для подготовки к ЕГЭ учеников 11 класса. В материале рассматриваются вопросы связанные с построением графов описания игровых ситуацийв играх с конечным количеством игроков.

Под «игрой» здесь понимается многоходовый процесс, в котором участвуют 2 и более игроков, каждый из которых на каждом шаге игры может сделать выбор (ход), изменяющий игровую ситуацию. Игроками выбор делается из конечной альтернативы вариантов действий. Такие игры называют играми «с полной информацией»

Проверен экспертом
Общая информация
Учебник: «Информатика (базовый и углублённый уровень)», Гейн А.Г., Сенокосов А.И.

Номер материала: ДБ-460868

Вам будут интересны эти курсы:

Курс повышения квалификации «Методика преподавания информатики в начальных классах»
Курс повышения квалификации «Внедрение системы компьютерной математики в процесс обучения математике в старших классах в рамках реализации ФГОС»
Курс повышения квалификации «Организация работы по формированию медиаграмотности и повышению уровня информационных компетенций всех участников образовательного процесса»
Курс повышения квалификации «Использование компьютерных технологий в процессе обучения в условиях реализации ФГОС»
Курс повышения квалификации «Специфика преподавания информатики в начальных классах с учетом ФГОС НОО»
Курс повышения квалификации «Применение MS Word, Excel в финансовых расчетах»
Курс повышения квалификации «Введение в программирование на языке С (СИ)»
Курс профессиональной переподготовки «Математика и информатика: теория и методика преподавания в образовательной организации»

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.