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井字棋
• 遊戲複雜度