В комбинаторной теории игр аргумент о краже стратегии является общим аргументом , который показывает, что для многих игр с двумя игроками второй игрок не может иметь гарантированно выигрышную стратегию . Аргумент о краже стратегии применим к любой симметричной игре (в которой у любого игрока есть тот же набор доступных ходов с теми же результатами, так что первый игрок может «использовать» стратегию второго игрока), в которой дополнительный ход никогда не может быть недостатком. Ключевым свойством аргумента о краже стратегии является то, что он доказывает, что первый игрок может выиграть (или, возможно, сыграть вничью) игру, фактически не создавая такую стратегию. Таким образом, хотя это может доказать существование выигрышной стратегии, доказательство не дает никакой информации о том, что это за стратегия.
Аргумент работает, получая противоречие . Предполагается, что выигрышная стратегия существует для второго игрока, который ее использует. Но затем, грубо говоря, сделав произвольный первый ход – который по условиям выше не является недостатком – первый игрок может затем также играть в соответствии с этой выигрышной стратегией. Результатом является то, что оба игрока гарантированно выиграют – что абсурдно, тем самым противореча предположению о существовании такой стратегии.
Кража стратегии была изобретена Джоном Нэшем в 1940-х годах, чтобы показать, что игра в гексагон всегда является победой первого игрока, поскольку в этой игре ничья невозможна. [1] Однако Нэш не опубликовал этот метод, и Йожеф Бек приписывает его первую публикацию Альфреду У. Хейлзу и Роберту И. Джуэтту в статье 1963 года о крестиках-ноликах , в которой они также доказали теорему Хейлза–Джуэтта . [1] [2] Другие примеры игр, к которым применим этот аргумент, включают m , n , k -игры, такие как гомоку . В игре Chomp кража стратегии показывает, что у первого игрока есть выигрышная стратегия на любой прямоугольной доске (кроме 1x1). В игре Silver coinage кража стратегии использовалась, чтобы показать, что первый игрок может выиграть в определенных позициях, называемых «эндерами». [3] Во всех этих примерах доказательство ничего не раскрывает о фактической стратегии.
Аргумент о краже стратегии можно использовать на примере игры в крестики-нолики для доски и выигрышных рядов любого размера. [1] [2] Предположим, что второй игрок (P2) использует стратегию S , которая гарантирует победу. Первый игрок (P1) размещает X в произвольной позиции. P2 отвечает размещением O в соответствии с S. Но если P1 игнорирует первый случайный X , P1 теперь находится в той же ситуации, что и P2 при первом ходе P2: единственная вражеская фигура на доске. Поэтому P1 может сделать ход в соответствии с S — то есть, если только S не потребует разместить еще одну X там, где уже размещена игнорируемая X. Но в этом случае P1 может просто разместить X в какой-то другой случайной позиции на доске, чистый эффект которой будет заключаться в том, что одна X находится в позиции, требуемой S , в то время как другая находится в случайной позиции и становится новой игнорируемой фигурой, оставляя ситуацию прежней. Продолжая таким образом, S , по гипотезе, гарантированно создаст выигрышную позицию (с дополнительным игнорируемым X, не имеющим последствий). Но тогда P2 проиграл, что противоречит предположению, что P2 имел гарантированную выигрышную стратегию. Такой выигрышной стратегии для P2, следовательно, не существует, и крестики-нолики — это либо вынужденная победа для P1, либо ничья. (Дальнейший анализ показывает, что на самом деле это ничья.)
Такое же доказательство справедливо для любой сильной позиционной игры .
Существует класс шахматных позиций, называемых цугцванг , в которых игрок, обязанный сделать ход, предпочел бы «пасовать», если бы это было разрешено. Из-за этого аргумент о краже стратегии не может быть применен к шахматам. [4] В настоящее время неизвестно, могут ли белые или черные добиться победы при оптимальной игре, или оба игрока могут добиться ничьей. Однако практически все студенты шахмат считают первый ход белых преимуществом, а статистика современных игр высокого уровня показывает, что процент побед белых примерно на 10% [ требуется ссылка ] выше, чем у черных.
В го пас разрешен. Когда начальная позиция симметрична (пустая доска, ни у одного из игроков нет очков), это означает, что первый игрок может украсть выигрышную стратегию второго игрока, просто отказавшись от первого хода. Однако с 1930-х годов [5] второму игроку обычно присуждаются некоторые компенсационные очки , что делает начальную позицию асимметричной, и аргумент о краже стратегии больше не будет работать.
Элементарной стратегией в игре является « зеркальный ход », когда второй игрок выполняет ходы, которые по диагонали противоположны ходам этого противника. Этот подход можно победить, используя тактику лестницы , ко-бои или успешно соревнуясь за контроль над центральной точкой доски.
Аргумент о краже стратегии показывает, что второй игрок не может победить, посредством вывода противоречия из любой гипотетической выигрышной стратегии для второго игрока. Аргумент обычно применяется в играх, где не может быть ничьей, посредством закона исключенного третьего . Однако он не дает явной стратегии для первого игрока, и из-за этого его называют неконструктивным. [4] Это поднимает вопрос о том, как на самом деле вычислить выигрышную стратегию.
Для игр с конечным числом достижимых позиций, таких как chomp , выигрышная стратегия может быть найдена путем исчерпывающего поиска. [6] Однако это может быть непрактично, если число позиций велико.
В 2019 году Грег Бодвин и Офер Гроссман доказали, что проблема поиска выигрышной стратегии является PSPACE-сложной в двух типах игр, в которых использовались аргументы о краже стратегии: минимальная игра с частично упорядоченными множествами и симметричная игра Maker-Maker . [7]