Теория игр, или как играть, чтобы не проиграть?
Цель: привить интерес к математике, показать возможности математических методов.
Важным качеством любого человека является умение выбрать и обосновать лучший вариант своих действий, в каких бы то ни было условиях. Современная математика представляет собой объединение различных направлений.
Нетождественность интересов – вот что определяет процессы, происходящие в обществе. Явления, в которых участвуют различные стороны с несовпадающими интересами и эффективность принимаемого одной стороной решения зависят от действий другой стороны. Необходимость анализа таких ситуаций вызвала к жизни специальный математический аппарат. Выработкой рекомендаций по рациональному образу действий участников многократно повторяющейся конфликтной ситуации занимается теория игр.
Теомрия игр — математический метод изучения оптимальных стратегий в играх. Под игрой понимается процесс, в котором участвуют две и более сторон, ведущих борьбу за реализацию своих интересов. Каждая из сторон имеет свою цель и использует некоторую стратегию, которая может вести к выигрышу или проигрышу — в зависимости от поведения других игроков. Теория игр помогает выбрать лучшие стратегии с учётом представлений о других участниках, их ресурсах и их возможных поступках.
Теория игр — это раздел прикладной математики, точнее — исследования операций. Чаще всего методы теории игр находят применение в экономике, чуть реже в других общественных науках — социологии, политологии, психологии, этике, юриспруденции и других. Начиная с 1970-х годов её взяли на вооружение биологи для исследования поведения животных и теории эволюции. Очень важное значение она имеет для искусственного интеллекта и кибернетики, особенно с проявлением интереса к интеллектуальным агентам.
История
Оптимальные решения или стратегии в математическом моделировании предлагались ещё в XVIII в. Задачи производства и ценообразования в условиях конкуренции, которые стали позже хрестоматийными примерами теории игр, рассматривались в XIX в.
Математическая теория игр берёт своё начало из экономики. Впервые математические аспекты и приложения теории были изложены в классической книге 1944 года Джона фон Неймана и Оскара Моргенштерна «Теория игр и экономическое поведение» (англ. Theory of Games and Economic Behavior).
Эта область математики нашла некоторое отражение в общественной культуре. В 1998 году американская писательница и журналистка Сильвия Назар издала книгу о судьбе Джона Нэша, нобелевского лауреата по экономике и учёного в области теории игр; а в 2001 по мотивам книги был снят фильм «Игры разума».
Дж. Нэш в 1949 году пишет диссертацию по теории игр, через 45 лет он получает Нобелевскую премию по экономике. Дж. Нэш после окончания Политехнического института Карнеги с двумя дипломами — бакалавра и магистра — поступил в Принстонский университет, где посещал лекции Джона фон Неймана. В своих трудах Дж. Нэш разработал принципы «управленческой динамики». Первые концепции теории игр анализировали антагонистические игры, когда есть проигравшие и выигравшие за их счет игроки. Нэш разрабатывает методы анализа, в которых все участники или выигрывают, или терпят поражение. Эти ситуации получили названия «равновесие по Нэшу», или «некооперативное равновесие», в ситуации стороны используют оптимальную стратегию, что и приводит к созданию устойчивого равновесия. Игрокам выгодно сохранять это равновесие, так как любое изменение ухудшит их положение. Эти работы Дж. Нэша сделали серьёзный вклад в развитие теории игр, были пересмотрены математические инструменты экономического моделирования. Дж. Нэш показывает, что классический подход к конкуренции, когда каждый сам за себя, неоптимален. Более оптимальны стратегии, когда каждый старается сделать лучше для себя, делая лучше для других.
Хотя теория игр первоначально и рассматривала экономические модели, вплоть до 1950-х она оставалась формальной теорией в рамках математики. Но уже с 1950-х гг. начинаются попытки применить методы теории игр не только в экономике, но в биологии, кибернетике, технике, антропологии. Во время Второй мировой войны и сразу после неё теорией игр серьёзно заинтересовались военные, которые увидели в ней мощный аппарат для исследования стратегических решений.
В 1960—1970 гг. интерес к теории игр угасает, несмотря на значительные математические результаты, полученные к тому времени. С середины 1980-х гг. начинается активное практическое использование теории игр, особенно в экономике и менеджменте. За последние 20 — 30 лет значение теории игр и интерес значительно растет, некоторые направления современной экономической теории невозможно изложить без применения теории игр.
Математическая теория игр сейчас бурно развивается, рассматриваются динамические игры. Однако математический аппарат теории игр затратен. Его применяют для оправданных задач: политика, экономика монополий и распределения рыночной власти и т. п. Ряд известных ученых стали Нобелевскими лауреатами по экономике за вклад в развитие теории игр, которая описывает социально-экономические процессы. Дж. Нэш, благодаря своим исследованиям в теории игр, стал одним из ведущих специалистов в области ведения «холодной войны», что подтверждает масштабность задач, которыми занимается теория игр.
Во всех судебных системах кара за бандитизм (совершение преступлений в составе организованной группы) намного тяжелее, чем за те же преступления, совершённые в одиночку (отсюда альтернативное название — «дилемма бандита»).
Классическая формулировка дилеммы заключённого такова:
Двое преступников, А и Б, попались примерно в одно и то же время на сходных преступлениях. Есть основания полагать, что они действовали по сговору, и полиция, изолировав их друг от друга, предлагает им одну и ту же сделку: если один свидетельствует против другого, а тот хранит молчание, то первый освобождается за помощь следствию, а второй получает максимальный срок лишения свободы (10 лет). Если оба молчат, их деяние проходит по более лёгкой статье, и каждый из них приговаривается к 0,5 года. Если оба свидетельствуют против друг друга, они получают минимальный срок (по 2 года). Каждый заключённый выбирает, молчать или свидетельствовать против другого. Однако ни один из них не знает точно, что сделает другой. Что произойдёт?
Дилемма появляется, если предположить, что оба заботятся только о минимизации собственного срока заключения.
Представим рассуждения одного из заключённых. Если партнёр молчит, то лучше его предать и выйти на свободу (иначе — полгода тюрьмы). Если партнёр свидетельствует, то лучше тоже свидетельствовать против него, чтобы получить 2 года (иначе — 10 лет). Стратегия «свидетельствовать» строго доминирует над стратегией «молчать». Аналогично другой заключённый приходит к тому же выводу.
С точки зрения группы (этих двух заключённых) лучше всего сотрудничать друг с другом, хранить молчание и получить по полгода, так как это уменьшит суммарный срок заключения. Любое другое решение будет менее выгодным.
Задача 1.
Сидит на опушке леса Баба Яга скучает. Вдруг видит, идет к ней сынок богатого купца бездельник Онуфрий.
- Добрый день, добрый молодец! Куда путь держишь?- сказала Баба Яга.
- Заблудился! – грустно ответил Онуфрий.
- А мне скучно! Поиграем с тобой в игру, а потом я тебе дорогу покажу, - сказала Баба Яга.
- И делать то тебе особенно ничего не придется. Есть у меня мешок, а в нем 45 шариков. Каждый из нас по очереди будет вынимать из мешка любое число шариков от 1 до 5. Выигрывает тот, кто вытащит последний шарик.
Онуфрий согласился. Кто бы игру ни начинал, Онуфрий не выиграл ни разу. Баба Яга была в восторге и радостно указала Онуфрию путь домой!
Какую хитрость знала Баба Яга? Как она должна была играть, чтобы победить в любом случае?
Решение:
Начнем с конца. Важно чем закончится игра. Если у игрока в мешке останется 6 шаров он проиграет, т. к. соперник вынимает от 1 до 5 шаров. Онуфрию достается последний шар, и он проигрывает. Стратегия игры Бабы Яги - вынимать столько шаров, чтобы в мешке оставалось число шаров кратных 6.
Ответ: Онуфрий проиграет, если после хода Бабы Яги в мешке останется количество шариков кратких 6 .
Задача 2.
Малыш и Фрекен Бок играют в игру. На столе лежат конфеты. Первым ходом Малыш делит конфеты на три не пустых кучки, потом Фрекен Бок две кучки отдает Карлсону, а третью снова делит на три не пустых, потом Малыш также две отдает Карлсону, третью делит и так далее. Кто не сможет сделать ход проигрывает. Кто победит при верной игре, если на столе: а) 7конфет? б) 9 конфет? в)12 конфет? г) 14 конфет?
Решение:
Пусть игра началась с какого-то большого числа конфет. Чем она закончилась? Тем, что у игрока нет хода. Это бывает, когда конфет ему досталось 1 или 2. Это позиции проигрышные для того, кому они достались (п). Позиция 3-выигрышная (в). Имея три конфеты, игрок делит их на три кучки по конфете, и сопернику остается одна конфет. Игрок выиграл. Выиграть можно и при 4, 5 и 6 конфетах. Делить 6 конфет надо с умом (6=2+2+2), деля на (6=1+1+4) игрок проиграет.
Теперь рассмотрим 7 конфет. Игрок может их разложить на кучки (3+3+1), (4+2+1), (5+1+1). Соперник оставляет ему 1 конфету. Игрок проиграл.
Ответ: а) Малыш проиграл, если в кучке 7 конфет б) Малыш выиграл, если в кучке 9 конфет в) Малыш выиграл, если в кучке 12 конфет г) Малыш проиграл, если в кучке 14 конфет при верной игре.
Стратегия выигрыша Малыша: если в кучке 7,8 или 13,14 конфет, то Малыш должен предложить Фрекен Бок первый ход и вести верную игру. Если в кучке от 3 до 6 конфет или от 9 до 12, то его ход должен быть первым.
Задача 3 «Поставь на ноль».
Возьмём полоску клетчатой бумаги и занумеруем клетки числами 0, 1, 2, …, 14. На одной из 15 – ти клеток стоит фишка. Двое игроков по очереди передвигают фишку влево на 1, 2, 3 или 4 клетки. Проигрывает тот, кому некуда ходить.
Дать учащимся поиграть, затем предложить задание: при каком начальном положении фишки выигрывает начинающий, а при каком его партнёр?
Решение игры «Поставь на ноль».
Начальное положение фишки, при котором начинающий выигрывает, назовём выигрышным и соответствующие ему клетки отметим знаком «+». Остальные клетки для начинающего назовём проигрышными и отметим знаком «−». Расставлять плюсы и минусы начнём с нуля. В этой клетке ставится знак «−», так как если фишка стоит на нуле, начинающему некуда ходить.
В клетках 1, 2, 3 и 4 ставим «+», так как если фишка стоит на этих клетках начинающий выигрывает одним ходом, ставя фишку на ноль.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
─ | + | + | + | + | ─ | + | + | + | + | ─ | + | + | + | + | ─ |
Клетка 5. Если фишка стоит в этой клетке, то, как бы ни пошёл начинающий фишка после его хода окажется в клетках 1, 2, 3 или 4. Его партнёр пойдёт на ноль и выиграет. Значит клетка 5 проигрышная.
Клетки 6, 7, 8, 9 – выигрышные. Начинающий может передвинуть фишку в клетку 5 и тем самым поставить своего противника в проигрышное положение.
Точно так же клетка 10 – проигрышная, из неё начинающий может попасть в клетки 6, 7, 8, 9, выигрышные для противника.
Клетки 11, 12, 13 и 14 – выигрышные, а клетка 15 – проигрышная и так далее.
Ясно, что начинающий в любом случае выиграет, если каждый раз будет ставить фишку на клетку с номером, делящимся на 5. Он сможет это сделать, если вначале фишка стоит на клетке с номером не кратным 5. В противном случае этой стратегией может воспользоваться противник.
Задача 4 «Игра Боше».
На столе лежат 15 спичек. Два игрока берут поочерёдно со стола спички. За один ход игрок может взять 1, 2 или 3 спички. Выигрывает тот, кто берёт последнюю спичку.
Задача 5 «Игра дат»
Первый игрок сообщает какую–нибудь дату января. Каждый игрок на своём ходе называет более позднюю дату, увеличивая каждый раз или календарную дату в месяце, или порядковый номер месяца, но не то и другое одновременно. Первый, кто доберётся до 31 декабря, выигрывает.
Раздаточный материал:
Сидит на опушке леса Баба Яга скучает. Вдруг видит, идет к ней сынок богатого купца бездельник Онуфрий.- Добрый день, добрый молодец! Куда путь держишь?- сказала Баба Яга.
- Заблудился! – грустно ответил Онуфрий.
- А мне скучно! Поиграем с тобой в игру, а потом я тебе дорогу покажу, - сказала Баба Яга.
- И делать то тебе особенно ничего не придется. Есть у меня мешок, а в нем 45 шариков. Каждый из нас по очереди будет вынимать из мешка любое число шариков от 1 до 5. Выигрывает тот, кто вытащит последний шарик.
Онуфрий согласился. Кто бы игру ни начинал, Онуфрий не выиграл ни разу. Баба Яга была в восторге и радостно указала Онуфрию путь домой!
Какую хитрость знала Баба Яга? Как она должна была играть, чтобы победить в любом случае?
Малыш и Фрекен Бок играют в игру. На столе лежат конфеты. Первым ходом Малыш делит конфеты на три не пустых кучки, потом Фрекен Бок две кучки отдает Карлсону, а третью снова делит на три не пустых, потом Малыш также две отдает Карлсону, третью делит и так далее. Кто не сможет сделать ход проигрывает. Кто победит при верной игре, если на столе: а) 7конфет? б) 9 конфет? в)12 конфет? г) 14 конфет? «Поставь на ноль».Возьмём полоску клетчатой бумаги и занумеруем клетки числами 0, 1, 2, …, 14. На одной из 15 – ти клеток стоит фишка. Двое игроков по очереди передвигают фишку влево на 1, 2, 3 или 4 клетки. Проигрывает тот, кому некуда ходить.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
ИГРА БОШЕ
На столе лежат 15 спичек. Два игрока берут поочерёдно со стола спички. За один ход игрок может взять 1, 2 или 3 спички. Выигрывает тот, кто берёт последнюю спичку.
Игра датПервый игрок сообщает какую–нибудь дату января. Каждый игрок на своём ходе называет более позднюю дату, увеличивая каждый раз или календарную дату в месяце, или порядковый номер месяца, но не то и другое одновременно. Первый, кто доберётся до 31 декабря, выигрывает.
