Теория игр

13

Федеральное государственное образовательное учреждение среднего профессионального образования

«Омский промышленно-экономический колледж»

Курсовая работа

по дисциплине "Программирование"

Тема: "Теория игр, их программирование"

Выполнил:

Каримов Руслан Ринатович

3 курс, БП 2 - 117

Руководитель:

Белгородцева Наталья Александровна

2010

Содержание

Введение

1. Основные понятия теории игр

2. Игры с противодействием и нулевой суммой

3.Графический метод решения игровых задач с нулевой суммой

3.1 Решение задач графическим методом

4. Общий метод решения игровых задач с нулевой суммой

5. Игры с природой (без противодействия)

5.1 Решение задач

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

Введение

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

Организация современного производства требует не только наличия современных станков и оборудования, но и разработки новых технологических процессов и современных методов управления производством. Для решения каждой из поставленных задач разрабатываются математические модели, анализируя которые удаляются найти наилучшее решение поставленной задачи. Создание математической модели - сложная кропотливая работа, которая в современных условиях под силу коллективам разработчиков. Для создания математической модели одного и того же объекта различные коллективы могут использовать различный математический аппарат. После создания математической модели специалистами-аналитиками за дело принимаются специалисты-программисты, которые реализуют созданную модель в виде программных кодов. Далее с математической моделью работают специалисты-практики. Целенаправленно воздействуя на модель, они изучают ее поведение и подбирают оптимальный режим работы для реального объекта. Одной из таких моделей является игровая модель и поиск стратегий поведений в условиях полной или частичной неопределенности. В очень редких (исключительных) случаях для игровых моделей можно определить количественную оценку или указать оптимальное решение. В игровых моделях не ставиться задача найти какое-то числовое решение, а требуется лишь или очертить область возможных решений, или предоставить некоторые дополнительные сведения о возможном развитии событий и рекомендовать правила поведения. Результаты исследования модели носят рекомендательный характер, позволяют ориентироваться в сложившейся ситуации и принять правильное решение.

1. Основные понятия теории игр

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

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

Развитие игры во времени представляет как ряд последовательных «ходов». Ходы могут быть сознательные и случайные. Случайный ход - результат, получаемый не решением игрока, а каким либо механизмом случайного выбора (покупательский спрос, задержка с поставкой материалов и т.п.). Сознательный ход - выбор игроком одного из возможных вариантов действия (стратегий) и принятие решения о его осуществлении.

Конфликтная же ситуация, строго говоря, развивается спонтанно.

Участниками игры (конфликтной ситуации) могут быть минимум два человека (парная игра) или несколько человек (множественная игра). Игра развивается по оговоренным правилами. Игроки по очереди делают свои ходы. Естественно, перед каждым ходом игрок может или сохранить предыдущую стратегию или применить новую стратегию. Если игрок при выборе очередного хода придерживаются каких-либо правил, то такая игра носит название стратегической. Однако игрок во время игры может менять вариант своего поведения (но не правил), т.е. сменить стратегию. Возможны варианты (исходы) игры сводятся в прямоугольную таблицу (табл. 1) - платежную матрицу, в которой строки соответствуют различным стратегиям игрока А, столбцы - стратегиям игрока В, a_{i j} называется ценной игры.

Таблица 1. - Возможные исходы игры

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

Стратегия, приносящая игроку максимальный выигрыш, называется оптимальной. Для нахождения оптимальной стратегии необходимо проанализировать все возможные стратегии и рассчитывать на то, что разумный противник на каждую из них будет отвечать такой, при которой выигрыш игрока А минимален. Обычно минимальные числа в каждой строке обозначаются Ь_i и выписываются в виде добавочного столбца матрицы (табл. 2). В каждой строке будет свое Ь _i = min a_ij . Предпочтительной для игрока А является стратегия, при которой Ь _i обращается в максимум, т.е.

Ь = max (min a_ij),

где Ь - максимальный выигрыш (максимин).

Если придерживаться максиминной стратегии, то при любом поведении стороны В (конкурента) гарантирован выигрыш, во всяком случае не меньше Ь. Поэтому Ь называют также ценной игры - тот гарантированный минимум, который можно обеспечить при наиболее осторожной (перестраховочной) стратегии. Очевидно, что аналогично распределения можно провести и для конкурента В, который должен рассмотреть все свои стратегии, выделяя для каждой из них максимальные значения выигрыша: в = min (max a_ij), которое дает минимаксный выигрыш, или минимакс.

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

Если Ь = в = С, то число С называют чистой ценной игры или седловой точкой.

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

Таблица 2. - Добавочный столбец матрицы

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

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

2. Игры с противодействием и нулевой суммой

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

Пусть фирма А разработала четыре стратегии, а фирма В - пять стратегий.

То есть фирма А - a₁; a₂; a₃; a₄ a_i , где i = 1,m.

Фирма В соответственно - b₁; b₂; b₃; b₄ b_j , где j = 1,n.

Каждая фирма от реализации своей стратегии предполагает получить какой-то доход (табл. 3).

Таблица 3. - Стратегии каждой игры и доходы

Если фирма А выберет первую стратегию, то минимальный доход составит 4. Минимальный доход от второй стратегии - 1; от третьей - 2; от четвертой - 3. У фирмы В имеется в наличии пять стратегий. Использование первой стратегии обернется убытком в 1 единицу; второй (убыток) - 4; третьей - 3 и четвертой - 2.

На первый взгляд фирма А должна избрать вторую стратегию (А₂), чтобы получить выигрыш 10, но в ответ вторая фирма изберет первую стратегию (В₁) и выигрыш фирмы А составит только 1. Поэтому можно сформулировать так: получит максимальный доход из возможных минимальных. Введем в (табл. 3) дополнительную строку и дополнительный столбец, в которых укажем возможные минимальные прибыли и убытки (табл. 4).

Таблица 4. - Минимальные прибыли и убытки

Исходя из данных (табл. 3) фирме А надо придерживаться стратегии А₁ , а фирме В - стратегии В₁ . Таким образом, гарантированный минимальный доход фирмы А составит 4, а минимально возможный доход, который отдаст фирма В, составит 5 (минимально возможный выигрыш).

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

Минимально возможный проигрыш называется верхней ценной игры.

Для нашего примера нижняя граница игры составляет 4 (минимальный гарантированный выигрыш фирмы А), а верхняя граница игры - 5 (минимально возможный проигрыш фирмы В). Приведенные выше рассуждения хороши, если конкурирующая фирма заранее не знает, как себя поведет противник. Если конкурирующая фирма ознакомлена с планами конкурента, то она может выбрать другую стратегию (отличную от осторожной стратегии) и получить больший выигрыш (доход). Таким образом, приведенные осторожные стратегии являются неустойчивыми по отношению к дополнительной информации.

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

Таблица 5. - Задача с седловой точкой представлена.

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

Если игровая задача не имеет седловой точки, то на практике конкурирующие фирмы (игроки) используют смешанные стратегии, т.е. попеременно используют две или более стратегий. В этом случае использование фирмой А нескольких стратегий можно записать как сумму вероятностей использования каждой стратегии S_a= p₁+ p₂+ …+ p_n .

Соответственно, использование нескольких стратегий фирмой В можно записать S_b= q₁+ q₂+ …+ q_m . Поэтому в общем случае исследование игровой модели сводиться к определению вероятностей использования конкретных стратегий каждой фирмой (игроком).

3. Графический метод решения игровых задач с нулевой суммой

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

Воспользуемся (табл. 3). Строка (стратегия) А₁ является доминирующей по отношению к строке (стратегии) А₄ , так как содержит элементы, большие соответствующих элементов строки А₄. Строка А₄ является поглощаемой и из дальнейшего рассмотрения удаляется (табл. 6).

Таблица 6.- Первый шаг упрощения таблицы

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

Таблица 7. - Второй шаг упрощения таблицы

Еще раз рассматриваем строки. Первая строка поглощает третью строку. Поглощаемые строки (столбцы) содержат самые плохие стратегии. Окончательно получим (табл. 8).

Таблица 8. - Третий шаг упрощения таблицы

Вероятность использования первой фирмой первой стратегии обозначим через p₁ . Тогда вероятность использования второй стратегии вторым игроком будет p₂ = 1- p₁ . Ожидаемый выигрыш фирмы А от применения первой стратегии составит:

a₁₁* p₁ + a₂₁* p₂ = a₁₁* p₁ + a₂₁(1- p₁) = a₁₁* p₁ + a₂₁ - a₂₁* p₂ = (a₁₁ - a₂₁)* p₁ + a₂₁ (1)

Аналогичным способом получим ожидаемый выигрыш фирмы А от применения второй стратегии:

(a₁₂ - a₂₂)* p₁ + a₂₂ (2)

В выражения (1) и (2) подставим конкретные значения.

(a₁₁ - a₂₁)* p₁ + a₂₁ = (5 - 1) p₁ + 1 = 4 p₁ + 1;

(a₁₂ - a₂₂)* p₁ + a₂₂ = (4 - 6) p₁ + 6 = -2 p₁ + 6.

На оси х отложим две точки 0 и 1. Через эти точки проведем прямые линии, параллельные оси у. Затем в первое выражение подставим 0 вместо p₁ , а потом - единицу. И по двум точкам построим прямую линию.

Аналогично построим вторую прямую линию. Пересечение двух прямых линий и ласт решение задач (рис. 1).

Рис. 1. - Графический способ определения стратегий фирмы А

(a₁₁ - a₁₂)* у₁ + a₁₂ = (5 - 4) у₁ + 4 = у₁ + 4;

(a₂₁ - a₂₂)* у₁ + a₂₂ = (1 - 6) у₁ + 6 = -5 у₁ + 6.

Итак, вероятность использования первой стратегии фирмой А составляет 0,83 (p₁ = 0,83), а второй стратегии - соответственно 0,17 (p₂ = 0,17).

Аналогично определим оптимальную стратегию поведения фирмы В:

Рис. 2. - Графический способ определения стратегий фирмы В

Вероятность использования первой стратегии фирмой В составляет 0,33 (у₁ = 0,33), а второй стратегии - соответственно 0,67 (у₂ = 0,67).

3.1 Решение задач графическим методом

Пример 1:Рассмотрим игру заданной платежной матрицей:

Решение:

Проверим если ли седловая точка:

Ь = max (min (2,2,3,2)) = 3

в = min (max (7,6,6,4,5)) = 4 Ь ? в

седловой точки нет, игра в чистой стратегии не решается. Найдем смешанную стратегию игроков. Посмотрим можно ли удалить не выгодную стратегию для игроков. Для первого игрока считается та стратегия не выгодная, которая обеспечивает выигрыш меньший чем какая либо другая; Для второго игрока считается та стратегия не выгодная которая обеспечить проигрыш больше чем другая стратегия.

Список литературы

1. « Математические методы в программировании » : / Агальцов В.П., Волдайская И.В. Учебник : - М . : ИД «ФОРУМ» : ИНФРА-М, 2006. - 224с. : ил. -(Профессиональное образование). - (Учимся программировать).