研究集会「組合せゲーム・パズル」,豊橋技術科学大学 正六角盤面上の一般化三並べ 東京電機大学 理工学部 入倉弘介 松浦昭洋 研究集会「組合せゲーム・パズル」,豊橋技術科学大学
ハラリイの一般化三並べ 三目並べを一般化した二人ゲーム m×m正方盤面で,n個のマスから成る図形 (n細胞生物)の完成を競う。 ○ × ○ × × ○ 斜めは認めない 先手必勝手順が存在する生物 = 勝ち型 先手必勝手順が存在しない生物 = 負け型
正六角盤面上の一般化三並べ ゲームに用いる盤面を正六角形に変更 move(α, m) : m×m×m盤面におけるn細胞生物α 3×3 正方盤面 2×2×2 正六角盤面 move(α, m) : m×m×m盤面におけるn細胞生物α の先手必勝手順の最小手数 負け型のとき、move(α, m) = ∞
3細胞以下の生物に対する結果 1細胞生物 one 3細胞生物 3I Rock Bow 1 2 b a 2細胞生物 two a b 2 1 move(one, 1) = 1 move(two, 1) = 2 move(Rock, 2) = move(Bow, 2) = 3 move(3I, m) = ∞ (m = 2) 3 (m > 3)
4細胞生物に対する結果 全て先手必勝 4細胞生物は以下の7通り move(α, m) = ∞ (m < 3) 6 (m > 4)
の必勝法 3手で両端の空いた“Bow”を作ればよい。
の必勝法 3手でRockを作れば、複数の完成形が可能 3 2 1
の必勝法 3手でRockを作れば、2方向で完成形が可能 3 2 1
の6手での必勝法 3手め以降、環状にBowを作り続ける 5手勝利の不可能性 そのためには、4手で次の いずれかを作る必要あり。 の6手での必勝法 3手め以降、環状にBowを作り続ける 5手勝利の不可能性 そのためには、4手で次の いずれかを作る必要あり。 2面待ちにするのが不可能。 2 5 4 3 3 4
の必勝法 a b c
の必勝法(続) i d,f c e k
5細胞生物に対する結果 5細胞生物は、以下の22通り B C D F G I J K L M N P Q R S T U V W X Y Z
5細胞生物に対する結果 5細胞生物は、以下の22通り 勝ち型 負け型 未解決
必勝法の分類 P,B,M J,G,N, Q,F, S,T,U Y,W K, V , L どの3生物、4生物から“進化”させるか 生物 Rock P,B,M J,G,N, Q,F, S,T,U Y,W K, V , L Bow 3I
生物 P の必勝法 move(P, m) < 7 (m = 3) move(P, m) = 5 (m > 4)
生物 B の必勝法 move(B, m) = 6 (m > 4) move(M, m) = 6 (m > 4)
生物 J の必勝法 move(J, m) = 5 (m > 4) 生物G, Nも類似の方法。
生物 Q の必勝法 move(Q, m) < 6 (m > 4) 生物Fも類似の方法。
生物 S の必勝法 move(S, m) < 7 (m > 4) move(T, m) = 6 (m > 4) move(U, m) < 7 (m > 4)
生物 Y の必勝法 最長手数の手順 b move(Y, m) < 10 (m > 5)
生物 V の必勝法 a
生物 V の必勝法 b (b-m) (b-n) move(V, m) < 8 (m > 4)
生物 L の必勝法 最長手数の手順 move(L, m) < 12 (m > 4)
5Xに対する後手の引き分け戦略 無限に広がる盤面を、隣り合う2つのマスをペアとし、階段状に並べる。 後手の戦略 ○ × × ○ どの方向の5マスも、ペアのマスを必ず1つ含む → 完成不可能
5Dに対する後手の引き分け戦略 × 〇 ○
5細胞生物に対するまとめ (1) m = 3 のとき、move(P, m) < 7 (2) m > 4 のとき、 move(α, m) = 5 (α = P, B, J, G, N, K) 6 (α = M, T) 6 (α = Q, F) 7 (α = S, U) 8 (α = V, W) 12 (α = L) < (3) m > 5のとき、move(Y, m) < 10 (4) move(α, m) = ∞ (α= D, X, m > 1)
まとめ 正六角盤面上で、5細胞以下の生物について 先手必勝法と後手の引き分け戦略を考察した。 課題 ・必勝か否か未解決の5細胞生物(R,C,Z,I) ・上下限の改良 (注記) 本発表後、以下の文献で同じ問題に対する解析が行われ ていることが判明した。同論文では、 R, C, Z, I, Y以外の生物に ついて、先手必勝法と後手の引き分け戦略が示されている。 (盤面サイズに関する議論はない) J.-P. Bode, H. Harborth, “Hexagonal polyomino achievement”, Discrete Math., vol. 212 (1-2), pp. 5-18, 2000