正六角盤面上の一般化三並べ
東京電機大学 理工学部
入倉弘介 松浦昭洋
研究集会「組合せゲーム・パズル」,豊橋技術科学大学
ハラリイの一般化三並べ


三目並べを一般化した二人ゲーム
m×m正方盤面で,n個のマスから成る図形
(n細胞生物)の完成を競う。
○ ×
○ ×
× ○
斜めは認めない
先手必勝手順が存在する生物
= 勝ち型
先手必勝手順が存在しない生物 = 負け型
正六角盤面上の一般化三並べ

ゲームに用いる盤面を正六角形に変更
3×3 正方盤面

2×2×2 正六角盤面
move(α, m) : m×m×m盤面におけるn細胞生物α
の先手必勝手順の最小手数
負け型のとき、move(α, m) = ∞
3細胞以下の生物に対する結果
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
4細胞生物に対する結果
4細胞生物は以下の7通り
全て先手必勝
move(α, m) = ∞ (m < 3)
6 (m > 4)
move(α, m) =
∞ (m = 2)
4 (m > 3)
の必勝法

3手で両端の空いた“Bow”を作ればよい。
の必勝法

3手でRockを作れば、複数の完成形が可能
1
2
1
2
3
の必勝法

3手でRockを作れば、2方向で完成形が可能
1
2
1
2
3
の6手での必勝法

3手め以降、環状にBowを作り続ける
2
5
5手勝利の不可能性
そのためには、4手で次の
いずれかを作る必要あり。
4
3
3
4
2面待ちにするのが不可能。
の必勝法
a
b
c
の必勝法(続)
d,f
i
e
k
c
5細胞生物に対する結果

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細胞生物に対する結果

5細胞生物は、以下の22通り
勝ち型
負け型
未解決
必勝法の分類

どの3生物、4生物から“進化”させるか
生物
Rock
P,B,M
Bow
J,G,N,
Q,F,
S,T,U
Y,W
3I
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)
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
ダウンロード

発表資料