Седловая точка. Чистая цена игры

Седловая точка. Чистая цена игры

Рассмотрим пример. Пусть дана матрица игры (4):

Требуется найти нижнюю цену игры α, верхнюю цену игры β  и минимаксные стра­тегии и проверить, являются ли они устой­чивыми.

Решение. Из анализа дополнительных столбца и строки получаем:  α= 5, β=5. Максимин равен минимаксу! Случай особый. Что же из этого следует?

Возьмем пару минимаксных стратегий: К₂ и С₃. Если оба держатся этих стратегий, то выигрыш будет равен 5. Теперь, допустим, мы узнали о поведении противника. Что будем делать? А ничего! Мы по-прежнему будем дер­жаться стратегии К₂, потому что любое отступ­ление от нее нам невыгодно. Знаем мы или не знаем о поведении противника — все равно будем держаться стратегии К₂! То же относится и к «синим» — им нет смысла менять свою стратегию С₃.

В данном примере пара стратегий К₂ и С₃ устойчива, т. е. представляет собой положение равновесия и дает решение игры.

Почему так получилось? Потому что в матрице имеется особый элемент 5; он является минимальным в своей строке и одновременно максимальным в своем столбце. Такой элемент называется седловой точкой. Если матри­ца имеет седловую точку (т. е. нижняя цена игры равна верхней), то игра имеет решение в чистых стратегиях: это — пара стратегий, пересекающихся в седловой точке. Сама же седловая точка дает цену игры — в нашем примере она равна 5.

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

Примерами игр с полной информацией мо­гут служить: шахматы, шашки, «крестики и нолики» и т. п.

Приведем пример игры с полной информацией, решение которой легко найти.

Два игрока — К и С — поочередно кладут одинаковые монеты на круглый стол. Положение каждой монеты выбирается произвольно, лишь бы она не перекрывалась другими. Выигры­вает тот из игроков, который положит монету последним (когда места для других уже не остается).

Стоит немножко подумать, чтобы убедиться, что исход этой игры всегда предрешен и что существует вполне определенная стратегия, га­рантирующая выигрыш тому из игроков, кото­рый кладет монету первым (пусть это будет К). А именно К должен положить первую монету в центр стола, а далее на каждый ход С отвечать в точности симметричным относи­тельно центра стола ходом! Бедный С может при этом вести себя как угодно, спасения ему все равно нет...

Очевидно, такая игра имеет смысл только для тех, кто не знает решения. Любопытно, что совершенно так же обстоит дело и с такой популярной игрой, как шахматы! Эта игра име­ет смысл только до тех пор, пока не найдено ее решение.

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

Наверное, любители шахмат заинтересованы в том, чтобы шахматная игра была решена еще не скоро.

Заметим в заключение, что седловых точек в матрице может быть не одна, а несколько; тог­да решений игры в чистых стратегиях суще­ствует столько, сколько имеется седловых точек. Каждое из них дает выигрыш, равный цене игры.

• ТЕОРИЯ ИГР

• Чем занимается теория игр    
• Парная игра с нулевой суммой. Цена игры      
• Игра в нормальной форме. Матрица игры    
• Примеры конечных игр. Принцип минимакса    
• Седловая точка. Чистая цена игры    
• Решение игры в смешанных стратегиях. Основная теорема теории игр