人工知能2 2005Apr26,May10

人工知能
Lecture 7a
ミニマックス法:αβ枝狩り
田中美栄子
ミニマックス法:アルファ・ベータ枝刈
1
2
自身が選択
ミニマックス法:アルファ・ベータ枝刈
1
2
相手が選択
ミニマックス法:アルファ・ベータ枝刈
1
αβ(3)=(5,5)
7
8
9
3
5
4
2
ミニマックス法:アルファ・ベータ枝刈
αβ(1)=(-∞ ,5)
1
αβ(3)=(5,5)
7
8
9
3
5
4
2
ミニマックス法:アルファ・ベータ枝刈
αβ(1)=(-∞ ,5)
1
2
αβ(3)=(5,5)
7
8
9
3
5
4
10
11
12
4
5
7
ミニマックス法:アルファ・ベータ枝刈
αβ(1)=(-∞ ,5)
1
2
αβ(3)=(5,5)
αβ(4)=(4,∞)
7
8
9
3
5
4
10
11
12
4
5
7
ミニマックス法:アルファ・ベータ枝刈
αβ(1)=(-∞ ,5)
1
2
αβ(3)=(5,5)
7
3
8
5
αβ(4)=(5,∞)
9
4
10
11
12
4
5
7
αβ(4)=(5,∞)となっ
た段階で親ノード1の
範囲
αβ(1)=(-∞ ,5)
と矛盾しない解は
αβ(4)=(5, 5)
αβ(1)=(5 ,5)
となってノード1も
ノード4も値が確定して
しまう。ノード12は調べ
る必要なし。
ノード12を調べる前に
ノード1のβ値より右に
ノード4の範囲が来た
ため、1と4の間の枝が
βカットされた
ミニマックス法:アルファ・ベータ枝刈
αβ(1)=(5,5)
1
2
αβ(3)=(5,5)
αβ(4)=(5,5)
7
8
9
3
5
4
10
4
11
5
12
7
調べなくてもよい
ミニマックス法:アルファ・ベータ枝刈
αβ(1)=(5,∞)
αβ(1)=(5,5)
1
2
αβ(3)=(5,5)
αβ(4)=(5,5)
7
8
9
3
5
4
10
11
12
4
5
7
ノード1の値が
確定したらSの
α値が決まる
ミニマックス法:アルファ・ベータ枝刈
αβ(S)=(5, ∞)
1
αβ(1)=(5,5)
2
ノード1以下の探索が終わって
Sの下限、α(S)=5が確定した。
次はノード2以下のノードを探索
ミニマックス法:アルファ・ベータ枝刈
αβ(S)=(5, ∞)
1
αβ(1)=(5,5)
2
ミニマックス法:アルファ・ベータ枝刈
αβ(S)=(5, ∞)
αβ(1)=(5,5)
1
2
αβ(5)=(4,4)
13
14
15
4
3
2
ミニマックス法:アルファ・ベータ枝刈
αβ(S)=(5,∞)
αβ(S)=(5, ∞)
1
2
αβ(2)=((-∞ ,4)
αβ(5)=(4,4)
13
14
15
4
3
2
αβ(2)=(-∞ ,4)
ノード2の範囲は4以下
であり、Sのαより小さ
いので,これ以上探
索を行わなくてもよ
い.
ノード6以下を探索
する前にノードSと
ノード2をつなぐ枝が
αカットされた