Методика проведения курса по выбору "Элементы теории игр" в классах естественно-математического профиля

№

На доске/проекторе

1

Приветствие.

2

Поднимите руку, кто решил домашнее задание?

Давайте посмотрим еще раз и разберемся вместе.

У меня есть колода из 27 карт. Давайте вживую посмотрим этот трюк.

Демонстрируем действия с видео.

Просим кого-нибудь вытащить карту, назвать число. Вновь демонстрируем трюк.

Кто-нибудь заметил что-нибудь необычное в действиях? Отличались ли они от действий первой демонстрации?

— Да.

Чем?

--Колоды собирались по-разному. Как вы думаете, с чем это связано?

— Системы счисления.

Демонстрация видеофайла.

Какая из них?

-- По основанию 3.

Разбираемся дальше по аналогии с видео.

3

Сообщение домашнего задания.

4

Завершение занятия.

№

Название

Время

1

Организационная часть

~2 мин.

2-3

Разбор домашнего задания

~25 мин.

4

Практическая работа

~20 мин.

5

Сообщение домашнего задания

~5 мин.

6

Завершение занятия

~3 мин.

№

На доске/проекторе

1

Приветствие.

2--3

Кто придумал решение домашней задачи? Давайте вспомним ее:

Царевич Иван сражается с 68--ми--головым змеем Горынычем. За один удар он может отрубить 21, 17 или 1 голову. Взамен

отрастает 0, 14 или 49 голов соответственно. Сможет ли Иван победить змея Горыныча?

Что значит «победить Змея Горыныча»?

-- Отрубит ему все головы.

Для того, чтобы проще, быстрее решит эту

задачу есть прием: составить дерево игры или карту игры. Мы с вами будем называть это именно деревом игры. Запишем: дерево игры

-- это направленный граф без циклов с выделенной вершиной -- корнем.

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

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

Кто--нибудь может привести пример, где именно за счет подобного расчета, подобного знания игрок выигрывает?

— Шахматы.

— Крестики--нолики.

Правильно. А стрелки -- это что тогда, в дереве, если мы вспомним предыдущие занятия?

— Стратегии. Верно.

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

См. рис. занятия

1

после

Разбираем и строим дерево на доске.

В этой игре ходит только Иван. Давайте теперь посмотрим другую игру. С двумя игроками.

4

Два игрока играют в игру: перед ними лежит две кучи камней. Игроки ходят по очереди. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 79. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 79 камня или больше. Для начальной позиции (15, 31) укажите, кто из игроков имеет выигрышную стратегию.

В этой игре два игрока. Как вы думаете, кто выиграет?

(отвечают)

Давайте построим дерево игры и посмотрим кто прав («правы ли мы», если ответ один). Какая тогда выигрышная стратегия второго игрока?

-- Увеличивать наибольшую кучку в два раза.

Правильно. Попробуйте аналогично решить следующую задачу:

Два игрока играют в игру: перед ними лежит две кучи камней. Игроки ходят по очереди. За

См. рис. занятия

2

после

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

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

-- Аукционы.

Проверяем (рис. 3)

на

доске

5

Сообщение домашнего задания

6

Завершение занятия

№

На доске/проекторе

1

Приветствие.

2

Давайте проверим домашнее задание.

1. Два игрока играют в игру: перед ними лежит две кучи камней. Игроки ходят по очереди. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 51. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, что в кучах всего будет 51 камня или больше. Для начальной позиции (23, 3) укажите, кто из игроков имеет выигрышную стратегию. Ответ: второй. Нужно увеличить первую кучу камней в два раза.

2. Два игрока играют в игру: перед ними лежит две кучи камней. Игроки ходят по очереди. За один ход игрок может увеличить

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

Ответ: второй. Нужно увеличить первую кучу камней.

2--3

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

Поднимите руки те, кто с ней справился. Поднимают.

На самом деле это задача решается с конца. Те, кто решили, наверняка это заметили. Давайте разберем ее вместе.

Последним ходит первый игрок, он выиграет тогда, когда значения -- различны, тогда нам подходят варианты:

? (16; 29)

? (22; 37)

? (28; 54)

? (21; 19)

Демонстрируется условие задачи с помощью проектора.

Если используется электронная доска, то лучше каким-нибудь образом выделять названные значения, и

Первый игрок ведь действует разумно и стремится выиграть. Логично, что он постарается попасть на один из этих вариантов. Второму же подходят оставшиеся, но больше всего его устроит позиция (21; 21) или (15; 15), которые получаются, если игрок сначала действует по первой стратегии, а потом второй по второй. Но это единственный вариант, когда второй выигрывает, следовательно, первый постарается его избежать. И значит, на первом ходу он скорее воспользуется второй стратегией, так как также полагает, что второй игрок разумен и не будет ходить себе во вред. И если первый игрок так действует, то вне зависимости от хода второго игрока он выиграет. Единственное, что в таком случае может контролировать второй игрок -- это выигрыш первого. Он может его сделать меньше, чем хотелось бы первому. Давайте наложим дополнительное условие, что выигравший получает то количество монет от второго игрока, какое наибольшее число стоит в скобках при последнем ходе. Тогда первый может получить:

· 54 монеты

· 21 монету

Почему мы говорим о 54 монетах, но не затрагиваем второй вариант в 37 монет?

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

— Потому что мы считаем, что первый игрок действует разумно и сделает наиболее выгодный шаг, а из 54--х и 37--ми монет 54

— больше.

Верное. Однако второй в своем стремлении направит перового по другому пути и предоставит ему два варианта:

· выиграть и забрать 21 монету от него;

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

Ответ: выиграет первый игрок, если воспользуется сначала второй стратегией, а потом первой. Стратегия второго игрока в таком случае -- вторая.

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

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

4

Давайте решим по аналогии следующую задачу (рис. 5). В скобках соответственно указаны выигрыши игроков. Первое число --

Условие демонстрируется с

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

Решают с подсказками и, возможно, наводящими вопросами:

· Кто ходил последним?

· Какая из позиций выгодна для игрока, который ходил последним?

· Как влияет ход игрока, чей ход был предпоследним?

А теперь решите самостоятельно игру (рис. 7). Найдите равновесие в игре и стратегии игроков.

помощью проектора

Условие демонстрируется с помощью проектора

5

Сообщение домашнего задания.

6

Завершение занятия