人工知能2 2005Apr26,May10

人工知能：第7回講義
まとめ：
問題の分解、AND/OR
ゲームの手の決定、ミニマックス枝狩り
αカット、βカット, 枝刈りの利得計算
Problem reduction representation
• 問題を分割し、すぐ解ける副問題の集合に変換
• 許された変換は「オペレータ（作用素）」として定義
• すぐ解ける問題は原始問題primitive problemとよぶ
• 問題分割を用いた問題表現は、
１．開始問題記述
２，問題を副問題群に変換する作用素
３．原始問題記述の集合
問題分割表現の例：ハノイの塔
• 大きさが順に大きくなる３つの円盤、A,B,Cと３つの
柱1,2,3. 最初円盤は全て柱１の上に、一番小さい
Aを一番上に、Cを一番下にして積み重ねられてい
る。これを柱３にAが一番上になるように移す、但し
一度に１個だけ円盤を動かせる、どの円盤もそれよ
り小さい円盤の上に置けない
• 最初に出来るのはAを柱2か柱3に移すことだが、そ
のあとAの上にはBもCも置けないので、つまりはA
を移さなかった柱にBを移して置いて、その上にAを
移し、空いた柱3にCを移すことができれば成功であ
る．次にそのCの上にBを載せ、その上にAを載せる
８段階を右の３段階と見る
１.ABC
１. BC
１.
C
１. C
2. ＿
2. ＿
2. B
2. AB
3.＿
3. A
3. A
3.＿＿
高さ２の山を1.
から2. へ移す
高さ１を1.から3.へ
１.＿＿
１. A
１. A
１.＿＿
2. AB
2. B
2. ＿
2.＿＿
3. C
3. C
3. BC
3. ABC
高さ２の山を2.
から3. へ移す
円盤をN個に増やしても右の３段階
１.AB..C
１. C
2. ＿
3.＿
高さN-1の山
を1.から2. へ
2. AB.. 3.＿＿
高さ１を1.から3.へ
１.＿＿ 2. AB..
3. C
高さN-1の山
を2.から3. へ
１.＿＿ 2.＿＿ 3. ABC
目標：高さ３の山を柱１から柱３へ移す
小目標：高さ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グラフ
１）各節点は単一問題か一連の問題であり、グラフは
開始節点（元問題）を含む．
２）終端節点（原始問題）＝葉
３）問題Pに対しこれを一組の副問題に変える作用素
があり、これを適用した結果生じる副問題に対応す
る節点へ向かって有向枝がある．このいずれかの
子節点が解かれたときＰが解けるのなら、OR節点
（OR-node）、全ての子節点が解かれたときPが解
けるのならAND節点（AND-node）とよぶ.AND節点
には枝を水平線で結ぶ
開始問題が解けるかどうかを示すグ
ラフ（or,木）を解グラフ（解木）という
• 解ける節点の条件として、
１）それが終端節点（原始問題）である
2)子節点が全て解けるAND節点であるような
非終端節点であるか、または
３）子節点がOR節点でそのうち少なくとも一つ
が解ける
• 解けない節点の条件
1)子節点のない非終端節点（どの作用素も適
用できないような非原始問題）
2)その子節点がAND節点で、そのうち少なくと
も一つが解けないような非終端節点
３）その子節点がOR節点で、その全てが解け
ないような非終端節点
問題の分解：ゲームの手の決定
• ゲームの木：チェスや碁等の特徴：交互にプレイす
る二人のプレーヤが参加し、最良の手を打つ、とい
うゲームに対してその全ての可能な手が表現されて
いる．
• 状態空間木との違いは、プレーヤが交互に選択す
ること：rootは初期状態で第１のプレーヤの手番、次
の子節点は第1のプレーヤが一手で到達できる状
態、その次の子節点は第２のプレーヤの応手で作ら
れる状態。終端節点は、勝、負、引分けのいずれか
• AND/OR木で表現できる（Aの立場からは自分の手
番はORで選べるが相手の手番はANDに対応）
• ゲームの手の決定
ミニマックス定理
MAX node：自分の
利益を最大にする
手を選ぶ
min node：相手の
利益を最小にする
手を選ぶ
f(S)
f(1)
１
２
f(2)
１
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) }
１
７
８
９
F(7)
F(8)
F(9)
２
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(１) = 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
アルファベータ（αβ）
枝刈り法
アルファ・ベータ法
１
２
自身が選択
アルファ・ベータ法
１
２
相手が選択
アルファ・ベータ法
１
αβ（3）＝(5，5)
７
８
９
３
５
４
２
アルファ・ベータ法
open
n αβ（n)
区間
S
1,2
αβ（1）＝(-∞，5)
１
αβ（3）＝(5,5)
２
3,4,2
7,8,9,4,2 3 (3,∞）
７
３
８
５
8,9,4,2
3
(5,∞）
9,4,2
3
(5,5）
4,2
1
(-∞,5）
９
４
アルファ・ベータ法
Open List n αβ区
間
αβ（1）＝(-∞，5)
10,11,12,2 4 (4,5）
２
１
αβ（3）＝(5,5)
αβ（４）＝(4,5)
７
８
９
３
５
４
１０
１１
１２
４
５
７
アルファ・ベータ法
Open List n αβ区
間
αβ（1）＝(-∞，5)
10,11,12,2 4 (4,5）
２
１
αβ（3）＝(5,5)
αβ（４）＝(4,5)
７
８
９
３
５
４
１０
１１
１２
４
５
７
11,12,2
4 (5,5）
アルファ・ベータ法
Open List n αβ区
間
αβ（1）＝(-∞，5)
10,11,12,2 4 (4,5）
２
１
αβ（3）＝(5,5)
αβ（４）＝(4,5)
７
８
９
３
５
４
１０
１１
１２
４
５
７
11,12,2
4 (5,5）
12,2
1 (5,5）
アルファ・ベータ法
Open List n αβ区
間
(5,∞）
(5,5)
２
１
12,2
4 (5,5）
2
1 (5,5）
S (5,∞）
(5,5)
(5,5)
７
８
９
３
５
４
１０
１１
１２
４
５
７
節12はカットされる(βcut)
枝狩り：βカットの場合
節１のβ以
上の範囲に
(-∞，5)
１
αβ（４）＝(-∞ ，5)
X
節４の範囲
が来ると
１2
その子節は
もう調べる
必要なしと
してカット
アルファ・ベータ法
αβ(S)＝(5，∞)
Open List n αβ区
間
１
(5,5)
２
2
1 (5,5）
S (5,∞）
アルファ・ベータ法
Open List n αβ区
(5，∞)
間
2
１
(5,5)
２
1 (5,5）
S (5,∞）
5,6
アルファ・ベータ法
Open List n αβ区
間
αβ(S)＝(5，∞)
5,6
S (5,∞）
13,14,15,6 5 (4,∞）
１
２
(5,5)
αβ（５）＝(４，４)
１３
１４
１５
４
３
２
アルファ・ベータ法
Open List n αβ区
間
αβ(S)＝(5，∞)
5,6
S (5,∞）
13,14,15,6 5 (4,∞）
１
２
(5,5)
14, 15,6
αβ（５）＝(４，４)
１３
１４
１５
４
３
２
5 (4,∞）
アルファ・ベータ法
Open List n αβ区
間
αβ(S)＝(5，∞)
5,6
S (5,∞）
13,14,15,6 5 (4,∞）
１
２
(5,5)
(４，４)
１３
１４
１５
４
３
２
(-∞,4）
14, 15,6
5 (4,∞）
15,6
5 (4,4）
6
2 (-∞,4）
アルファ・ベータ法
Sのαより小さいので，
これ以上探索を行わ
なくてもよい
αβ(S)＝(5，∞)
X
１
２
αβ（5）＝(4,4)
１３
１４
１５
４
３
２
αβ（2）＝(-∞，4)
枝狩り：αカットの場合
(5, ∞)
αβ（2）＝(-∞ ，5)
X
2
節１のα以
下の範囲に
節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乗以下、という
程度

Download Report