Дискретные игры двух игроков с полной информацией выигрышные стратегии конспект

Обновлено: 01.07.2024

Оборудование: ПК, интерактивная доска, проектор.

Дидактическое обеспечение урока: видеоматериал (объяснение темы), работы старшеклассников (мотивация учащихся).

Особенности изложения содержания урока: Данная методическая разработка актуальна для учителей информатики, работающих в 7-х классах по УМК Л.Л.Босовой в соответствии с ФГОС.

Ход урока

1. Организационный момент, объявление темы и цели урока.

2. Актуализация знаний и проверка усвоения изученного материала.

3. Первичное восприятие и усвоение нового теоретического учебного материала.

Под игрой будем понимать некоторый процесс, в котором участвуют два и более игроков, ведущих борьбу за реализацию своих интересов. Мы рассмотрим игры с полной информацией, в них на каждом шаге ход делает один игрок, имеющий полную информацию о текущем состоянии всех происходящих действий и общих правилах игры. Нашей задачей является поиск наилучшего способа игры или выигрышной стратегии [3].
Все позиции в играх делятся на выигрышные и проигрышные.

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

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

Выигрышные и проигрышные позиции можно охарактеризовать так:

– позиция, из которой все возможные ходы ведут в выигрышные позиции – проигрышная(п);

– позиция, из которой хотя бы один из возможных ходов ведет в проигрышную позицию – выигрышная(в), при этом стратегия игрока состоит в том, чтобы перевести игру в эту проигрышную (для соперника) позицию [5].

Задача 1 [3, с.98]. Использую файл Приложение1.swf

На столе лежат 25 спичек. Играют двое. Играющие по очереди могут взять от одной до четырех спичек. Выигрывает тот, кто берет последние(юю) спички(у). Для какого игрока существует выигрышная стратегия?

Решение: Победит тот игрок, которому достанутся последние 1-4 спички. Будем считать эти позиции выигрышными (в). Если же игроку достается 5 спичек, то любым своим ходом он обеспечивает победу сопернику, считаем такую позицию проигрышной (п):

Давайте начнем с простой игры. Имеется горка из 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 ходов, то потребуется рассмотреть 2 n последовательностей. Например, всего лишь 10 ходов приведет к дереву из 1024 листьев.

Давайте построим дерево игры для задачи, рассмотренной ранее, но возьмем количество монет — 9.

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

Вывод: Анализировать надо не последовательность ходов, а позиции, приводящие к выигрышу

Рассмотрим следующую игру:

На поле 10×10 находится фишка. За один ход ее можно переместить на любое количество клеток вправо или вниз, либо по диагонали вправо и вниз. Два игрока по очереди делают ходы. Проигрывает тот, кто не сможет сделать ход. Ясно, что проигрышная позиция здесь только одна — это правый нижний угол.

Следуя этим рассуждениям, заполним таблицу (рис.3)

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

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

Эвристика — это правило, сокращающее число потенциальных вариантов перебора.

позиционная игра определена, если задано 6 элементов игры:

1) связный ориентированный граф-дерево игры с выделенной вершиной А, являющийся начальной позицией игры. Каждая вершина графа называется позицией игры и соответствует ее определенному состоянию.

Каждое ребро графа называется альтернативой в развитии игры и соответствует определенному ходу в игре.

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

Реализацией или партией игры будем называть любую цепь AX, проходящую по ребрам и вершинам графа-дерева игры и соединяющую начальную позицию игры A с любой из конечных позиций X.

2) вектор – функция выигрыша

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

3) разбиение множества S всех вершин графа, кроме конечных, на три подмножества очередности хода

– множество вершин граф-дерева игры, в которых производится случайный ход;

– множество вершин графа, в которых ход делает первый игрок;

– множество вершин графа, в которых ход делает второй игрок;

– множество конечных вершин графа, в которых вместо хода игроки получают свои выигрыши.

Подмножества , взаимно не пересекаются.

4) для каждой вершины задано вероятностное распределение:

на множестве ребер-альтернатив , исходящих из , такое, что:

– количество ребер , соединяющих вершину с непосредственно следующими за вершинами графа:

Т.о. четвертый элемент игры определяет в вероятностном смысле развитие игры, если реализация игры попала в вершину .

Это означает, что реализация игры может из позиции пойти по любому из ребер , , причем вероятность случайного события, состоящая в том, что реализация игры пойдет по ребру равна

5) разбиение каждого из множеств очередности хода первого и второго игрока на области информированности игроков (

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

Основные свойства области информированности:

1. все позиции из одной и той же области информированности имеют одинаковое количество исходящих ребер альтернатив.

2. никакая позиция игры в графе не может следовать непосредственно за другой позицией из той же области информированности.

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

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

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

Лекция 8. Примеры дискретных позиционных игр

I. Игра в шахматы.

1. Множество вершин графа-дерева игры является множеством всех возможных позиций на доске.

Множество ребер-альтернатив, исходящих из графа-дерева игры – множество возможных ходов того игрока, чей ход в данной позиции

Начальная позиция – начальная позиция шахматной игры с ходом белых.

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

2. Вектор-функцией выигрыша является для всех позиций мата черным пара чисел (1,0), для всех позиций мата белым – (0,1) и для всех ничейных – (1/2,1/2).

3. Игра без случайных ходов (пустое множество вершин).

В множество включаются все позиции с ходом белых, в – с ходом черных.

4. Отсутствует, т.к. нет случайных ходов.

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

6. Вместо нумерации альтернатив для каждой позиции можно воспользоваться шахматной нотацией для записи ходов в партии.

Социальное обеспечение и социальная защита в РФ: Понятие социального обеспечения тесно увязывается с понятием .

Конфликтные ситуации в медицинской практике: Наиболее ярким примером конфликта врача и пациента является.

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Выигрышная стратегия.

Цель урока: сформировать навыки решения задач имеющих выигрышную стратегию.

Образовательные.

Освоить понятия: стратегия игры, дерево игры, выигрышная и проигрышная позиция.

Овладеть методом построения таблицы позиций, дерева игры.

Приводить доказательство того, что стратегия игры - правильная.

Развивающие.

Развивать умения и навыки анализа и построения дерева игры, таблицы позиций.

Способствовать интеграции знаний учащихся, полученных при изучении информатики, математики.

Развивать сообразительность, наблюдательность, быстроту в принятии решений.

Воспитательные.

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

Активировать творческие способности учащихся.

Эффективно использовать разные информационные ресурсы.

Ученик должен знать:

Метод построения таблицы позиций, дерева игры.

Ученик должен уметь :

Строить таблицы позиций, полное дерево игры.

Приводить доказательство того, что приведенная стратегия игры – правильная.

Уметь определять выигрывающего игрока.

Методы обучения: частично-поисковый, объяснительно-иллюстративный, репродуктивный.

Целеполагание и мотивация.

Объяснение нового материала.

Закрепление учебного материала.

Подведение итогов урока.

Формы организации познавательной деятельности:

Программное обеспечение ПК: операционная система Windows 7, MS Power Point.

Средства обучения: мультимедийный проектор, компьютер, MS Power Point 7; презентация “Выигрышная стратегия”, раздаточный материал с заданиями (Приложения1,2,3).

1. Организационный момент (1 мин.)

2. Актуализация знаний (3 мин.)

На предыдущих уроках мы изучали вопросы, связанные с различными линейными алгоритмами.

Разобрали такие понятия как:

этапы решения задачи на компьютере,

дерево возможных вариантов.

Дайте, пожалуйста, им определения.

Как вы усвоили эту тему, я пойму проверив домашнее задание. В конце урока не забудьте сдать тетради.

3. Целеполагание и мотивация (3 мин.)

А любите ли вы играть?

Тогда мы продолжим изучение темы Теория игр .

Мы не будем сегодня рассматривать все виды игр

Нас будут интересовать только логические игры определенного вида

Попробуем сформулировать цель урока

Определять выигрышную стратегию.

3. Объяснение нового материала (10 мин.)

Возьмите карту урока и выполните 1 задание, отметив буквами

В чем заключается выигрышная стратегия при игре в крестики нолики?

Занять выигрышные позиции: центр и углы

Используя Дерево возможных вариантов, попробуем решить следующую задачу

Строим полное дерево игры поэтапно в карте урока

В неполном дереве:

указываются все возможные ходы того, кто проигрывает;

достаточно одного хода того, кто выигрывает.

Нужно оставлять сопернику N = 3  k + 1 камней.

4. Физкультминутка

А теперь закрыли глаза, считаем до 3. Открываем глаза и смотрим вдаль, считаем до 5. И еще раз то же самое.

Теперь крепко зажмурились, считаем до 3, открываем глаза.

Следим за ручкой в моей руке. Рисую фигуры: круг, квадрат, зигзаг.

5. Закрепление учебного материала (10 мин.)

Правила игры – раздел математики изучающий конфликтные ситуации на основе их математических моделей.

Теория игры – система условий регламентирующих возможные варианты действий обоих сторон.

Партия – каждый вариант реализации игры определенным образом.

Ход – выбор и реализация одного из вариантов поведения.

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

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

Шоколадка представляет собой прямоугольник, разделённый углублениями на квадратики. Двое по очереди разламывают её на части по углублениям: за один ход можно разломить любой из кусков (больший одного квадратика) на два. Кто выигрывает при правильной игре? (У кого из игроков есть выигрышная стратегия?)

Фишка стоит в углу шахматной доски размером 8 на 8. Двое игроков по очереди передвигают ее на соседнее поле. Поля соседние, если у них есть общая сторона. Второй раз ходить на поле, где уже побывала фишка нельзя. Тот, кому некуда ходить, проигрывает. Кто победит при правильной игре?

В коробке 24 спички, за один ход можно взять любое количество спичек от одной до пяти. Проигрывает тот, кто не может сделать ход. Кто их игроков выиграет при правильной игре?

Работают ученики – консультанты

6. Подведение итогов урока (5 мин.)

Подводя итоги хочу услышать ваше мнение:

что нового вы сегодня узнали?

могут ли пригодиться в жизни вам эти знания?

А еще я хочу добавить: сегодня мы заложили основы для умений ь решать задание 26 ЕГЭ по информатике, которые мы научимся решать на следующем уроке.

Кроме этого, не лишним будет сказать, что умение правильно прогнозировать ситуацию пригодится вам в развитии личностного и карьерного роста, так как у понятия слова стратегия есть и более глубокий смысл, а именно:

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

7. Выставление оценок (3 мин.)

Помощники помогут мне подвести итоги и выставить оценки.
Результат вы увидите в электронном журнале

Домашнее задание (1 мин.)

1.Выучить теорию из карты урока.

2.Выполнить задания для домашней работы из файлов.

При наличии времени Викторина Kahoot !

Приложение 1

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

Изначально в куче 18 камней.

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

Изначально в куче 8 камней.

Приложение 2

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 20. Если при этом в куче оказалось не более 30 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник. Например, если в куче было 17 камней и Петя удвоит количество камней в куче, то игра закончится, и победителем будет Ваня. В начальный момент в куче было S камней, 1 ≤ S ≤ 19.

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

Выполните следующие задания:

1. а) При каких значениях числа S Петя может выиграть в один ход?

Укажите все такие значения и соответствующие ходы Пети.

б) У кого из игроков есть выигрышная стратегия при S = 18, 17, 16?

Опишите выигрышные стратегии для этих случаев.

2. У кого из игроков есть выигрышная стратегия при S = 9, 8?

Опишите соответствующие выигрышные стратегии.

3. У кого из игроков есть выигрышная стратегия при S = 7?

Постройте дерево всех партий, возможных при этой выигрышной стратегии в виде рисунка (дерева). На ребрах дерева указывайте, кто делает ход; в узлах – количество камней в позиции.

Читайте также: