探索木・8パズル

Image from Gyazo

ノートブックの作成

Jupyter Notebook を起動し,新規にノートブックを作成してください. ノートブックのタイトルは AI-4 とします. ノートブックの作成方法は第1回の資料を参照してください.

8パズル

今回は 8パズル(8 Puzzle) を取り上げましょう.

8パズル

1から8の数字が書いてあるタイルが不規則に3 $\times$ 3のマス目に並べてある. タイルをスライドさせ,左上から順番に1から8まで並び替えるにはどうしたらよいか. Image from Gyazo

この問題を 状態空間モデル で表現します.

状態空間モデル

タイルの数字を$x_i$で表します($i$はタイルの位置). 例えば初期状態と目的状態を下記で与える. タイルがないマスは$b(ブランク)$と表していることに注意すること. Image from Gyazo $$ 初期状態: (x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9) = (3, 1, 5, b, 7, 4, 6, 8, 2) $$ $$ 目的状態: (x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9) = (b, 1, 2, 3, 4, 5, 6, 7, 8) $$ タイルに対する行動(操作)はブランクの位置に応じて決まる. 例えば,ブランクが 左上($x_1$) にあるときは,上($x_2$)と左($x_4$)のタイルと入れ替えることができる.

  • A1: $(b, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9) \rightarrow (x_2, b, x_3, x_4, x_5, x_6, x_7, x_8, x_9)$
  • A2: $(b, x_2, x_3, x_4, x_5, x_6, x_7, x_8, x_9) \rightarrow (x_4, x_2, x_3, b, x_5, x_6, x_7, x_8, x_9)$
同様に,ブランクが 上($x_2$) にあるときは,左上($x_1$),右上($x_3$),中央($x_5$)と入れ替えることができます.
  • A3: $(x_1, b, x_3, x_4, x_5, x_6, x_7, x_8, x_9) \rightarrow (b, x_1, x_3, x_4, x_5, x_6, x_7, x_8, x_9)$
  • A4: $(x_1, b, x_3, x_4, x_5, x_6, x_7, x_8, x_9) \rightarrow (x_1, x_3, b, x_4, x_5, x_6, x_7, x_8, x_9)$
  • A5: $(x_1, b, x_3, x_4, x_5, x_6, x_7, x_8, x_9) \rightarrow (x_1, x_5, x_3, x_4, b, x_6, x_7, x_8, x_9)$
上記に沿って全てを列挙すると24の行動が定義できる.

実装

クラスの定義

最初にライブラリをインポートします. 前回と同様に,探索問題の型 を表すSearchPrblem幅優先探索 を表すbreadth_firstをインポートします.

from simpleai.search import SearchProblem, breadth_first

次に 初期状態目的状態 を定義します. 初期状態は$(3, 1, 5, b, 7, 4, 6, 8, 2)$, 目的状態は$(b, 1, 2, 3, 4, 5, 6, 7, 8)$です. ここでは,$b$を$0$で表現していることに注意してください.

START = (
    3, 1, 5,
    0, 7, 4,
    6, 8, 2
)

GOAL = (
    0, 1, 2,
    3, 4, 5,
    6, 7, 8
)

インポートしたSearchProblemクラスをオーバライドして, 8パズルを表すEightPuzzleを定義します. オーバライドするメソッドは,actionsresultis_goalの3種類です.

class EightPuzzle(SearchProblem):

    def actions(self, state):
        ...
        
    def result(self, state, action):
        ...
        
    def is_goal(self, state):
        ...

actions(self, state)

ブランクの位置に応じた行動のリストを返します. 行動は全部で24パターンが存在します. また,リストのインデックスは0番から始まることに注意してください. 例えば,state[0]は$x_1$を表しています.

def actions(self, state):
    list = []
    
    if state[0] == 0: #左上がブランク
        list.append((
            state[1], state[0], state[2],
            state[3], state[4], state[5],
            state[6], state[7], state[8]
        ))
        list.append((
            state[3], state[1], state[2],
            state[0], state[4], state[5],
            state[6], state[7], state[8]
        ))            
    elif state[1] == 0: #上がブランク
        list.append((
            state[1], state[0], state[2],
            state[3], state[4], state[5],
            state[6], state[7], state[8]
        ))
        list.append((
            state[0], state[2], state[1],
            state[3], state[4], state[5],
            state[6], state[7], state[8],
        ))
        list.append((
            state[0], state[4], state[2],
            state[3], state[1], state[5],
            state[6], state[7], state[8]
        ))            
    elif state[2] == 0: #右上がブランク
        list.append((
            state[0], state[2], state[1],
            state[3], state[4], state[5],
            state[6], state[7], state[8]
        ))
        list.append((
            state[0], state[1], state[5],
            state[3], state[4], state[2],
            state[6], state[7], state[8]
        ))
    elif state[3] == 0: #左がブランク
        list.append((
            state[3], state[1], state[2],
            state[0], state[4], state[5],
            state[6], state[7], state[8]
        ))
        list.append((
            state[0], state[1], state[2],
            state[4], state[3], state[5],
            state[6], state[7], state[8]
        ))
        list.append((
            state[0], state[1], state[2],
            state[6], state[4], state[5],
            state[3], state[7], state[8]
        ))
    elif state[4] == 0: #中央がブランク
        list.append((
            state[0], state[4], state[2],
            state[3], state[1], state[5],
            state[6], state[7], state[8]
        ))
        list.append((
            state[0], state[1], state[2],
            state[4], state[3], state[5],
            state[6], state[7], state[8]
        ))
        list.append((
            state[0], state[1], state[2],
            state[3], state[5], state[4],
            state[6], state[7], state[8]
        ))
        list.append((
            state[0], state[1], state[2],
            state[3], state[7], state[5],
            state[6], state[4], state[8]
        ))                        
    elif state[5] == 0: #右がブランク
        list.append((
            state[0], state[1], state[5],
            state[3], state[4], state[2],
            state[6], state[7], state[8]
        ))
        list.append((
            state[0], state[1], state[2],
            state[3], state[5], state[4],
            state[6], state[7], state[8]
        ))
        list.append((
            state[0], state[1], state[2],
            state[3], state[4], state[8],
            state[6], state[7], state[5]
        ))                        
    elif state[6] == 0: #左下がブランク
        list.append((
            state[0], state[1], state[2],
            state[6], state[4], state[5],
            state[3], state[7], state[8]
        ))
        list.append((
            state[0], state[1], state[2],
            state[3], state[4], state[5],
            state[7], state[6], state[8]
        ))                        
    elif state[7] == 0: #下がブランク
        list.append((
            state[0], state[1], state[2],
            state[3], state[7], state[5],
            state[6], state[4], state[8]
        ))
        list.append((
            state[0], state[1], state[2],
            state[3], state[4], state[5],
            state[7], state[6], state[8]
        ))
        list.append((
            state[0], state[1], state[2],
            state[3], state[4], state[5],
            state[6], state[8], state[7]
        ))                        
    elif state[8] == 0: #右下がブランク
        list.append((
            state[0], state[1], state[2],
            state[3], state[4], state[8],
            state[6], state[7], state[5]
        ))
        list.append((
            state[0], state[1], state[2],
            state[3], state[4], state[5],
            state[6], state[8], state[7]
        ))
        
    return list

result(self, state, action)

行動actionを,そのまま次の状態として扱います.

def result(self, state, action):
    return action

is_goal(self, state)

状態stateGOALと一致すれば目的状態に達したと判断します.

def is_goal(self, state):
    return state == GOAL

解の探索

幅優先探索(探索木)breadth_firstを用いて解を探索します.

problem = EightPuzzle(initial_state=START)
result = breadth_first(problem, graph_search=True)

探索が終了したら,最終状態,パス,コストを表示します. 最終状態は(0, 1, 2, 3, 4, 5, 6, 7, 8)となっており目的状態に到達できたことがわかります. このとき,初期状態から目的状態までのコスト(ステップ数)は13です.

print("State:", result.state)
print("Path:", result.path())
print("Cost:", result.cost)
State: (0, 1, 2, 3, 4, 5, 6, 7, 8)
Path: [(None, (3, 1, 5, 0, 7, 4, 6, 8, 2)), ((0, 1, 5, 3, 7, 4, 6, 8, 2), (0, 1, 5, 3, 7, 4, 6, 8, 2)), ((1, 0, 5, 3, 7, 4, 6, 8, 2), (1, 0, 5, 3, 7, 4, 6, 8, 2)), ((1, 5, 0, 3, 7, 4, 6, 8, 2), (1, 5, 0, 3, 7, 4, 6, 8, 2)), ((1, 5, 4, 3, 7, 0, 6, 8, 2), (1, 5, 4, 3, 7, 0, 6, 8, 2)), ((1, 5, 4, 3, 7, 2, 6, 8, 0), (1, 5, 4, 3, 7, 2, 6, 8, 0)), ((1, 5, 4, 3, 7, 2, 6, 0, 8), (1, 5, 4, 3, 7, 2, 6, 0, 8)), ((1, 5, 4, 3, 0, 2, 6, 7, 8), (1, 5, 4, 3, 0, 2, 6, 7, 8)), ((1, 0, 4, 3, 5, 2, 6, 7, 8), (1, 0, 4, 3, 5, 2, 6, 7, 8)), ((1, 4, 0, 3, 5, 2, 6, 7, 8), (1, 4, 0, 3, 5, 2, 6, 7, 8)), ((1, 4, 2, 3, 5, 0, 6, 7, 8), (1, 4, 2, 3, 5, 0, 6, 7, 8)), ((1, 4, 2, 3, 0, 5, 6, 7, 8), (1, 4, 2, 3, 0, 5, 6, 7, 8)), ((1, 0, 2, 3, 4, 5, 6, 7, 8), (1, 0, 2, 3, 4, 5, 6, 7, 8)), ((0, 1, 2, 3, 4, 5, 6, 7, 8), (0, 1, 2, 3, 4, 5, 6, 7, 8))]
Cost: 13

探索過程の可視化(任意)

最後に探索過程を可視化してみましょう. 8パズルは前回の水差し問題に比べると,非常に複雑な問題であり, とても大きな探索木になってしまいます(探索した状態数は2116). この探索する状態数をいかに減らすかが,探索アルゴリズムの重要なキーとなります.

from simpleai.search.viewers import WebViewer

web_viewer = WebViewer()
result = breadth_first(problem, graph_search=True, viewer=web_viewer)

Image from Gyazo

参考書籍