研究集会「組合せゲーム・パズル」，豊橋技術科学大学

Presentation on theme: "研究集会「組合せゲーム・パズル」，豊橋技術科学大学"— Presentation transcript:

1 研究集会「組合せゲーム・パズル」，豊橋技術科学大学
正六角盤面上の一般化三並べ 東京電機大学　理工学部 入倉弘介　　松浦昭洋 　　研究集会「組合せゲーム・パズル」，豊橋技術科学大学

2 ハラリイの一般化三並べ 三目並べを一般化した二人ゲーム m×m正方盤面で，n個のマスから成る図形 （n細胞生物）の完成を競う。
○ × ○ × × ○ 斜めは認めない 先手必勝手順が存在する生物 ＝ 勝ち型 先手必勝手順が存在しない生物 ＝ 負け型

3 正六角盤面上の一般化三並べ ゲームに用いる盤面を正六角形に変更 move(α, m) ： m×m×m盤面におけるn細胞生物α
３×３ 正方盤面 ２×２×２ 正六角盤面 move(α, m) ：　m×m×m盤面におけるn細胞生物α 　　　　　　　　　　　 　　　　　　　　　　　 の先手必勝手順の最小手数 負け型のとき、move(α, m) = ∞

4 ３細胞以下の生物に対する結果 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)

5 ４細胞生物に対する結果 全て先手必勝 ４細胞生物は以下の７通り move(α, m) = ∞ (m < 3) 6 (m > 4)

6 　　　　　　　　　　　　　　　の必勝法 ３手で両端の空いた“Bow”を作ればよい。

7 　　　　の必勝法 ３手でRockを作れば、複数の完成形が可能 ３ ２ １

8 　　　　の必勝法 ３手でRockを作れば、２方向で完成形が可能 ３ ２ １

9 の６手での必勝法 ３手め以降、環状にBowを作り続ける ５手勝利の不可能性 そのためには、４手で次の いずれかを作る必要あり。
　　　　　の６手での必勝法 ３手め以降、環状にBowを作り続ける　 ５手勝利の不可能性 そのためには、４手で次の いずれかを作る必要あり。 ２面待ちにするのが不可能。 2 5 4 3 3 4

10 　　　　の必勝法　 a b c

11 　　　　の必勝法（続） 　 i d,f c e k

12 ５細胞生物に対する結果 5細胞生物は、以下の22通り B C D F G I J K L M N P Q R S T U V W X Y Z

13 ５細胞生物に対する結果 5細胞生物は、以下の22通り 勝ち型 負け型 未解決

14 必勝法の分類 P,B,M J,G,N, Q,F, S,T,U Y,W K, V , L どの３生物、４生物から“進化”させるか 生物
Rock P,B,M J,G,N, Q,F, S,T,U Y,W K, V , L Bow ３I

15 　　　　　生物 P の必勝法 move(P, m) < 7 (m = 3) move(P, m) = 5 (m > 4)

16 　　　　　生物 B の必勝法 move(B, m) = 6 (m > 4) move(M, m) = 6 (m > 4)

17 　　　　　生物 J の必勝法 move(J, m) = 5 (m > 4) 生物G, Nも類似の方法。

18 　　　　　生物 Q の必勝法 move(Q, m) < 6 (m > 4) 生物Fも類似の方法。

19 生物 S の必勝法 move(S, m) < 7 (m > 4) move(T, m) = 6 (m > 4)
move(U, m) < 7 (m > 4)

20 　　　　　生物 Y の必勝法 最長手数の手順 b move(Y, m) < 10 (m > 5)

21 　　　　　生物 V の必勝法 a

22 　　　　　生物 V の必勝法 b (b-m) (b-n) move(V, m) < 8 (m > 4)

23 　　　　　生物 L の必勝法 最長手数の手順 move(L, m) < 12 (m > 4)

24 ５Xに対する後手の引き分け戦略 無限に広がる盤面を、隣り合う２つのマスをペアとし、階段状に並べる。 後手の戦略
○ × × ○ どの方向の５マスも、ペアのマスを必ず１つ含む　→　完成不可能

25 ５Dに対する後手の引き分け戦略 × 〇 ○

26 5細胞生物に対するまとめ (1) m = 3 のとき、move(P, m) < 7 (2) m > 4 のとき、
move(α, m) = (α = 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)

27 まとめ 正六角盤面上で、５細胞以下の生物について 先手必勝法と後手の引き分け戦略を考察した。 課題
　・必勝か否か未解決の５細胞生物（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