<a href="http://www.hyuki.com/d/200610.html#i20061009222222">[結] 2006年10月 - 結城浩の日記 - ルソー展と陣取りゲーム・クイズ</a>

game study

前提

将棋盤(9×9のマス目を持つ盤)を使って二人が陣取りゲームをする。自分の番になったとき、空いているマス目（自分の陣地でも相手の陣地でもないマス目）の中からいくつか選んで「自分の陣地」にすることができる。一度に自分の陣地にできるのは、「1個」か「隣り合った2個」のいずれかである。隣り合った2個は縦の2個でも横の2個でもよい。パスはできない。自分の番になったとき空いているマス目がひとつもなかったら負け。

問題

この陣取りゲームは、以下のうちどれか。
(A)先手必勝　(B)先手必敗　(C)いずれでもない

Log of ROYGBを読んでちょっと考えた. パリティだけでは上手くいかない.
以下, AとBが対戦しているとし, Aからマスを取り始めるものとする.

平らな盤

囲碁で最初に天元打って, 以下後手の真似をするような感じ.

m*nでnが奇数の場合
先手必勝. 先手が中央1マスを取る. 以下, 後手と点対称にマスを取っていく.
n*nでnが偶数の場合
後手必勝. 後手が先手と点対称にマスを取っていく.
mとnがともに奇数の場合
先手必勝. 先手が中央1マスを取る. 以下, 後手と点対称にマスを取っていく.
mが奇数, nが偶数の場合
先手必勝. 先手が中央2マスを取れば良い. 以下は, 後手と点対称にマスを取っていく.
mが偶数, nが奇数の場合
先手必勝. さっきと同じ.
mが偶数, nが偶数の場合
後手必勝. 後手が先手と点対称にマスを取っていく.

円筒やトーラスの場合は, 端が無い(ことがある)ので解法が変わる.
これは飯食いながらちょっと考えれば分かりそうなので, また後で. 腹減った.
->まだ, 考え中. 3*3の円筒形と3*3のトーラスで必勝法が変わるという事態に.

円筒形

m=1の場合
n=1,2
先手必勝.
n>2
後手必勝. 先手がどう取ろうと, B先手で平らな1*(n-2)の盤面.
m=2の場合
n=1
先手必勝.
n=2
後手必勝.
n=2k+1
先手必勝. 先手が縦に2マス取ってB先手で平らな2*2kの盤面.
n=2k
後手必勝. 先手がどう取ろうと, 平らな点対称な盤面に取れる.
m=3の場合
n=1
先手必勝. 平らな1*3と同じ扱い.
n=2
先手必勝. 平らな2*3と同じ扱い.
n=3
ここからややこしい. 以下の円筒形3*3のパターンにより先手必勝. 先手が中央1マスだと先手必敗.
一般の場合

m偶数, n偶数の場合に後手必勝だけ確認.

円筒形 3*3のパターン


番号は画像参照. 1-3, 4-6, 7-9は繋がっている.
先手Aが1-4と取るとA必勝.

  • 後手が1マス
    • B2. A8で先手の勝ち (後手が3に6-9, 5に6-9, 6に7-9, 7に6-9, 9に5-6. 3-6に7, 5-6に7, 6-9に5, 9-7に6.)
    • B3, A9で先手の勝ち (後手が2に5-8, 5に7-8, 6に5-8, 7に5-6, 8に5-6. 2-5に8, 5-6に7, 5-8に6, 7-8に5.)
    • B5, A3で先手の勝ち (後手が2に6, 6に2, 7に8-9, 8に7-9, 9に7-8. 6-9に7, 7-8に9, 8-9に7, 9-7に8.)
    • B6, A2で先手の勝ち (後手が3に5, 5に3, 7に8-9, 8に7-9, 9に7-8. 5-8に7, 7-8に9, 8-9に7, 9-7に8.)
    • B7, A8-9で2*2なので先手の勝ち.
    • B8, A2で先手の勝ち (上と同様)
    • B9, A3で先手の勝ち (上と同様)
  • 後手が2マス
    • B2-3, A7で2*2
    • B2-5, A3-6で1*3の円筒
    • B3-6, A2-5で1*3の円筒
    • B5-6, A2-3で1*3の円筒
    • B5-8, A6で1*2が2つ
    • B6-9, A5で1*2が2つ
    • B7-8, A9で2*2
    • B8-9, A7で2*2
    • B9-7, A8で2*2

トーラス

トーラスなので横に倒していいぞ. やったね!

m=1の場合

1*nの円筒形と同じ. n=1,2で先手必勝. n>2で後手必勝.

m=2の場合

2*nの円筒形と同様. n奇数で先手必勝. n偶数で後手必勝.

m=3の場合
n=1
後手必勝. 1*3の円筒形と同じ扱い.
n=2
先手必勝. 2*3の円筒形と同じ扱い.
n=3
先手が1マス取って先手必勝.
一般の場合

m偶数, n偶数の場合に後手必勝だけ確認.

3*3のトーラス


番号は画像参照. 1-3, 4-6, 7-9, 1-7, 2-8, 3-9は繋がっている.
先手がA1-4と取ると先手の勝ちかと思って確かめてみる. 実は, 後手B5-8, B8-2, B6-9, B9-3の4パターン(対称形)で後手が必勝になる.
実際, B5-8の場合,

  • A2にはB6-9で3,7が余って後手勝ち.
  • A3にはB6-9で2,7が余って後手勝ち. 6, 9も同様に2,7が余る.
  • A7にはB3-6で2,9が余って後手勝ち.
  • A2-3にはB9で6,7が余って後手勝ち.
  • A7-9にはB3で2,6が余って後手勝ち.
  • A3-6にはB9で2,7が余って後手勝ち. A6-9, A9-3も同様に2,7が余る.

トーラスなので, 横に1-2と取っても1-4と取っているのと同じ.
したがって残りは1マスだけ取るパターン. どこを取っても同じなので, Aは5を取る. この場合, A必勝.
以下分岐.

  • g2
    • s4-7で先手必勝となる. s8とした場合には, g1-3で後手必勝. (2*2の平らな盤)
  • g3
    • s7
      • g1
        • s9で, 平らな1*2が2つ残る
      • g2
        • s6で, 平らな1*2が2つ残る
      • g4, g6, g8はg2と同じ扱い. g9はg1と同じ扱い
      • g1-2
        • s6-9で4, 8が残る
      • g4-6, g8-9はg1-2と同じ扱い. また, g1-4, g2-8, g6-9もg1-2と同じ扱い.
    • s1-4でも先手必勝. このときの形は, s2-5, g4-7と等しい.
  • g1-2
    • s6. このときの形は, s2-5, g4-7と等しい.
  • g1-3
    • s2-8. このとき, 2*2の平らな盤.
  • g4-6
    • s1-7. このとき, 2*2の平らな盤.

最終的な拡張

次数が4以下の頂点からなるグラフを考える. 取っていくルールは以下.

  1. 1度に取れる頂点は1個か2個
    1. 2個取る場合は, 辺で繋がった点を取る
  2. パスは許されない

この場合にはどちらが必勝か?
同様に, 次数が2^n以下の頂点からなるグラフを考える. この場合にはどちらが必勝か? (n次元直方体に拡張した場合を含む. クラインの壺もこれに含まれる)
同様に, 任意のグラフに対してこのルールを適用したとき, 先手と後手のどちらが必勝かを判定するアルゴリズムは存在するか?