Добро
пожаловать на наш сайт!
ПОЗНАНИЕ
ПРОДОЛЖАЕТСЯ...
15.04.2019 20:42 дата обновления страницы
Вещество и энергия. Числа и фигуры
Дата создания сайта:
08/12/2012
Дата создания
сайта: 08/12/2012 Дата обновления главной страницы:
15.04.2019 20:42
icq:
613603564
Теория игр
Так называется математическая теория конфликтов. А что такое конфликт?
Это - такая ситуация (положение, стечение обстоятельств), в которой
сталкиваются интересы сторон, происходит борьба интересов. Примеры
конфликтов есть в самых разных областях: в военном деле, в экономике, в
спортивных состязаниях.
Самые простые примеры конфликтов - игры (шашки, шахматы, различные
спортивные игры). Они отличаются тем, что ведутся по правилам,
обусловливающим образ действий игроков и исход игры в зависимости от их
действий.
Теория игр ставит и решает следующий вопрос: как должен вести себя
(какую стратегию применять) разумный игрок в конфликте с разумным
противником, чтобы обеспечить себе в среднем наибольший возможный
выигрыш?
Интересы участников конфликта противоречивы, каждый из них принимает все
меры к тому, чтобы обеспечить лучшее положение себе и худшее - своему
противнику. В итоге борьбы интересов, если оба противника одинаково
разумны, по-видимому, должно быть найдено некоторое равновесное
положение, при котором каждый игрок получит то, что ему причитается,- не
больше и не меньше. Решить игру - это и значит найти такое равновесное
положение, т. е. пару разумных (оптимальных) стратегий, дальнейшее
улучшение которых уже невозможно, и указать, какой при этих стратегиях
выигрыш (или проигрыш) должен достаться каждому игроку.
Если результат зависит не только от стратегий, но и от случайности (как,
например, бывает при сдаче карт), нужно говорить не о результате каждой
отдельной партии, а о среднем результате, приходящемся на одну партию
при многократном повторении игры.
Чтобы представить себе своеобразие игровых задач, рассмотрим простенький
пример.
Игра <Поиск>. В игре участвуют двое: игрок К (<красные>) и игрок С
(<синие>), К должен найти С, а С, наоборот, прячется от К. У С есть два
убежища - 1 и 2, он может выбрать любое из них по своему усмотрению. К,
в свою очередь, может искать С в
любом из этих убежищ. Если К искал С в убежище 1 и нашел его, С платит К
штраф 1 очко, если же искал и не нашел - наоборот, К платит С штраф в 1
очко. Для убежища 2 условия аналогичные, но размер штрафа - 2 очка.
Требуется решить задачу, т. е. найти оптимальные стратегии участников и
соответствующий этим стратегиям выигрыш (проигрыш) каждого игрока.
Давайте порассуждаем за наших игроков. Так как каждый из них выигрывает
то, что
проигрывает другой, то выигрыши их равны по величине и противоположны по
знаку. Поэтому нет смысла рассматривать выигрыши обоих - достаточно
заняться выигрышем одного из игроков (пусть это будет К). Запишем
правила игры в виде таблицы (матрицы), где будут указаны возможные
стратегии игроков и соответствующий каждой паре стратегий выигрыш игрока
К (он же - проигрыш С).
У <красных> две стратегии: К\ - искать в убежище 1, Ко - искать в
убежище 2.
У <синих> тоже две стратегии: С1 - прятаться в убежище 1, С2 - прятаться
в убежище 2.
Условия игры записаны в матрице (см. ниже), где для каждой пары
стратегий <красных> и <синих> приведен результат - выигрыш <красных>:
Эта матрица полностью исчерпывает условия игры.
Нам надо дать рекомендации каждому из игроков: как себя вести в данной
игре. Давайте сначала подумаем за К. Если он примет стратегию К\ (т. е.
будет искать С только в убежище 1), его разумный противник С через
несколько партий игры догадается об этом и станет всегда прятаться в
убежище 2. Выигрыш К при этом равен- 1, т. е. он будет систематически
проигрывать одно очко. Плохо!
Давайте попробуем вторую стратегию - К2. Опять плохо! Если К захочет все
время искать в убежище 2, умный С догадается об этом и начнет прятаться
в убежище 1. При этом К будет систематически проигрывать 2 очка. Из огня
да в полымя!
Нашему К обидно все время проигрывать. <А если, - думает он, - менять
свою стратегию: один раз искать в убежище 1, а другой - в убежище 2?> Но
ведь умный С
и об этой попеременной стратегии тоже может догадаться после первых же
партий, и снова К придется плохо... Он будет проигрывать : одну игру -
очко, другую - два очка. <Нет уж, - думает К, - если проигрывать, то
лучше поменьше. Дай-ка выберу я стратегию К\\ Пользуясь ею, я уж во
всяком случае больше одного очка не проиграю...>
Тот осторожный принцип, который сейчас положил К в основу своего выбора,
в теории игр называется принципом мини-макса. Смысл его следующий: в
игре с разумным противником старайся, чтобы твой выигрыш даже при
наихудшем для тебя его поведении был наибольшим. Зная, что противник
разумен, надо при обсуждении каждой стратегии рассчитывать на
минимальный в данной строке выигрыш и выбрать ту стратегию, при которой
этот минимальный выигрыш - максимален. Для этого сбоку от матрицы
выписывается дополнительный столбец, в котором ставятся минимумы строк:
Максимальный из этих минимумов (мак-симин) отмечается звездочкой (в
нашем примере он равен -1). Стратегия К соответствующая максимину, и
является наиболее осторожной (максиминной) стратегией <красных>.
Конечно, К недоволен - ему не хочется каждую игру проигрывать очко, но
что поделаешь... Другого выхода пока не видно!
Однако не будем торопиться. Попробуем теперь стать на точку зрения С. Не
забудьте, что он хочет отдать поменьше, поэтому, просматривая свои
стратегии, он должен в каждом столбце ориентироваться на самый
неприятный для него максимальный выигрыш К (рассуждая в той же
последовательности, как выше рассуждал К). Запишем внизу матрицы
дополнительную строку, где будут приведены максимумы столбцов. Отметим
звездочкой минимальный из них (минимакс). В данном случае он равен 1, и
ему соответствует стратегия С \ (минимаксная стратегия <синих>).
Что же у нас получилось? Исходя из осторожного принципа минимакса, мы
вынуждены рекомендовать <синим> стратегию С\: прятаться в убежище 1! Но
ведь <синие> при этом неизбежно будут проигрывать! Как же так? Ведь мы
только что убедились, что неизбежно проигрывать должны <красные>?!
Удивительно! Оказывается, для <синих> игра тоже невыгодна...
Давайте, впрочем, подумаем: образуют ли две найденные нами стратегии К i
и С\ решение игры? Предположим, что обе стороны
придерживаются этих стратегий. При этом К выигрывает 1 очко. Как вы
думаете, является ли это положение равновесным? Очевидно, нет, потому
что игрок С, узнав, что К пользуется стратегией К немедленно перейдет на
Сг и будет выигрывать 2 очка. В свою очередь, узнав об этом, хитрый К
перейдет на стратегию К2 и будет выигрывать 2 очка, и так далее... Уж
какое тут равновесие! Обоим все время приходится менять стратегии, и
совершенно неизвестно, чем все это кончится-
Значит, мы с вами не нашли решения игры. Может быть, его вообще не
существует?
Нет, решение существует, но, как говорят в теории игр, не в чистых
стратегиях, а в смешанных. Смешанной называется такая стратегия, при
которой игрок применяет не одну, а две или больше стратегий, чередуя их
случайным образом.
Почему нужно чередовать стратегии именно случайным (а не закономерным)
образом? А потому, что любое закономерное чередование стратегий может
быть разгадано умным противником, а случайное - нет! Поди догадайся,
какую стратегию применит | противник в очередной партии игры, если он и
сам этого не знает!
С помощью теории игр можно найти решение игры <Поиск>. Оно состоит в
следующем: игрок К должен применять свою стратегию К1 с частотой 2/3 (т.
е. в среднем в 2/з всех случаев искать противника в убежище 1, а в '/з
всех случаев искать в убежище 2). Что касается игрока С, то он должен
одинаково часто прятаться как в первом, так и во втором убежищах... При
этом равновесный выигрыш К будет равен нулю, т. е. игра будет одинаково
выгодна или невыгодна для обеих сторон. Не оеньто приятно, но все же
лучше, чем на каждую игру терять очко, верно?
В разобранном примере решение оказалось в смешанных стратегиях. Всегда
ли это будет так? Нет, не всегда. Рассмотрим другой пример.
Игра <Два числа>. Два игрока К и С одновременно, не видя друг друга,
записывают на бумаге каждый одно из трех чисел: 1, 2 или 3. Если оба
запишут одинаковые нечетные числа, К выигрывает 5 очков, если одинаковые
четные - одно очко. Если К и С напишут разные нечетные числа, К
проигрывает 3 очка; если К напишет четное число,
Игра "Два числа"
а С - нечетное, то К выигрывает 3 очка; если наоборот, С напишет четное,
а К нечетное, то К проигрывает одно очко. Условия игры записаны в
матрице:
Сбоку и снизу выписаны минимумы строк и максимумы столбцов. Минимакс и
максимин отмечены звездочками. Оказывается, в данном примере минимакс
равен максимину! Случай особый...
Действительно, рассмотрим пару минимаксных стратегий ДГ2 и Эти стратегии
образуют равновесную пару и, значит, дают решение игры. Пока оба игрока
держатся таких стратегий, выигрыш К будет равен 1 очку. Посмотрим, может
ли С улучшить свое положение, отступая от стратегии ее? Очевидно, нет!
Что бы он ни делал, его проигрыш может только увеличиться. И наоборот,
если С держится своей стратегии Сг, то К никакими усилиями не может
увеличить свой выигрыш. Значит, мы нашли решение игры - пару чистых
стратегий Ki и С2 и равновесный выигрыш К - 1 очко, отражающий
объективное преимущество К над С в данной игре.
Почему так получилось? Потому что в матрице имеется особый элемент 1,
который является одновременно максимином и мини-
максом: он минимален в своей строке и одновременно максимален в своем
столбце. Такой элемент называется седловой точкой. Если матрица игры
имеет седловую точку, игра имеет решение в чистых стратегиях.
Класс игр, имеющих седловую точку, занимает важное место в теории игр. К
этому классу принадлежат, в частности, так называемые игры с полной
информацией, в которых каждый игрок перед любым ходом полностью знает
все предыдущие ходы, как свои, так и противника, и их результаты.
Оказывается, каждая игра с полной информацией имеет седловую точку и,
значит, решение в чистых стратегиях. И как только такое решение будет
найдено, игра теряет смысл, потому что ее исход предрешен!
А как же,- спросите вы,- шашки, шахматы? Это ведь тоже игры с полной
информацией?
Совершенно верно! Теоретически доказано, что каждая из них имеет решение
в чистых стратегиях, т. е. существует определенный образ действий для
каждой стороны, пользуясь которым (в борьбе с разумным противником),
можно всегда свести игру к определенному концу. Будет ли это всегда
выигрыш белых, или всегда - черных, или всегда - ничья, мы пока еще не
знаем, потому что число стратегий в шахматной игре слишком велико, чтобы
можно было построить матрицу и найти в ней седловую точку...
Наверное, любители шахмат заинтересованы в том, чтобы шахматная игра
была решена еще не скоро!
Е.С. Вентцель
Размещение фотографий и
цитирование статей с нашего сайта на других ресурсах разрешается при
условии указания ссылки на первоисточник и фотографии.
