Document

正六角盤面上の一般化三並べ
東京電機大学理工学部
入倉弘介松浦昭洋
研究集会「組合せゲーム・パズル」，豊橋技術科学大学
ハラリイの一般化三並べ


三目並べを一般化した二人ゲーム
m×m正方盤面で，n個のマスから成る図形
（n細胞生物）の完成を競う。
○ ×
○ ×
× ○
斜めは認めない
先手必勝手順が存在する生物
＝勝ち型
先手必勝手順が存在しない生物＝負け型
正六角盤面上の一般化三並べ

ゲームに用いる盤面を正六角形に変更
３×３正方盤面

２×２×２正六角盤面
move(α, m) ： m×m×m盤面におけるn細胞生物α
の先手必勝手順の最小手数
負け型のとき、move(α, m) = ∞
３細胞以下の生物に対する結果
1細胞生物
3細胞生物
one
b
a
2細胞生物
1
b
1
a
2
two



Rock
Bow
move(one, 1) = 1
move(two, 1) = 2
move(Rock, 2) = move(Bow, 2) = 3
move(3I, m) = ∞ (m = 2)
3 (m > 3)
3I
b
2
1
a
４細胞生物に対する結果
４細胞生物は以下の７通り
全て先手必勝
move(α, m) = ∞ (m < 3)
6 (m > 4)
move(α, m) =
∞ (m = 2)
4 (m > 3)
の必勝法

３手で両端の空いた“Bow”を作ればよい。
の必勝法

３手でRockを作れば、複数の完成形が可能
１
２
１
２
３
の必勝法

３手でRockを作れば、２方向で完成形が可能
１
２
１
２
３
の６手での必勝法

３手め以降、環状にBowを作り続ける
2
5
５手勝利の不可能性
そのためには、４手で次の
いずれかを作る必要あり。
4
3
3
4
２面待ちにするのが不可能。
の必勝法
a
b
c
の必勝法（続）
d,f
i
e
k
c
５細胞生物に対する結果

B
L
U
5細胞生物は、以下の22通り
C
M
V
D
F
G
I
N
P
Q
R
Y
Z
W
X
J
K
S
T
５細胞生物に対する結果

5細胞生物は、以下の22通り
勝ち型
負け型
未解決
必勝法の分類

どの３生物、４生物から“進化”させるか
生物
Rock
P,B,M
Bow
J,G,N,
Q,F,
S,T,U
Y,W
３I
K,
V,
L
生物 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)
５Xに対する後手の引き分け戦略
無限に広がる盤面を、隣り合う２つの
マスをペアとし、階段状に並べる。
後手の戦略
○ ×
× ○
どの方向の５マスも、
ペアのマスを必ず１つ
含む → 完成不可能
５Dに対する後手の引き分け戦略
× 〇 ×
〇〇
× ○ ×
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)
まとめ

正六角盤面上で、５細胞以下の生物について
先手必勝法と後手の引き分け戦略を考察した。

課題
・必勝か否か未解決の５細胞生物（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

Download Report