投入計算量の有限性に基づくUCT探索の枝刈り

投入計算量の有限性に
基づくUCT探索の枝刈り
東京大学大学院
北川竜平栗田哲平近山隆
1
発表の流れ




はじめに
提案手法
実験
まとめ
2
はじめに

時間が限られている状態で最大の成果を得たい時には


現時点で良さそうな考えを重点的に考える
考えても無駄そうなことは早めに打ち切る
 例：数学の問題集




家で解くときは時間がたくさんあるので全ての問題を解いてみる
試験等で時間が限られている時はとりあえず解けそうな問題から解く
考えても解けそうにない問題は解かない
この考え方をUCT探索の枝刈りに利用
3
背景


モンテカルロ探索 [Brugmann. 1996]
UCT探索 [Koscis et al. 2006]
 それぞれの手の評価値としてゲームのシミュレーションの勝率を用いる
 シミュレーションの回数を多くすると評価値の精度は高くなる
 評価関数を用いないので知識表現の難しいゲームや新しいゲームで効果的
30
100
…
60
勝ち数
シミュレーション数 100
…
…
シミュレーション
55
100
4
UCTのシミュレーション


未探索ノードはランダムゲーム
既に探索したことのあるノードはUCB値が一番
高いものを選ぶ
勝率
UCB  X 
log n
c
s
親ノードの
探索回数
そのノードの
探索回数
 勝率の高いノード・探索された回数の少ないノード程
多く探索される
5
UCTの利点

結果的に勝率が高くなりそうなノードが多く探索
される



ゲーム木探索では選ばれそうな手の評価値の精度
が高いことが重要
ダメな手の評価値はデタラメでいい
枝刈りをして勝率が高くなりそうなノードの探索
回数を増やせば評価値の精度は向上する
6
目的

探索効率を上げるためにUCTで枝刈りをする


新しいゲームにも対応できるようにゲームの知識は
用いない
探索結果と探索時間の有限性から枝刈りを行う
7
関連研究

UCB1-TUNED [Gelly et al. 2006]


報酬の分散を考慮することで勝率の低い枝の探索回
数がより少なくなる
Progressive Pruning [Bouzy. 2006]



モンテカルロ探索での枝刈り
区間推定を用いてそれぞれの手の勝率が取りそうな
範囲を予測
選ばれにくそうな手を探索しない
8
UCB1-TUNED
[Gelly et al. 2006]

UCB値を以下のように定める
勝率
UCB  X 
log n
c
s
1
c  min( , V )
4
V  
2
親ノードの
探索回数
そのノードの
探索回数
2 log n
s
報酬の分散

勝率が極端に低い枝の探索回数が減る
9
Progressive Pruning
[Bouzy. 2006]

区間推定より、勝率は[ X L , X R ]となる可能性が高い
勝率
XL  X r
信頼係数
XR  X  r


報酬の標準偏差
s

探索回数
s
手Aの X Rより手Bの X Lの方が大きい時、手Aが選択さ
れる可能性は低い

手Aを枝刈り
手A
手B
XL
X
XR
X
XL
手C
XL
X
XR
XR
10
勝率
PPの問題点

シミュレーション回数が多くならないと枝刈りが発生しな
い


UCT探索では勝率の低い手のシミュレーション回数が
少ない



予測区間が広いため
予測区間が小さくなりにくい
枝刈りの発生が遅い
シミュレーション数が少なくとも予測区間が狭まる手法
が必要
11
提案手法

ゲーム木探索を行うのに使える時間は有限


残りシミュレーション回数から、それぞれの手が
どのような値になりそうかという範囲を予測する
ことができる


今後シミュレーションができる回数も有限
現在非常に勝率の低い枝は、今後のシミュレーショ
ンでたくさん勝ったとしても高い勝率にはならない
その範囲によって選ばれる可能性の低い手を見
つけることができる
12
提案手法概要
残り10シミュレーション
しかできない
絶対に選択されないので
枝刈り
…
…
…
シミュレーション
60
勝ち数
シミュレーション数 90
30
90
55
90
70
勝ち数
シミュレーション数 100
40
100
65
100
結果が最善だった場合
60
勝ち数
シミュレーション数 100
30
100
55
100
結果が最悪だった場合
13
予測到達勝率

残り探索回数からの予測到達勝率

今後のシミュレーションによって勝率は[ PL , PR ] とな
る可能性が高い
現在の勝ち数
今後のシミュレーション
今後のシミュレーション
最終的な勝ち数の予測
による予測勝率
による勝ち数
X  eX L
PL 
se
現在の探索回数
その手の予測残り探索回数
最終的な探索回数の予測
X  eX R
PR 
se
14
今後の勝率

今後のシミュレーションによって得られる報酬を現在の
勝率より高め(低め)に設定

今の勝率よりも低くなるとすると
勝率
信頼係数

X L  max(0, X  r


s
)
今の勝率よりも高くなるとすると
X R  min(1, X  r

報酬の標準偏差

s
探索回数
)
r を非常に大きく取ると、残り探索で全敗(全勝)としたときの勝
率の範囲を予測する
探索回数が十分大きい場合は以上のように近似できる
15
予測残り探索回数

モンテカルロ探索でのある手の残り探索回数は
残り全探索回数
1
ei  N
k

合法手数
UCT探索では勝率が高い手程多く探索されるの
で、現在の勝率によって重みづけ
ei 
全ての手の勝率が等
しければ↑と同じ
その手の勝率
Xi
N
k
X
j 1
j
全ての手の勝率の和
16
枝刈り条件

手Aの PR より手Bの PL の方が大きい時、手Aが
選択される可能性は低い

PRi  max(PL1 , PL 2 ,, PLk ) を満たす手 i は
枝刈りしてもよい
手A
手B
PL
X
PR
X
PL
手C
PL
X
PR
PR
17
勝率
利点

Progressive Pruningよりも多く枝刈りができる



探索した回数が多くなると枝刈りが進む
残り探索回数が少なくなると枝刈りが進む
勝率の低い手の探索回数が少ないUCT探索で
も効果が期待できる
18
実験

提案手法をブロックスデュオのゲームプレイヤに実装




UCB値としてUCB1-TUNEDを使用
探索時間の半分を超えたら枝刈りを開始する


探索回数が十分多くないと勝率予測の近似が不正確なため
ルートノードで枝刈り条件を満たす枝の探索を行わない


二人確定完全情報ゲーム
オセロや囲碁の陣取りゲームに近い
枝刈り条件を満たさない枝の中でUCB値が最大の枝に対して
シミュレーションを行う
実験環境


Opteron 2.1GHz Quad･メモリ 3GB
初期局面に対して200～300シミュレーション/秒
19
枝刈りの進行
探索対象となる合法手の数
250
proposal
PP
200
150
100
50
0
0
2000
4000
6000
8000
10000
12000
14000
シミュレーション回数
初期局面に対して探索時間50秒で実験
20
ランダム局面に対する評価


中盤（8～15手目）の局面をランダムに100個作成
1000秒の従来のUCTによってそれぞれの局面を評価



50秒の提案手法がどれだけ1000秒のUCTの評価に近
づけたかを調べる


それぞれの手が勝率を保持している
これをそれぞれの手の評価値の正解とする
これもそれぞれの手が勝率を保持している
r の値は信頼区間99%･95%･90%のものを使用
21
評価方法
最善手
手番号
評価値
手番号
評価値
1
0.25
1
0.30
2
0.60
2
0.45
3
0.33
3
0.25
4
0.45
4
0.35
5
0.50
5
0.70




n
0.10
n
0.20
UCT1000秒での評価値
最善手
提案手法50秒での評価値
それぞれの最善手がどのような
評価をされているか調べる
22
評価値の誤差
UCT1000秒が最
善とした手の誤差
それぞれの手法が最善
とした手の誤差
UCT50秒
0.057
0.072
UCT100秒
0.056
0.052
提案手法50秒
r 
0.061
0.055
提案手法50秒
r  2.58
0.072
0.051
提案手法50秒
r  1.96
0.072
0.051
提案手法50秒
r  1.64
0.066
0.052
UCT+PP50秒
r  1.96
0.072
0.066
選択された手の評価値の平均二乗誤差の平方根
23
平均評価順位
UCT1000秒が最善それぞれの手法が最
とした手の平均順位善とした手の平均順位
UCT50秒
6.73
6.87
UCT100秒
4.31
2.55
提案手法50秒
r 
11.71
3.23
提案手法50秒
r  2.58
19.20
2.92
提案手法50秒
r  1.96
19.63
2.40
提案手法50秒
r  1.64
25.16
2.99
UCT+PP50秒
r  1.96
16.47
6.42
選択された手の平均評価順位
24
正解率
正解率
UCT50秒
0.41
UCT100秒
0.51
提案手法50秒
r 
0.42
提案手法50秒 r  2.58
0.47
提案手法50秒 r  1.96
0.51
提案手法50秒 r  1.64
0.46
UCT+PP50秒 r  1.96
0.45
UCT1000秒とそれぞれの手法の
最善手が一致した割合
25
UCT vs 提案手法

UCT50秒・UCT100秒と提案手法50秒の対戦


提案手法は r   ・ r  1.96 を使用
先手後手50戦ずつの計100戦を行った
26
対戦結果(1)
先手
後手
提案手法
UCT
引き分け
提案手法50秒
UCT50秒
32
16
2
UCT50秒
提案手法50秒
22
26
2
54
42
4
計
提案手法50秒
UCT100秒
34
16
0
UCT100秒
提案手法50秒
10
38
2
44
54
2
計
UCT vs 提案手法 r   の勝利数
27
対戦結果(2)
先手
後手
提案手法
UCT
引き分け
提案手法50秒
UCT50秒
41
7
2
UCT50秒
提案手法50秒
23
26
1
64
33
3
計
提案手法50秒
UCT100秒
34
14
2
UCT100秒
提案手法50秒
16
33
1
50
47
3
計
UCT vs 提案手法 r  1.96 の勝利数
28
まとめ




提案手法は最善手や最善に近い手を見つける
可能性が上がる
しかし最善手を非常に悪い手と判断する可能性
もある
同じ時間を使ったUCTよりは強い
2倍の時間を使ったUCTと同じくらいの強さにも
なり得る
29
今後の課題

知識を入れたUCTプレイヤと提案手法の共存



知識枝刈り
評価関数による未探索ノードの勝率予測
モンテカルロシミュレーションの結果を用いた学
習への利用

短い時間で高い精度の評価値を出せるので学習効
率の上昇が期待できる
30

Download Report