Слайд 1
Стратегия игры или теория игр на уроках информатики и в заданиях ЕГЭ 12.10.2019
Слайд 2
Какие бывают игры? Вы любите играть? А какие бывают игры? Чем отличаются и чем бывают похожи игры?
Слайд 3
В ряде задач задается один и тот же вопрос: кто из двух игроков выиграет при правильной игре? Слова «правильная игра» означают, что если у кого-то из игроков есть стратегия , позволяющая выигрывать при любых ходах другого игрока, и он не делает «глупых» ходов, а стремится выиграть и следует своей выигрышной стратегии. В каждой задаче необходимо придумать такую стратегию для одного из игроков. Стратегия игры
Слайд 4
«Кто первым назовет число 100 ?» В игре «Кто первым назовет число 100» участвуют двое. Один называет любое число от 1 до 9 включительно. Другой прибавляет к названному числу любое число от 1 до 9 и называет сумму. К этой сумме первый снова добавляет любое число от 1 до 9 и называет новую сумму. Выигрывает тот, кто назовет число 100. Кто выиграет при правильной игре?
Слайд 5
Выигрышная стратегия Многие простейшие игры имеют определенную закономерность и секрет выигрыша (выигрышную стратегию). В таких играх выигрышная стратегия зависит: от правил (условий) игры; от общего количества предметов, предложенных в игре; от выбора игроком первого или второго хода. Два карандаша по очереди закрашивают нарисованные ступеньки. За один ход можно закрасить не более двух ступенек. Выигрывает тот, кто закрасит последнюю ступеньку. Игра «Не больше двух предметов»
Слайд 6
Первая игра Давайте ответим на вопросы: Кто начинает ходить? Кто выигрывает? Если первый закрашивает один предмет, то второй … Если первый закрашивает два предмета, то второй..? Вторая игра Третья игра 5. Почему в третьей игре начинает желтый и он же выигрывает? Что изменилось? Игра «Не больше двух…»
Слайд 7
Правила (секреты) выигрышной стратегии Правило 1. Перед началом игры раздели все предметы на группы ОТ КОНЦА К НАЧАЛУ . Кол-во предметов в группе определяется условиями (не больше 2, тогда группы по 3, т.е. ( n +1)). Самая первая группа может оказаться неполной – эти предметы мы называем «лишними». Правило 2. Если есть «лишние» предметы, то выбери 1-ый ход и закрась «лишние» предметы. Если нет «лишних» предметов – то выбери второй ход. Правило 3. Дополняй ход другого игрока до ( n +1) предмета, тогда в последней группе самый последний предмет будет ваш.
Слайд 8
Выигрышные и проигрышные позиции ходят нолики а) × × × б) × × × в) × × × г) × × × д) × × × е) × × ж) × × × з) × ×
Слайд 9
Имеются 1 куч а камней. Двое играющих берут по очереди камни. Разрешается взять один камень или два камня из кучи . Выигрывает взявший последни й кам е н ь (последние камни) . При каком числе камней в куч е выиграет начинающий? «Куча камней»
Слайд 10
Дерево перебора вариантов Рассмотрим случай, если у нас 4 камня в куче 4 П: В: П: В: 0 -1 0 -1 0 -2 1 -1 0 -1 0 1 -1 -2 -2 2 1 -1 Первый Второй 3 -1 -2 2 Какие выигрышные? ? 2 2 1 1 1 3 4 Нужно оставлять сопернику N = 2 k + 1 камней. Начинающий выиграет, если в куче четное число камней.
Слайд 11
Задача 26 ЕГЭ Два игрока , Петя и Ваня , играют в следующую игру . Перед игроками лежит куча камней . Игроки ходят по очереди , первый ход делает Петя . За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза . У каждого игрока , чтобы делать ходы , есть неограниченное количество камней . Игра завершается в тот момент , когда количество камней в куче становится не менее 48. Победителем счит а ется игрок , сделавший последний ход , то есть первым получивший кучу , в которой будет 48 или больше камней . В начальный момент в куче было S камней , 1 ≤ S ≤ 47. 1. Укажите все такие значения числа S, при которых Петя может выиграть в один ход . Петя может выиграть , если S= 16, …, 47. 4 3 + 1 *3 2 16 47 48
Слайд 12
2. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя . За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Победителем счит а ется игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 48 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 47. 4 3 *3 +1 2 16 45 15 48 135 *3 *3 П В
Слайд 13
Спасибо за внимание!
Игровые модели
На практике часто приходится сталкиваться с задачами, в которых необходимо принимать решения в условиях неопределенности, т.е. возникают ситуации, в которых две (или более) стороны преследуют различные цели, а результаты любого действия каждой из сторон зависят от мероприятий партнера.
Такие ситуации, возникающие при игре в шахматы, шашки, домино и т.д., относятся к конфликтным: результат каждого хода игрока зависит от ответного хода противника, цель игры — выигрыш одного из партнеров.
Для грамотного решения задач с конфликтными ситуациями необходимы научно обоснованные методы. Такие методы разработаны, математической теорией конфликтных ситуаций, которая носит название теория игр .
Основные понятия:
- 1. Игра – математическая модель конфликтной ситуации
- 2. Игроки – стороны, участвующие в конфликте
- 3. Выигрыш – исход конфликта
Для каждой формализованной игры вводятся правила, т.е. система условий, определяющая:
- 1. варианты действий игроков;
- 2. объем информации каждого игрока о поведении партнеров;
- 3. выигрыш, к которому приводит каждая совокупность действий.
Как правило, выигрыш (или проигрыш) может быть задан количественно; например, можно оценить проигрыш нулем, выигрыш — единицей , а ничью — 1/2 .
Игра называется парной , если в ней участвуют два игрока, и множественной , если число игроков больше двух.
Рассмотрим суть парной игры:
- В них участвуют два игрока А и В, интересы которых противоположны, а под игрой будем понимать ряд действий со стороны А и В. Игра называется игрой с нулевой суммой, или антагонистической , если выигрыш одного из игроков равен проигрышу другого, т.е. для полного задания игры достаточно указать величину одного из них. Если обозначить а — выигрыш одного из игроков, b — выигрыш другого, то для игры с нулевой суммой b = — а, поэтому достаточно рассматривать, например а.
Основные понятия парной игры:
- Ход игрока — выбор и осуществление одного из предусмотренных правилами действий
- Личный ход — это сознательный выбор игроком одного из возможных действий (например, ход в шахматной игре).
- Случайный ход — это случайно выбранное действие (например, выбор карты из перетасованной колоды).
- Стратегия игрока — совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации
- Игра называется конечной , если у каждого игрока имеется конечное число стратегий, и бесконечной — в противном случае.
Решение игры
- Для того чтобы решить игру, или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получать максимальный выигрыш, когда второй придерживается своей стратегии.
- В то же время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными.
- Оптимальные стратегии должны также удовлетворять условию устойчивости, т.е. любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре.
Если игра повторяется достаточно много раз, то игроков может интересовать не выигрыш и проигрыш в каждой конкретной партии, а средний выигрыш (проигрыш) во всех партиях.
Цель теории игр:
- определение оптимальной стратегии для каждого игрока . При выборе оптимальной стратегии естественно предполагать, что оба игрока ведут себя разумно с точки зрения своих интересов. Важнейшее ограничение теории игр — единственность выигрыша как показателя эффективности, в то время как в большинстве реальных экономических задач имеется более одного показателя эффективности. Кроме того, в экономике, как правило, возникают задачи, в которых интересы партнеров не обязательно антагонистические.
Аннотация:
В составе комплекта входят:
- Программа для отработки навыков в теории игр.
- Презентация для учителя (для опытного, уже разбирающегося в данной группе задач)
- Презентация для ученика, более наглядная презентация с файлом решения задач в excel
Программа может быть использована под руководством педагога делая занятия по изучению теории игр более интерактивными. У меня это 4-8 уроков.
Целевая аудитория: для 11 класса
Автор: Голяков Николай Александрович
Место работы: МБОУ «Средняя общеобразовательная школа № 5 г.Дубны Московской области»
Добавил: KoliyR
Уважаемые коллеги! Автор ждёт Ваши отзывы! Оставьте своё мнение о разработке!
Всего комментариев: 0
Физкультминутки
Физкультминутки обеспечивают кратковременный отдых детей на уроке, а также способствуют переключению внимания с одного вида деятельности на другой.
В помощь учителю
Уважаемые коллеги! Добавьте свою презентацию на Учительский портал и получите бесплатное свидетельство о публикации методического материала в международном СМИ.
Для добавления презентации на портал необходимо зарегистрироваться.
Конкурсы
Диплом и справка о публикации каждому участнику!
© 2007 — 2023 Сообщество учителей-предметников «Учительский портал»
Свидетельство о регистрации СМИ: Эл № ФС77-64383 выдано 31.12.2015 г. Роскомнадзором.
Территория распространения: Российская Федерация, зарубежные страны.
Учредитель / главный редактор: Никитенко Е.И.
Сайт является информационным посредником и предоставляет возможность пользователям размещать свои материалы на его страницах.
Публикуя материалы на сайте, пользователи берут на себя всю ответственность за содержание этих материалов и разрешение любых спорных вопросов с третьими лицами.
При этом администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта.
Если вы обнаружили, что на сайте незаконно используются материалы, сообщите администратору через форму обратной связи — материалы будут удалены.
Все материалы, размещенные на сайте, созданы пользователями сайта и представлены исключительно в ознакомительных целях. Использование материалов сайта возможно только с разрешения администрации портала.
Фотографии предоставлены 
1.
Теория игр
Информатика ЕГЭ 19-21
Голяков Николай Александрович
2.
Как правило задания на теорию игр в ЕГЭ лаконичные
• при конкретной начальной позиции стратегию имеет только один
игрок
• нет возможности ничьи
• однозначно описаны правила ходов при игре
3.
выигрышная позиция – это такая позиция, в которой игрок,
делающий первый ход, обязательно выиграет при любых действиях
соперника, если не допустит ошибки; при этом говорят, что у
данного игрока есть выигрышная стратегия – алгоритм выбора
очередного хода, позволяющий ему выиграть;
Если рассмотреть игру для первого игрока, то возможно выделить
• выигрышную позицию
• проигрышную позицию
Так же выделяется последний возможный номер хода стратегии
4.
(7,S) – Петя – Ваня
+1
*2
>=77
5.
Выигрышная
позиция
возможна
при
рассмотрении любого возможного хода с
получением требуемого результата
(7,S) – Петя – Ваня
+1 или *2
>=77
6.
if (n mod 2 =1) and
(hod(i+1,j,n) or
hod(i,j+1,n) or
hod(i*2,j,n) or
hod(i,j*2,n)) then mas[i,j]:=n;
(7,S) – Петя – Ваня
+1 или *2
>=77
7.
Проигрышная позиция неизбежна, когда при
любом возможном ходе с не достигнут
результат, но противник всегда имеет
возможность этот результат добрать
(7,S) – Петя – Ваня
+1 или *2
>=77
Проигрышная позиция – это
стратегия для второго игрока
8.
if (n mod 2 =0) and
(hod(i+1,j,n) and
hod(i,j+1,n) and
hod(i*2,j,n) and
hod(i,j*2,n)) then mas[i,j]:=n;
(7,S) – Петя – Ваня
+1 или *2
>=77
9.
=МАКС(B$1;$A2)*2+МИН(B$1;$A2)
10.
Видео по разбору решения в таблицах
https://youtu.be/G8wMmW0qTK8
https://youtu.be/9Ssh8ubqdvI
Моя запись к презентации:
https://youtu.be/JXB_mbV7nqg
11.
const gl=40;
var mas:array [1..100,1..100] of integer;
i,j,n:integer;
function hod(i,j,n:integer):boolean;
begin result:=(mas[i,j]<>n) and (mas[i,j]<>0) and ((mas[i,j] mod 2)=((n+1) mod 2));
end;
begin
for i:=1 to 100 do for j:=1 to 100 do if max(i,j)*2+min(i,j)>=77 then mas[i,j]:=1;
for n:=2 to 40 do
for i:=1 to gl do
for j:=1 to gl do begin
if ((i<gl) and (j<gl) and (mas[i,j]=0)) then begin
if (n mod 2 =1) and (hod(i+1,j,n) or hod(i,j+1,n) or
hod(i*2,j,n) or hod(i,j*2,n)) then mas[i,j]:=n;
if (n mod 2 =0) and(hod(i+1,j,n) and hod(i,j+1,n) and
hod(i*2,j,n) and hod(i,j*2,n)) then mas[i,j]:=n;
end;
end;
for i:=1 to gl do begin
for j:=1 to gl do write(mas[i,j]:3);
writeln();
end;
readln();
end.
12.
13.
А. Кабанов
14.
15.
Скрипт для тренировки в стратегии игр:
http://оннаш.рф/eg19.exe
Моя запись к презентации, краткий обзор программы:
https://youtu.be/qen8H6S2KQE
16.
17.
18.
Видео для презентации
https://youtu.be/YFXIpLkBTyQ
Слайд 1
Слайд 2
Слайд 3
Слайд 4
Слайд 5
Слайд 6
Слайд 7
Слайд 8
Берто и Роберт были арестованы за ограбление банка, не сумев правильно использовать для
побега угнанный автомобиль. Полиция не может доказать, что именно они ограбили банк, но поймала их с поличным в украденном автомобиле. Их развели по разным комнатам и каждому предложили сделку: сдать сообщника и отправить его за решетку на 10 лет, а самому выйти на свободу. Но если они оба сдадут друг друга, то каждый получит по 7 лет. Если же никто ничего не скажет, то оба сядут на 2 года только за угон автомобиля.
ИГРА 1
Слайд 9
Давайте быстро поделим 100$. Вы и я решаем, сколько из сотни мы требуем и одновременно озвучиваем
суммы. Если наша общая сумма меньше ста, каждый получает то, что хотел. Если общее количество больше ста, тот, кто попросил наименьшее количество, получает желаемую сумму, а более жадный человек получает то, что осталось. Если мы просим одинаковую сумму, каждый получает 50 $. Сколько вы попросите? Как вы разделите деньги? Существует единственный выигрышный ход.
ИГРА 2
Слайд 10
Слайд 11
Слайд 12
Слайд 13
Слайд 14
Слайд 15
Слайд 16
Слайд 17
Задание 26. Два игрока, Паша и Вова, играют в следующую
игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу 1 камень или 10 камней. Например, имея кучу из 7 камней, за один ход можно получить кучу из 8 или 17 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 41 или больше камней.В начальный момент в куче было S камней, 1 ≤ S ≤ 40.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Слайд 18
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а)
Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающие ходы.
б) Укажите такое значение S. при котором Паша не может выиграть за один ход, но при любом ходе Паши Вова может выиграть своим первым ходом. Опишите выигрышную стратегию Вовы.
2. Укажите два значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Вова. Для указанных значений S опишите выигрышную стратегию Паши.
3. Укажите значение S, при котором у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши, однако у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вовы.
Слайд 19
1. а) Паша может выиграть, если S = 31, …,
40. При меньших значениях S за один ход нельзя получить кучу, в которой больше 40 камней. Паше достаточно увеличить количество камней на 10. При S < 31 получить за один ход больше 40 камней невозможно.
б) Вова может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 30 камней. Тогда после первого хода Пети в куче будет 31 камень или 40 камней. В обоих случаях Ваня увеличивает количество камней на 10 и выигрывает в один ход.
2. Возможные значения S: 20, 29. В этих случаях Паша, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 30 камней (при S = 20 он увеличивает количество камней на 10; при S = 29 добавляет 1 камень). Эта позиция разобрана в п. 1. б). В ней игрок, который будет ходить (теперь это Вова), выиграть не может, а его противник (то есть Паша) следующим ходом выиграет.
3. Возможное значение S: 28. После первого хода Паши в куче будет 29 или 38 камней. Если в куче станет 38 камней, Вова увеличит количество камней на 10 и вы играет своим первым ходом. Ситуация, когда в куче 29 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Вова), выигрывает своим вторым ходом.
В таблице изображено дерево возможных партий при описанной стратегии Вовы. Заключительные позиции (в них выигрывает Вова) подчёркнуты. На рисунке это же дерево изображено в графическом виде (оба способа изображения дерева допустимы).
Слайд 20
Задание 26 Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в пять раз. Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или 50 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.Игра завершается в тот момент, когда количество камней в куче становится более 200. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 201 или больше камней. В начальный момент в куче было S камней,
1 ≤ S ≤ 200.
Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) При каких значениях числа S Петя может выиграть первым ходом? Укажите все такие значения и выигрывающий ход Пети.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
2. Укажите два значения S, при которых у Пети есть выигрышная стратегия, причём (а) Петя не может выиграть первым ходом, но (б) Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня.
Для указанных значений S опишите выигрышную стратегию Пети.
3. Укажите такое значение S, при котором
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в позиции.
Слайд 21
1. а) Петя может выиграть, если S=41, …,200. При меньших
значениях S за один ход нельзя получить кучу, в которой больше 200 камней. Пете достаточно увеличить количество камней в 5 раз. При S < 41 получить за один ход больше 200 камней невозможно.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 40 камней. Тогда после первого хода Пети в куче будет 41 камень или 200 камней. В обоих случаях Ваня увеличивает количество камней в 5 раз и выигрывает в один ход.
2. Возможные значения S: 8, 39. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 40 камней (при S=8 он увеличивает количество камней в 5 раз; при 5=39 — добавляет 1 камень). Эта позиция разобрана в п.
1 б. В ней игрок, который будет ходить (теперь это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.
3. Возможное значение S: 38. После первого хода Пети в куче будет 39 или 190 камней. Если в куче станет 190 камней, Ваня увеличит количество камней в 5 раз и выиграет своим первым ходом. Ситуация, когда в куче 39 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.
Слайд 22
Задание 26 .Два игрока, Петя и Ваня, играют в следующую игру.
Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, или добавить в кучу два камня, или увеличить количество камней в куче в два раза.
Например, имея кучу из 10 камней, за один ход можно получить кучу из 11, 12 или 20 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче превышает 33. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 34 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 33.
Говорят, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания.
Задание 1.
а) При каких значениях числа S Петя может выиграть первым ходом? Укажите все такие значения и выигрывающий ход Пети.
б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. Опишите выигрышную стратегию Вани.
Задание 2.
Укажите три значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для указанных значений S опишите выигрышную стратегию Пети.
Задание 3.
Укажите такое значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом
Слайд 23
Задание 1.
а) Петя может выиграть, если S = 17, …, 33. При
меньших значениях S за один ход нельзя получить кучу, в которой будет 34 или более камней. Пете достаточно увеличить количество камней в 2 раза.
б) Ваня может выиграть первым ходом (как бы ни играл Петя), если исходно в куче будет S = 16 камней. Тогда после первого хода Пети в куче будет 17 камней, 18 камней или 22 камня. Во всех случаях Ваня увеличивает количество камней в 2 раза и выигрывает в один ход.
Задание 2.
Возможные значения S: 8, 14, 15. В этих случаях Петя, очевидно, не может выиграть первым ходом. Однако он может получить кучу из 16 камней (при S = 8 он удваивает количество камней; при S = 14 добавляет 2 камня; при S = 15 добавляет 1 камень). Эта позиция разобрана в п. 1б. В ней игрок, который будет ходить (в данном случае это Ваня), выиграть не может, а его противник (то есть Петя) следующим ходом выиграет.
Задание 3.
Возможное значение S: 13. После первого хода Пети в куче будет 14 камней, 15 камней или 26 камней. Если в куче станет 26 камней, то Ваня увеличит количество камней в 2 раза и выиграет своим первым ходом. Ситуация, когда в куче 14 или 15 камней, разобрана в п. 2. В этой ситуации игрок, который будет ходить (теперь это Ваня), выигрывает своим вторым ходом.
Информатика, 11 класс. Урок № 8.
Тема — Знакомство с теорией игр
Цели и задачи урока:
- Научиться анализировать множество вариантов развития ситуации.
- Освоить понятия: стратегия игры, выигрышная стратегия, дерево игры.
- Овладеть методом анализа дерева игры.
- Научится находить вариант хода, приводящий к выигрышу.
На уроке вы научитесь:
- Строить дерево игры.
- Находить выигрышные стратегии.
- Решать 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
Рассматривая данную игру, то можно прийти к выводу, что стратегией мы будем называть некоторый алгоритм планирования.
Для каждой стратегии существует некоторый гарантированный результат игры — это минимальный результат среди всех результатов, которые получаются, если рассматривать все варианты игры противника при этой стратегии. Дж. фон Нейман предложил использовать такую стратегию, которая обеспечивает наибольший гарантированный результат.
Однако таких вариантов очень много и справиться с перебором всех не может ни только человек, но и компьютер. При этом человек «интуитивно» может отбрасывать некоторые из неперспективных вариантов основываясь на не совсем логичных обоснованиях. Такие обоснования называются эвристиками.
Эвристика — это правило, сокращающее число потенциальных вариантов перебора.
Презентация «Теория игр. Методы решения»
Подписи к слайдам:
Теория игр
- Методы решения
- Математическая теория игр берёт своё начало из неоклассической экономики. Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение.
- Эта область математики нашла некоторое отражение в общественной культуре. В 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона Нэша, нобелевского лауреата по экономике и учёного в области теории игр; а в 2001 по мотивам книги был снят фильм «Игры разума».
Теория игр
- Теория игр — математический метод изучения оптимальных стратегий в играх. Под игрой понимается процесс, в котором участвуют две и более сторон, ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу — в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках.
Представление игр
- Игры представляют собой строго определённые математические объекты. Игра образуется игроками, набором стратегий для каждого игрока и указания выигрышей, или платежей, игроков для каждой комбинации стратегий. Большинство кооперативных игр описываются характеристической функцией, в то время как для остальных видов чаще используют нормальную или экстенсивную форму.
- Игры в экстенсивной, или расширенной, форме представляются в виде ориентированного дерева, где каждая вершина соответствует ситуации выбора игроком своей стратегии. Каждому игроку сопоставлен целый уровень вершин. Платежи записываются внизу дерева, под каждой листовой вершиной.
- В нормальной, или стратегической, форме игра описывается платёжной матрицей. Каждая сторона (точнее, измерение) матрицы — это игрок, строки определяют стратегии первого игрока, а столбцы — второго. На пересечении двух стратегий можно увидеть выигрыши, которые получат игроки.
- Кооперативные игры используют так называемую характеристическую функцию, определяющую выигрыш каждой коалиции игроков. При этом предполагается, что выигрыш пустой коалиции равен нулю.
Типы игр
- Игра называется кооперативной, или коалиционной, если игроки могут объединяться в группы, беря на себя некоторые обязательства перед другими игроками и координируя свои действия. Этим она отличается от некооперативных игр, в которых каждый обязан играть за себя.
- Игра будет симметричной тогда, когда соответствующие стратегии у игроков будут равны, то есть иметь одинаковые платежи. Иначе говоря, если игроки могут поменяться местами и при этом их выигрыши за одни и те же ходы не изменятся. Многие изучаемые игры для двух игроков — симметричные.
Типы игр
- Игры с нулевой суммой (антагонистические) – особая разновидность игр с постоянной суммой, то есть таких, где игроки не могут увеличить или уменьшить имеющиеся ресурсы, или фонд игры. В этом случае сумма всех выигрышей равна сумме всех проигрышей при любом ходе. Многие изучаемые математиками игры иного рода: в играх с ненулевой суммой выигрыш какого-то игрока не обязательно означает проигрыш другого, и наоборот. Исход такой игры может быть меньше или больше нуля. Такие игры могут быть преобразованы к нулевой сумме — это делается введением фиктивного игрока, который «присваивает себе» излишек или восполняет недостаток средств.
- В параллельных играх игроки ходят одновременно, или, по крайней мере, они не осведомлены о выборе других до тех пор, пока все не сделают свой ход. В последовательных, или динамических, играх участники могут делать ходы в заранее установленном либо случайном порядке, но при этом они получают некоторую информацию о предшествующих действиях других.
Типы игр
- Важное подмножество последовательных игр составляют игры с полной информацией. В такой игре участники знают все ходы, сделанные до текущего момента, равно как и возможные стратегии противников, что позволяет им в некоторой степени предсказать последующее развитие игры. Полная информация не доступна в параллельных играх, так как в них неизвестны текущие ходы противников.
- Игры в реальном мире или изучаемые в экономике игры, как правило, длятся конечное число ходов. Математика не так ограничена, и в частности, в теории множеств рассматриваются игры, способные продолжаться бесконечно долго. Причём победитель и его выигрыш не определены до окончания всех ходов.
Типы игр
- Большинство изучаемых игр дискретны: в них конечное число игроков, ходов, событий, исходов и т. п. Однако эти составляющие могут быть расширены на множество вещественных чисел. Игры, включающие такие элементы, часто называются дифференциальными. Они связаны с какой-то вещественной шкалой (обычно — шкалой времени), хотя происходящие в них события могут быть дискретными по природе. Дифференциальные игры также рассматриваются в теории оптимизации, находят своё применение в технике и технологиях, физике.
Подходы к принятию решений с позиций теории игр
- Теория игр нашла применение в самых различных областях человеческой деятельности.
- Теория показала, что везде, где возникает соревнование за ограниченные ресурсы, длительное и стабильное равновесие может установиться только в том случае, если игроки применяют смешанные стратегии, т.е. когда в игре применяется многообразие отдельных линий поведения, стилей мышления и стратегий решения проблем.
Орлянка
- Простейшим примером антагонистической игры является игра «Орлянка». Первый игрок прячет монету орлом или решкой вверх, а второй пытается угадать, как она спрятана. Если он не угадывает — он платит первому одну денежную единицу, если угадывает — первый платит ему одну денежную единицу.
- В данной игре каждый участник имеет две стратегии: «орел» и «решка». Множество ситуаций в игре состоит из четырех элементов. В строках таблицы указаны стратегии первого игрока х, в столбцах — стратегии второго игрока y. Для каждой из ситуаций указаны выигрыши первого и второго игроков.
|
|
|
|
|
|
|
|
|
Дилемма заключенного
- Двое преступников, А и Б, попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку:
- если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок лишения свободы (10 лет). Однако иных доказательств их вины у следствия нет. Если оба молчат, их деяние квалифицируется как неоказание помощи следствию, и они приговариваются к 6 месяцам. Если оба свидетельствуют против друг друга, они получают минимальный срок (по 2 года). Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. Что произойдёт?
Дилемма заключенного
|
|
|
|
|
|
|
|
|
Обмен закрытыми сумками
- Два человека встречаются и обмениваются закрытыми сумками, понимая, что одна из них содержит деньги, другая — товар. Каждый игрок может уважать сделку и положить в сумку то, о чём договорились, либо обмануть партнёра, дав пустую сумку.
Cпираль гонки вооружений
- Очевидно, что для каждой стороны превосходство лучше дешевого равновесия, а дорогое равновесие лучше незащищенности.
- Равновесие двух противников может быть обеспечено как в случае, когда обе стороны вооружены до зубов, так и на существенно более низком уровне, что гораздо дешевле. Поэтому такой вариант является для обеих сторон самым выгодным.
- Однако каждая сторона стремится ни в коем случае не допустить превосходства другой стороны, поэтому тратит все больше средств на вооружение.
- Оптимальным для обеих сторон вариантом было бы дешевое равновесие, но этому мешает отсутствие доверия.
Cпираль гонки вооружений
- Стратегия второй страны
- Сильно вооружиться
- Умеренно вооружиться
- Стратегия
- первой
- страны
- Сильно вооружиться
- Умеренно вооружиться
- 2, 2
- (дорогое равновесие)
- 4,1
- (превосходство)
- 1, 4
- (незащищенность)
- 3, 3
- (дешевое равновесие)
Примеры из реальной жизни
- Обе страны, вовлечённые в гонку вооружений, будут заявлять, что у них есть две возможности: либо увеличить расходы на военные нужды, либо сокращать вооружения. Ни одна из сторон не может быть уверена, что другая будет соблюдать договорённость, следовательно, обе будут стремиться к военной экспансии.
- Похожие явления наблюдаются и в автоспорте — «Формула-1», где последние 20 лет происходит гонка бюджетов команд. Из-за этого число машин-участников сократилось с 36 в 1990 году до 20 в 2003.
- В велогонках дилемма заключённого возникает, когда два сильных гонщика оторвались от общей группы. Каждый из них может либо предоставить соседу слипстрим («сотрудничать»), либо ехать сзади («предать»). Для обоих идеалом будет, когда они по очереди «висят» друг у друга на хвосте — но всегда есть желание не дать соседу слипстрима (тогда тот постепенно устаёт и «скатывается» в пелотон, а ты финишируешь с большим отрывом).
- Случай дилеммы заключённого может быть найден в бизнесе. Две конкурирующие фирмы должны определиться, сколько средств тратить на рекламу. Эффективность рекламы и прибыль каждой фирмы уменьшается с ростом расходов на рекламу у конкурента. Обе фирмы принимают решение увеличить расходы на рекламу, при этом их доли рынка и, возможно, объёмы продаж остаются неизменными, а прибыль сокращается.
Спасибо за внимание!