探索木、宣教師、コイン

• 探索木：前回の例
  
  
  • 問題の表現：　 初期状態、目標状態（ゴール）
  • 操作の明確化：可能な操作(手)、禁止される操作(手)
  • 探索木の生成：可能な操作を枝として伸ばす
  • 枝刈り：　　　　　不要な枝を削除する(下記問題)→探索効率化
  • ゴールの判定： 枝に目標状態が出現すれば終了
    
    
  • 知識の有無
  
  
• 問題
  
  
  • ループ

    
    　　小中大
    　　　┃
    　　　　中
    　　小□大
    　　　┃
    　　　┃
    　　小中大
    
    

  • 部分木の重複

    
    小中大　　　中小大
    　┃　　　　　┃
    　　中　　　　　中
    小□大　　　□小大
    　┗━━┳━━┛
    　　　　　小
    　　　　　中
    　　　□□大
    
    

  • 探索空間の爆発：上の例では≒2*3^n-1
    　　　　　　　　　　　　(1→2→3×3→3×3×3→3×3×3×3→…)
    　　　　　　　　　　　　なぜこのような数になるか？
  
  
  
• 探索の種類
  
  
  • グラフと木

    
    　　Ｓ　　　　　　　　Ｓ
    ┏━┻━┓　　　　┏━┻━┓
    ┃　　　┃　　　　┃　　　┃
    Ａ━━━Ｂ　　　　Ａ　　　Ｂ
    ┃　　　┃　　　┏┻┓　┏┻┓
    Ｃ　　　Ｇ　　　Ｃ　Ｂ　Ａ　Ｇ
    　　　　　　　　　　┃　┃
    　　　　　　　　　　Ｇ　Ｃ
    
    

    ---

    ２分木 　　　　　　　　　　　○ 　　　　　┏━━━━━┻━━━━━┓ 　　　　　○　　　　　　　　　　　○ 　　┏━━┻━━┓　　　　　┏━━┻━━┓ 　　○　　　　　○　　　　　○　　　　　○ ┏━┻━┓　┏━┻━┓　┏━┻━┓　┏━┻━┓ ○　　　○　○　　　○　○　　　○　○　　　○

    
    
    
  • 幅優先 (breadth first)探索；（横型探索）

    
    　　　　　　　　　　　１
    　　　　　┏━━━━━┻━━━━━┓
    　　　　　２　　　　　　　　　　　３
    　　┏━━┻━━┓　　　　　┏━━┻━━┓
    　　４　　　　　５　　　　　６　　　　　７
    ┏━┻━┓　┏━┻━┓　┏━┻━┓　┏━┻━┓
    ８　　　９　１０　１１　１２　１３　１４　１５
    

    
    
  • 深さ優先 (depth first)探索；（縦型探索）

    
    　　　　　　　　　　　１
    　　　　　┏━━━━━┻━━━━━┓
    　　　　　２　　　　　　　　　　　９
    　　┏━━┻━━┓　　　　　┏━━┻━━┓
    　　３　　　　　６　　　　　１０　　　１３
    ┏━┻━┓　┏━┻━┓　┏━┻━┓　┏━┻━┓
    ４　　　５　７　　　８　１１　１２　１４　１５
    

  
  
  
• 探索のアルゴリズム
  
  
  • 幅優先探索

    
    S:=初期状態;
    if S が解 then success;
    　　　　　else L:=[S];
    fi;
    
    do while L≠[];
    　　H:=car(L);
    　　if H から枝が生成できる
    　　　　then
    　　　　do until {H から新たな枝が生成できない}
    　　　　　　S:=枝; 
    　　　　　　if S が解 then success;
    　　　　　　　　　　　else L:=set_tail(L,S);
    　　　　　　fi;
    　　　　od;
    　　fi;
    　　 L:=cdr(L);
    od;
    failure;
    
    
    　 小
    　 中
    [[[大],[],[]]]
    
    　 中　　　　　　 中
    [[[大],[小],[]],[[大],[],[小]]]
    
    　　　　　　　　　 小
    　　　　　　　　　 中　　　　　中
    [[[大],[小],[中]],[大],[],[]],[大],[],[小]],
    　　　　　　　　　　　　　　　　　　小
    　　　　　　　　　　中　　　　　　  中
     [[大],[中],[小]],[[大],[小],[]],[[大],[],[]]]
    

    
    
  • 深さ優先探索

    
    T:=[初期状態S];
    
    do while T≠[];
    　　H:=car(T);
    　　if H が解 then sucess; fi;
    　　if H から新たな枝が生成できる
    　　　　then
    　　　　do S:=枝; 
    　　　　　　if S が解 then success
    　　　　　　　　　　　else T:=append(S,T); 
    　　　　　　fi;
    　　　　od;
    　　fi;
    od;
    failure;
    
    　 小
    　 中
    [[[大],[],[]]]
    
    　　　　　　　　　小
    　 中　　　　　　 中
    [[[大],[小],[]],[[大],[],[]]]
    
    　　　　　　　　　　　　　　　　　　小
    　　　　　　　　　　中　　　　　　　中
    [[[大],[小],[中]],[[大],[小],[]],[[大],[],[]]]
    
    

  • 計算ルール
    枝を生成するとき生成可能な枝は一般に複数ある。 どれを先に生成するかのルールを計算ルールという。
  
  
  
• 幅優先と深さ優先の利点と欠点
  
  
  • 解を求める効率 (時間)
  • 探索空間の大きさ (空間)
  • 解の最短経路 (最適性)
  • 全解探索
  • ループの危険性 (完全性)
  
  
  
• 反復深化法 (iterative deepening)
  ある一定の深さでみつからなければ別の枝を探索する

• 初期状態をテーブルに登録する
• 生成したサブゴール(副目標)がテーブルに登録されていれば実行しない
• 登録されていなければサブゴールをテーブルに登録する

• カードゲーム
  
  1から7の数字を書いたカードが2枚ずつ計14枚ある。
  そしてこれを1列に並べ，
  
  
  • 2枚のnの間にはカードがn枚 (1≦n≦7)
  
  はさまれるように14枚のカードを並べて下さい。
  
  
  
  
  
  
• ５パズルゲーム
  
  

宣教師と人食い人種

各３人の宣教師と人食い人種が川の右岸から左岸に一隻のボートで無事に渡るには どうしたらようか。ただしボートには一度に二人しか乗れず、また宣教師の数が 人食い人種より少なくなると危害が加えられる。

　　　　　初期状態　　　　　　目標
　　　　　┃　　　┃　　　　┃　　　┃
　　○○○┃　　　┃　　　　┃　　　┃　○○○
　　×××┃＝　　┃　　　　┃　　＝┃　×××
　　　　　┃　　　┃　　　　┃　　　┃

• 問題表現：右岸での宣教師、人食い人種、ボートの数で表現
  初期状態；(3,3,1) ⇒⇒⇒ 最終状態：(0,0,0)
  
  
• 探索木（search tree）
  枝の関係は互いにORの関係になっているのでOR木とも呼ぶ。
  
  
• 状態の種類
  • すべての状態：4×4×2＝32
  • 食べられる状態：(2,1,*),(2,0,*),(1,0,*),(1,2,*),(1,3,*),(2,3,*)
  • ありえない状態：(3,3,0),(0,0,1)
  
  
  
• 状態遷移(有限オートマトン)

  
  
  　　　　　(3,3,1)	　　　 ○○○×××＝
  　┏━━━━╋━━━━┓
  (3,2,0) 　　┃　　　　┃　　○○○××　　×＝
  　　　　　(3,1,0) 　　┃　　○○○×　　　××＝
  　　　　　　┃　　(2,2,0)　 ○○××　　　○×＝
  　　　　　　┗━┳━━┛
  　　　　　　　(3,2,1)	　　 ○○○××＝　×
  　　　　　　　　┃
  　　　　　　　(3,0,0)	　　 ○○○　　　　×××＝
  　　　　　　　　┃
  　　　　　　　(3,1,1)	　　 ○○○×＝　　××
  　　　　　　　　┃
  　　　　　　　(1,1,0)	　　 ○×　　　　　○○××＝
  　　　　　　　　┃
  　　　　　　　(2,2,1)	　　 ○○××＝　　○×
  　　　　　　　　┃
  　　　　　　　(0,2,0)	　　 ××　　　　　○○○×＝
  　　　　　　　　┃
  　　　　　　　(0,3,1)	　　 ×××＝　　　○○○
  　　　　　　　　┃
  　　　　　　　(0,1,0)	　　 ×　　　　　　○○○××＝
  　　　　　　┏━┻━━┓
  　　　　　(1,1,1) 　　┃　　○×＝　　　　○○××
  　　　　　　┃　　(0,2,1)　 ××＝　　　　○○○×
  　　　　　　┗━┳━━┛
  　　　　　　　(0,0,0)	　　　　　　　　　 ○○○×××＝
  
  
  (3,3,1)┳(3,2,0)
         ┣(3,1,0)┳(3,2,1)━(3,0,0)━(3,1,1)━(1,1,0)┓
         ┗(2,2,0)┛　　　　　　　　　　　　　　　　　 ┃
     ┏━━━━━━━━━━━━━━━━━━━━━━━━┛
  (2,2,1)━(0,2,0)━(0,3,1)━(0,1,0)┳(1,1,1)┓
  　　　　　　　　　　　　　　　　　 ┗(0,2,1)┻(0,0,0)
  
  探索木と有向グラフ/有限オートマトン
  
  

  状態空間探索（state-space search）

• ２組の夫婦が川を渡ろうとした。
• あいにく２人乗りのボートが１つしかない、船頭もいないし、橋もないので、 自分たちで漕いで渡るしかない。
• しかしボートが漕げるのは男だけである。
• ところが夫２人は嫉妬深く、 ボートの中にしろ、川岸にしろ、自分がいないときに妻が他の男と一緒にいるのを 許さない。
• 最小の往復回数でめでたく２組の夫婦が川を渡るにはどうすればよいか。

初期状態　　　　　　					目標状態
　　　　       ┃　　　┃	┃　　　┃
夫1,妻1,夫2,妻2┃ボ　　┃	┃　　ボ┃夫1,妻1,夫2,妻2
　　　　       ┃　　　┃	┃　　　┃

可能な渡り方
	夫1
	夫2
	夫1,妻1
	夫2,妻2
	夫1,夫2
嫉妬条件
	夫1,妻2
	夫2,妻1

解は２つ

• 農夫が狼と山羊とキャベツを持って川の左岸にいます。
• 農夫はこれらを川の右岸へ運ばなければいけませんが、ボートにはそのうちのひとつしか乗せることができません。
• 狼は山羊を好んで食べるため、この 2 つを同じ岸に残すことはできません。
• また、山羊はキャベツを好んで食べるため、この 2 つも同じ岸に残すことはできません。

• 第１６回世界コンピュータ将棋選手権にて、Bonanzaが優勝
  http://www.magnolia.co.jp/bona.html
• コンピュータ将棋協会
  http://www.computer-shogi.org/

  ---

• 情報処理学会誌 2006年8月, Vol.47, No.8
  特集「コンピュータ将棋の新しい動き」

  0．編集にあたって
  久門耕一, 873-874ページ

  1.「全幅探索」と学習による新感覚のコンピュータ将棋の成功とその高速アルゴリズムの及ぼす影響
  瀧澤武信, 875-881ページ

  2．今年の選手権を観戦した女流プロとしての戸惑い
  安食総子, 882-883ページ

  3.コンピュータ将棋における全幅探索と futility pruning の応用
  保木邦仁, 884-889ページ

  4.コンピュータは本当に名人を超えられるか─Bonanzaの活躍
  飯田弘之, 890-892ページ