はじめに
この記事はSpeedcubing Advent Calendar 2019の17日目の記事です。
[連載]ルービックキューブを解くプログラムを書いてみよう(前編) の続きをやっていきます。
前編では、ルービックキューブの状態/操作を表現するクラスを作り、状態を操作するメソッドを書きました。
これで、キューブをプログラム的に自由に回せる状態になったので、探索を進めていきましょう。
中編では単純な総当りで探索するので、計算量的な問題でまだ任意の状態のルービックキューブの解を見つけられるようにはなりませんが、ピラミンクスや2x2x2キューブなどの小さいパズルならこの方法でも解くことができます。
追記: 後編を書きました ルービックキューブを解くプログラムを書いてみよう(後編:状態のindex化, Two-Phase-Algorithm)
環境
環境については、前編と同様Python3.6以上です。
前編に引き続き、以下で出てくるコードをColaboratoryノートブック化したもの
も用意したので、[Play Groundで開く] をクリックし、順に実行しながら進めれば、環境構築など不要で楽だと思います。
総当りでルービックキューブを解く
ルービックキューブは 約 4.3*10^19 通りの状態数があり、最短手数は平均18手くらいです。
最悪の場合でも20手で完成することが知られています (c.f. https://www.cube20.org/) 。
総当りでは現実的な時間では太刀打ちできない規模ですが、まずは、総当りでルービックキューブを解くプログラムを書いてみて、それをベースに改善していきましょう。
ルービックキューブは状態数が膨大のため、幅優先探索はメモリの使用量が大きすぎます。
ルービックキューブを総当りで解くには、反復深化深さ優先探索が使えます。
探索の深さ (解の長さ) に制限を加えた深さ優先探索 (深さ制約探索) を制限深さを徐々に増やして繰り返していくやり方です。
完成状態を判定する関数
まず、探索の過程で現れる状態が完成状態かどうかを判定しなければいけないので判定する関数を書いておきます。
EO, CO, EP, CPが全部揃っていれば完成状態ということなのでそのように判定する関数を書きました。
def is_solved(state):
return (state.eo == [0] * 12 # EOが全部揃っている
and state.co == [0] * 8 # COが全部揃っている
and state.ep == list(range(12)) # EPが全部揃っている
and state.cp == list(range(8)) # CPが全部揃っている
)
操作が次の1手として使えるかを返す関数
前の1手を参照し、操作が次の1手として使えるかを返す関数を書いておきます。
単純なケースとして、同じ面を連続して回すのは不可です。 (R' R2 など)
他にも、U D U は U2 D と同じなので、まずいです。
これを避けるため、対面を続けて回すときは面の名前の辞書順で順序を固定しておきます(D Uの順は良いが、U Dの順は不可のように)。
inv_face = {
"U": "D",
"D": "U",
"L": "R",
"R": "L",
"F": "B",
"B": "F"
}
def is_move_available(prev_move, move):
"""
前の1手を考慮して次の1手として使える操作であるかを判定する
- 同じ面は連続して回さない (e.g. R' R2 は不可)
- 対面を回すときは順序を固定する (e.g. D Uは良いが、U Dは不可)
"""
if prev_move is None:
return True # 最初の1手はどの操作も可
prev_face = prev_move[0] # 1手前で回した面
if prev_face == move[0]:
return False # 同一面は不可
if inv_face[prev_face] == move[0]:
return prev_face < move[0] # 対面のときは、辞書順なら可
return True
反復深化深さ優先探索の実装
こんな感じで書きました。
start_search では、0手からスタートして、次第に手数を増やしながら深さ制限探索の実装を呼び、解を見つけたらそれを返します。
depth_limited_search の引数 depth は残りの深さを表し、これを減らしながら再帰的に探索を進め、depth=0のときに今探索している手数になるようにしています。
今考えている解 (手順) を管理するスタックを一つ用意します。
探索の過程で次のノードに入るときに操作をpush、出るときにpopすれば、今探索中の解が常にこのスタックに入った状態になり、状態ごとに解を持つ必要はありません。
class Search:
def __init__(self):
self.current_solution = [] # 今探索している手順を入れておくスタック
def depth_limited_search(self, state, depth):
if depth == 0 and is_solved(state):
# is_solvedがTrueなら完成しているので解が見つかったということでTrueを返す
# depth==0はなくてもいいが、depth > 0には解がないことがすでにわかっているのでいちいち判定関数を呼ぶ必要はない
return True
if depth == 0: # depth 0 までたどり着いたのに解が見つからなかったらFalseを返す
return False
# depth=0まで探索を続ける
prev_move = self.current_solution[-1] if self.current_solution else None # 1手前の操作
for move_name in move_names:
if not is_move_available(prev_move, move_name):
continue
self.current_solution.append(move_name)
if self.depth_limited_search(state.apply_move(moves[move_name]), depth - 1):
return True
self.current_solution.pop()
def start_search(self, state, max_length=20):
for depth in range(0, max_length): # 0から次第にに手数を増やしながら深さ制限探索を繰り返す
print(f"# Start searching length {depth}")
if self.depth_limited_search(state, depth):
# 解が見つかったらその時点でそれを返却
return " ".join(self.current_solution)
return None
反復深化深さ優先探索を実行してみる
この実装では、普通のランダムスクランブルに対しては現実的な時間では解は見つからないので、適当な6手のスクランブルを与えてみます。
34秒で解が見つかりました。当然ですが、スクランブルを逆から回したものが解となります。
import time
scramble = "R U R' F2 D2 L"
scrambled_state = scamble2state(scramble)
search = Search()
start = time.time()
solution = search.start_search(scrambled_state)
print(f"Finished! ({time.time() - start:.2f} sec.)")
if solution:
print(f"Solution: {solution}.")
else:
print("Solution not found.")
Finished! (34.11 sec.)
Solution: L' D2 F2 R U' R'.
枝刈りによる高速化 (IDA*探索)
探索を高速化するテクニックとして枝刈りがあります。
ルービックキューブに関する事前知識を使って、もうこれ以上探索しても意味がないと分かった場合はどんどん切り上げていくことができます。
このように反復深化深さ優先探索を知識ありにしたものを IDA探索 といいます (c.f. https://en.wikipedia.org/wiki/Iterative_deepening_A )。
例えば、depth=1 (残り1手) の時点で、揃っているパーツが1つも揃っていなかったらどうでしょうか。
ルービックキューブを完成状態から1手動かしてみてください。残り1手の状態では、少なくともコーナー4個とエッジ8個が揃っていなければ、次の1手で揃うことはありません。
ですので、そこから次の1手 depth=0 の探索を進めても無意味です。
同じように、depth=2(残り2手) のとき、コーナーはすべて崩れている可能性がありますが (L R など)、エッジは必ず4つは揃っていないと残り2手で完成する可能性はありません。
depth=3 (残り3手) では、その時点でエッジが少なくとも2個揃っていなければ残り3手で完成することはありません。
この知識を使った枝刈りを実装してみます。
def count_solved_corners(state):
"""
揃っているコーナーの個数をカウント
"""
return sum([state.cp[i] == i and state.co[i] == 0 for i in range(8)])
def count_solved_edges(state):
"""
揃っているエッジの個数をカウント
"""
return sum([state.ep[i] == i and state.eo[i] == 0 for i in range(12)])
def prune(depth, state):
"""
それ以上探索を進めても無意味ならTrueを返す
"""
if depth == 1 and (count_solved_corners(state) < 4 or count_solved_edges(state) < 8):
# 残り1手で揃っているコーナーが4個未満、もしくは、揃っているエッジが8個未満ならもう揃わない
return True
if depth == 2 and count_solved_edges(state) < 4:
# 残り2手で揃っているエッジが4個未満ならもう揃わない
return True
if depth == 3 and count_solved_edges(state) < 2:
# 残り3手で揃っているエッジが2個未満ならもう揃わない
return True
return False
class Search:
def __init__(self):
self.current_solution = []
def depth_limited_search(self, state, depth):
if depth == 0 and is_solved(state):
return True
if depth == 0:
return False
# 枝刈り (変えたのはこの2行の追加のみ)
if prune(depth, state):
return False
prev_move = self.current_solution[-1] if self.current_solution else None # 1手前の操作
for move_name in move_names:
if not is_move_available(prev_move, move_name):
continue
self.current_solution.append(move_name)
if self.depth_limited_search(state.apply_move(moves[move_name]), depth - 1):
return True
self.current_solution.pop()
def start_search(self, state, max_length=20):
for depth in range(0, max_length):
print(f"# Start searching length {depth}")
if self.depth_limited_search(state, depth):
return " ".join(self.current_solution)
return None
枝刈りした場合の探索時間
34秒かかった探索が1秒未満になりました。
このように、枝刈りはとても強力です。
scramble = "R U R' F2 D2 L"
scrambled_state = scamble2state(scramble)
search = Search()
start = time.time()
solution = search.start_search(scrambled_state)
print(f"Finished! ({time.time() - start:.2f} sec.)")
if solution:
print(f"Solution: {solution}.")
else:
print("Solution not found.")
Finished! (0.21 sec.)
Solution: L' D2 F2 R U' R'.
これだけでも、ピラミンクスや2x2x2キューブなど小さめのパズルなら現実的な時間で解くことができます。
一部のマニアには、ルービックキューブの一部分 (クロス手順や2x2x3ブロックを揃える手順など) を探索したいなどの人もいるかと思いますが、短いものであればここまでの方法で対応できます。
最初の解を見つけてもすぐにreturnせずに、探索を続けるように改変すれば、複数種類の解を探すこともできます。
次回予告: 状態のインデックス化 + Two-Phase-Algorithm
総当りでルービックキューブを解くプログラムを書き、枝刈りで多少高速化できましたが、任意の状態から短時間で解を見つけるには程遠いです。
現実的な時間でルービックキューブの準最適解を見つけるアルゴリズムとして、Two-Phase-Algorithmが広く使われています。
ルービックキューブの解法をを2つのフェーズに分解し、それぞれを総当りで解くというやり方です。
Phase1では、ルービックキューブを自由に動かして、<U,D,R2,L2,F2,B2> の動きだけで完成できる状態に持っていきます。
Phase2では、そこから <U,D,R2,L2,F2,B2> の動きだけを使って完成まで持っていきます。
Phase1は最悪で12手、だいたい10手くらい、
Phase2は最悪で18手、だいたい13〜14手くらいで完成できます (c.f. http://kociemba.org/math/symmetric.htm)。
探索深さ (手順長) が深くなればなればなるほど指数関数的に探索範囲も増えていくので、フェーズを分けずに総当りするとだいたい18手掛かるのに対し、10手の探索と13手の探索に分ければ速くなります。
Two-Phase-Algorithmは、程よく2フェーズに分解して手数の短い2ステップに分けたということも重要なのですが、加えて重要なのは、フェーズを2つに分けたことにより各フェーズの状態数が減り、状態をインデックス化し予め状態遷移表を作っておくことができる点と、枝刈り用の表も事前計算しておけるということです。
中編の実装は、探索のたびにStateクラスのインスタンスが生成されたり、完成状態の判定といった部分も遅いです。状態のインデックス化によってそこも改善していくことができます。
探索に時間をかければ最適解にどんどん近づけて行くことができるのも特徴です。
Two-Phase-Algorithmの実装は後編に回します。