Теория игр

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

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

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

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

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

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

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

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

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

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