人工知能2 2005Apr26,May10

人工知能 :第7回講義
まとめ:
問題の分解、AND/OR
ゲームの手の決定、ミニマックス枝狩り
αカット、βカット, 枝刈りの利得計算
Problem reduction representation
• 問題を分割し、すぐ解ける副問題の集合に変換
• 許された変換は「オペレータ(作用素)」として定義
• すぐ解ける問題は原始問題primitive problemとよぶ
• 問題分割を用いた問題表現は、
1.開始問題記述
2,問題を副問題群に変換する作用素
3.原始問題記述の集合
問題分割表現の例:ハノイの塔
• 大きさが順に大きくなる3つの円盤、A,B,Cと3つの
柱1,2,3. 最初円盤は全て柱1の上に、一番小さい
Aを一番上に、Cを一番下にして積み重ねられてい
る。これを柱3にAが一番上になるように移す、但し
一度に1個だけ円盤を動かせる、どの円盤もそれよ
り小さい円盤の上に置けない
• 最初に出来るのはAを柱2か柱3に移すことだが、そ
のあとAの上にはBもCも置けないので、つまりはA
を移さなかった柱にBを移して置いて、その上にAを
移し、空いた柱3にCを移すことができれば成功であ
る.次にそのCの上にBを載せ、その上にAを載せる
8段階を右の3段階と見る
1.ABC
1. BC
1.
C
1. C
2. _
2. _
2. B
2. AB
3._
3. A
3. A
3.__
高さ2の山を1.
から2. へ移す
高さ1を1.から3.へ
1.__
1. A
1. A
1.__
2. AB
2. B
2. _
2.__
3. C
3. C
3. BC
3. ABC
高さ2の山を2.
から3. へ移す
円盤をN個に増やしても右の3段階
1.AB..C
1. C
2. _
3._
高さN-1の山
を1.から2. へ
2. AB.. 3.__
高さ1を1.から3.へ
1.__ 2. AB..
3. C
高さN-1の山
を2.から3. へ
1.__ 2.__ 3. ABC
目標:高さ3の山を柱1から柱3へ移す
小目標:高さ2の
山を柱1から柱2
へ避難させる
原始問題:高さ
1の山を柱1か
ら柱3へ移動
高さ1の
高さ1の 山を柱3
高さ1 山を柱1 から柱2
の山を から柱2 へ移動
柱1か へ移動
ら柱3
へ移動
小目標:高さ2の
山を柱2から柱3
へ移す
高さ1の山を
高さ1の山 柱2から柱3
を柱2から へ移動
柱1へ移動
高さ1の
山を柱1
から柱3
へ移動
Nilsson(1971)によるAND/ORグラフ
1)各節点は単一問題か一連の問題であり、グラフは
開始節点(元問題)を含む.
2)終端節点(原始問題)=葉
3)問題Pに対しこれを一組の副問題に変える作用素
があり、これを適用した結果生じる副問題に対応す
る節点へ向かって有向枝がある.このいずれかの
子節点が解かれたときPが解けるのなら、OR節点
(OR-node) 、全ての子節点が解かれたときPが解
けるのならAND節点(AND-node)とよぶ.AND節点
には枝を水平線で結ぶ
開始問題が解けるかどうかを示すグ
ラフ(or,木)を解グラフ(解木)という
• 解ける節点の条件として、
1)それが終端節点(原始問題)である
2)子節点が全て解けるAND節点であるような
非終端節点であるか、または
3)子節点がOR節点でそのうち少なくとも一つ
が解ける
• 解けない節点の条件
1)子節点のない非終端節点(どの作用素も適
用できないような非原始問題)
2)その子節点がAND節点で、そのうち少なくと
も一つが解けないような非終端節点
3)その子節点がOR節点で、その全てが解け
ないような非終端節点
問題の分解:ゲームの手の決定
• ゲームの木:チェスや碁等の特徴:交互にプレイす
る二人のプレーヤが参加し、最良の手を打つ、とい
うゲームに対してその全ての可能な手が表現されて
いる.
• 状態空間木との違いは、プレーヤが交互に選択す
ること:rootは初期状態で第1のプレーヤの手番、次
の子節点は第1のプレーヤが一手で到達できる状
態、その次の子節点は第2のプレーヤの応手で作ら
れる状態。終端節点は、勝、負、引分けのいずれか
• AND/OR木で表現できる(Aの立場からは自分の手
番はORで選べるが相手の手番はANDに対応)
• ゲームの手の決定
ミニマックス定理
MAX node:自分の
利益を最大にする
手を選ぶ
min node: 相手の
利益を最小にする
手を選ぶ
f(S)
f(1)
1
2
f(2)
1
f(3)
f(1)
f(4)
f(S) = Max {f(1), f(2) }
f(1) = min {f(3), f(4) }
F(s) = MAX { F(1), F(2) }
1
7
8
9
F(7)
F(8)
F(9)
2
F(1) = min { F(3), F(32) }
F(3) = MAX { F(7), F(8), F(9) }
ミニマックス定理
• 自分と相手が交互にminとMAXを取り合う
F(s) = MAX { F(1), F(2) }
F(1) = min{ F(3), F(4) }
F(3) = MAX { F(7), F(8),F(9) }
• よって
f (S)  MAX{f ( n )}
n
 MAX min{f ( n i )}
n
i
 MAX min MAX{f ( n ij )}
n
i
j
 MAX min MAX min   {f ( n ijk )}
n
i
j
k
アルファベータ(αβ)
枝刈り法
openList
アルファ・ベータ法
変更のあった
αβ(n)区間
S
1,2
1
2
自身が選択
openList
アルファ・ベータ法
S
1,2
3,4,2
1
2
相手が選択
変更のあった
αβ(n)区間
アルファ・ベータ法
openList
変更のあっ
たαβ(n)区
間
7,8,9,4,2 αβ(3)=(3,∞)
1
8,9,4,2
αβ(3)=(5,∞)
9,4,2
αβ(3)=(5,5)
2
αβ(1)=(-∞,5)
4,2
7
8
9
3
5
4
アルファ・ベータ法
openList
変更のあった
αβ(n)区間
S
1,2
αβ(1)=(-∞,5)
1
αβ(3)=(5,5)
2
3,4,2
7,8,9,4,2 αβ(3)=(3,∞)
7
8
9
3
5
4
8,9,4,2
αβ(3)=(5,∞)
9,4,2
αβ(3)=(5,5)
αβ(1)=(-∞,5)
4,2
アルファ・ベータ法
αβ(1)=(-∞,5)
2
1
αβ(3)=(5,5)
αβ(4)=(4,5)
7
8
9
3
5
4
10
11
12
4
5
7
openList
変更のあった
αβ(n)区間
10,11,12,2
αβ(4)=(4,∞)
αβ (1)=(-∞,5)
と照合して
αβ(4)=(4,5)
アルファ・ベータ法
αβ(1)=(5,5)
2
1
αβ(3)=(5,5)
αβ(4)=(5,5)
7
8
9
3
5
4
10
11
12
4
5
7
openList
変更のあった
αβ(n)区間
11,12,2
αβ(4)=(5,5)
αβ (1)=(5,5)
2
枝狩り:βカットの場合
節1のβ以
上の範囲に
αβ (1)=(-∞,5)
1
αβ(4)=(5,5)
X
節4の範囲
が来ると
12
その子節は
もう調べる
必要なしと
して カット
アルファ・ベータ法
αβ(S)=(5,∞)
1
(5,5)
openList
変更のあった
αβ(n)区間
11,12,2
αβ(4)=(5,5)
αβ (1)=(5,5)
αβ (S)=(5,∞)
2
2
アルファ・ベータ法
openList
(5,∞)
2
1
(5,5)
2
5,6
変更のあった
αβ(n)区間
アルファ・ベータ法
openList
変更のあった
αβ(n)区間
2
αβ(S)=(5,∞)
5,6
1
2
(5,5)
αβ(5)=(4,4)
13,14,15.6
14,15,6
15,6
13
14
15
4
3
2
αβ(5)=(4,∞)
αβ(5)=(4,4)
αβ(2)=(-∞,4)
αβ (S)=(5,∞)
と照合して
αβ (S)=(5,5)
アルファ・ベータ法
Sのαより小さいので,
これ以上探索を行わ
なくてもよい
αβ(S)=(5,∞)
X
1
2
αβ(5)=(4,4)
13
14
15
4
3
2
αβ(2)=(-∞,4)
枝狩り:αカットの場合
(5, ∞)
αβ(2)=(-∞ ,4)
X
2
節1のα以
下の範囲に
節2の範囲
が来ると
その子節は
もう調べる
必要なしと
して カット
枝刈でどこまで節約できるのか?
•
•
•
•
親節がゴールでなければ子節を展開するが、
最初の子節は必ず調べなければならない
2番目以降は刈れる可能性がある
子節nが刈れるのはその親,及び親の親がい
ずれも1番目に探索される子節でない場合
• 始節Sからnに至る節の列が2点続いて1番目
なら刈れる可能性はない(必ず調べる必要)
• 系列を探索される番号で表す:(1,2,3)なら,1番
目の節の次に2番目の節,3番目の節,となる
刈れない節の数
• 系列の奇数段目の節が全て1なら刈れる可
能性ゼロ,偶数番目の節が全て1でも同じ
• 系列長をkとして,m分木の場合、
• ほぼmのk/2乗の2倍→半分の深さの木を探
索するのと同じ手間
• まったく刈れない場合もあるので
• 結局、mのk/2乗以上でmのk乗以下、という
程度