В комбинаторной теории игр , то заимствование стратегии является общим аргументом , который показывает для многих двух игроков , что второй игрок не может иметь гарантированную стратегию победы . Аргумент кражи стратегии применим к любой симметричной игре (в которой любой из игроков имеет одинаковый набор доступных ходов с одинаковыми результатами, так что первый игрок может «использовать» стратегию второго игрока), в которой лишний ход никогда не может быть недостаток.
Аргумент работает, получая противоречие . Предполагается, что выигрышная стратегия существует для второго игрока, который ее использует. Но затем, грубо говоря, после того, как он сделает свой первый ход - что по приведенным выше условиям не является недостатком, - первый игрок может также играть в соответствии с этой выигрышной стратегией. В результате оба игрока гарантированно выиграют, что абсурдно и противоречит предположению о существовании такой стратегии.
Стратегия кражи была изобретена Джоном Нэшем в 1940-х годах, чтобы показать, что игра в гексагон всегда является победой первого игрока, поскольку ничьи в этой игре невозможны. [1] Однако, Нэш не опубликовал этот метод, и Бек (2008) кредиты первой публикации на Alfred W. Хейлзом и Роберт И. Jewett, в 1963 документ по крестики-нолики , в котором они доказали и Hales- Теорема Джеветта . [2] Другие примеры игр, к которым применим этот аргумент, включают m , n , k -игры, такие как гомоку . В игре Сильвер монеты, стратегия кражи использовалась, чтобы показать, что первый игрок выигрывает, а не то, что игра заканчивается ничьей. [3]
Пример [ править ]
Аргумент кражи стратегии можно использовать на примере игры в крестики-нолики для доски и выигрышных рядов любого размера. [1] [2] Предположим, что второй игрок использует стратегию S , которая гарантирует ему победу. Первый игрок помещает X в произвольном положении, а второй игрок затем реагирует путем размещения O в соответствии с S . Но если они проигнорируют первый случайный X, который они поставили, первый игрок окажется в той же ситуации, с которой второй игрок столкнулся на своем первом ходу; единственная фигура врага на доске. Следовательно, первый игрок может делать свои ходы в соответствии с S - то есть, если толькоS требует, чтобы другой X был помещен там, где игнорируемый X уже размещен. Но в этом случае игрок может просто поместить свой X в какую-либо другую случайную позицию на доске, в результате чего один X окажется в позиции, требуемой S , а другой - в случайной позиции, и станет новый проигнорированный кусок, оставляя ситуацию как раньше. Продолжая таким образом, S , по гипотезе, гарантированно создаст выигрышную позицию (с дополнительным игнорируемым Xне имеет значения). Но затем второй игрок проиграл, что противоречит предположению, что у него была гарантированная выигрышная стратегия. Таким образом, такой выигрышной стратегии для второго игрока не существует, а крестики-нолики - это либо принудительная победа для первого игрока, либо ничья. Дальнейший анализ показывает, что на самом деле это ничья.
То же доказательство справедливо для любой сильной позиционной игры .
Шахматы [ править ]
| а | б | c | d | е | ж | грамм | час | ||
| 8 |      | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| а | б | c | d | е | ж | грамм | час | ||
Существует класс шахматных позиций под названием Цугцванг, в котором игрок, обязанный двигаться, предпочел бы «пас», если бы это было разрешено. Из-за этого аргумент о краже стратегии неприменим к шахматам. [4] В настоящее время неизвестно, могут ли белые или черные форсировать победу при оптимальной игре, или оба игрока могут форсировать ничью. Однако практически все изучающие шахматы считают первый ход белых преимуществом, а статистика современных высокоуровневых партий показывает, что процент победы белых примерно на 10% выше, чем у черных.
Перейти [ править ]
В го разрешен проездной. Когда начальная позиция симметрична (пустая доска, ни один из игроков не имеет очков), это означает, что первый игрок может украсть выигрышную стратегию второго игрока, просто отказавшись от первого хода. Однако с 1930-х годов [5] второму игроку обычно присуждаются некоторые компенсационные баллы , что делает начальную позицию асимметричной, и аргумент о краже стратегии больше не работает.
Элементарной стратегией в игре является « движение в зеркало », когда второй игрок выполняет движения, диагонально противоположные движениям этого противника. Этот подход можно обойти, используя лестничную тактику , ко-бои или успешную борьбу за контроль над центральной точкой доски.
Конструктивность [ править ]
Аргумент кражи стратегии показывает, что второй игрок не может выиграть, путем вывода противоречия из любой гипотетической выигрышной стратегии для второго игрока. Аргумент обычно используется в играх, где не может быть ничьей, посредством закона исключенного третьего . Однако он не предоставляет явной стратегии для первого игрока, и из-за этого был назван неконструктивным. [4] Это поднимает вопрос о том, как на самом деле вычислить выигрышную стратегию.
Для игр с конечным числом доступных позиций, таких как chomp , выигрышная стратегия может быть найдена с помощью исчерпывающего поиска. [6] Однако это может оказаться непрактичным, если количество позиций велико.
В 2019 году Грег Бодвин и Офер Гроссман доказали, что проблема поиска выигрышной стратегии является сложной для PSPACE в двух типах игр, в которых использовались аргументы кражи стратегии: игра с минимальным набором позиций и симметричная игра Maker-Maker . [7]
Ссылки [ править ]
- ^ a b Бек, Йожеф (2008), Комбинаторные игры: теория крестиков-ноликов , Энциклопедия математики и ее приложений, 114 , Кембридж: Издательство Кембриджского университета, стр. 65 , 74 , DOI : 10.1017 / CBO9780511735202 , ISBN 9780511735202, Руководство по ремонту 2402857.
- ^ а б Хейлз, AW ; Джеветта, Р. (1963), "Равномерность и позиционные игры", Труды Американского математического общества , 106 (2): 222-229, DOI : 10,2307 / 1993764 , JSTOR 1993764 , МР 0143712 .
- ^ Сичерман, Джордж (2002), "Теория и практика Sylver Coinage" (PDF) , Целые числа , 2 , G2
- ^ а б Бишоп, JM; Насуто, SJ; Танай, Т .; Roesch, EB; Спенсер, MC (2016), «HeX and the single anthill: Playing games with Aunt Hillary», in Müller, Vincent C. (ed.), Fundamental Issues of Artificial Intelligence (PDF) , Synthese Library, 376 , Springer, pp. 369-390, DOI : 10.1007 / 978-3-319-26485-1_22 . См., В частности, раздел 22.2.2.2, Аргумент о краже стратегии, стр. 376 .
- ↑ Fairbairn, John, History of Komi , получено 9 апреля 2010 г.
- ^ rjlipton ( 2 октября 2013 г.). «Стратегии воровства» . Потерянное письмо Гёделя и P = NP . Проверено 30 ноября 2019 .
- ^ Бодвин, Грег; Гроссман, Офер (15.11.2019). «Воровство стратегии неконструктивно». arXiv : 1911.06907 [ cs.DS ].
