Станем сначала на сторону К.
ЭЛЕМЕНТЫ ТЕОРИИ ИГР
Во многих практических задачах возникают ситуации, когда требуется принять решение, не имея достаточной информации.
Неизвестными могут быть как условия осуществления какой-либо операции, так и сознательные действия лиц, от которых зависит успех этой операции.
Основные определения
— Ситуации, в которых сталкиваются интересы двух сторон и результат любой операции, осуществляемой одной из сторон, зависит от действий другой стороны, называются конфликтными
— Математическая модель конфликтной ситуации называется игрой, аматематическая теория, помогающая принимать рациональные решения в конфликтной ситуации, - теорией игр
— Конфликтующие стороны называются игроками,а действия, которые могут выполнять игроки, - стратегиями.
Матричной игрой называется игра, осуществляемая по следующим правилам:
1. В игре участвуют два игрока
2. Каждый из игроков обладает конечным набором стратегий
3. Игра заключается в том, что каждый из игроков, не имея информации о действиях противника, делает один ход (выбирает одну из своихстратегий). Результатом выбора игроками стратегий является выигрыш и проигрыш в игре.
4. И выигрыш, и проигрыш выражаются числами
— Матричная игра называется игрой с нулевой суммой, если в этой игре выигрыш одного игрока равняется проигрышу другого игрока
— Ход игры – этап в развитии игры, а именно выбор одним из участников варианта развития игры в рамках правил данной игры. Ходы могут быть личными и случайными.
— Цель игры – поиск оптимальной стратегии, т.е. стратегии которые при многократном повторении обеспечит игроку максимально возможный средний выигрыш и минимально возможный средний проигрыш
— Каждая матричная игра с нулевой суммой имеет платежную матрицу
— Для того чтобы построить эту матрицу, обозначим одного из игроков символом A, а другого - символом B, и предположим, что А1, А2 ,…, Аm – стратегии, которые может применять игрок А, а B1 ,B2 ,…, Bn - стратегии, которые может применять игрок B
— Матричная игра, в которой у игрока A имеется m стратегий, а у игрока B - n стратегий, называется игрой типа mxn
Матрица C: cij (i =1,...,m; j =1,...,n) - выигрыши игрока A (и проигрыши игрока B) при применении игроками стратегий Аi и Bj соответственно. C - платежная матрица игры
Нижняя и верхняя цена игры (принцип минимакса)
Игрок А, выбирая стратегию с номером i, понимает что игрок В, в свою очередь, ответит на нее той из стратегий, согласно которой выигрыш игрока А будет минимальным. Поэтому в каждой строке платежной матрицы выбирается минимум.
Из этих минимумов игрок А выберет максимум, тем самым определит для себя оптимальную стратегию. Полученное число называется максиминным или нижней ценой игры.
Игрок В, в свою очередь выбирая стратегию, понимает, что его проигрыш не превысит максимального числа в фиксированном столбце. Согласно данной логике в каждом столбце мы выбираем максимальный элемент, а из этих максимумов мы выбираем минимум, это и будет верхняя цена игры.
Пример. Игра «Три пальца».
Два игрока К и С одновременно и не сговариваясь показывают друг другу один, два или три пальца. Если всего показанных пальцев (первым и вторым вместе) будет четное число, то выигрывает К: он получает столько очков, сколько всего было пальцев, если нечетное - выигрывает С, на тех же условиях. Требуется записать игру в нормальной форме.
Решение:
Перенумеруем стратегии по числу показанных пальцев. Игра 3x3. Матрица игры будет:
| C1 | C2 | C3 | |
| К1 | -3 | ||
| К2 | -3 | -5 | |
| К3 | -5 |
Пример игры с полной информацией.
Два игрока - К и С - поочередно кладут одинаковые монеты на круглый стол. Положение каждой монеты выбирается произвольно, лишь бы она не перекрывалась другими. Выигрывает тот из игроков, который положит монету последним (когда места для других уже не остается).
Стоит немножко подумать, чтобы убедиться, что исход этой игры всегда предрешен и что существует вполне определенная стратегия, гарантирующая выигрыш тому из игроков, который кладет монету первым (пусть это будет К). А именно К должен положить первую монету в центр стола, а далее на каждый ход С отвечать в точности симметричным относительно центра стола ходом! Бедный С может при этом вести себя как угодно, спасения ему все равно нет...
Очевидно, такая игра имеет смысл только для тех, кто не знает решения.
Любопытно, что совершенно так же обстоит дело и с такой популярной игрой, как шахматы! Эта игра имеет смысл только до тех пор, пока не найдено ее решение.
Теоретически доказано, что решение существует и исход шахматной игры в сущности предрешен: если каждая сторона будет пользоваться своей оптимальной стратегией, то игра либо всегда будет кончаться выигрышем белых, либо всегда выигрышем черных, либо всегда ничьей! Но чем же именно? Мы пока этого не знаем, так как число возможных стратегий слишком велико, чтобы можно было построить матрицу шахматной игры и найти в ней седловую точку...
Наверное, любители шахмат заинтересованы в том, чтобы шахматная игра была решена еще не скоро.
Заметим в заключение, что седловых точек в матрице может быть несколько; тог да решений игры в чистых стратегиях существует столько, сколько имеется седловых точек. Каждое из них дает выигрыш, равный цене игры.
Пример. Игра «Поиск».
В игре участвуют две стороны: К и С.
К хочет найти С; С, наоборот, хочет спрятаться от К.
У С есть два места — убежища I и II, где он может прятаться. Выбирает он себе любое убежище. Игрок К по правилам игры тоже может искать С, где ему вздумается.
Если он нашел С, С проиграл одно очко, если не нашел, т. е. пошел не в то убежище, где спрятался С, то, наоборот, К проиграл одно очко.
Требуется записать игру в нормальной форме.
Решение:
Для К - 2 стратегии: К1 - искать в убежище I, К2 - искать в убежище II.
Для С - тоже 2 стратегии: C1 - прятаться в убежище I, C2 -прятаться в убежище II.
Игра конечная - 2x2, матрица игры будет:
| C1 | C2 | |
| К1 | -1 | |
| К2 | -1 |
К этой игре мы еще вернемся в дальнейшем и найдем ее решение.
Порассуждаем за игрока К.
Выберем, например, К1, т.е. будем искать всегда в убежище I. Но тогда разумный противник через несколько партий догадается о нашей стратегии и будет прятаться там, где мы его не ищем, т.е. в убежище II. Плохо! Выберем стратегию К2. Ничуть не лучше: противник снова догадается и будет прятаться в убежище I. Что же нам делать?
Попробуем применять стратегии К1 и К2 попеременно, через одну партию игры. Но ведь противник и об этом может догадаться и будет прятаться каждый раз не там, где мы его ищем. Как ни кинь — все клин! Что же, значит, наше положение безвыходно?
Вопросы для самоконтроля
1. Что называется игрой?
2. Что называется матричной игрой?
3. Что называется матричной игрой типа mxn ?
4. Какая игра называется игрой с нулевой суммой?
5. Что называется нижней ценой игры?
6. Что называется верхней ценой игры?
7. Что называется ценой игры?
8. В чем состоит принцип минимакса?
9. Какая игра называется игрой с седловой точкой?
10. Что называется седловой точкой?
Используемая литература:
— Борзунова Т.Л., Барыкин М.П. , Данилов Е.А. Соловьева О.Ю. - Математическое моделирование: учебное пособие/ВолгГТУ, - Волгоград, 2008.
— Вентцель Е. С. Элементы теории игр. Изд. 2. М., Физматгиз, 1961. 68 стр. с черт. (Популярные лекции по математике).
— Конюховский П.В. Математические методы исследования операций в экономике – СПб: Питер, 2000.
ЭЛЕМЕНТЫ ТЕОРИИ ИГР
Во многих практических задачах возникают ситуации, когда требуется принять решение, не имея достаточной информации.
Неизвестными могут быть как условия осуществления какой-либо операции, так и сознательные действия лиц, от которых зависит успех этой операции.
Основные определения
— Ситуации, в которых сталкиваются интересы двух сторон и результат любой операции, осуществляемой одной из сторон, зависит от действий другой стороны, называются конфликтными
— Математическая модель конфликтной ситуации называется игрой, аматематическая теория, помогающая принимать рациональные решения в конфликтной ситуации, - теорией игр
— Конфликтующие стороны называются игроками,а действия, которые могут выполнять игроки, - стратегиями.
Матричной игрой называется игра, осуществляемая по следующим правилам:
1. В игре участвуют два игрока
2. Каждый из игроков обладает конечным набором стратегий
3. Игра заключается в том, что каждый из игроков, не имея информации о действиях противника, делает один ход (выбирает одну из своихстратегий). Результатом выбора игроками стратегий является выигрыш и проигрыш в игре.
4. И выигрыш, и проигрыш выражаются числами
— Матричная игра называется игрой с нулевой суммой, если в этой игре выигрыш одного игрока равняется проигрышу другого игрока
— Ход игры – этап в развитии игры, а именно выбор одним из участников варианта развития игры в рамках правил данной игры. Ходы могут быть личными и случайными.
— Цель игры – поиск оптимальной стратегии, т.е. стратегии которые при многократном повторении обеспечит игроку максимально возможный средний выигрыш и минимально возможный средний проигрыш
— Каждая матричная игра с нулевой суммой имеет платежную матрицу
— Для того чтобы построить эту матрицу, обозначим одного из игроков символом A, а другого - символом B, и предположим, что А1, А2 ,…, Аm – стратегии, которые может применять игрок А, а B1 ,B2 ,…, Bn - стратегии, которые может применять игрок B
— Матричная игра, в которой у игрока A имеется m стратегий, а у игрока B - n стратегий, называется игрой типа mxn
Матрица C: cij (i =1,...,m; j =1,...,n) - выигрыши игрока A (и проигрыши игрока B) при применении игроками стратегий Аi и Bj соответственно. C - платежная матрица игры
Нижняя и верхняя цена игры (принцип минимакса)
Игрок А, выбирая стратегию с номером i, понимает что игрок В, в свою очередь, ответит на нее той из стратегий, согласно которой выигрыш игрока А будет минимальным. Поэтому в каждой строке платежной матрицы выбирается минимум.
Из этих минимумов игрок А выберет максимум, тем самым определит для себя оптимальную стратегию. Полученное число называется максиминным или нижней ценой игры.
Игрок В, в свою очередь выбирая стратегию, понимает, что его проигрыш не превысит максимального числа в фиксированном столбце. Согласно данной логике в каждом столбце мы выбираем максимальный элемент, а из этих максимумов мы выбираем минимум, это и будет верхняя цена игры.
Пример. Игра «Три пальца».
Два игрока К и С одновременно и не сговариваясь показывают друг другу один, два или три пальца. Если всего показанных пальцев (первым и вторым вместе) будет четное число, то выигрывает К: он получает столько очков, сколько всего было пальцев, если нечетное - выигрывает С, на тех же условиях. Требуется записать игру в нормальной форме.
Решение:
Перенумеруем стратегии по числу показанных пальцев. Игра 3x3. Матрица игры будет:
| C1 | C2 | C3 | |
| К1 | -3 | ||
| К2 | -3 | -5 | |
| К3 | -5 |
Станем сначала на сторону К.
Предположим, что мы выбрали стратегию К1. Что будет делать противник? Он разумен и хочет отдать поменьше. Ясно, он выберет стратегию С2; наш выигрыш при этом будет равен -3, т. е. мы потеряем 3 очка. Плоховато! Запишем число 3 против первой строки в добавочном столбце (см. матрицу 3):
| C1 | C2 | C3 | Минимумы строк | |
| К1 | -3 | -3* | ||
| К2 | -3 | -5 | -5 | |
| К3 | -5 | -5 | ||
| Максимумы столбцов | 4* | 4* |
Попробуем другую стратегию - К2. На нее разумный противник ответит С3. Тогда мы потеряем 5 очков. Еще хуже! Третья стратегия К3 дает точно тот же результат: выигрыш (-5).
Что же делать? Пожалуй, лучше других будет все-таки стратегия К1 - при ней мы, по крайней мере, не проиграем больше 3 очков! Ведь против этой стратегии стоит максимальное число дополнительного столбца — мы его отметили звездочкой. Выбрав стратегию К1, мы гарантируем себе, что, как бы ни вел себя противник, мы никак не проиграем больше 3 очков (т. е. не выиграем меньше (-3) очков). Величина (-3) есть максимальный гарантированный выигрыш, который мы («красные») можем себе обеспечить, применяя только одну единственную стратегию. Такой стратегией должна быть К1.
Как мы получили (-3)? Нашли минимум каждой строки и из этих минимумов взяли максимальный (максиминили нижняя цена игрыα).