Нелинейное программирование Практическое занятие 6

Тема занятия Антагонистические игры

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

Основные понятия Конфликтные ситуации –Это ситуации в которых сталкиваются интересы двух или более сторон, преследующих различные цели –Любой шаг каждой из сторон зависит от того какой образ действий выберет противник

Основные понятия Теория игр –Это математическая теория конфликтных ситуаций –Задача теории – выработка рекомендаций по рациональному образу действий участников конфликта

Основные понятия Игра –Это упрощенная, схематизированная модель ситуации –От реальной конфликтной ситуации игра отличается тем, что ведется по определенным правилам

Основные понятия Игры бывают –Парными – когда в игре сталкиваются интересы двух противников –Множественными - более двух противников Мы будем рассматривать только первые

Основные понятия Игра с нулевой суммой –Это такая игра, когда один игрок выигрывает ровно столько, сколько проигрывает второй Мы будем рассматривать только такие игры

Основные понятия Ход –Ходом в теории игр называется выбор одного из предусмотренных правилами игры действий и его осуществление. –Развитие игры во времени состоит из последовательности ходов.

Основные понятия Ходы бывают –Личные Это сознательный выбор игроком одного из вариантов действий и его осуществление –Случайные Выбор осуществляется не решением игрока, а каким- либо механизмом случайного выбора Теория игр занимается анализом игр, содержащих только личные ходы

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

Основные понятия В зависимости от числа возможных стратегий игры делятся на –Конечные У каждого игрока имеется конечное число стратегий –Бесконечные Хотя бы у одного игрока число стратегий бесконечно

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

Платежная матрица Рассмотрим конечную, парную игру двух игроков А и В, в которой игрок А имеет m стратегий, а игрок В n A i возможные стратегии игрока А B j возможные стратегии игрогка В a i,j выигрыш игрока А (проигрыш игрока В) B1B1 B2B2 …BnBn A1A1 a 11 a 12 …a 1n A2A2 a 21 a 22 …a 2n …………… AmAm a m1 a m2 …a mn BjBj AiAi

Пример Игра «поиск» –Имеется два игрока А и В. Первый прячется, второй его ищет. Прятаться можно только в двух местах, любое из которых игрок А выбирает по своему усмотрению. –Если при очередном ходе игрок А спрятался в одном из мест, и игрок В его нашел, то В получает 1 рубль игрок В его не нашел, то А получает 1 рубль

Игра «поиск» Решение –Игра состоит из двух ходов, оба – личные –У игрока А две стратегии Прятаться в месте 1 Прятаться в месте 2 –У игрока В тоже две стратегии Искать в месте 1 Искать в месте 2

Игра «поиск» Решение –Имеем игру 2х2. –Платежная матрица: B1B1 B2B2 A1A1 A2A2 BjBj AiAi

Игра «поиск» Решение –Имеем игру 2х2. –Платежная матрица: B1B1 B2B2 A1A1 1 A2A2 1 BjBj AiAi

Основные понятия Смешанная стратегия –Это такая стратегия в которой, отдельные «чистые» стратегии чередуются случайным образом с какими-то вероятностями. –При использовании смешанных стратегий перед каждым ходом путем механизма случайного выбора обеспечивается появление каждой стратегии с некоторой вероятностью.

Смешанные стратегии Обозначение смешанных стратегий –Пусть имеется игра в которой игрок А имеет m стратегий ( A 1, A 2,…, A m ), а игрок В - n ( B 1, B 2,…, B n ) S A =(p 1,p 2,…,p m ) –Обозначение смешанной стратегии игрока А, в которой стратегии A 1, A 2,…, A m применяются с вероятностями p 1,p 2,…,p m –Причем p 1 +p 2 +…+p m =1

Смешанные стратегии Обозначение смешанных стратегий S B =(q 1,q 2,…,q n ) –Обозначение смешанной стратегии игрока, где q 1 +q 2 +…+q n =1

Игра «три пальца» –Игроки А и В одновременно и независимо друг от друга показывают один два или три пальца. –Выигрыш (в рублях) равен общему числу показанных пальцев: Если оно четное – выиграл игрок А Если оно нечетное – выиграл игрок В

Игра «три пальца» Решение –Имеем игру 3х3. –Платежная матрица: B1B1 B2B2 B3B3 A1A1 A2A2 A3A3 BjBj AiAi

Игра «три пальца» Решение –Имеем игру 3х3. –Платежная матрица: B1B1 B2B2 B3B3 A1A A2A2 4-5 A3A3 4 6 BjBj AiAi

Пример Игра «вооружение и самолет» –В нашем распоряжении имеется три вида оружия, а у противника три вида самолетов Первым оружием самолеты поражаются с вероятностями соответственно 0,5; 0,6 и 0,8 Вторым - соответственно 0,9; 0,7 и 0,8 Третьим - соответственно 0,7; 0,5 и 0,6 –Наша задача – поразить самолет, задача противника – сохранить его непораженным

Игра «вооружение и самолет» Решение –Имеем игру 3х3. –Платежная матрица: B1B1 B2B2 B3B3 A1A1 0,50,60,8 A2A2 0,90,70,8 A3A3 0,70,50,6 BjBj AiAi

Нижняя и верхняя цена игры Принцип минимакса Рассмотрим игру m х n Как определить наилучшую из стратегий игрока А? Проанализируем все возможные стратегии A i Выбирая A i мы должны рассчитывать, что противник ответит на нее той, из своих стратегий В i, для которой наш выигрыш минимален B1B1 B2B2 …BnBn A1A1 a 11 a 12 …a 1n A2A2 a 21 a 22 …a 2n …………… AmAm a m1 a m2 …a mn BjBj AiAi

Нижняя и верхняя цена игры Принцип минимакса Найдем минимальной из чисел a ij в i –й строке и обозначим его a i : i =min a ij Действуя наиболее осторожно мы должны предпочесть ту стратегию, для которой i максимально: =max i j i

Нижняя и верхняя цена игры Принцип минимакса Объеденив обе формулы, получим : =max min a ij Величина называется нижней ценой игры, максиминным выигрышем или максимином. Стратегия игрока А, соответствующая максимину называется максиминной стратегией. j i

Нижняя и верхняя цена игры Принцип минимакса Рассуждая аналогично для игрока В : =min max a ij Величина называется верхней ценой игры, минимаксным выигрышем или минимаксом. Стратегия игрока B, соответствующая минимаксу называется минимаксной стратегией. i j

Пример Найти верхнюю и нижнюю цены в играх –«Поиск» –«Три пальца» –«Вооружение и самолет»

Игра «поиск» Решение – =? B1B1 B2B2 i A1A1 1 A2A2 1 j BjBj AiAi

Игра «поиск» Решение – =? B1B1 B2B2 i A1A1 1 A2A2 1 j 11 BjBj AiAi

Игра «поиск» Решение – =-1 – =1 B1B1 B2B2 i A1A1 1 A2A2 1 j 11 BjBj AiAi

Игра «три пальца» Решение – =? B1B1 B2B2 B3B3 i A1A A2A2 4-5 A3A3 4 6 j BjBj AiAi

Игра «три пальца» Решение – =-3 – =4 B1B1 B2B2 B3B3 i A1A A2A2 4-5 A3A3 4 6 j 446 BjBj AiAi

Игра «вооружение и самолет» Решение – =? B1B1 B2B2 B3B3 i A1A1 0,50,60,8 A2A2 0,90,70,8 A3A3 0,70,50,6 j BjBj AiAi

Игра «вооружение и самолет» Решение – =0,7 B1B1 B2B2 B3B3 i A1A1 0,50,60,80,5 A2A2 0,90,70,80,7 A3A3 0,50,60,5 j 0,90,70,8 BjBj AiAi

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

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

Решение игры В общем случае решением игры называется пара оптимальных смешанных стратегий S A *, S B *, обладающих следующим свойством: –Если один игрок придерживается своей оптимальной стратегии, то другому не выгодно отклоняться от своей оптимальной стратегии. Каждая конечная игра имеет по крайней мере одно решение, возможно, в области смешанных стратегий

Основные понятия Активные стратегии –Это те стратегии игроков, которые входят в его оптимальную смешанную стратегию с отличными от нуля вероятностями

Тема следующего занятия Статистические игры с единичным экспериментом

Спасибо за внимание