Введение
Абстрактная настольная игра для двух игроков.
Игра m,n,k — это абстрактная настольная игра, в которой два игрока по очереди размещают фишку своего цвета на поле размером m на n. Побеждает игрок, первым собравший k своих фишек в ряд по горизонтали, вертикали или диагонали. Таким образом, крестики-нолики — это игра 3,3,3, а гомоку в свободном стиле — игра 15,15,5. Игра m,n,k также называется «k в ряд» на поле m на n. Игры m,n,k представляют в основном математический интерес. Задача состоит в определении теоретической ценности игры, то есть результата игры при оптимальной стратегии обеих сторон. Это называется решением игры.
Аргумент кражи стратегии
Стандартный аргумент о краже стратегии из комбинаторной теории игр показывает, что в игре m,n,k не может существовать стратегии, гарантирующей победу второго игрока (выигрышная стратегия второго игрока). Это связано с тем, что добавление одного камня любому игроку в любой позиции может только улучшить его шансы на победу. Аргумент о краже стратегии исходит из предположения, что у второго игрока есть выигрышная стратегия, и демонстрирует выигрышную стратегию для первого игрока. Первый игрок начинает с произвольного хода. Затем он действует так, как будто он второй игрок, и применяет выигрышную стратегию второго игрока. Он может делать это до тех пор, пока стратегия не потребует разместить камень на "произвольной" клетке, которая уже занята. Если это происходит, он снова делает произвольный ход и продолжает действовать, используя выигрышную стратегию второго игрока. Поскольку дополнительный камень не может ему навредить, это выигрышная стратегия для первого игрока. Полученное противоречие означает, что исходное предположение неверно, и у второго игрока не может быть выигрышной стратегии. Этот аргумент не дает информации о том, является ли конкретная игра ничьей или выигрышной для первого игрока. Кроме того, он не предоставляет фактическую стратегию для первого игрока.
Применение результатов к различным размерам доски
Полезным понятием является "слабая (m,n,k) игра", в которой k подряд, сделанных вторым игроком, не завершают игру победой второго игрока. Если слабая (m,n,k) игра заканчивается вничью, то уменьшение m или n, или увеличение k также приведет к ничьей. И наоборот, если слабая или нормальная (m,n,k) игра заканчивается победой, то любая слабая (m,n,k) игра с большими значениями также закончится победой. Следует отметить, что доказательства ничьей, использующие стратегии сопоставления, также доказывают ничью для слабой версии и, следовательно, для всех версий с меньшими значениями.
Общие результаты
Следующие утверждения относятся к первому игроку в слабой игре, предполагая, что оба игрока используют оптимальную стратегию. Если конкретная (m0, n0, k0) является ничьей, то (m0, n0, k) с k ≥ k0 является ничьей, а (m, n, k0) с m ≤ m0 и n ≤ n0 является ничьей. Аналогичным образом, если (m0, n0, k0) является выигрышем, то (m0, n0, k) с k ≤ k0 является выигрышем, а (m, n, k0) с m ≥ m0 и n ≥ n0 является выигрышем. k ≥ 9 – ничья: когда k = 9 и доска бесконечна, второй игрок может обеспечить ничью, используя "стратегию пар". Ничья на бесконечной доске означает, что игра будет продолжаться бесконечно при безупречной игре. Стратегия пар заключается в разделении всех клеток доски на пары таким образом, что, всегда делая ход на паре клетки, сделанной первым игроком, второй игрок гарантирует, что первый игрок не сможет выстроить k в ряд. Стратегию пар с бесконечной доски можно применить и к любой конечной доске – если стратегия требует хода за пределами доски, второй игрок делает произвольный ход внутри доски. k ≥ 8 – ничья на бесконечной доске. Неизвестно, применима ли эта стратегия к каким-либо конечным размерам доски, что означает, что (m,n,5) является ничьей при m ≤ 8 и n ≤ 8. Компьютерный поиск, проведенный Л. Виктором Аллисом, показал, что (15,15,5) является выигрышем, даже с одним из ограничительных правил Гомоку. (9,6,6) и (7,7,6) – оба являются ничьими, достигнутыми с помощью стратегии пар.