Аргумент о краже стратегии
В комбинаторной теории игр аргумент кражи стратегии — это общий аргумент , который показывает для многих игр с двумя игроками , что второй игрок не может иметь гарантированно выигрышную стратегию . Аргумент о краже стратегии применим к любой симметричной игре (в которой любой игрок имеет одинаковый набор доступных ходов с одинаковыми результатами, так что первый игрок может «использовать» стратегию второго игрока), в которой никогда не может быть сделан дополнительный ход. недостаток. Ключевым свойством аргумента о краже стратегии является то, что он доказывает, что первый игрок может выиграть (или, возможно, сыграть вничью) в игре, фактически не создавая такой стратегии. Таким образом, хотя оно и может доказать существование выигрышной стратегии, оно не дает никакой информации о том, что это за стратегия.
Аргумент работает, получая противоречие . Предполагается, что выигрышная стратегия существует для второго игрока, который ее использует. Но тогда, грубо говоря, сделав произвольный первый ход, который по вышеизложенным условиям не является недостатком, первый игрок также может играть по этой выигрышной стратегии. В результате оба игрока гарантированно выиграют – что абсурдно и противоречит предположению о существовании такой стратегии.
Стратегия воровства была изобретена Джоном Нэшем в 1940-х годах, чтобы показать, что игра в гексагонах всегда приводит к победе первого игрока, поскольку ничья в этой игре невозможна. [1] Однако Нэш не опубликовал этот метод, и Йожеф Бек приписывает его первую публикацию Альфреду В. Хейлзу и Роберту И. Джуэтту в статье 1963 года о крестиках-ноликах , в которой они также доказали теорему Хейлза-Джеветта . [1] [2] Другие примеры игр, к которым применим этот аргумент, включают m , n , k -игры, такие как гомоку . В игре «Чомп» кража стратегии показывает, что у первого игрока есть выигрышная стратегия на любой прямоугольной доске (кроме 1х1). В игре с чеканкой Сильвера стратегия кражи использовалась, чтобы показать, что первый игрок может выиграть в определенных позициях, называемых «эндингами». [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 имел гарантированную выигрышную стратегию. Таким образом, такой выигрышной стратегии для П2 не существует, и крестики-нолики — это либо вынужденная победа П1, либо ничья. (Дальнейший анализ показывает, что на самом деле это ничья.)
То же доказательство справедливо для любой сильной позиционной игры .
шахматы [ править ]
| а | б | с | д | и | ж | г | час | ||
| 8 |      | 8 | |||||||
| 7 | 7 | ||||||||
| 6 | 6 | ||||||||
| 5 | 5 | ||||||||
| 4 | 4 | ||||||||
| 3 | 3 | ||||||||
| 2 | 2 | ||||||||
| 1 | 1 | ||||||||
| а | б | с | д | и | ж | г | час | ||
Существует класс шахматных позиций, называемый цугцванг , в которых игрок, обязанный двигаться, предпочел бы «пасовать», если бы это было разрешено. По этой причине аргумент о краже стратегии неприменим к шахматам. [4] В настоящее время неизвестно, смогут ли белые или черные добиться победы при оптимальной игре, или оба игрока смогут добиться ничьей. Однако практически все изучающие шахматы считают первый ход белых преимуществом, а по статистике современных партий высокого уровня процент выигрышей белых составляет около 10%. [ нужна ссылка ] выше, чем у черных.
Иди [ править ]
В Го пас разрешен. Когда стартовая позиция симметрична (пустая доска, ни у одного из игроков нет очков), это означает, что первый игрок может украсть выигрышную стратегию второго игрока, просто отказавшись от первого хода. Однако с 1930-х гг. [5] второму игроку обычно присуждаются некоторые компенсационные очки , что делает стартовую позицию асимметричной, и аргумент о краже стратегии больше не работает.
Элементарной стратегией в игре является « зеркальное движение », когда второй игрок выполняет ходы, диагонально противоположные движениям противника. Этот подход можно победить, используя тактику лестницы , бои ко или успешно конкурируя за контроль над центральной точкой доски.
Конструктивность [ править ]
Аргумент кражи стратегии показывает, что второй игрок не может выиграть, путем вывода противоречия из любой гипотетической выигрышной стратегии второго игрока. Этот аргумент обычно используется в играх, где не может быть ничьей, посредством закона исключенного третьего . Однако он не дает четкой стратегии для первого игрока, поэтому его назвали неконструктивным. [4] Это поднимает вопрос о том, как на самом деле вычислить выигрышную стратегию.
Для игр с конечным числом достижимых позиций, таких как chomp , выигрышная стратегия может быть найдена путем перебора. [6] Однако это может оказаться непрактичным, если количество позиций велико.
В 2019 году Грег Бодвин и Офер Гроссман доказали, что проблема поиска выигрышной стратегии является PSPACE-сложной в двух видах игр, в которых использовались аргументы, перехватывающие стратегию: игре с минимальным ЧУП и симметричной игре Создатель-Создатель . [7]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с Бек, Йожеф (2008), Комбинаторные игры: теория крестиков-ноликов , Энциклопедия математики и ее приложений, том. 114, Кембридж: Издательство Кембриджского университета, стр.65 , 74 , doi : 10.1017/CBO9780511735202 , ISBN 9780511735202 , МР 2402857 .
- ^ Jump up to: Перейти обратно: а б Хейлз, AW ; Джуэтт, Р.И. (1963), «Регулярность и позиционные игры», Труды Американского математического общества , 106 (2): 222–229, doi : 10.2307/1993764 , JSTOR 1993764 , MR 0143712 .
- ^ Зихерман, Джордж (2002), «Теория и практика чеканки серебряных монет» (PDF) , Целые числа , 2 , G2
- ^ Jump up to: Перейти обратно: а б Бишоп, Дж. М.; Насуто, С.Дж.; Танай, Т.; Роеш, Е.Б.; Спенсер, MC (2016), «HeX и одиночный муравейник: играем в игры с тетей Хиллари», в книге Мюллер, Винсент К. (редактор), «Фундаментальные проблемы искусственного интеллекта» (PDF) , Synthese Library, vol. 376, Springer, стр. 369–390, номер документа : 10.1007/978-3-319-26485-1_22 , ISBN. 978-3-319-26483-7 . См., в частности, Раздел 22.2.2.2, Аргумент кражи стратегии, с. 376 .
- ^ Фэйрберн, Джон, История Коми , получено 9 апреля 2010 г.
- ^ Рилиптон (2 октября 2013 г.). «Стратегии кражи» . Потерянное письмо Гёделя и P=NP . Проверено 30 ноября 2019 г.
- ^ Бодвин, Грег; Гроссман, Офер (15 ноября 2019 г.). «Воровство стратегии неконструктивно». arXiv : 1911.06907 [ cs.DS ].