状態空間表現で色々な問題を解く

Python 人工知能

勉強と練習。


解き方は分からないけどルールとゴールは決まっている。そういう問題を解く場合、与えられた問題を状態空間表現により定義する。
状態空間表現を使うことで問題定義が厳密になるし、直接的解法が分からない問題の解く手続きの探索が簡単になる。


状態空間表現というのは以下の三つによって定義される。

  • 初期状態
  • ゴール状態
  • ルール (現在の状態とそのルールの適用によって生じる新しい状態によって表される)

それだけの知識で問題を解くプログラムを書いてみた。


とりあえず解答を見つけるための簡単な幅優先探索の関数を書いた。
現在の状態から取り得る次の状態（複数ある場合もある）を全部キューに放り込んで
ゴール状態が見つかるか、キューが空になる（解がなかった場合）まで探索する。


この探索アルゴリズムと状態空間表現とがあれば、試行錯誤的に問題を解くことができる。
とりあえず、水差し問題、川渡りの問題（２つ）、８パズルの状態空間表現を書いてやってみた。

import types

def breadth_first_search(start, goal, rules, invariant=None):
    """幅優先探索"""
    
    if not invariant:
        is_invariant = lambda last: True
    else:
        is_invariant = lambda last: invariant(*last)
        
    if isinstance(goal, types.FunctionType):
        is_goal = lambda last: goal(*last)
    else:
        is_goal = lambda last: last == goal
        
    l = [ [(start, None)] ]
    checked = set(start)
    
    while l:
        path = l.pop(0)
        
        last = path[-1][0]
        # ルールを適用して新しい状態をキューに保存
        for cond, action, desc in rules:
            if not cond(*last): continue
            next = action(*last)
            
            # 不変条件は満たされているか？
            if not is_invariant(next): continue
            
            # すでにチェック済み？
            if next in checked: continue
            checked.add(next)
            
            # もしかしてゴール状態？
            new_path = path + [(next, desc)]
            if is_goal(next): return new_path
            
            l.append(new_path)

例１：水差し問題

8ガロンと5ガロンの容器を使って4ガロンの水を用意する

def make_case_water_jug(capacity, target):
    start = (0, 0)
    goal  = lambda a, b: a == target or b == target
    cap_a, cap_b = capacity
    
    rules = (
        (lambda a, b: a > 0, lambda a, b: (0, b), u'aを空にする'),
        (lambda a, b: b > 0, lambda a, b: (a, 0), u'bを空にする'),
        (lambda a, b: a < cap_a, lambda a, b: (cap_a, b), u'aを満タンにする'),
        (lambda a, b: b < cap_b, lambda a, b: (a, cap_b), u'bを満タンにする'),
        (lambda a, b: a < cap_a and b > 0, lambda a, b: (min(cap_a, a+b), max(a+b-cap_a, 0)), u'aにbを移す'),
        (lambda a, b: a > 0 and b < cap_b, lambda a, b: (max(a+b-cap_b, 0), min(cap_b, a+b)), u'bにaを移す'),
        )
    invariant = None
    
    return start, goal, rules, invariant

start, goal, rules, invariant = make_case_water_jug(capacity=(8,5), target=4)
path = breadth_first_search(start, goal, rules, invariant)
if path:
    for i, (cur, desc) in enumerate(path):
        print '%2d %s %s' % (i, cur, desc)

結果

 0 (0, 0) None
 1 (0, 5) bを満タンにする
 2 (5, 0) aにbを移す
 3 (5, 5) bを満タンにする
 4 (8, 2) aにbを移す
 5 (0, 2) aを空にする
 6 (2, 0) aにbを移す
 7 (2, 5) bを満タンにする
 8 (7, 0) aにbを移す
 9 (7, 5) bを満タンにする
10 (8, 4) aにbを移す

例２：川渡りの問題

3人の宣教師と３人の人食い人種が、左岸から右岸に2人乗りのボートで川を渡ろうとしている。
川の両岸、あるいはボートの上で宣教師よりも人食い人種の数が多くなった場合、宣教師は人食い人種に食べられてしまう。全員が無事にボートを使って川を渡る手順を考えよ。(http://www.yuge.ac.jp/home/~nagao/teaching/AI/chap2/chap2-2.html)

def make_case_river_01():
    LEFT, RIGHT = MISSIONARY, CANNIBAL = 0, 1
    
    start = ((3, 3), (0, 0), LEFT )
    goal  = ((0, 0), (3, 3), RIGHT)
    
    rules = (
        # 左から右
        (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 2,
         lambda L, R, boat: ((L[MISSIONARY]-2,L[CANNIBAL]),(R[MISSIONARY]+2,R[CANNIBAL]), RIGHT),
         u'宣教師2人が左岸から右岸へ移動'),
        (lambda L, R, boat: boat == LEFT and L[CANNIBAL] >= 2,
         lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]-2),(R[MISSIONARY],R[CANNIBAL]+2), RIGHT),
         u'人食い2人が左岸から右岸へ移動'),
        (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 1,
         lambda L, R, boat: ((L[MISSIONARY]-1,L[CANNIBAL]),(R[MISSIONARY]+1,R[CANNIBAL]), RIGHT),
         u'宣教師1人が左岸から右岸へ移動'),
        (lambda L, R, boat: boat == LEFT and L[CANNIBAL] >= 1,
         lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]-1),(R[MISSIONARY],R[CANNIBAL]+1), RIGHT),
         u'人食い1人が左岸から右岸へ移動'),
        (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 1 and L[CANNIBAL] >= 1,
         lambda L, R, boat: ((L[MISSIONARY]-1,L[CANNIBAL]-1),(R[MISSIONARY]+1,R[CANNIBAL]+1), RIGHT),
         u'宣教師1人と人食い1人が左岸から右岸へ移動'),

        # 右から左
        (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 2,
         lambda L, R, boat: ((L[MISSIONARY]+2,L[CANNIBAL]),(R[MISSIONARY]-2,R[CANNIBAL]), LEFT),
         u'宣教師2人が右岸から左岸へ移動'),
        (lambda L, R, boat: boat == RIGHT and R[CANNIBAL] >= 2,
         lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]+2),(R[MISSIONARY],R[CANNIBAL]-2), LEFT),
         u'人食い2人が右岸から左岸へ移動'),
        (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 1,
         lambda L, R, boat: ((L[MISSIONARY]+1,L[CANNIBAL]),(R[MISSIONARY]-1,R[CANNIBAL]), LEFT),
         u'宣教師1人が右岸から左岸へ移動'),
        (lambda L, R, boat: boat == RIGHT and R[CANNIBAL] >= 1,
         lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]+1),(R[MISSIONARY],R[CANNIBAL]-1), LEFT),
         u'人食い1人が右岸から左岸へ移動'),
        (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 1 and R[CANNIBAL] >= 1,
         lambda L, R, boat: ((L[MISSIONARY]+1,L[CANNIBAL]+1),(R[MISSIONARY]-1,R[CANNIBAL]-1), LEFT),
         u'宣教師1人と人食い1人が右岸から左岸へ移動'),
        )
    invariant = lambda L, R, boat: not (0 < L[MISSIONARY] < L[CANNIBAL] or 0 < R[MISSIONARY] < R[CANNIBAL])
    
    return start, goal, rules, invariant

start, goal, rules, invariant = make_case_river_01()
path = breadth_first_search(start, goal, rules, invariant)
if path:
    for i, (cur, desc) in enumerate(path):
        print '%2d %s %s' % (i, cur, desc)

結果

 0 ((3, 3), (0, 0), 0) None
 1 ((3, 1), (0, 2), 1) 人食い2人が左岸から右岸へ移動
 2 ((3, 2), (0, 1), 0) 人食い1人が右岸から左岸へ移動
 3 ((3, 0), (0, 3), 1) 人食い2人が左岸から右岸へ移動
 4 ((3, 1), (0, 2), 0) 人食い1人が右岸から左岸へ移動
 5 ((1, 1), (2, 2), 1) 宣教師2人が左岸から右岸へ移動
 6 ((2, 2), (1, 1), 0) 宣教師1人と人食い1人が右岸から左岸へ移動
 7 ((0, 2), (3, 1), 1) 宣教師2人が左岸から右岸へ移動
 8 ((0, 3), (3, 0), 0) 人食い1人が右岸から左岸へ移動
 9 ((0, 1), (3, 2), 1) 人食い2人が左岸から右岸へ移動
10 ((1, 1), (2, 2), 0) 宣教師1人が右岸から左岸へ移動
11 ((0, 0), (3, 3), 1) 宣教師1人と人食い1人が左岸から右岸へ移動

例３：川渡りの問題２

さっきの問題の４人ずつ、３人乗りボートのバージョン。

def make_case_river_02():
    LEFT, RIGHT = MISSIONARY, CANNIBAL = 0, 1
    
    start = ((4, 4), (0, 0), LEFT )
    goal  = ((0, 0), (4, 4), RIGHT)
    
    rules = (
        # 左から右
        (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 3,
         lambda L, R, boat: ((L[MISSIONARY]-3,L[CANNIBAL]),(R[MISSIONARY]+3,R[CANNIBAL]), RIGHT),
         u'宣教師3人が左岸から右岸へ移動'),
        (lambda L, R, boat: boat == LEFT and L[CANNIBAL] >= 3,
         lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]-3),(R[MISSIONARY],R[CANNIBAL]+3), RIGHT),
         u'人食い3人が左岸から右岸へ移動'),
        (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 2 and L[CANNIBAL] >= 1,
         lambda L, R, boat: ((L[MISSIONARY]-2,L[CANNIBAL]-1),(R[MISSIONARY]+2,R[CANNIBAL]+1), RIGHT),
         u'宣教師2人と人食い1人が左岸から右岸へ移動'),
        
        (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 2,
         lambda L, R, boat: ((L[MISSIONARY]-2,L[CANNIBAL]),(R[MISSIONARY]+2,R[CANNIBAL]), RIGHT),
         u'宣教師2人が左岸から右岸へ移動'),
        (lambda L, R, boat: boat == LEFT and L[CANNIBAL] >= 2,
         lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]-2),(R[MISSIONARY],R[CANNIBAL]+2), RIGHT),
         u'人食い2人が左岸から右岸へ移動'),
        (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 1,
         lambda L, R, boat: ((L[MISSIONARY]-1,L[CANNIBAL]),(R[MISSIONARY]+1,R[CANNIBAL]), RIGHT),
         u'宣教師1人が左岸から右岸へ移動'),
        (lambda L, R, boat: boat == LEFT and L[CANNIBAL] >= 1,
         lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]-1),(R[MISSIONARY],R[CANNIBAL]+1), RIGHT),
         u'人食い1人が左岸から右岸へ移動'),
        (lambda L, R, boat: boat == LEFT and L[MISSIONARY] >= 1 and L[CANNIBAL] >= 1,
         lambda L, R, boat: ((L[MISSIONARY]-1,L[CANNIBAL]-1),(R[MISSIONARY]+1,R[CANNIBAL]+1), RIGHT),
         u'宣教師1人と人食い1人が左岸から右岸へ移動'),
        
        # 右から左
        (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 3,
         lambda L, R, boat: ((L[MISSIONARY]+3,L[CANNIBAL]),(R[MISSIONARY]-3,R[CANNIBAL]), LEFT),
         u'宣教師3人が右岸から左岸へ移動'),
        (lambda L, R, boat: boat == RIGHT and R[CANNIBAL] >= 3,
         lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]+3),(R[MISSIONARY],R[CANNIBAL]-3), LEFT),
         u'人食い3人が右岸から左岸へ移動'),
        (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 2 and R[CANNIBAL] >= 1,
         lambda L, R, boat: ((L[MISSIONARY]+2,L[CANNIBAL]+1),(R[MISSIONARY]-2,R[CANNIBAL]-1), LEFT),
         u'宣教師2人と人食い1人が右岸から左岸へ移動'),

        (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 2,
         lambda L, R, boat: ((L[MISSIONARY]+2,L[CANNIBAL]),(R[MISSIONARY]-2,R[CANNIBAL]), LEFT),
         u'宣教師2人が右岸から左岸へ移動'),
        (lambda L, R, boat: boat == RIGHT and R[CANNIBAL] >= 2,
         lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]+2),(R[MISSIONARY],R[CANNIBAL]-2), LEFT),
         u'人食い2人が右岸から左岸へ移動'),
        (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 1,
         lambda L, R, boat: ((L[MISSIONARY]+1,L[CANNIBAL]),(R[MISSIONARY]-1,R[CANNIBAL]), LEFT),
         u'宣教師1人が右岸から左岸へ移動'),
        (lambda L, R, boat: boat == RIGHT and R[CANNIBAL] >= 1,
         lambda L, R, boat: ((L[MISSIONARY],L[CANNIBAL]+1),(R[MISSIONARY],R[CANNIBAL]-1), LEFT),
         u'人食い1人が右岸から左岸へ移動'),
        (lambda L, R, boat: boat == RIGHT and R[MISSIONARY] >= 1 and R[CANNIBAL] >= 1,
         lambda L, R, boat: ((L[MISSIONARY]+1,L[CANNIBAL]+1),(R[MISSIONARY]-1,R[CANNIBAL]-1), LEFT),
         u'宣教師1人と人食い1人が右岸から左岸へ移動'),
        )
    invariant = lambda L, R, boat: not (0 < L[MISSIONARY] < L[CANNIBAL] or 0 < R[MISSIONARY] < R[CANNIBAL])
    
    return start, goal, rules, invariant

start, goal, rules, invariant = make_case_river_02()
path = breadth_first_search(start, goal, rules, invariant)
if path:
    for i, (cur, desc) in enumerate(path):
        print '%2d %s %s' % (i, cur, desc)

結果

 0 ((4, 4), (0, 0), 0) None
 1 ((4, 1), (0, 3), 1) 人食い3人が左岸から右岸へ移動
 2 ((4, 3), (0, 1), 0) 人食い2人が右岸から左岸へ移動
 3 ((4, 0), (0, 4), 1) 人食い3人が左岸から右岸へ移動
 4 ((4, 1), (0, 3), 0) 人食い1人が右岸から左岸へ移動
 5 ((1, 1), (3, 3), 1) 宣教師3人が左岸から右岸へ移動
 6 ((2, 2), (2, 2), 0) 宣教師1人と人食い1人が右岸から左岸へ移動
 7 ((0, 1), (4, 3), 1) 宣教師2人と人食い1人が左岸から右岸へ移動
 8 ((0, 3), (4, 1), 0) 人食い2人が右岸から左岸へ移動
 9 ((0, 0), (4, 4), 1) 人食い3人が左岸から右岸へ移動

例４：８パズル

def make_case_eight_puzzle(start=None, goal=None):
    
    if start is None:
        start = (( 5, 4, 3,
                   2, 1, 6,
                   7, 0, 8, ),)
        
    if goal is None:
        goal  = (( 1, 2, 3,
                   4, 5, 6,
                   7, 8, 0, ),)
    
    def swap(l, a, b):
        l = list(l)
        l[a], l[b] = l[b], l[a]
        return ( tuple(l), )
    
    rules = (
        (lambda l: l[0] == 0,
         lambda l: swap(l, 0, 1),
         u'',),
        (lambda l: l[0] == 0,
         lambda l: swap(l, 0 ,3),
         u'',),
        (lambda l: l[1] == 0,
         lambda l: swap(l, 1 ,0),
         u'',),
        (lambda l: l[1] == 0,
         lambda l: swap(l, 1, 2), 
         u'',),
        (lambda l: l[1] == 0,
         lambda l: swap(l, 1, 4),
         u'',),
        (lambda l: l[2] == 0,
         lambda l: swap(l, 2, 1), 
         u'',),
        (lambda l: l[2] == 0,
         lambda l: swap(l, 2, 5), 
         u'',),
        (lambda l: l[3] == 0,
         lambda l: swap(l, 3, 0), 
         u'',),
        (lambda l: l[3] == 0,
         lambda l: swap(l, 3, 4), 
         u'',),
        (lambda l: l[3] == 0,
         lambda l: swap(l, 3, 6),
         u'',),
        (lambda l: l[4] == 0,
         lambda l: swap(l, 4, 1),
         u'',),
        (lambda l: l[4] == 0,
         lambda l: swap(l, 4, 3),
         u'',),
        (lambda l: l[4] == 0,
         lambda l: swap(l, 4, 5), 
         u'',),
        (lambda l: l[4] == 0,
         lambda l: swap(l, 4, 7),
         u'',),
        (lambda l: l[5] == 0,
         lambda l: swap(l, 5, 2),
         u'',),
        (lambda l: l[5] == 0,
         lambda l: swap(l, 5, 4),
         u'',),
        (lambda l: l[5] == 0,
         lambda l: swap(l, 5, 8),
         u'',),
        (lambda l: l[6] == 0,
         lambda l: swap(l, 6, 3),
         u'',),
        (lambda l: l[6] == 0,
         lambda l: swap(l, 6, 7),
         u'',),
        (lambda l: l[7] == 0,
         lambda l: swap(l, 7, 4), 
         u'',),
        (lambda l: l[7] == 0,
         lambda l: swap(l, 7, 6), 
         u'',),
        (lambda l: l[7] == 0,
         lambda l: swap(l, 7, 8), 
         u'',),
        (lambda l: l[8] == 0,
         lambda l: swap(l, 8, 5),
         u'',),
        (lambda l: l[8] == 0,
         lambda l: swap(l, 8, 7),
         u'',),
        )
    invariant = None
    
    return start, goal, rules, invariant

start, goal, rules, invariant = make_case_eight_puzzle()
path = breadth_first_search(start, goal, rules, invariant)
if path:
    for i, (cur, desc) in enumerate(path):
        print '%2d %s %s' % (i, cur, desc)

結果

 0 ((5, 4, 3, 2, 1, 6, 7, 0, 8),) None
 1 ((5, 4, 3, 2, 0, 6, 7, 1, 8),) 
 2 ((5, 0, 3, 2, 4, 6, 7, 1, 8),) 
 3 ((0, 5, 3, 2, 4, 6, 7, 1, 8),) 
 4 ((2, 5, 3, 0, 4, 6, 7, 1, 8),) 
 5 ((2, 5, 3, 4, 0, 6, 7, 1, 8),) 
 6 ((2, 5, 3, 4, 1, 6, 7, 0, 8),) 
 7 ((2, 5, 3, 4, 1, 6, 0, 7, 8),) 
 8 ((2, 5, 3, 0, 1, 6, 4, 7, 8),) 
 9 ((2, 5, 3, 1, 0, 6, 4, 7, 8),) 
10 ((2, 0, 3, 1, 5, 6, 4, 7, 8),) 
11 ((0, 2, 3, 1, 5, 6, 4, 7, 8),) 
12 ((1, 2, 3, 0, 5, 6, 4, 7, 8),) 
13 ((1, 2, 3, 4, 5, 6, 0, 7, 8),) 
14 ((1, 2, 3, 4, 5, 6, 7, 0, 8),) 
15 ((1, 2, 3, 4, 5, 6, 7, 8, 0),)

８パズルの問題は幅優先探索のような網羅的探索法より発見的探索法ってのを使ったほうが良い。それはまた今度やる。