m,n,k 型游戏

11,10,5 型游戏结果范例

m,n,k 型游戏是一种两人对弈的纯策略型棋类游戏的总称，指在 m×n 的棋盘上进行的 k 子棋（k-in-a-row）游戏，其为井字棋（3,3,3 型）与五子棋（15,15,5 型）的一般化形式。游戏中，双方使用不同颜色的棋子，轮流下在 m×n 的棋盘上，先把 k 个自己的棋子连成横、直、或斜线者获胜。

数学对m,n,k 型游戏有一定的兴趣和研究。博弈论寻找一盘完美的游戏的结果。这样的结果被称为一个游戏的解。

策略盗取论证

组合博弈论通过策略盗取论证可以证明m,n,k 型游戏中后抄子的玩家不管使用什么样的战略都不可能赢。原因是每个玩家的下一个子只会提高玩家赢的机会。策略盗取论证假设第二名玩家有一个赢局战略并向第一名玩家展示他的策略。一开始的时候第一名玩家把第一枚子放到任意一个地方。此后玩家假装他是第二名玩家并开始使用第二名玩家的赢局策略。只要这个策略不要求玩家把一枚子放到一个已经被占据的位置上他可以按照这个策略不断下子。假如策略要求玩家把下子在一个已经被占据的位置那么他就随便把子放在任何一个可以放的地方，然后再恢复第二名玩家的策略。由于第一名玩家多出来的那枚子对他无害，因此这个策略实际上是第一名玩家的策略。这个反证法证明初始的假设是错误的，第二名玩家没有赢局策略。

这个证明无法显示一个特定的局对于第一名玩家来说是和局还是赢局。它也不提供一个第一名玩家赢局的策略。

不同棋盘大小的结果

假如第二名玩家虽然不能赢，但是能够和的话那么m,n,k 型游戏就有一个弱解构。一个游戏的弱解构只有两个可能的结局（赢局和和局），而不是三个。

假如一个m,n,k型游戏是一个和局弱解构，那么降低m或n或者提高k也是和局弱解构。

相反的，假如一个m,n,k型游戏是一个赢局弱解构或强解构，那么任何更大的m,n,k型游戏也是一个赢局弱解构。

假如能够证明一个游戏是和局的话，那么也能证明它是一个和局弱解构，那么所有比它小的游戏也同样是和局弱解构。

结局

假如两名玩家都使用最佳策略，那么以下的结局适用于第一名玩家：

• 假如一个特别的m₀，n₀，k₀局是一个和局，那么m₀，n₀，k（k ≥ k₀）局也是和局，m，n，k₀（m ≤ m₀和n ≤ n₀）局也是和局。同样，假如一个m₀，n₀，k₀局是赢局，那么m₀，n₀，k（k ≥ k₀）局也是赢局，m，n，k₀（m ≤ m₀和n ≤ n₀）局也是赢局。
• k ≥ 9是和局：假如k = 9和棋盘是无限大那么第二名玩家可以通过使用“配对策略”达成和棋。使用完美的策略在无限大的棋盘上一盘局可以永无止境。配对策略把一个棋盘里所有的四方形都分为对，不管第一名玩家在哪里落子，第二名玩家就在第一名玩家落子的四方形的对里落子，这样第二名玩家可以保证第一名玩家无法达到k个棋子练成一线。在无限大棋盘上的配对策略也可以用在有限大的棋盘上，假如策略要求在棋盘外落子的话那么第二名玩家就在棋盘上随意一处落子即可。
• 在无限大棋盘上k ≥ 8是和局。这个策略在有限棋盘上是否适用不明。k是6或7的情况下第二名玩家是否能够在无限大棋盘上获得和局不明。
• k ≥ 3和k > m或k > n是和局。

特殊结局

• 除(1,1,2)和(2,1,2)外k = 1和k = 2都是显然的赢局。
• (3,3,3)是和局，假如m < 3或n < 3的话(m,n,3)是和局。假如m ≥ 3和n ≥ 4或m ≥ 4和n ≥ 3则(m,n,3)是赢局。
• (5,5,4)是和局，也就是说假如m ≤ 5和n ≤ 5的话(m,n,4)也是和局，(6,5,4)是赢局，也就是说假如m ≥ 6和n ≥ 5或m ≥ 5和n ≥ 6的话(m,n,4)也是赢局。假如m ≥ 9的话(m,4,4)是赢局，否则它是和局。
• 计算机模拟显示(7,7,5)和(8,8,5)是和局。也就是说假如m ≤ 8和n ≤ 8的话(m,n,5)是和局。计算机模拟还证明即使使用五子棋中限制更大的规则(15,15,5)是赢局。
• (9,6,6)和(7,7,6)均是和局。

多维

数学家也考虑多维棋盘上的M,n,k型游戏。

在一个n维超方形中假如所有的边都是k格，那么k成一行的局里，可以证明假如k是奇数而且k ≥ 3ⁿ − 1的话那么它是和局。假如k是偶数而且k ≥ 2ⁿ⁺¹ − 2的话也是和局。

这个证明的作者猜测假如格的数量至少是线的数量的两倍的话，当且仅当2 kⁿ ≥ (k + 2)ⁿ则是和局。

参见

• Kaplansky棋
• Harary井字棋
• 游戏复杂度