ルービックキューブロボットのソフトウェアをアップデートした 3. 解法探索

この記事はなに？

私は現在2x2x2ルービックキューブを解くロボットを開発中です。これはそのロボットのプログラムの解説記事集です。

かつてこちらの記事に代表される記事集を書きましたが、この時からソフトウェアが大幅にアップデートされたので新しいプログラムについて紹介しようと思います。

該当するコードはこちらで公開しています。

関連する記事集

「ルービックキューブを解くロボットを作ろう！」

1. 概要編
2. アルゴリズム編
3. ソフトウェア編
4. ハードウェア編

ルービックキューブロボットのソフトウェアをアップデートした

1. 基本関数
2. 事前計算
3. 解法探索(本記事)
4. 状態認識
5. 機械操作(Python)
6. 機械操作(Arduino)
7. 主要処理

今回は解法探索編として、solver.pyを紹介します。

基本関数をインポートする

基本関数編で紹介した関数をインポートします

from basic_functions import *

グローバル変数

グローバルに置いた変数や配列です。

''' 配列の読み込み '''
''' Load arrays '''

with open('cp_cost.csv', mode='r') as f:
    cp_cost = [int(i) for i in f.readline().replace('\n', '').split(',')]
with open('co_cost.csv', mode='r') as f:
    co_cost = [int(i) for i in f.readline().replace('\n', '').split(',')]
cp_trans = []
with open('cp_trans.csv', mode='r') as f:
    for line in map(str.strip, f):
        cp_trans.append([int(i) for i in line.replace('\n', '').split(',')])
co_trans = []
with open('co_trans.csv', mode='r') as f:
    for line in map(str.strip, f):
        co_trans.append([int(i) for i in line.replace('\n', '').split(',')])
neary_solved_idx = []
with open('neary_solved_idx.csv', mode='r') as f:
    for line in map(str.strip, f):
        neary_solved_idx.append([int(i) for i in line.replace('\n', '').split(',')])
neary_solved_solution = []
with open('neary_solved_solution.csv', mode='r') as f:
    for line in map(str.strip, f):
        if line.replace('\n', '') == '':
            neary_solved_solution.append([])
        else:
            neary_solved_solution.append([int(i) for i in line.replace('\n', '').split(',')])


len_neary_solved = len(neary_solved_idx)
solution = []
solved_cp_idx = 0
solved_co_idx = 0

枝刈りやパズルを回す操作、そしてあと少しで揃う状態をCSVファイルから読み込みます。

また、solution配列は解法探索に用い、ここに要素を追加/削除していくことでこの配列に解法が格納されるようにします。

色の状態からパズルの状態配列を作る

これは少し煩雑です。パズルの各パーツにある色とその順番(パーツを斜め上から時計回りに見ていったときの色の現れる順番)を事前に手動で列挙しておいて、それに合うパーツを1つずつ探していきます。

すべての色が4色ずつ現れていなかったり、同じパーツが複数出てきたり、どのパーツ候補にも当てはまらないパーツがあったりするとエラーです。ここのエラー処理は結構面倒でした。

''' 色の情報からパズルの状態配列を作る '''
''' Create CO and CP arrays from the colors of stickers '''

def create_arr(colors):
    # すべての色が4つずつ現れているかチェック
    for i in j2color:
        cnt = 0
        for j in colors:
            if i in j:
                cnt += j.count(i)
        if cnt != 4:
            return -1, -1
    cp = [-1 for _ in range(8)]
    co = [-1 for _ in range(8)]
    set_parts_color = [set(i) for i in parts_color]
    # パーツ1つずつCPとCOを埋めていく
    for i in range(8):
        tmp = []
        for j in range(3):
            tmp.append(colors[parts_place[i][j][0]][parts_place[i][j][1]])
        tmp1 = 'w' if 'w' in tmp else 'y'
        co[i] = tmp.index(tmp1)
        if not set(tmp) in set_parts_color:
            return -1, -1
        cp[i] = set_parts_color.index(set(tmp))
    tmp2 = list(set(range(7)) - set(cp))
    if tmp2:
        tmp2 = tmp2[0]
        for i in range(7):
            if cp[i] > tmp2:
                cp[i] -= 1
    return cp, co

意味のない変数名を多用していて申し訳ありません。変数名を考えるのは大変ですが過去の自分にきつく言っておきます。

パズルの状態から解までの距離を求める

探索の途中で枝刈りに使うため、パズルの状態から解までの距離を知る必要があります。

''' その状態から解までの距離を返す '''
''' Returns the distance between the state and the solved state '''

def distance(cp_idx, co_idx):
    # CPだけ、COだけを揃えるときのそれぞれの最小コストの最大値を返す
    return max(cp_cost[cp_idx], co_cost[co_idx])

この関数は、「CPのみを揃える際の最小コスト」と「COのみを揃える際の最小コスト」の最大値を返します。この数字は、実際にCPとCOを両方揃えるときにかかるコストと同じか、または小さくなりますよね。distance関数が返す値を$h(cp, co)$、実際にかかるコストを$h^*(cp, co)$とすると、

$h(cp, co) \leq h^*(cp, co)$

ということです。このとき許容可能であると言い、必ず最短手順が探索できます。

パズルを回す

パズルを回す行為はインデックスレベルで行います。つまり、パズルの配列を作ってそれを置換するのではなく、パズルの状態を表す数値を使って表を見るだけで行えます。前回の事前計算で作った表を使います。

''' 遷移テーブルを使ってパズルの状態を変化させる '''
''' Change the state using transition tables '''

def move(cp_idx, co_idx, twist):
    return cp_trans[cp_idx][twist], co_trans[co_idx][twist]

ここで、co_transおよびcp_transが遷移を表す配列です。これについて、

遷移配列[回転前の状態番号][回転番号] == 回転後の状態番号

です。CPとCOのそれぞれにおいて遷移させます。

二分探索

二分探索は、事前計算で作った「少ないコストで揃う状態とその解法」を列挙した配列を検索するのに使います。

この配列はCPとCOを合わせた値($cp\times2187+co$: ここで2187はCOの最大値+1)をキーにソートされています。ただしこのキーは連続した整数として表されているわけではなく、この中から目的の番号を探すのは大変です。

そこで二分探索を用います。二分探索は$N$個の要素で構成されたソート済み配列から目的の要素を探し出すのに$\log_2N$(ここで底の2はしばしば省略されます)の計算回数、厳密にはループ、で済みます。普通にしらみ潰しに見ていったら最大で$N$回のループが必要であることを考えれば圧倒的に速いのが想像できると思います。例として$N=100, 100000, 1000000000=10^2, 10^5, 10^9$で$\log N$の値を見てみましょう。

$N$	$\log N$
$10^2$	$6.6$
$10^5$	$16.6$
$10^9$	$29.9$

$N$が大きくなるにつれて凄まじい差が現れます。

''' 二分探索 '''
''' Binary search '''

def bin_search(num):
    # 二分探索でneary_solvedの中で目的のインデックスを探す
    l = 0
    r = len_neary_solved
    while r - l > 1:
        c = (l + r) // 2
        if neary_solved_idx[c][0] == num:
            return c
        elif neary_solved_idx[c][0] > num:
            r = c
        else:
            l = c
    if r == len_neary_solved:
        return -1
    if num == neary_solved_idx[l][0]:
        return l
    elif num == neary_solved_idx[r][0]:
        return r
    else:
        return -1

深さ優先探索

解法探索の本丸であるIDA*探索の中身には深さ優先探索(厳密には少し違うかもしれません)が使われています。深さ優先探索は再帰で実装するとスッキリ書けるので、再帰で実装しました。基本的にはこれまで紹介した関数を使って回転させ、コストを計算して次にまた自分自身を呼びます。このとき、グローバル変数に置いたsolution配列に要素(回転番号)を追加/削除していくだけで、揃った時(Trueを返した時)のsolution配列が解法になります。これが再帰のスッキリした点です。

''' 深さ優先探索 '''
''' Depth-first search '''

def search(cp_idx, co_idx, depth, mode):
    global solution
    # 前回に回した手と直交する方向の回転を使う
    twist_idx_lst = [range(6, 12), range(6), range(12)]
    for twist in twist_idx_lst[mode]:
        # パズルを回転させる
        cost = cost_lst[twist]
        n_cp_idx, n_co_idx = move(cp_idx, co_idx, twist)
        # 残り深さを更新
        n_depth = depth - cost - grip_cost
        # 次の再帰に使う値を計算
        n_mode = twist // 6
        n_dis = distance(n_cp_idx, n_co_idx)
        if n_dis > n_depth:
            continue
        # グローバルの手順配列に要素を追加
        solution.append(twist)
        # 前計算した少ないコストで揃う状態のどれかになった場合
        if n_dis <= neary_solved_depth <= n_depth:
            tmp = bin_search(n_cp_idx * 2187 + n_co_idx)
            if tmp >= 0 and neary_solved_solution[tmp][0] // 6 != solution[-1] // 6:
                solution.extend(neary_solved_solution[tmp])
                return True, grip_cost + neary_solved_idx[tmp][1]
        # 次の深さの探索
        tmp, ans_cost = search(n_cp_idx, n_co_idx, n_depth, n_mode)
        if tmp:
            return True, ans_cost
        # 解が見つからなかったらグローバルの手順配列から要素をpop
        solution.pop()
    return False, -1

IDA*探索

やっと本丸です。とは言ってもIDA*探索は、深さ優先探索を最大深さを増やしながら何回も行うだけなので、そこまで複雑な実装ではありません。

探索する前から「もうすぐ揃う状態」になっている場合は探索しません。探索する場合はdepthを1から順番に大きくしながら深さ優先探索をします。解が見つかった時点で探索を打ち切り、その解(を次の処理がしやすいように変換したもの)を返します。

''' IDA*探索 '''
''' IDA* algorithm '''

def solver(colors):
    global solution
    # CPとCOのインデックスを求める
    cp, co = create_arr(colors)
    if cp == -1 or co == -1:
        return -1, -1
    cp_idx = cp2idx(cp)
    co_idx = co2idx(co)
    # 探索する前にもう答えがわかってしまう場合
    if distance(cp_idx, co_idx) <= neary_solved_depth:
        tmp = bin_search(cp_idx * 2187 + co_idx)
        if tmp >= 0:
            return [twist_lst[i] for i in neary_solved_solution[tmp]], neary_solved_idx[tmp][1]
    res_cost = 0
    # IDA*
    for depth in range(1, 34):
        solution = []
        tmp, cost = search(cp_idx, co_idx, depth, 2)
        if tmp:
            res_cost = depth + cost
            break
    if solution == []:
        return -1, res_cost
    return [twist_lst[i] for i in solution], res_cost

まとめ

今回はこのロボットの一番面白い(と筆者が感じている)ところである解法探索のプログラムを解説しました。ここで解説した方法は他の様々なパズルを解くのに使えると思います。パズルを解きたい方の参考になれば幸いです。