ルービックキューブロボットのソフトウェアをアップデートした 2. 事前計算

この記事はなに？

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

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

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

関連する記事集

「ルービックキューブを解くロボットを作ろう！」
1. 概要編
2. アルゴリズム編
3. ソフトウェア編
4. ハードウェア編

ルービックキューブロボットのソフトウェアをアップデートした
1. 基本関数
2. 事前計算(本記事)
3. 解法探索
4. 状態認識
5. 機械操作(Python)
6. 機械操作(Arduino)
7. 主要処理

今回は事前計算編として、create_array.pyを紹介します。

ライブラリ等のインポート

ライブラリと基本関数をインポートします

from collections import deque
import csv

from basic_functions import *

状態の遷移テーブルを作る

前回の記事で作った、状態を遷移させる関数は少し遅いです。今後何十万回、何百万回と状態を遷移させるのにいちいちこの関数を使っていては時間がかかってしまいます。そこで、状態の遷移を即座に(計算量$O(1)$で)済ませるために、状態の遷移配列を作ります。

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

となるような遷移配列を作ります。

''' 状態の遷移テーブルを作る '''
''' Create state transition tables '''

def create_cp_trans():
    # CPの遷移配列
    # 8!個の状態それぞれに対して12種類の回転でどう遷移するかを記述
    cp_trans = [[-1 for _ in range(12)] for _ in range(fac[8])]
    # 遷移前の状態を表す番号idxを回す
    for idx in range(fac[8]):
        if idx % 1000 == 0:
            print(idx / fac[8])
        # idxからCP配列を作り、実際に回す
        cp = idx2cp(idx)
        for i, twist in enumerate(twist_lst):
            twisted_cp = [j for j in cp]
            for each_twist in twist:
                twisted_cp = move_cp(twisted_cp, each_twist)
            # CP配列を固有の番号に変換
            twisted_idx = cp2idx(twisted_cp)
            cp_trans[idx][i] = twisted_idx
    # CSVファイルに保存
    with open('cp_trans.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in cp_trans:
            writer.writerow(line)
    print('cp trans done')

def create_co_trans():
    # 処理の内容はcreate_cp_transのCPがCOになったのみ
    co_trans = [[-1 for _ in range(12)] for _ in range(3 ** 7)]
    for idx in range(3 ** 7):
        if idx % 1000 == 0:
            print(idx / 3 ** 7)
        co = idx2co(idx)
        for i, twist in enumerate(twist_lst):
            twisted_co = [j for j in co]
            for each_twist in twist:
                twisted_co = move_co(twisted_co, each_twist)
            twisted_idx = co2idx(twisted_co)
            co_trans[idx][i] = twisted_idx
    with open('co_trans.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in co_trans:
            writer.writerow(line)
    print('co trans done')

基本関数にある状態配列と状態番号を行き来する関数を使って効率良く配列を埋めていき、そして最後にできた配列をCSVファイルに保存します。

なお、回転に使っているtwist_lstは前回の基本関数編に出てきた配列で、パズルの独自の回転記号をまとめたものです。

枝刈り用配列を作る

実際にパズルの解法を探索する時には、「これ以上探索しても絶対に解が見つからない」とわかっている場合の探索を打ち切ります。これを枝刈りと言います。

「これ以上探索しても絶対に解が見つからない」かどうかをチェックするのに使うのがこの枝刈り用配列です。この配列にはCPとCO別々に、各状態についてあとコストいくつで揃うのかを記録しておきます。ちなみにCPとCOが別々なのは、両方を考慮すると状態の数が爆発的に増えてしまいメモリ使用量が膨大になってしまうからです。

''' 枝刈り用配列を作る '''
''' Create prunning tables '''

def create_cp_cost():
    # 状態の遷移配列を読み込む
    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(',')])
    # 8!個の各状態に対してコストを計算する
    cp_cost = [1000 for _ in range(fac[8])]
    # 幅優先探索をするのでキューに最初の(揃っている)状態を入れておく
    solved_cp_idx = [cp2idx(i) for i in solved_cp]
    que = deque([[i, 0] for i in solved_cp_idx])
    for i in solved_cp_idx:
        cp_cost[i] = 0
    cnt = 0
    # 幅優先探索
    while que:
        cnt += 1
        if cnt % 1000 == 0:
            print(cnt, len(que))
        # キューから状態を取得
        cp, cost = que.popleft()
        twists = range(12)
        # 回転させ、コストを計算する
        for twist, cost_pls in zip(twists, cost_lst):
            twisted_idx = cp_trans[cp][twist]
            n_cost = cost + grip_cost + cost_pls
            # コストの更新があったら配列を更新し、キューに追加
            if cp_cost[twisted_idx] > n_cost:
                cp_cost[twisted_idx] = n_cost
                que.append([twisted_idx, n_cost])
    # CSVファイルに保存
    with open('cp_cost.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        writer.writerow(cp_cost)
    print('cp cost done')

def create_co_cost():
    # 処理の内容はcreate_cp_transのCPがCOになったのみ
    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(',')])
    co_cost = [1000 for _ in range(3 ** 7)]
    solved_co_idx = list(set([co2idx(i) for i in solved_co]))
    que = deque([[i, 0] for i in solved_co_idx])
    for i in solved_co_idx:
        co_cost[i] = 0
    cnt = 0
    while que:
        cnt += 1
        if cnt % 1000 == 0:
            print(cnt, len(que))
        co, cost = que.popleft()
        twists = range(12)
        for twist, cost_pls in zip(twists, cost_lst):
            twisted_idx = co_trans[co][twist]
            n_cost = cost + grip_cost + cost_pls
            if co_cost[twisted_idx] > n_cost:
                co_cost[twisted_idx] = n_cost
                que.append([twisted_idx, n_cost])
    with open('co_cost.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        writer.writerow(co_cost)
    print('co cost done')

基本的な処理は幅優先探索によって行います。最初に揃っている状態24種類(同じ揃っているパズルでも見る方向によって状態は24通りになります)をキューに入れておき、while文の中でキューから状態を取得して順次処理していきます。

回転処理には先程作った状態の遷移配列を使います。もちろん使わなくてもできますが、かかる時間が桁違いです。

あと少しで揃う状態を列挙する

解法の探索ではIDA*というルービックキューブの解法探索に最適なアルゴリズムを使うのですが(詳しくは「ルービックキューブを解くロボットを作ろう！」のアルゴリズム編参照)、今回のプログラムではコスト: パズルが解けるまでにかかる時間に近い値を最小化するように解法を探索します。これを使うと手数など他の指標を使うよりも探索が重くなります。そこで、パズルが解けた状態まで一定コスト以上近かったらそこで探索を終了し、事前計算しておいた解をくっつけて全体の解とするようにしました。どれくらい「あと少しで解ける状態」を列挙するかはメモリや計算時間によって決める必要があります。

この状態列挙はパズルが揃っている状態から逆回転を使って作っていく必要があります。そこでまずは逆回転用の状態遷移配列を作ります。その後が本編です。

前編 逆回転による状態の遷移配列を作る

前述の通り、パズルの手順の逆回転に関する状態遷移配列を作ります。ここで、「前に作った遷移配列を使い回せないのか」と思う方がいらっしゃるかもしれませんが、ロボットの構造上、逆回転は前に作った配列に含まれていません。これはロボットがパズルを必ず反時計回りにしか回せない構造をしていることによります。詳しい話は「ルービックキューブを解くロボットを作ろう！」のハードウェア編をご覧ください。

''' 逆手順を回した際の状態遷移配列を作る '''
''' Create state transition tables for reverse twists'''

def create_cp_trans_rev():
    # 基本的な処理はcreate_cp_transと同じ
    cp_trans_rev = [[-1 for _ in range(12)] for _ in range(fac[8])]
    for idx in range(fac[8]):
        if idx % 1000 == 0:
            print(idx / fac[8])
        cp = idx2cp(idx)
        for i, twist in enumerate(twist_lst):
            twisted_cp = [j for j in cp]
            for each_twist in twist:
                twisted_cp = move_cp(twisted_cp, each_twist)
            twisted_idx = cp2idx(twisted_cp)
            # create_cp_transと違いcp_trans_rev[twisted_idx][i]を更新する
            cp_trans_rev[twisted_idx][i] = idx
    with open('cp_trans_rev.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in cp_trans_rev:
            writer.writerow(line)
    print('cp trans rev done')

def create_co_trans_rev():
    # 基本的な処理はcreate_co_transと同じ
    co_trans_rev = [[-1 for _ in range(12)] for _ in range(3 ** 7)]
    for idx in range(3 ** 7):
        if idx % 1000 == 0:
            print(idx / 3 ** 7)
        co = idx2co(idx)
        for i, twist in enumerate(twist_lst):
            twisted_co = [j for j in co]
            for each_twist in twist:
                twisted_co = move_co(twisted_co, each_twist)
            twisted_idx = co2idx(twisted_co)
            # create_co_transと違いco_trans_rev[twisted_idx][i]を更新する
            co_trans_rev[twisted_idx][i] = idx
    with open('co_trans_rev.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in co_trans_rev:
            writer.writerow(line)
    print('co trans rev done')

前の状態繊維配列を作ったときのプログラムにとても近いですが、一箇所違うところがあります。

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

としなくてはならないところです。

後編 あと少しで揃う状態を列挙する

状態の列挙には幅優先探索を使います。しかし、

• 状態の番号
• その状態から完成までのコスト
• その状態から完成までの手順

と、たくさんのパラメータを保持しておく必要があるので少し面倒です。

また、すでに訪れた状態でも、前に訪れた時よりもコストが小さく完成できる場合があることがあります。その場合の計算量を減らすため、(この方法は少し冗長でもう少し良い方法がある気がしますが)neary_solved_idx, neary_solved_cost_dic, neary_solved_idx_dicを使います。

実際の解法探索では、CPとCOの番号の組み合わせを使って二分探索を用いてこの配列にある要素を取得します。そのため、出来上がった配列はソートしてから保存します。

''' あと少しで揃う状態を列挙する '''
''' Create array of states that can be solved soon '''

def create_neary_solved():
    # 逆手順の遷移配列を読み込む
    cp_trans_rev = []
    with open('cp_trans_rev.csv', mode='r') as f:
        for line in map(str.strip, f):
            cp_trans_rev.append([int(i) for i in line.replace('\n', '').split(',')])
    co_trans_rev = []
    with open('co_trans_rev.csv', mode='r') as f:
        for line in map(str.strip, f):
            co_trans_rev.append([int(i) for i in line.replace('\n', '').split(',')])
    # neary_solved配列を更新していくが、計算を高速にするため他の配列も用意する
    neary_solved = []
    neary_solved_idx = set()
    neary_solved_cost_dic = {}
    neary_solved_idx_dic = {}
    # 幅優先探索のキューを作る
    solved_cp_idx = [cp2idx(i) for i in solved_cp]
    solved_co_idx = [co2idx(i) for i in solved_co]
    que = deque([])
    for i in range(24):
        twisted_idx = solved_cp_idx[i] * 2187 + solved_co_idx[i]
        neary_solved_idx.add(twisted_idx)
        neary_solved_cost_dic[twisted_idx] = 0
        neary_solved_idx_dic[twisted_idx] = len(neary_solved)
        neary_solved.append([twisted_idx, 0, []])
        que.append([solved_cp_idx[i], solved_co_idx[i], 0, [], 2])
    twists = [range(6, 12), range(6), range(12)]
    cnt = 0
    while que:
        cnt += 1
        if cnt % 1000 == 0:
            print(cnt, len(que))
        # キューから状態を取得
        cp_idx, co_idx, cost, move, mode = que.popleft()
        for twist in twists[mode]:
            # 回転後の状態とコストを取得、手順リストを更新
            cost_pls = cost_lst[twist]
            twisted_cp_idx = cp_trans_rev[cp_idx][twist]
            twisted_co_idx = co_trans_rev[co_idx][twist]
            twisted_idx = twisted_cp_idx * 2187 + twisted_co_idx
            n_cost = cost + grip_cost + cost_pls
            n_mode = twist // 6
            n_move = [i for i in move]
            n_move.append(twist)
            if neary_solved_depth >= n_cost and not twisted_idx in neary_solved_idx:
                # 新しく見た状態だった場合
                neary_solved_idx.add(twisted_idx)
                neary_solved_cost_dic[twisted_idx] = n_cost
                neary_solved_idx_dic[twisted_idx] = len(neary_solved)
                neary_solved.append([twisted_idx, n_cost, list(reversed(n_move))])
                que.append([twisted_cp_idx, twisted_co_idx, n_cost, n_move, n_mode])
            elif neary_solved_depth >= n_cost and neary_solved_cost_dic[twisted_idx] > n_cost:
                # すでに見た状態だがその時よりも低いコストでその状態に到達できた場合
                neary_solved_cost_dic[twisted_idx] = n_cost
                neary_solved[neary_solved_idx_dic[twisted_idx]] = [twisted_idx, n_cost, list(reversed(n_move))]
                que.append([twisted_cp_idx, twisted_co_idx, n_cost, n_move, n_mode])
    # solverパートでは2分探索を用いるため、予めインデックスでソートしておく
    neary_solved.sort()
    # インデックスとコストをCSVに配列を保存
    with open('neary_solved_idx.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in [i[:2] for i in neary_solved]:
            writer.writerow(line)
    # 手順をCSV配列に保存
    with open('neary_solved_solution.csv', mode='w') as f:
        writer = csv.writer(f, lineterminator='\n')
        for line in [i[2] for i in neary_solved]:
            writer.writerow(line)
    print('neary solved done')

まとめ

今回はルービックキューブの解法探索に用いる様々な配列を事前計算しました。実際には紹介した関数全てを実行することで目的の配列を作ります。ソルバーはこれらの配列を読み込んで、解法探索の中で使用します。