Теория игр в школьном курсе математики и информатики

Автор: Ширяева Гузель Равилевна

Организация: МБОУ СОШ №72 с углубленным изучением немецкого языка Советского района

Населенный пункт: Республика Татарстан, г. Казань

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

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

Официальный разбор задач начинается либо при подготовке к олимпиадам либо при разборе задач Всеросийских проверочных работ и заданий ГИА: например в ЕГЭ
по информатике (задания 19-21 «Куча камней»).

Для начала работы с этой темой полезно изучить видео-лекции Алесея Савватеева (они есть в бесплатном доступе на Ютуб).

Стратегическое мышление, наравне с критическим, имеет право начинать свое развитие со школьной скамьи и не только у тех учащихся, которые проявляют интерес именно к математической науке. Для участников можно предложить ролик из фильма «Игры разума», 2002, режиссера Рона Ховарда: о математическом гении.

Несмотря на увлеченность играми в жизни и особенно в интернете, мало, кто знает, что Теории игр более 70 лет, как разделу математики.

Точкой старта можно считать 1944 год, когда вышла в свет книга «Теория игр и экономическое поведение» авторов Джона фон Неймана и Оскара Моргенштерна. Однако надо понимать, что проблемами, составляющими классический предмет современной теории игр занимались задолго до 1944 года [1].

Оптимальные решения предлагались ещё в XVIII в. Это были задачи производства и ценообразования в условиях олигополии (тип рыночной структуры несовершенной конкуренции, в которой доминирует крайне малое количество фирм)

Примером из теории игр в XIX в. Может быть работа Антуана Огюстена Курно (французский философ, экономист, математик) «Исследование математических принципов теории богатства» (1838).

В начале XX в. Эмануил Ласкер, Эрнст Цермело и Эмиль Борель выдвигают идею математической теории конфликта интересов: Эрнст Цермело(немецкий математик) «О применении теории множеств к теории шахматной доски»(1913); Эмиль Борель (французский математик) «Случай» (1923).

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

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

Современная теория игр делится на две относительно независимые части: теория некооперативных игр (бескоалиционные игры) и теория кооперативных игр (коалиционные игры), которые в свою очередь разделяются на статические (одновременные ходы сторон) и динамические (ходы упорядочены относительно друг друга).

Примером статической игры может служить «Камень-ножницы-бумага», в которой оба участника выбирают комбинации одновременно[2].

К динамическим играм относятся крестики-нолики, шахматы, шашки, нарды и т.д.

Еще один раздел теории игр – дифференциальные игры, где моделируются процессы управления объектами в конфликтных ситуациях. Примерами являются игры-преследования типа «Шофер-убийца», «Торпеда и корабль» и т.п. , где для получения общей картины есть преследователь Р (pursuer) и преследуемый Е (evader) управляемые человеком или автоматически, иногда может быть более двух объектов, например, группа боевых самолетов противостоит эскадре бомбардировщиков. Т.е. Р и Е разумные противники с противоположными интересами. Заканчивается такая игра захватом.

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

Относительно бескоалиционных игр на первый план выступает Равновесие по Нэшу.

Данное понятие было предложено американским математиком Джоном Нэшем в серии работ 1950-1953 гг., за что в 1994 году он получил Нобелевскую премию.

Равновесие по Нэшу - это такая ситуация в игре, когда игрокам не выгодно отклоняться поодиночке, при условии что все остальные участники придерживаются своих стратегий, образующих равновесие Нэша. Ярким примером такой игры является «Дилемма заключенного», здесь возможна лишь одна ситуация равновесия по Нэшу, когда оба игрока получают по 5 лет тюремного заключения. Данная задача впервые была сформулирована в 1950 г. Мерилом Фладом и Мелвином Дрешером, а название сформулировано канадским математиком Альбертом Такером.

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

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

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

Таким образом, равновесие по Штакельбергу соответствует максимуму полезности игроков в условиях неодновременности принятия ими решений. В отличие от равновесия доминирующих стратегий и равновесия по Нэшу этот вид равновесия существует всегда.

Равновесие по Парето – ситуация, когда нельзя улучшить положение ни одного из игроков, не ухудшая при этом положения другого. Существует при условии, что нельзя увеличить полезность обоих игроков одновременно.

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

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

Игра «Крестики-нолики»: Поле «три-на-три», два игрока, две фигуры, ходы по очереди. Дерево игровых ситуаций, то есть возможных сценариев развития событий для игры крестики-нолики состоит из 255168 узлов.

Это число получается как сумма всех возможных вариантов ходов: 9 вариантов на первом шаге, 8 — для каждого из 9 на втором шаге, 7 — на каждом из 72 вариантов на третьем шаге и так далее, за вычетом ситуаций досрочного окончания игры (выигрыша).

Легко выиграть в «крестики-нолики», как и проиграть, может каждый, если для человека это нерегулярный процесс. А вот если в крестики-нолики играют опытные соперники, знающие все премудрости, то партия за партией будут заканчиваться ничьей, а победитель появится только, если кто-то из участников схватки ошибётся. Хорошая новость в том, что далеко не все знакомы со стратегиями победы в этой игре.

Игра «Дракон-принцесса-самурай» Это более зрелищная версия игры «Камень-ножницы-бумага», где по знакам рук определяют победителя.

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

Что касается «силы» персонажей, то самурай убивает дракона. Принцесса покоряет сердце самурая. А дракон съедает принцессу. Выбор игроки демонстрируют одновременно, по команде «раз-два-три».

Стратегии: по статистике, с наибольшей вероятностью (38%) новички выберут дракона, потому что фигура кажется сильной (33% — самурая, 29% — принцессу). Но в классе играют не новички, поэтому подумают на шаг дальше и выберут самурая, который преодолеет дракона. А для того, кто предвидит и этот выбор одноклассников, правильная стратегия — выбрать принцессу.

Примеры задач из ВПР-6 класс[3]:

Пример№1 Племя людоедов поймало Робинзона Крузо. Вождь сказал: «Мы рады бы отпустить тебя, но по нашему закону ты должен сказать какое-нибудь утверждение. Если оно окажется истинным, мы съедим тебя. Если оно окажется ложным, тебя съест наш ручной лев». Что сказать Робинзону, чтобы людоеды его отпустили?

Решение: «Меня съест Ваш ручной лев». Это утверждение не истинно и не ложно.

Пример№2 На доске написано число. Олег играет в арифметическую игру: он может либо стереть последнюю цифру написанного числа, либо прибавить к написанному числу число 2018 и записать полученный результат, стерев предыдущее число. Может ли Олег, действуя таким образом, в конце концов получить число 1? Если да, покажите как; если нет, объясните почему.

Решение: Если число, написанное на доске, начинается с единицы, то Олег должен просто

стереть последовательно все цифры, кроме первой. Если число начинается с цифры можно стереть все цифры, кроме первой, и затем 5 раз прибавить 2018, чтобы первой цифрой была единица. Получится пятизначное число, которое начинается с 1. Затем нужно стереть по очереди четыре последние цифры. Ответ: да

Пример№3 В Стране Чудес проводилось следствие по делу об украденной муке. На суде Мартовский Заяц заявил, что муку украл Болванщик. В свою очередь Болванщик и Соня дали показания, которые по каким-то причинам не были записаны. В ходе судебного заседания выяснилось, что муку украл лишь один из трёх подсудимых и что только он дал правдивые показания. Кто украл муку?

Решение.Рассмотрим возможные случаи.

1.  Предположим, что украл Мартовский Заяц, тогда он должен говорить правду. Тогда его показание: «муку украл Болванщик» не соответствует предположению.

2.  Если украл Болванщик, то он говорит правду, а Заяц  — ложь. Тогда ложное высказывание зайца не соответствует предположению.

Так как сказано, что муку украл лишь один из трёх подсудимых, остаётся только Соня. Ответ: Соня.

Примеры задания из ЕГЭ [3]:

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

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

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

Найдите минимальное значение S, при котором одновременно выполняются два условия:

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

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

Решение: Минимальное значение S: 8. После первого хода Пети в куче будет 9, 12 или 40 камней. Если в куче станет 40 камней, Ваня увеличит количество камней в 5 раз и выиграет первым ходом. Когда в куче 9 или 12 камней, можно получить кучу из 13 камней (при S  =  9 нужно добавить 4 камня, при S  =  12 нужно добавить 1 камень). Тогда после второго хода Пети в куче будет 14 камней, или 17 камней, или 65 камней. Во всех случаях Ваня увеличивает количество камней в куче в 5 раз и выигрывает вторым ходом.

Таким образом, ответ  — 8.

№2 Петя и Ваня играют в камни, есть 2 кучи камней. За один ход игрок может добавить в любую кучу один камень или добавить в любую кучу столько камней, сколько их в данный момент в другой куче. Игра завершается, когда суммарное количество камней будет не менее 58. В начальный момент было 6 камней, во второй куче S камней.

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

Решение: Выпишем все возможные ходы Пети: 6+S; S, 6+1;S, 6; S+1, 6: S+6. Выгодный ход для Вани — сходить по максимальному: увеличить минимальную кучу камней на максимальную. И эти значения должны удовлетворять условию выигрыша: >=58.

2(6+S)+S>=58 2S+7>=58 2S+6>=58 2(S+6)+6>=58

и выберем минимальное, S=16

Если нужно найти два значение, при которых у Пети есть выигрышная стратегия, причем Петя не может гарантированно выиграть за один ход.
Выигрышные ходы мы берем из предыдущего пункта, например это: 22;16+, 22;15+, 21;16+, 25;8+.

Тогда распишем дерево ходов в выигрышные позиции. В позицию 21;16 мы можем попасть из позиции 21;15 Пети (то есть был сделан ход увеличить кол-во камней в меньшей кучи на большее кол-во),а также из 21;15 мы попадем в другие выигрышные позиции: 22;15,21; 36, и 36;15. Тогда начальное значение = 6; 15.

Необходимо найти и второе значение: например, в выигрышную позицию 8;25 можно попасть из позиции 7;25, также мы попадем в другие выигрышные для Пети позиции: 7;26, 7;32, 32;25 — тогда начальное значение = 6; 25 [2]

Игра «Старая и новая дороги»

В городе построили новую короткую дорогу. Сегодня она открывается для проезда. Какую дорогу вы выбираете — старую или новую? Проголосуйте. Например, с помощью WhatsApp опроса.

Стратегии. Дорога открылась. Все водители, которые так долго этого ждали, двинутся туда. Возникнет затор. Таким образом, вам стоит выбрать старую дорогу. Впрочем, статистика показывает, что именно так думают 75% людей (это докажут и результаты голосования). Поэтому на самом деле новая дорога почти свободна, следует выбрать ее. Это парадокс Браеса в «переводе» с математического языка на бытовой.

Можно сделать еще один шаг. Сообщить эту стратегию участникам и снова предложить им определиться, куда поехать.

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

Не менее интересна она и сточки зрения профессиональной ориентации учащихся.

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

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

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

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

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

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

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

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

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

 

Список используемой литературы и интернет- ресурсов

1. Математические олимпиады: методика подготовки.5-8 классы: пособие для учителя/ А.В.Фарков.- М.:ВАКО, 2021
2. Сайт СДАМ ГИА https://sdamgia.ru
3. Теория игр: основные понятия: учебное пособие для вузов/ А.Г.Кремлев, ред.А.М.Тарасьева.- Москва: Издательство Юрайт, 2022
4. Теория игр: учебник для академического бакалавриата/ П.В.Конюховский, А.С.Малова – М.:Издательство Юрайт, 2015
5. Статья. Принятие медицинских решений в условиях неопределенности. Восточно-Европейский журнал передовых технологий, 2014 г.

1. file0.docx.. 37,0 КБ

Опубликовано: 12.04.2023