Случайность в игре

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

Вопрос был поставлен так: что обязан знать игрок об игре, чтобы решение было в принципе возможно? Простейший тип игры – матричная игра, т.е. игра двух игроков, в которой первый должен выбрать одно из m действий, а второй – одно из n действий, и задание этой пары определяет выигрыш первого (он же – проигрыш второго). Выигрыши образуют матрицу размером mXn. Решение игры в общем случае являет собой пару оптимальных стратегий (два набора вероятностей, с которыми игроки применяют свои действия), и реализующийся при этом средний выигрыш – цену игры. Для матричной игры решение всегда существует (теорема фон Неймана, 1928 г.), причем игрок, применяющий свою оптимальную стратегию, гарантирует себе выигрыш не менее цены игры, независимо от того, как ведет себя противник (и получает больше цены, если противник ошибся).

Решение может быть найдено с помощью эффективной процедуры – решения системы дифференциальных уравнений. Эту процедуру я и использовал для ответа на поставленный выше вопрос [Чайковский, 1971].

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

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

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

Подробнее это рассмотрено в п. 4.3 книги [Чайковский, 1990], а идея доказательства (данного в моей диссертации) приведена в заметке [Чайковский, 1971a]. Поскольку заметка в итоге оказалась единственной публикацией доказательства, ее надо пояснить.

Игровые задачи интересовали меня в одном отношении – можно ли их решать методом проб и ошибок. С этой позиции среди методов решения важны те, которые можно трактовать как случайный поиск. Наиболее привлекала внимание доказанная в 1950 г. теорема Брауна– Неймана: всякая симметричная игра (игра, в которой роли обоих игроков одинаковы; она описывается антисимметричной матрицей размера mXm) может быть решена путем решения системы (m – 1) обыкновенных дифференциальных уравнений, в которой переменными являются вероятности применения действий первым игроком. Доказательство ее построено на двух свойствах симметричной игры: во-первых, она имеет нулевую (а потому заранее известную) цену, а во-вторых, достаточно найти оптимальную стратегию одного игрока – у другого будет та же. Правую часть каждого уравнения образует кусочно-аналитическая функция, которая равна выгодности данного действия (в данном случае – выигрышу первого игрока при данном действии, если этот выигрыш положителен, и равна нулю в ином случае) [Льюс, Райфа, 1961, c. 551].

Здесь сумма выгодностей действий игрока является так называемой функцией Ляпунова, и потому решение системы прозрачно как аналитически, так и поведенчески. Однако в таком виде задача не привлекает ввиду явной искусственности симметричной игры. К счастью, оказалось, что симметрия игры ни при чем: теорема сохраняет силу для произвольной матричной игры. Эту систему уравнений естественно рассмотреть как модель поведения двух бесконечных коллективов автоматов, непрерывно играющих попарно в матричную игру, причем переменные величины будут играть роль распределений автоматов по действиям в данный момент поиска. Существование решения означает, что данные коллективы способны к оптимальному поведению.

Естественно встал вопрос: существует ли решение системы уравнений, в которых вместо выгодностей взяты невыгодности? Оказывается – нет. Удалось найти простой пример игры 3Х3, в котором система уравнений не приближается к решению игры (траектории блуждают по всему фазовому пространству). Это и было интерпретировано мной как недостаточность штрафов – в игре коллективов надо поощрять тех, чьи действия лучше среднего. И наконец, оказалось, что численное значение выгодностей лишь замедляет процесс поиска: быстрее всего ищут те, кто знает лишь знак выгодности, т.е. лишь номер действия, к которому следует перейти.

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