m,n,k-ゲーム
m,n,k-ゲームとは、三目並べや五目並べのようなゲームを一般化したもので、2人のプレイヤーがm×nマスの盤面上に自分の石を交互に置き、先に自分の石を縦・横・斜めのいずれかにk個並べたプレイヤーが勝利となるゲームの総称である[1][2]。三目並べは3,3,3-ゲーム、15路盤を使用した五目並べは15,15,5-ゲームとなる。並べる石の数のみに着目してk目並べ（k-in-a-row）とも呼ばれる。
戦略拝借論証 編集
組合せゲーム理論からの標準的な戦略拝借論証(Strategy stealing argument)により、m,n,k-ゲームには、後手が勝つことを保証する戦略（後手の必勝戦略）が存在しないことが示されている。これは、どちらかのプレイヤーに与えられた任意の位置の余分な石が、そのプレイヤーのチャンスを改善することができるためである。
戦略拝借論証は、「後手の必勝戦略がある」と仮定することで、後手に必勝戦略がないことを背理法的に証明するものである。先手は最初に任意の手を指す。その後、先手は後手のふりをして、後手必勝戦略を採る。その戦略に基づいて石を置くマスに既に石が置かれていない限り、先手は後手必勝戦略を採ることができる。もしそのマスに既に石が置かれていた場合でも、先手は再び任意の手を指した後に、同様に後手のふりをして後手必勝戦略を続けることができる。すなわち、（本来の）後手がどこに石を置いても先手を邪魔することはできないので、これは先手の必勝戦略となる。この矛盾は、「後手必勝の戦略がある」という元々の仮定が間違っていることを意味しており、よって後手の必勝戦略は存在しない。
この論証は、後手に必勝戦略がない（最善手を採れば先手が負けることはない）ことを証明しているだけで、先手必勝であることは証明していない。よって引き分けになることもあり得る。また、実際の先手必勝戦略が何であるかまでは示していない。
異なる盤面サイズへの結果の適用 編集
便利な概念として「弱い(m,n,k)」(weak (m,n,k))があり、これは後手の勝利でゲームが終わらないものを指す。弱い(m,n,k)が引き分けであれば、mやnを減らしたり、kを増やしたりしても引き分けになる。対照的に、弱い、または普通の(m,n,k)で先手が勝った場合は、より大きな「弱い(m,n,k)」でも先手が勝つ。
一般的な結果 編集
以下の記述は、先手・後手とも各局面で最善手を指すと仮定して、先手について記述している。
- 特定の(m0, n0, k0)が引き分けになる場合、k ≥ k0の(m0, n0, k)も、m ≤ m0かつn ≤ n0の(m, n, k0)も引き分けになる。同様に、(m0, n0, k0)が勝利の場合、k ≤ k0の(m0, n0, k)も、m ≥ m0かつn ≥ n0の(m, n, k0)も勝利となる。
- k ≥ 9では引き分けになる。k = 9で盤面が無限大の場合、後手はペアリング戦略で引き分けに持ち込める。無限大の盤面での引き分けとは、最善手を指し続ける限り、ゲームが永遠に続くことを意味する。ペアリング戦略とは、盤面の全てのマスをペアに分割して、後手は、常に先手が置いたマスとペアになるマスに石を置く戦略で、先手が石をk個並べられないことが保証される。無限大の盤面でのペアリング戦略は、任意の有限の大きさの盤面にも適用することができる。ただし、戦略に基づくと盤面の外に石を置かなければならなくなる場合が出てきてしまい、その場合には盤面上の（戦略に基づかない）任意の場所に石を置くことになるため、後手が負けとなる可能性がある[3]。
- 無限大の盤面においてk ≥ 8は引き分けとなる。この戦略が有限大の盤面に適用されるかどうかは不明である[2]。無限大の盤面でkが6か7のとき、後手が強制的に引き分けに持ち込めるかどうかは不明である。
- k ≥ 3で、k > mとk > nのいずれかの場合は引き分けとなる[3]。
特定の結果 編集
- k = 1 および k = 2 は先手が勝つ。ただし、(1,1,2)と(2,1,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 ≥ 30の場合の(m,4,4)は先手が勝ち(Lustenberger, 1967)、m ≤ 8の場合は引き分けになる[1]。9 ≤ m ≤ 29の場合の(m,4,4)は、引き分けか先手が勝つかは確定しない。
- Wei-Yuan HsuとChu-Ling Koによるコンピュータを使った探索では、(7,7,5)と(8,8,5)のどちらも引き分けとなることが示された[4]。すなわち、m ≤ 8かつn ≤ 8の場合の(m,n,5)は引き分けとなる。
- ビクター・アリスによるコンピュータを使った探索では、(15,15,5)（15路盤の五目並べ）は先手が勝つ。m ≥ 15かつn ≥ 15の場合の(m,n,5)は先手が勝つ。
- (9,6,6)と(7,7,6)は、後手がペアリング戦略を採れば引き分けとなる。
多次元の変種 編集
二次元の盤面の代わりに、多次元の盤面による変種を考えることができる。
例えば、n次元空間における、各辺をk個のマス目に区切った超立方体におけるk目並べを考える。HalesとJewett[5]は、kが奇数かつ
- k ≥ 3n - 1
の場合、または、kが偶数かつ
- k ≥ 2n+1 - 2
の場合、引き分けになることを証明した。
彼らは、マス（セル）の数が辺の数の2倍以上の場合も引き分けになる推測しているが、これは以下の場合かつ以下の場合にのみ発生する。
- 2 kn ≥ (k + 2)n
関連項目 編集
- 三目並べ
- 四目並べ - コネクト・フォー
- 五目並べ
- コネクト6（六目並べ）
- ハラリーの三目並べの一般化
- カプランスキーのゲーム
- ndゲーム
脚注 編集
- ^ a b J. W. H. M. Uiterwijk and H. J van der Herik, The advantage of the initiative, Information Sciences 122 (1) (2000) 43-58.
- ^ a b Jaap van den Herik, Jos W.H.M. Uiterwijk, Jack van Rijswijck (2002). "Games solved: Now and in the future". Artificial Intelligence.
- ^ a b Wei Ji Ma. "Generalizations of tic-tac-toe"
- ^ Hsu, Wei-Yuan; Ko, Chu-Ling; Hsueh, Chu-Hsuan; Wu, I-Chen (2018). “Solving 7,7,5-game and 8,8,5-game”. ICGA Journal 40 (3) 2019年11月6日閲覧。.
- ^ Elwyn R. Berlekamp, John Horton Conway, Richard K. Guy. "Winning ways for your mathematical plays, Volume 3", A K Peters (2003)
外部リンク 編集
- W.J. Ma, Generalizations of tic-tac-toe, [1]