23 страниц
61% уникальность
2013 год
79 просмотров
Хотите узнать стоимость докторской диссертации в Кемерово ? Заходите на Work5.
. Нет математической теории, которая могла бы дать алгоритм любой реальной игры, но существуют ситуации, подобные игровыми допускающие математический анализ. Классификация игр Остановимся на классификации игр. Интересы участников игры (игроков) могут оказаться несовпадающими и даже противоположными. В последнем случае игра называется антагонистической. В игре могут участвовать два или более игроков. Случай игры с одним участником (пасьянс, управление физическим объектом и т.д.) в сущностиявляется игрой двух лиц, где вторым участником выступает природа (судьба, рок, провидение). Игроки могут в игре выступать каждый за себя или объединяться в группы. В последнем случае игра называется коалиционной. Игры, в которых игроки осведомлены о состоянии своем и партнеров, а также о прошлом поведении участников игры, относятся к категории игр с полной информацией(типичные примеры - шахматы, "крестики-нолики" и т.п.). Большинство же игр протекает в условиях неполной информации, где сведения о состоянии партнеров исчерпываются лишь вероятностными характеристиками (домино, карточные игры, игры против "природы"). Антагонистическую игру, где выигрыш одного коллектива равен проигрышу другого, называют игрой с нулевой суммой. Система правил, однозначно определяющая выбор хода игрока в зависимости от сложившейся ситуации, называется стратегией. Каждая фиксированная стратегия игрока, где любой ситуации сопоставлен конкретный выбор, называется чистой. В реальности чаще используются т.н. смешанныестратегии, где чистые стратегии смешиваются с некоторыми частотами. Простейшими являются игры 2 лиц с нулевой суммой. Пусть в такой игре игрок 1 имеет m выборов и игрок 2 - n выборов. Если игрок 1 делает свой i-й выбор, а игрок 2 - свой j-й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен Rij. Такая игра называется матричнойи матрица R =[ Rij/ i=1..m , j=1..n ] называетсяматрицей выигрышей(платежной матрицей). При ведении игры игрок должен ориентироваться на оптимальную политику партнера и наказывать его за отступления от таковой. Проведем рассуждения за игрока 1. Если Я воспользуюсь i-м выбором, мой противник для минимизации моего выигрыша сделает тот из своих выборов, который даст minRij. Соответственно, Я должен использовать тот выбор, который гарантирует мне выигрыш, не меньший [-- Image: Рисунок 4 --] Противник, рассуждая аналогично, приходит к выводу о гарантированном проигрыше, не превышающем [-- Image: Рисунок 5 --] Если в матрице выигрышей существует элемент Rkl= V1= V2, то говорят о наличии оптимальной политики "в пространстве чистых стратегий" и оптимальными выборами для игроков соответственно являются выборы k и l. Пару (k, l) называют седловойточкой. Пример 1.Пусть игра определяется матрицей [-- Image: Рисунок 6 --] Седловыеточки - (4, 1) и (4, 2). Цена игры = 6; оптимальный выбор для игрока 1 - четвертый, для игрока 2 равнозначны первый и второй (под ценой игры понимают гарантированный выигрыш-проигрыш при оптимальной политике обоих игроков). Пример 2.Пусть игра определяется матрицей [-- Image: Рисунок 7 --] Здесь равенство V1= V2не выполняется; оптимальной чистой стратегии для игроков нет. При анализе игр часто прибегают к попыткам обнаружить доминирование между строками и столбцами. Так в примере 1 элементы четвертой строки больше элементов других строк: использование выбора 4 выгоднее других выборов при любой политике противника. Противник видит, что в такой ситуации использовать выборы 3 и 4 неразумно. Использование доминирования т.о. позволяет уменьшить размеры изучаемой матрицы исключением "невыгодных" строк и столбцов. При отсутствии седловойточки среди чистых стратегий приходится искать таковую среди смешанных. Если игрок 1 прибегает к своему выбору i с вероятностью Pi, а игрок 2 - к своему j-мувыбору с вероятностьюQj, то ожидаемый выигрыш игрока 1 (проигрыш игрока 2) равен [-- Image: Рисунок 8 --] Основная теорема теории игр (теорема Джона фон Неймана) утверждает, что любая матричная игра с нулевой суммой всегда имеет седловуюточку, т.е. существуют векторы P и Q такие, что [-- Image: Рисунок 9 --] (V - цена игры). Матричные игры и линейное программирование Очевидно, что если игрок 1 отступит от оптимальной политики, а игрок 2 будет действовать оптимально, то выигрыш игрока 1 будет меньше цены игры, и если игрок 2 отступит от оптимальной политики при сохранении оптимального поведения игроком 1, то его проигрыш превысит цену игры: [-- Image: Рисунок 10 --] Рассуждения игрока 1: мне хотелось бы максимизировать цену игры, т.е. мой гарантированный выигрыш, и я должен подобрать систему значений Piтак, чтобы при любом выборе противника мой ожидаемый выигрыш был больше цены игры.
