m, n, k-game - m,n,k-game

m, n, k-game абстрактная настольная игра, в котором два игрока по очереди кладут камень своего цвета на доску размером m × n, причем победителем становится игрок, который первым получит k камней своего цвета в ряд по горизонтали, вертикали или диагонали. Таким образом, крестики-нолики - это 3,3,3-игра, а свободный стиль гомоку - это игра 15,15,5. Игра m, n, k также называется игрой k-in-a-row на доске размером m × n.

m, n, k-игры представляют в основном математический интерес. Требуется найти значение теоретико-игровой, результат игры с идеальной игрой. Это известно как решение игры.

• 1 Аргумент кражи стратегии
• 2 Применение результатов к платам разного размера
• 3 Общие результаты
• 4 Конкретные результаты
• 5 Многомерный вариант
• 6 См. Также
• 7 Ссылки
• 8 Внешние ссылки

Стандартный аргумент кражи стратегии из комбинаторной теории игр показывает, что ни в одной игре m, n, k может ли существовать стратегия, обеспечивающая победу второго игрока (выигрышная стратегия второго игрока ). Это потому, что дополнительный камень, отданный любому игроку в любой позиции, может только улучшить шансы этого игрока. Аргумент кражи стратегии предполагает, что у второго игрока есть выигрышная стратегия, и демонстрирует выигрышную стратегию для первого игрока. Первый игрок для начала делает произвольный ход. После этого игрок притворяется вторым игроком и принимает выигрышную стратегию второго игрока. Они могут делать это до тех пор, пока стратегия не требует размещения камня на «произвольной» площади, которая уже занята. Однако если это произойдет, они снова могут сыграть произвольный ход и продолжить, как и прежде, с выигрышной стратегией второго игрока. Поскольку дополнительный камень не может повредить им, это выигрышная стратегия для первого игрока. Противоречие означает, что исходное предположение неверно, и у второго игрока не может быть выигрышной стратегии.

Этот аргумент ничего не говорит о том, является ли конкретная игра ничьей или победой для первого игрока. Кроме того, он фактически не дает стратегии для первого игрока.

Полезное понятие - это «слабая (m, n, k) игра», где k-подряд вторым игроком не заканчивается игра со вторым игроком выигрывает.

Если weak (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 - ничья на бесконечной доске. Неясно, применима ли эта стратегия к любым доскам конечного размера. Неизвестно, может ли второй игрок форсировать ничью, когда 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 or n < 3. (m,n,3) is a win if m ≥ 3 and n ≥ 4 or m ≥ 4 and 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. Неизвестно, является ли (m, 4,4) победой или ничьей для 9 ≤ m ≤ 29.
• Компьютерный поиск Wei-Yuan Hsu и Chu-Ling Ko показал что и (7,7,5), и (8,8,5) - ничьи, что означает, что (m, n, 5) - ничья для m ≤ 8 и n ≤ 8. Компьютерный поиск по L. Виктор Аллис показал, что (15,15,5) - это победа, даже с одним из ограничительных правил Гомоку.
• (9,6,6) и (7,7,6) обе ничьи через пары.

Можно рассматривать варианты, разыгрываемые на многомерном поле вместо двухмерного.

Для случая k-in-a-row, когда доска представляет собой n-мерный гиперкуб со всеми ребрами длиной k, Хейлз и Джеветт доказали, что игра является ничьей, если k нечетно и

k ≥ 3-1

или если k четно и

k ≥ 2-2.

Они предполагают, что игра является ничьей также тогда, когда количество ячеек как минимум вдвое превышает количество строк, что происходит тогда и только тогда, когда

2 k ≥ (k + 2).

• Connect6
• Гомоку
• Обобщенный тиктакто Харари
• Игра Каплански
• Nd-игра
• Соедините четыре

1. ^ J. В. Х. М. Уйервейк и Х. Дж. Ван дер Херик, Преимущество инициативы, Информационные науки 122 (1) (2000) 43-58.
2. ^ Яап ван ден Херик, Jos W.H.M. Уитервейк, Джек ван Рейсвейк (2002). «Игры решены: сейчас и в будущем». Искусственный интеллект.
3. ^ Вэй Цзи Ма. «Обобщения крестиков-ноликов»
4. ^Сюй, Вэй-Юань; Ко, Чу-Линг; Сюэ, Чу-Сюань; Ву, И-Чен (2018). «Решающая 7,7,5-игра и 8,8,5-игра». Журнал ICGA. 40(3). Проверено 6 ноября 2019 г.
5. ^Элвин Р. Берлекамп, Джон Хортон Конвей, Ричард К. Гай. «Победа в ваших математических пьесах, Том 3», А. К. Петерс (2003)

• W.J. Ма, Обобщения крестиков-ноликов, [1 impression.