М, п, к -game является абстрактной настольной игрой , в которой два игрока по очереди размещения камня своего цвета на м × н борта, победителя является игроком , который первым получает K камней своего собственного цвета в ряде , по горизонтали, вертикали или диагонали. [1] [2] Таким образом, крестики-нолики - это 3,3,3-игра, а гомоку вольного стиля - это игра 15,15,5. М, п, к -game также называется к -в-строку игра на м × н борту.
m, n, k -игры представляют в основном математический интерес. Каждый пытается найти теоретико-игровую ценность, результат игры с совершенной игрой . Это известно как решение игры.
Аргумент кражи стратегии [ править ]
Стандартный аргумент кражи стратегии из комбинаторной теории игр показывает, что ни в одной 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 - ничья на бесконечной доске. Неясно, применима ли эта стратегия к доскам любого конечного размера. [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 .
- Компьютерный поиск Wei-Yuan Hsu и Chu-Ling Ko показал, что и (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 к n ≥ ( к + 2) п .
См. Также [ править ]
Ссылки [ править ]
- ^ a b J. WHM Uiterwijk и H. J van der Herik, Преимущество инициативы , Информационные науки 122 (1) (2000) 43-58.
- ^ a b Яап ван ден Херик , Йос У. М. Уитервейк, Джек ван Рейсвейк (2002). «Игры решены: сейчас и в будущем». Искусственный интеллект.
- ^ Сюй, Вэй-Юань; Ко, Чу-Линг; Сюэ, Чу-Сюань; Ву, И-Чен (2018). «Решающая 7,7,5-игра и 8,8,5-игра» . Журнал ICGA . 40 (3) . Дата обращения 6 ноя 2019 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Элвин Р. Берлекамп, Джон Хортон Конвей, Ричард К. Гай. «Победа в ваших математических пьесах, Том 3», А.К. Петерс (2003)
