反復深化と下限値枝刈り法編
今回は「ペグ・ソリティア」というパズルを「反復深化」で解いてみましょう。
●ペグ・ソリテアとは？
ペグ・ソリテアは盤上に配置されたペグ (駒) を、最後にはひとつ残るように取り除いていく古典的なパズルです。ペグは、次のルールに従って移動し、除去することができます。
- ペグは隣にあるペグをひとつだけ跳び越して、空き場所へ着地する。
- 跳び越されたペグは盤上から取り除かれる。
- 移動方向はふつう縦横のみの 4 方向だが、ルールによっては斜め方向の移動を許す場合もある。
- 同じペグの連続跳び越しは 1 手と数える。
盤は今までに多数考案されていますが、33 穴英国盤、37 穴フランス盤、41 穴盤が有名です。下図に 33 穴英国盤を示します。
図 : 33 穴英国盤
33 のマスにペグがありますが、そこからひとつペグを取り除いてゲームを始めます。上図では黒丸でペグを表し、白丸で空き場所を表しています。ルールに従ってペグを移動し、最後にひとつだけ残ればクリアとなります。ただし、ペグを取り除く位置によって、解けない場合もあるので注意してください。
橋本哲氏の記事 (3) によると、最初の空き位置と最後に残ったペグの位置が同じになることを「補償型の解」といい、最初の空き位置が盤の中央で、なおかつ、補償型の解がある場合を「中央補償型の解」と呼ぶそうです。33 穴英国盤には、中央補償型の解があるそうです。
ペグ・ソリテアの場合、昔から補償型や中央補償型の解の最小手数を求めることが行われてきました。33 穴英国盤のように、ペグの数が多くなるとパソコンで解くのは大変になります。そこで、今回はサイズを小さくした簡単なペグ・ソリテアを反復深化で解いてみましょう。
●変形三角盤
下図は「変形三角盤」と呼ばれるペグ・ソリテアです。21 個のマスが少し変わった三角形に並んでいて、そこにペグを配置します。ペグは別のペグをひとつだけ跳び越えることで、任意の方向へ移動することができます。もちろん、着地する地点が空いていなければ、跳び越すことはできません。
図 : 変形三角盤
今回は上図のように 21 個のペグの中からひとつのペグを取り除き、最初の空き位置と最後に残ったペグの位置が同じになる「補償型の解」の最短手数を、反復深化で求めることにします。
●跳び先表と盤面の定義
ペグ・ソリテアの場合、ペグの「跳び先表」を用意すると簡単にプログラムできます。盤面は 1 次元配列を使って表し、座標を下図のように定義すると、跳び先表は次のようになります。
リスト : 跳び先表と盤面の定義
# 定数
const SIZE = 21 # 盤面の大きさ
const HOLE = 7 # 穴の位置
const MAX_JUMP = 19
# 跳び先表
const jump_table = Vector{Tuple{Int,Int}}[
[(3, 5)], # 1
[(3, 4)], # 2
[(4, 6), (5, 8)], # 3
[(3, 2), (6, 9), (7, 11)], # 4
[(3, 1), (7, 10), (8, 12)], # 5
[(4, 3), (7, 8), (9, 14), (10, 16)], # 6
[(10, 15), (11, 17)], # 7
[(5, 3), (7, 6), (11, 16), (12, 18)], # 8
[(6, 4), (10, 11), (14, 20)], # 9
[(7, 5), (11, 12)], # 10
[(7, 4), (10, 9)], # 11
[(8, 5), (11, 10), (18, 21)], # 12
[(14, 15)], # 13
[(9, 6), (15, 16)], # 14
[(10, 7), (14, 13), (16, 17)], # 15
[(10,6), (11,8), (15,14), (17,18)], # 16
[(11, 7), (16, 15), (18, 19)], # 17
[(12, 8), (17, 16)], # 18
[(18, 17)], # 19
[(14, 9)], # 20
[(18, 12)] # 21
]
# 盤面
const board = trues(SIZE)
跳び先表 jump_table は配列の配列で、その要素は跳び越すペグの位置と着地する位置を格納したタプルです。たとえば、3 のペグは 4 を跳び越して 6 に着地するという跳び方と、5 を跳び越して 8 に着地する跳び方があります。
盤面は配列 board で表します。ペグの有無は真偽値 (true, false) で表します。探索はこの配列を直接書き換え、バックトラックする時に元の値に戻します。ペグが 19 回移動すると、盤上のペグはひとつになります。その値を MAX_JUMP で表します。
●移動手順の表示
次は移動手順を表示する関数 print_moves() を作ります。
リスト : 手順の表示
function print_moves(moves)
print("($(moves[1][1]),$(moves[1][2])")
for i in 2 : MAX_JUMP
if moves[i - 1][2] == moves[i][1]
print(",$(moves[i][2])")
else
print(")($(moves[i][1]),$(moves[i][2])")
end
end
println(")")
end
移動手順は 1 手を (from, to) で表し、連続跳びの場合は (from, to1, to2, ..., toN) とします。引数 moves はタプルを格納した配列で、タプルの先頭要素が動かすペグの位置、二番目の要素が着地する位置を表します。初手を表示したあと、2 手目以降を for ループで表示します。1 手前の着地位置 moves[i - 1][2] と動かす位置 moves[i][1] が等しければ連続跳びです。カンマと跳び先を表示します。異なる場合は連続跳びではありません。 ")(" と i 番目の手順を表示します。最後に ")" を表示します。
●反復深化による解法
次は、反復深化でペグ・ソリテアを解く関数 solver() を作ります。
リスト : 単純な反復深化
function solver()
try
fill!(board, true)
board[15] = false
board[10] = false # 初手 15 -> 10 -> 7
for limit in 2 : MAX_JUMP
println("----- $limit -----")
ids(limit, 1, [(15, 7)])
end
catch e
println(e)
end
end
最初に board を true で初期化します。変数 board は const なので、board 自身の値を書き換えることはできませんが、そこに格納されている配列は書き換えることができます。最初に動かすことができるペグは 15 番と 17 番の 2 つがありますが、盤面は左右対称なので、初手は 15 番のペグを 7 番に動かすこととします。あとは for ループで上限値 limit を 1 つずつ増やしながら関数 ids() を呼び出します。解を見つけた場合、ids() は throw() で大域脱出するので、try - catch でそれを捕捉するようにします。
最後に、上限値まで深さ優先探索する関数 ids() を作ります。
リスト : 反復深化 (2)
function ids(limit, jc, moves)
if length(moves) == MAX_JUMP
if board[HOLE]
print_moves(moves)
throw("found!")
end
else
for from in 1 : SIZE
if !board[from]; continue; end
for (del, to) in jump_table[from]
if !board[del] || board[to]; continue; end
jc1 = jc + (from == moves[end][2] ? 0 : 1)
if jc1 <= limit
board[from] = false # ペグの移動
board[del] = false
board[to] = true
push!(moves, (from, to))
ids(limit, jc1, moves)
pop!(moves) # 元に戻す
board[to] = false
board[del] = true
board[from] = true
end
end
end
end
end
引数 limit が上限値、jc はペグが跳んだ回数で、moves に移動手順を格納します。length(moves) が MAX_JUMP で board[Hole] が true であれば、解を見つけることができました。print_moves() で手順を表示してから throw() で大域脱出します。そうでなければ、for ループでペグを選んで動かします。from, del の位置にペグがあり、to の位置にペグがない場合、from のペグを動かすことができます。
このプログラムのポイントは連続跳びを判断するところです。直前に移動した場所 move[end][1] からペグを動かすときは、連続跳びと判断することができますね。したがって、move[end][1] と from が等しい場合は跳んだ回数 jc を増やしません。異なっている場合は連続跳びではないので jc をひとつ増やします。これを変数 jc1 にセットします。
そして、jc1 が limit 以下であれば ids() を再帰呼び出しして探索を続行します。そうでなければ探索を打ち切ります。jc が limit に達していても連続跳びすることで解ける場合があることに注意してください。jc < limit とすると最短手順を求めることができなくなります。あとはペグを移動して、上限値 limit を上回るまで深さ優先探索を行うだけです。
●実行結果
それでは実行してみましょう。
julia> @time solver() ----- 2 ----- ----- 3 ----- ----- 4 ----- ----- 5 ----- ----- 6 ----- ----- 7 ----- ----- 8 ----- ----- 9 ----- ----- 10 ----- ----- 11 ----- ----- 12 ----- (15,7)(12,10)(4,11)(2,4)(8,3)(1,5)(13,15,7)(6,3,8,6,14)(21,12,10)(16,18)(20,9,11)(19,17,7) found! 123.254245 seconds (349 allocations: 19.906 KiB)
最短手数は 12 手、実行時間は Julia ver 1.6.4, Ubuntu 18.04 (WSL), Intel Core i5-6200U 2.30GHz で約 2 分かかりました。やっぱり、単純な反復深化では時間がかかりますね。そこで、ペグ・ソリティアの特徴を使って枝刈りを行うことにします。
●ペグのグループ分け
ペグ・ソリティアは、ペグをグループに分けることにより、枝刈りを行うことができる場合があります。ペグは移動できる場所が決まっていて、下図に示すグループに分けることができます。
図 : ペグのグループ分け
盤面の座標と見比べてください。たとえば、座標 1 番のペグは 5, 10, 12, 21 番にしか移動することができません。逆にいえば、この場所にあるペグは、これ以外の場所へ移動することはできないのです。これらのペグをひとつのグループとして考えましょう。同じようにペグの移動場所によって、上図のように 4 つのグループに分けることができます。ペグは移動しても所属するグループは変わりませんし、跳び越すペグは必ずほかのグループのペグになります。
ここで、グループ 3 とコーナーペグの個数に注目してください。コーナーペグの移動にはグループ 3 のペグが必要になりますが、コーナーペグの数は 6 つ、グループ 3 のペグの数も 6 つですから同じ個数しかありません。したがって、コーナー以外のペグがグループ 3 のペグを跳び越すと、コーナーペグの移動ができなくなります。つまり、4, 5, 9, 12, 15, 17 番のペグは、グループ 3 のペグを跳び越すことはできないのです。グループ 3 のペグを跳び越すことができるのはコーナーペグだけです。
この枝刈りは跳び先表を変更することで実現できます。修正は次のようになります。
リスト : ペグの跳び先表 (修正)
const jump_table1 = Vector{Tuple{Int,Int}}[
[(3, 5)], # 1
[(3, 4)], # 2
[(4, 6), (5, 8)], # 3
[(7, 11)], # 4 (3, 2), (6, 9) は禁止
[(7, 10)], # 5 (3, 1), (8, 12) は禁止
[(4, 3), (7, 8), (9, 14), (10, 16)], # 6
[(10, 15), (11, 17)], # 7
[(5, 3), (7, 6), (11, 16), (12, 18)], # 8
[(10, 11)], # 9 (6, 4), (14, 20) は禁止
[(7, 5), (11, 12)], # 10
[(7, 4), (10, 9)], # 11
[(11, 10)], # 12 (8, 5), (18, 21) は禁止
[(14, 15)], # 13
[(9, 6), (15, 16)], # 14
[(10, 7)], # 15 (14, 13), (16, 17) は禁止
[(10,6), (11,8), (15,14), (17,18)], # 16
[(11, 7)], # 17 (16, 15), (18, 19) は禁止
[(12, 8), (17, 16)], # 18
[(18, 17)], # 19
[(14, 9)], # 20
[(18, 12)] # 21
]
●実行結果 (2)
さっそく ids() を修正して試してみたところ、結果は次のようになりました。
julia> @time solver() ----- 2 ----- ----- 3 ----- ----- 4 ----- ----- 5 ----- ----- 6 ----- ----- 7 ----- ----- 8 ----- ----- 9 ----- ----- 10 ----- ----- 11 ----- ----- 12 ----- (15,7)(12,10)(4,11)(2,4)(8,3)(1,5)(13,15,7)(6,3,8,6,14)(21,12,10)(16,18)(20,9,11)(19,17,7) found! 12.846531 seconds (23.70 k allocations: 1.512 MiB, 0.12% compilation time)
約 10 倍の高速化に成功しましたが、まだまだ遅いですね。そこで、反復深化の常套手段である「下限値枝刈り法」を使って、プログラムのさらなる高速化に挑戦しましょう。
●下限値枝刈り法
下限値枝刈り法は難しいアルゴリズムではありません。たとえば、5 手進めた局面を考えてみます。探索の上限が 10 手とすると、あと 5 手だけ動かすことができますね。このとき、パズルを解くのに 6 手以上かかることがわかれば、ここで探索を打ち切ることができます。このように、必要となる最低限の手数が明確にわかる場合、この値を「下限値 (Lower Bound)」と呼びます。この下限値を求めることができれば、「今の移動手数 + 下限値」が探索手数を超えた時点で、枝刈りすることが可能になります。これが下限値枝刈り法の基本的な考え方です。
ペグ・ソリテアの場合、コーナーにあるペグは他のペグから跳び越されることはありません。コーナーのペグは自分でジャンプするしか移動する方法がないのです。したがって、コーナーにペグが残っていれば、最低でもその個数だけ移動手数が必要になります。変形三角盤の場合、コーナーは 1, 2, 13, 19, 20, 21 の 6 つあります。これを下限値として利用することにしましょう。
コーナーペグを判定するため配列 corner を定義します。
リスト : コーナーペグの位置
const corner = [
true,true,
false,
false,false,
false,false,false,
false,false,false,false,
true,false,false,false,false,false,true,
true, true
]
1, 2, 13, 19, 20, 21 を true に、あとは false に設定します。
●解法プログラム
下限値枝刈り法のプログラムは次のようになります。
リスト : 下限値枝刈り法による探索
function ids1(limit, jc, moves, lower)
if length(moves) == MAX_JUMP
if board[HOLE]
print_moves(moves)
throw("found!")
end
else
for from in 1 : SIZE
if !board[from]; continue; end
for (del, to) in jump_table1[from]
if !board[del] || board[to]; continue; end
jc1 = jc + (from == moves[end][2] ? 0 : 1)
lower1 = corner[from] ? lower - 1 : lower
if jc1 + lower1 <= limit
board[from] = false
board[del] = false
board[to] = true
push!(moves, (from, to))
ids1(limit, jc1, moves, lower1)
pop!(moves)
board[to] = false
board[del] = true
board[from] = true
end
end
end
end
end
引数 lower が下限値を表します。ペグを動かすとき、from の位置がコーナーかチェックします。そうであれば、新しい下限値 lower1 の値は lower - 1 になります。そうでなければ lower1 の値は lower のままです。jc1 + lower1 が limit より大きくなったら探索を打ち切ります。これだけの修正で下限値枝刈り法が機能します。とても簡単ですね。
最後に ids1() を呼び出す関数 solver1() を作ります。
リスト : 下限値枝刈り法
function solver1()
try
fill!(board, true)
board[15] = false
board[10] = false # 初手 15 -> 10 -> 7
for limit in 7 : MAX_JUMP
println("----- $limit -----")
ids1(limit, 1, [(15, 7)], 6)
end
catch e
println(e)
end
end
下限値の初期値は 6 で初手に移動するペグはコーナーにはありません。上限値 limit は 6 + 1 = 7 から始めます。あとは特に難しいところはないので説明は割愛いたします。
●実行結果 (3)
それでは実行結果を示します。
julia> @time solver1() ----- 7 ----- ----- 8 ----- ----- 9 ----- ----- 10 ----- ----- 11 ----- ----- 12 ----- (15,7)(12,10)(4,11)(2,4)(8,3)(1,5)(13,15,7)(6,3,8,6,14)(21,12,10)(16,18)(20,9,11)(19,17,7) found! 0.269959 seconds (266 allocations: 13.328 KiB)
実行時間は 0.27 秒でした。枝刈りを入れたプログラムよりも約 47 倍速くなりました。下限値枝刈り法の効果はとても高いですね。
下限値枝刈り法の場合、下限値の精度によって実行時間が大きく左右されます。今回は単純な方法で下限値を求めましたが、盤面が大きくなるとコーナーペグの下限値では不十分で、より精度の高い方法が必要になります。興味のある方は拙作のページ Puzzle DE Programming ペグ・ソリテア「トライトライ」 をお読みください。
●参考文献
- A.V.Aho,J.E.Hopcroft,J.D.Ullman, 『データ構造とアルゴリズム』, 培風館, 1987
- 高橋謙一郎, 『特集 悩めるプログラマに効くアルゴリズム』, C MAGAZINE 2000 年 11 月号, ソフトバンク
- 橋本哲, 『特集コンピュータパズルへの招待 ペグ・ソリテア編』, C MAGAZINE 1996 年 2 月号, ソフトバンク
●プログラムリスト
#
# peg21.jl : ペグ・ソリティア「変形三角盤」の解法
#
# Copyright (C) 2016-2021 Makoto Hiroi
#
# 定数
const SIZE = 21
const HOLE = 7
const MAX_JUMP = 19
# 跳び先表
const jump_table = Vector{Tuple{Int,Int}}[
[(3, 5)], # 1
[(3, 4)], # 2
[(4, 6), (5, 8)], # 3
[(3, 2), (6, 9), (7, 11)], # 4
[(3, 1), (7, 10), (8, 12)], # 5
[(4, 3), (7, 8), (9, 14), (10, 16)], # 6
[(10, 15), (11, 17)], # 7
[(5, 3), (7, 6), (11, 16), (12, 18)], # 8
[(6, 4), (10, 11), (14, 20)], # 9
[(7, 5), (11, 12)], # 10
[(7, 4), (10, 9)], # 11
[(8, 5), (11, 10), (18, 21)], # 12
[(14, 15)], # 13
[(9, 6), (15, 16)], # 14
[(10, 7), (14, 13), (16, 17)], # 15
[(10,6), (11,8), (15,14), (17,18)], # 16
[(11, 7), (16, 15), (18, 19)], # 17
[(12, 8), (17, 16)], # 18
[(18, 17)], # 19
[(14, 9)], # 20
[(18, 12)] # 21
]
# 盤面
const board = trues(SIZE)
# 跳び先表 (グループ分け)
const jump_table1 = Vector{Tuple{Int,Int}}[
[(3, 5)], # 1
[(3, 4)], # 2
[(4, 6), (5, 8)], # 3
[(7, 11)], # 4 (3, 2), (6, 9) は禁止
[(7, 10)], # 5 (3, 1), (8, 12) は禁止
[(4, 3), (7, 8), (9, 14), (10, 16)], # 6
[(10, 15), (11, 17)], # 7
[(5, 3), (7, 6), (11, 16), (12, 18)], # 8
[(10, 11)], # 9 (6, 4), (14, 20) は禁止
[(7, 5), (11, 12)], # 10
[(7, 4), (10, 9)], # 11
[(11, 10)], # 12 (8, 5), (18, 21) は禁止
[(14, 15)], # 13
[(9, 6), (15, 16)], # 14
[(10, 7)], # 15 (14, 13), (16, 17) は禁止
[(10,6), (11,8), (15,14), (17,18)], # 16
[(11, 7)], # 17 (16, 15), (18, 19) は禁止
[(12, 8), (17, 16)], # 18
[(18, 17)], # 19
[(14, 9)], # 20
[(18, 12)] # 21
]
# コーナーペグ
const corner = [
true,true,
false,
false,false,
false,false,false,
false,false,false,false,
true,false,false,false,false,false,true,
true, true
]
# 手順の表示
function print_moves(moves)
print("($(moves[1][1]),$(moves[1][2])")
for i in 2 : MAX_JUMP
if moves[i - 1][2] == moves[i][1]
print(",$(moves[i][2])")
else
print(")($(moves[i][1]),$(moves[i][2])")
end
end
println(")")
end
# 単純な反復深化
function ids(limit, jc, moves)
if length(moves) == MAX_JUMP
if board[HOLE]
print_moves(moves)
throw("found!")
end
else
for from in 1 : SIZE
if !board[from]; continue; end
for (del, to) in jump_table[from] # jump_table1 に変更すると速くなる
if !board[del] || board[to]; continue; end
jc1 = jc + (from == moves[end][2] ? 0 : 1)
if jc1 <= limit
board[from] = false
board[del] = false
board[to] = true
push!(moves, (from, to))
ids(limit, jc1, moves)
pop!(moves)
board[to] = false
board[del] = true
board[from] = true
end
end
end
end
end
# 反復深化 + 下限値枝刈り法
function ids1(limit, jc, moves, lower)
if length(moves) == MAX_JUMP
if board[HOLE]
print_moves(moves)
throw("found!")
end
else
for from in 1 : SIZE
if !board[from]; continue; end
for (del, to) in jump_table1[from]
if !board[del] || board[to]; continue; end
jc1 = jc + (from == moves[end][2] ? 0 : 1)
# コーナーに着地するペグは無い
lower1 = corner[from] ? lower - 1 : lower
if jc1 + lower1 <= limit
board[from] = false
board[del] = false
board[to] = true
push!(moves, (from, to))
ids1(limit, jc1, moves, lower1)
pop!(moves)
board[to] = false
board[del] = true
board[from] = true
end
end
end
end
end
# 解法
function solver()
try
fill!(board, true)
board[15] = false
board[10] = false # 初手 15 -> 10 -> 7
for limit in 2 : MAX_JUMP
println("----- $limit -----")
ids(limit, 1, [(15, 7)])
end
catch e
println(e)
end
end
function solver1()
try
fill!(board, true)
board[15] = false
board[10] = false # 初手 15 -> 10 -> 7
for limit in 7 : MAX_JUMP
println("----- $limit -----")
ids1(limit, 1, [(15, 7)], 6)
end
catch e
println(e)
end
end