Численно ограниченная версия равновесия Нэша?

14

Мне интересно, существует ли вычислительно ограниченная версия концепции равновесия по Нэшу, что-то вроде следующего.

Представьте себе какую-то идеальную информационную игру для двух игроков, в которую играют на доске , и которая сложна в том смысле, что оптимальная игра трудна для ОПЫТА. Предположим также, что для простоты розыгрыши невозможны. Представьте себе пару ( A , B ) рандомизированных машин Тьюринга за полиномиальное время, играющих в эту игру друг против друга. Для каждого n пусть p A , B ( n ) - вероятность того, что A побьет B в игре порядка n . (Для конкретности, допустим, что АN×N(A,В)NпA,В(N)AВNAполучает первый играть с вероятностью 0,5.) То , что я думаю , что было бы здорово, если бы можно было доказать существование пары с тем свойством , что не рандомизированного полиномиального времени машина Тьюринга A ' доминирует над A (где " А " доминирует A "означает p A ' , B ( n ) > p A , B ( n ) для всех достаточно больших n ), и, аналогично, отсутствует рандомизированная машина Тьюринга с полиномиальным временем B '(A,В)A' AA'AпA',В(N)>пA,В(N)NВ'доминирует над (где « B доминирует над B » означает p A , B ( n ) < p A , B ( n ) для всех достаточно больших n ).ВВ'ВпA,В'(N)<пA,В(N)N

Почему-то я подозреваю, что на это слишком много надежды, но есть ли надежда, что что-то подобное будет правдой, возможно, для ограниченного класса игр?

Одним из мотивов этого вопроса является то, что я ищу способ формализовать представление о том, что данная шахматная позиция «выгодна для белых». Классически позиция - это либо победа белых, либо нет. Однако шахматисты, как люди, так и компьютеры, имеют интуитивное понимание того, что значит для белых иметь преимущество. Похоже, что-то связано с вероятностью того, что белые выиграют, учитывая, что игроки ограничены в вычислительном отношении и должны угадывать лучший ход. Для конкретной пары рандомизированных алгоритмов можно, конечно, говорить о вероятности того, что белые выиграют, но мне интересно, может ли быть, в некотором смысле, канонический пара ограниченных в вычислительном отношении игроков, чьи вероятности выигрыша дают значение для позиции, которая зависит только от самой игры, а не от особенностей игроков.

Тимоти Чоу
источник
У вычислительно ограниченных концепций равновесия, о которых я знаю, есть другой вкус - мышление о Гальперне, Пассе и Симане, как в « Истине за мифом о народной теореме» , 2014. Там мы не предполагаем, что нахождение стратегии равновесия для данной игры это сложно (потому что для данной игры, это может или не может быть). Скорее, мы допускаем равновесие любой стратегии, если любому игроку сложно рассчитать прибыльное отклонение. (Обратите внимание, что это предполагает экспоненциальное пространство стратегии, в противном случае мы можем проверить все отклонения.)
usul

Ответы:

1

Я не могу придумать, каким образом может быть простой, полностью элегантный / удовлетворительный ответ на этот вопрос, особенно потому, что конечный выигрыш так сложно вычислить; однако мои мысли слишком длинны, чтобы оставлять комментарии.

Лучшая идея, которая у меня есть, заключается в следующем: в случае с шахматами попытайтесь приблизить вероятность того, что белые выиграют, основываясь на материальном преимуществе белых (то есть, дополнительных пешках, рыцарях и т. Д.) Для данной позиции, случайным образом выбирая позиции с этой точной суммой. материальная конфигурация. Возможно, в случае с «шахматами с полными ладьями» мы могли бы сказать: «Какова вероятность того, что белые выиграют с 8-ю ладьями по 17-ти черным?» Возможно, эта вероятность составляет 4%; чтобы вычислить его, мы должны были бы изучить (скажем) 1000 различных случайно сгенерированных шахматных позиций, которые имеют 8 белых ладей и 17 черных ладей, а затем посмотреть в будущее (скажем) 10 ходов глубоко в каждом случае, и посмотреть, какова новая конфигурация материала , Затем возьмите ожидаемые шансы на основе конфигурации материала в конце,

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

Для исходной позиции не просто используйте статистику, которую вы получаете (то есть, если исходная позиция имеет ( М = 6, N = 7) грачей, не просто предполагайте, что у белых есть 25% шанс на победу, потому что это ожидаемые шансы на победу (6,7)); вместо этого, поскольку вы можете быть более точным, посмотрите на 10 ходов как обычно только на эту одну позицию и найдите все возможные конечные позиции. Затем найдите правильный путь (который включает в себя оптимальную игру обеих сторон) к конфигурации с 10 ходами в глубину и выберите ожидаемые шансы этого пути в качестве ожидаемых шансов исходной позиции.

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

Если это звучит сложно и трудно объяснить, это потому, что это так. Более краткое резюме того, что я описываю: Используйте рекурсию и базовую статистику, чтобы рассчитать шансы на победу белых, учитывая M белых ладей и N черных ладей на доске. Затем используйте эти значения, чтобы посмотреть на k ходов и выяснить шансы на победу белых в исходной позиции.

Заключительный комментарий: я думаю, что эта проблема также интересна для неэкспериментальных игр, таких как крестики-нолики, которые, согласно Википедии, являются PSPACE-полными. Кроме того, я полагаю, что процесс, подобный тому, который я описал выше, также мог бы быть полезным и там, хотя очевидно, что было бы невозможно иметь «материальное» преимущество в крестики-нолики; должна быть какая-то другая основа для оценки превосходства позиции Х или О.

Филип Уайт
источник