м , н , к -игра
m — , n , k -игра это абстрактная настольная игра , в которой два игрока по очереди кладут камень своего цвета на доску размером m × n , причем победителем становится игрок, который первым соберет k камней своего цвета в ряд, по горизонтали, вертикали или диагонали. [1] [2] Таким образом, крестики-нолики вольного стиля — это 3,3,3-игры, а гомоку — 15,15,5-игры. Игру m , n , k также называют игрой k - в ряд на доске m - n .
m n , -игры представляют , k главным образом математический интерес. Пытаются найти теоретико-игровую ценность, результат игры с идеальной игрой . Это известно как решение игры.
Аргумент кражи стратегии
[ редактировать ]Стандартный о краже стратегии аргумент из комбинаторной теории игр показывает, что в игре no m , n , k может существовать стратегия, гарантирующая победу второго игрока ( стратегия выигрыша второго игрока ). Это связано с тем, что дополнительный камень, предоставленный любому игроку в любой позиции, может только улучшить шансы этого игрока. Аргумент кражи стратегии предполагает, что второй игрок имеет выигрышную стратегию, и демонстрирует выигрышную стратегию для первого игрока. Для начала первый игрок делает произвольный ход. После этого игрок притворяется вторым игроком и принимает выигрышную стратегию второго игрока. Они могут это сделать до тех пор, пока стратегия не требует установки камня на «произвольную» клетку, которая уже занята. Однако если это произойдет, они снова смогут сделать произвольный ход и продолжить, как и раньше, с выигрышной стратегией второго игрока. Поскольку лишний камень им не повредит, это выигрышная стратегия для первого игрока. Противоречие означает , что исходное предположение неверно и у второго игрока не может быть выигрышной стратегии.
Этот аргумент ничего не говорит о том, является ли конкретная игра ничьей или победой первого игрока. Кроме того, на самом деле он не дает стратегии для первого игрока.
Применение результатов к платам разных размеров
[ редактировать ]Полезным понятием является «слабая ( m , n , k ) игра», где k - подряд вторым игроком не завершает игру победой второго игрока.
Если слабая ( m , n , k ) является ничьей, то уменьшение m или n или увеличение k также приведет к ничьей.
И наоборот, если слабый или нормальный ( m , n , k ) является выигрышем, то любой больший слабый ( m , n , k ) является выигрышем.
Обратите внимание, что доказательства ничьих с использованием парных стратегий также доказывают ничью для слабой версии и, следовательно, для всех меньших версий.
Общие результаты
[ редактировать ]Следующие утверждения относятся к первому игроку в слабой игре, предполагая, что оба игрока используют оптимальную стратегию.
- Если конкретный ( m 0 , n 0 , k 0 ) является ничьей, то ( m 0 , n 0 , k ) с k ≥ k 0 является ничьей, и ( m , n , k 0 ) с m ≤ m 0 и n ≤ n 0 — ничья. Аналогично, если ( m 0 , n 0 , k 0 ) является выигрышем, то ( m 0 , n 0 , k ) с k ≤ k 0 является выигрышем, и ( m , n , k 0 ) с m ≥ m 0 и n ≥ n 0 — выигрыш.
- k ≥ 9 — это ничья: когда k = 9 и доска бесконечна, второй игрок может сделать ничью с помощью «стратегии спаривания». Ничья на бесконечной доске означает, что игра будет продолжаться вечно при идеальной игре. Стратегия образования пар предполагает разделение всех клеток доски на пары таким образом, чтобы, всегда играя на паре клеток первого игрока, второй игрок гарантировал, что первый игрок не сможет получить k в линии. Стратегию спаривания на бесконечной доске можно применить и к любой конечной доске: если стратегия предполагает ход за пределами доски, то второй игрок делает произвольный ход внутри доски.
- k ≥ 8 — ничья на бесконечной доске. Неясно, применима ли эта стратегия к доскам любого конечного размера. [2] Неизвестно, сможет ли второй игрок добиться ничьей, если k равно 6 или 7 на бесконечной доске.
- k ≥ 3, и либо k > m , либо k > n является ничьей, также с помощью стратегии жеребьёвки в размерности не меньше k (или тривиально невозможно выиграть, если оба меньше)
Конкретные результаты
[ редактировать ]- k = 1 и k = 2 — тривиальные выигрыши, за исключением (1,1,2) и (2,1,2)
- (3,3,3) — ничья (см. Крестики-нолики ), а ( m , n ,3) — ничья, если m < 3 или n < 3. ( m , n ,3) — победа, если m ≥ 3 и n ≥ 4 или m ≥ 4 и n ≥ 3.
- (5,5,4) — это ничья, а это означает, что ( m , n ,4) — это ничья для m ≤ 5 и n ≤ 5, а (6,5,4) — выигрыш, а это означает, что ( m , n ,4) — выигрыш для m ≥ 6 и n ≥ 5 или m ≥ 5 и n ≥ 6. ( m ,4,4) — выигрыш для m ≥ 30 (Lustenberger, 1967) и ничья для m ≤ 8. [1] Неизвестно, является ли ( m ,4,4) победой или ничьей для 9 ≤ m ≤ 29.
- Компьютерный поиск Вэй-Юаня Сюя и Чу-Лин Ко показал, что и (7,7,5), и (8,8,5) ничьи. [3] что означает, что ( m , n ,5) является ничьей для m ≤ 8 и n ≤ 8. Компьютерный поиск Л. Виктора Аллиса показал, что (15,15,5) является выигрышем, даже с учетом одного из ограничительных правил. из Гомоку .
- (9,6,6) и (7,7,6) являются ничьими через пары.
Многомерный вариант
[ редактировать ]Вместо двумерной доски можно рассматривать варианты игры на многомерной доске.
Для случая k -в-ряде, когда доска представляет собой n- мерный гиперкуб со всеми ребрами длины k , Хейлз и Джуэтт доказали: [4] что игра заканчивается вничью, k нечетно если и
- к ≥ 3 н − 1
или k четно и если
- к ≥ 2 п +1 − 2.
Они предполагают , что игра является ничьей, даже если число клеток по крайней мере в два раза превышает количество линий, что происходит тогда и только тогда, когда
- 2 тыс. н ≥ ( к + 2) н .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б JWHM Uiterwijk и HJ van der Herik, Преимущество инициативы , Information Sciences 122 (1) (2000) 43-58.
- ^ Перейти обратно: а б Яап ван ден Херик , Йос УХМ Уитервейк, Джек ван Рейсвейк (2002). «Игры решены: сейчас и в будущем». Искусственный интеллект.
- ^ Сюй, Вэй-Юань; Ко, Чу-Линг; Сюэ, Чу-Сюань; Ву, И-Чен (2018). «Решение 7,7,5-игр и 8,8,5-игр » Журнал ICGA . 40 (3 ) Получено 6 ноября.
- ^ Элвин Р. Берлекамп, Джон Хортон Конвей, Ричард К. Гай. «Пути победы для ваших математических игр, Том 3», А. К. Петерс (2003).
