M, n, k-игра - M,n,k-game

An 11,10,5 игра

An м, н, к-игра это абстрактный настольная игра в котором два игроки по очереди кладут камень из своих цвет на м×п доска, победителем становится игрок, который первым получит k камни своего цвета в ряд по горизонтали, вертикали или диагонали.[1][2] Таким образом, крестики-нолики это 3,3,3-игра и свободный стиль гомоку это 15,15,5-игра. An м, н, к-игра также называется k-в ряд игра на м×п доска.

м, н, к-игры в основном математический интерес. Один стремится найти теоретико-игровой значение, результат игры с идеальная игра. Это известно как решение игра.

Аргумент кражи стратегии

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

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

Применение результатов к разным размерам досок

Полезное понятие - "слабый (м, п, к) игра », где второй игрок подряд не завершает игру выигрышем второго игрока.

Если слабый (м, п, к) это ничья, затем уменьшается м или же п, или увеличение k также приведет к ничьей.

И наоборот, если слабый или нормальный (м, п, к) это победа, то любой более крупный слабый (м, п, к) это победа.

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

Общие результаты

Следующие утверждения относятся к первому игроку в слабой игре, предполагая, что оба игрока используют оптимальную стратегию.

  • Если конкретный (м0, п0, k0) ничья, то (м0, п0, k) с k ≥ k0 это ничья, и (м, п, k0) с м ≤ м0 и п ≤ п0 это ничья. Аналогично, если (м0, п0, k0) выигрыш, то (м0, п0, k) с k ≤ k0 это победа, и (м, п, k0) с м ≥ м0 и п ≥ п0 это победа.
  • k ≥ 9 ничья: когда к = 9 и доска бесконечна, второй игрок может тянуть с помощью «стратегии пар». Ничья на бесконечной доске означает, что игра будет продолжаться вечно с идеальной игрой. Стратегия создания пар включает в себя разделение всех квадратов доски на пары таким образом, чтобы, всегда играя на пару квадратов первого игрока, второй игрок был уверен, что первый игрок не сможет получить k в линию. Стратегия пар на бесконечной доске может быть применена и к любой конечной доске - если стратегия требует сделать ход за пределами доски, то второй игрок делает произвольный ход внутри доски.[3]
  • k ≥ 8 - ничья на бесконечной доске. Неясно, применима ли эта стратегия к любым доскам конечного размера.[2] Неизвестно, может ли второй игрок форсировать ничью, когда k 6 или 7 на бесконечной доске.
  • k ≥ 3 и либо k> m или же k> n является ничьей, также по стратегии спаривания в размерности не меньше k (или тривиально невозможно выиграть, если оба меньше)[3]

Конкретные результаты

  • k = 1 и k = 2 - тривиальные победы, за исключением (1,1,2) и (2,1,2)
  • (3,3,3) - ничья (см. Крестики-нолики ), и (м,п, 3) - ничья, если м <3 или же п <3. (м,п, 3) выигрыш, если м ≥ 3 и п ≥ 4 или же м ≥ 4 и п ≥ 3.
  • (5,5,4) - ничья, что означает, что (м,п, 4) - ничья для м ≤ 5 и п ≤ 5, а (6,5,4) - выигрыш, а это значит, что (м,п, 4) выигрыш для м ≥ 6 и п ≥ 5 или же м ≥ 5 и п ≥ 6. (м, 4,4) - выигрыш для м ≥ 30 (Lustenberger, 1967) и ничья для м ≤ 8.[1] Неизвестно, если (м, 4,4) - это выигрыш или ничья для 9 ≤ м ≤ 29.
  • Компьютерный поиск Wei-Yuan Hsu и Chu-Ling Ko показал, что и (7,7,5), и (8,8,5) - ничьи,[4] что обозначает (м,п, 5) - ничья для м ≤ 8 и п ≤ 8. Компьютерный поиск по Л. Виктор Аллис показал, что (15,15,5) - это выигрыш, даже с одним из ограничительных правил Гомоку.
  • (9,6,6) и (7,7,6) - ничьи через пары.

Многомерный вариант

Смотрите также: 3D крестики-нолики

Можно рассматривать варианты, сыгранные на многомерной доске, а не на двумерной.

В случае k-в ряду, где доска является п-мерный гиперкуб со всеми ребрами длины k, Хейлз и Джуэтт доказали[5] что игра - ничья, если k это странно и

k ≥ 3п - 1

или если k даже и

k ≥ 2п+1 - 2.

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

2 kп ≥ (k + 2)п.

Смотрите также

Рекомендации

  1. ^ а б Дж. В. Х. М. Уйервейк и Х. Дж. Ван дер Херик, Преимущество инициативы, Информационные науки 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].