Тема — Знакомство с теорией игр
Цели и задачи урока:
- Научиться анализировать множество вариантов развития ситуации.
- Освоить понятия: стратегия игры, выигрышная стратегия, дерево игры.
- Овладеть методом анализа дерева игры.
- Научится находить вариант хода, приводящий к выигрышу.
На уроке вы научитесь:
- Строить дерево игры.
- Находить выигрышные стратегии.
- Решать 26 задачу ЕГЭ по информатике.
Любая игра, такая как футбол, шахматы, «крестики-нолики» и другие, всегда определена начальными позициями, результатом и ходами, которые может сделать игрок в этой игре.
При этом игра в футбол будет сильно отличаться от игры в шахматы. Так как в играх типа теннис, баскетбол может вмешиваться третьи стороны: ветер, солнце и т. д. и не всегда ясно к чему приведет тот или иной ход игрока. Если же игрок точно знает, к какой позиции приведет его выбранный ход, то она называется игрой с полной информацией, к таким играм мы отнесем шахматы, шашки, «крестики-нолики» и много других интересных игр, в которых будет участвовать только игроки.
Давайте начнем с простой игры. Имеется горка из n монет. Маша и Петя должны каждым своим ходом делить одну горку на две таким образом, чтобы в каждой из них было не менее 2. При этом если игрок не сможет этого сделать, то он проигрывает.
Для примера, рассмотрим задачу, когда n=10. Тогда Маша может сходить (2,8), (3,7), (4,6) и (5,5). Запишем это в виде графа. (Такой граф мы будем называть деревом игры). Продолжим рисовать граф. Его анализ покажет, что Маше не выгодно ходить первым ходом (2,8) или (4,6), что может привести к позиции (2,2,2,4), которая приведет ее к проигрышу. Поэтому если она хочет выиграть своим первым ходом она сходит (5,5) или (3,7), что гарантированно приведет ее к победе независимо от ходов Пети. Это и будет ее выигрышной стратегией.
Итак, выигрышная стратегия — это такое правило совершения ходов, при соблюдении которого игрок добьется выигрыша при любых ответных ходах противника.
Для построения дерева игры необходимо перебрать все возможные ходы игроков, что может потребовать огромного количества времени. Так, если игра состоит в выборе одного из 2 шагов и будет сделано n ходов, то потребуется рассмотреть 2n последовательностей. Например, всего лишь 10 ходов приведет к дереву из 1024 листьев.
Давайте построим дерево игры для задачи, рассмотренной ранее, но возьмем количество монет — 9.
Ясно, что, если два хода игрока приводят к одному и тому же результату, рассматривать их как разные не имеет смысла.
Вывод: Анализировать надо не последовательность ходов, а позиции, приводящие к выигрышу
Рассмотрим следующую игру:
На поле 10×10 находится фишка. За один ход ее можно переместить на любое количество клеток вправо или вниз, либо по диагонали вправо и вниз. Два игрока по очереди делают ходы. Проигрывает тот, кто не сможет сделать ход. Ясно, что проигрышная позиция здесь только одна — это правый нижний угол.
Рис. 1
Получается, что если за один ход можно попасть в эту клетку, то ты гарантированно придешь к победе. Поставим «+» во все такие клетки (рис.1).
Далее проставим знаком «–» клетки из которых нельзя попасть в «–» за 1 ход, но любой ход приводит в клетку «+» (рис.2).
Рис. 2
Следуя этим рассуждениям, заполним таблицу (рис.3)
Рис. 3
Рассматривая данную игру, то можно прийти к выводу, что стратегией мы будем называть некоторый алгоритм планирования.
Для каждой стратегии существует некоторый гарантированный результат игры — это минимальный результат среди всех результатов, которые получаются, если рассматривать все варианты игры противника при этой стратегии. Дж. фон Нейман предложил использовать такую стратегию, которая обеспечивает наибольший гарантированный результат.
Однако таких вариантов очень много и справиться с перебором всех не может ни только человек, но и компьютер. При этом человек «интуитивно» может отбрасывать некоторые из неперспективных вариантов основываясь на не совсем логичных обоснованиях. Такие обоснования называются эвристиками.
Эвристика — это правило, сокращающее число потенциальных вариантов перебора.
Графы как информационные модели находят широкое применение во многих сферах нашей жизни. С их помощью можно планировать оптимальные транспортные маршруты, кратчайшие объездные пути, расположение торговых точек и других объектов.
Путь между вершинами А и В графа считается кратчайшим, если эти вершины соединены минимальным числом рёбер (в случае, если граф не является взвешенным) или если сумма весов рёбер, соединяющих эти вершины, минимальна (для взвешенного графа).
Для определения кратчайшего пути между вершинами графа используются алгоритм построения дерева решений, алгоритм Дейкстры, метод динамического программирования и другие алгоритмы.
Важную роль в решении многих задач экономики, социологии, политологии, биологии, искусственного интеллекта и ряда других областей, где необходимо изучение поведения человека и животных в различных ситуациях, играет теория игр.
Игра, выступающая в качестве математической модели некоторой ситуации, характеризуется такими признаками, как:
1) присутствие нескольких игроков;
2) неопределённость поведения игроков, связанная с имеющимися у каждого из них несколькими вариантами действий;
3) различие (несовпадение) интересов игроков;
4) взаимосвязанность поведения игроков (результат, получаемый каждым из них, зависит от поведения всех игроков);
5) наличие правил поведения, известных всем игрокам.
Игра может быть представлена в виде дерева, каждая вершина которого соответствует ситуации выбора игроком своей стратегии.
В играх с полной информацией участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры.
Выигрышная стратегия — это правило, следуя которому игрок выигрывает независимо от того, как играет противник.
Самостоятельная работа по теме «ДЕРЕВО ИГРЫ»
1 . Петя и Вася играют в «Камешки». В начальной позиции у игроков есть кучка из 7 камешков; за один ход игрок может взять 1 или 2 камешка. Выигрывает тот, кто своим ходом забирает последний камешек (последние камешки). Постройте дерево игры по этим правилам.
2 . Петя и Вася играют в «Камешки». В начальной позиции у игроков есть кучка из 700 камешков; за один ход игрок может взять 1 или 2 камешка. Выигрывает тот, кто своим ходом забирает последний камешек (последние камешки).
Проанализируйте начало числовой линейки и выясните, какие позиции являются выигрышными, а какие проигрышными в этой игре.
Для кого из игроков существует выигрышная стратегия в этой игре? Опишите выигрышную стратегию для этого игрока.
3 . Петя и Ваня играют в «Цифры». Первоначально выбирается и записывается одна десятичная цифра N, О S лт S 8. Игроки ходят по очереди; начинает игру Петя. За один ход игрок может дописать к уже имеющейся строке цифр одну или две следующие по порядку значений цифры. Победителем считается игрок, написавший цифру 9.
Считается, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока значит описать, какой ход он должен сделать в любой ситуации, с которой он может столкнуться при различной игре противника.
- Укажите все значения N, при которых Петя может выиграть за один ход. Обоснуйте, что найдены все нужные значения N, и укажите выигрывающий ход для каждого указанного значения N.
- Укажите такое значение N, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
З) Укажите такие значения N, при которых у Пети есть выигрышная стратегия, причём:
- Петя не может выиграть за один ход;
- Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Для каждого указанного значения лт опишите выигрышную стратегию Пети.
4) Укажите значения N, при которых:
- Ваня не может выиграть за один ход;
- Ваня может выиграть своим вторым ходом независимо от того, как будет ходить Петя.
Для указанных значений лт опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани. На рёбрах дерева укажите, кто делает ход, в узлах последовательность цифр.
Комментарии: