UCTを用いた訓練初期局面の 多様化によるTD学習 法

東京大学
三木 理斗 三輪 誠 田浦 健次朗 近山 隆

新興のゲームや研究の浅いゲームの機械学習
◦ 棋譜や対戦サーバがない

自己対戦による強化学習を利用
◦ TD(λ)学習など
◦ 局所解から抜け出しにくい

どのようにして学習局面の多様化を図るか
◦ 従来手法:ε-greedy法

TD(λ)学習における新しい局面多様化手法を提案
◦ 題材としてブロックスデュオを使用

序盤の手をUCTによって決定
◦ 勝率に基づいた着手
◦ 完全ランダムよりも、明らかな悪手を選びにくい
◦ TD(λ)学習のバックアップが途切れにくい

他の手法と比較して評価

ゲームプレイヤの強化学習
◦ TD(λ)学習
◦ ε-greedy法

UCT

新しいゲームでも適用可能
なぜ?

棋譜(教師信号)が不要
なぜ?



報酬をもとに評価関数を調整
ゲームでの報酬=勝敗結果
つまり評価関数は勝敗を推定する
修正
修正
報酬r
評価値
局面
s1
s2
s3
s4
s5(終局)
いっきに修正
報酬r
評価値
局面
s1
s2
s3
s4
s5(終局)

学習局面を多様化する手法の一つ

通常は最も評価値の高い手を打つ
◦ これだけだと確定ゲームの場合、ゲームが固定化しやすい

小さい確率εでランダムな手を打つ

バックアップが細切れになる
評価値
修正ここまで
ランダムな手
ここから別のゲーム
UCB1[Auerら, 2000]を木探索に応用したもの
勝率の高い手を優先的に展開する(頻度重み付き)
末端ではランダムシミュレーションを行う



0
0.3
0.6
0
0.8
0.9
Random
Simulation
1
0.6
0.7
0.8
1
0
1
0
1
1
0
1
0
0
1
0
0
0
1
0
0
モンテカルロ法
0
1
1
0
1
1
0
UCT


序盤の数手をUCTで決定する
以降は最も評価値の高い手を選択する

利点1:序盤のみ手を変化させるので、バックアップが
細切れにならず、学習がより早く進む

利点2:完全にランダムな手を打つよりも、良い手を打
ちやすい(悪手によるノイズを減らす)

問題点:UCTシミュレーションに時間がかかりすぎる

事前にUCTによる序盤のツリーを作成
◦ 多数のマシンで並列に行うことが可能

学習時はこれを用い、ツリーの手の出現確率に基づ
いてランダムに手を選択する
◦ 学習時間は他のランダム手法とほぼ同じ

事前シミュレーションを増やすと、精度と時間はリアル
タイムUCTに近づく

800000試合の自己対戦を行い、ブロックスデュオの
評価関数の重み付けを学習

多様化手法は3通り

序盤UCTは100000シミュレーションを行った4手目
までの序盤ツリーを880試合分作成し、それによる
疑似UCTを行った
◦ ε-greedy法・・・ε=0.03
◦ 序盤ランダム・・・4手目までランダム
◦ 序盤UCT(提案手法)・・・4手目まで疑似UCT


14×14マスの正方形の盤面に21種類のピースを
置いていく。
自分のピースと角同士が接し、辺同士が接しない位
置にしか置けない。
OK
置くピース
角が接して
いればOK
NG
辺が接している
角が接していない
置いたピースの合計面積が大きい方の勝ち。

盤面上のピース面積の差のみを評価値とする単純な
コンピュータプレイヤと対戦させ、学習試合数に対す
る勝率の変化を見る

評価対戦は先手後手それぞれ500回の計1000回

序盤の4手までは両者とも完全ランダムに打つ
1
0.9
0.8
0.7
勝率
0.6
0.5
ε-greedy
0.4
序盤ランダム
0.3
序盤UCT
0.2
0.1
0
0
200000
400000
600000
学習試合数
800000 1000000

序盤に多様化を行うと、早くからよりよい結果に
◦ バックアップが途切れないので学習が早い(傾きが大きい)
◦ 序盤以外での変化は実際には大した多様化にならないの
で、ε-greedyは局所解から抜け出すのが遅い

はじめは、UCTはランダムより学習が早い
◦ ランダムは悪手のノイズの影響が比較的大きい

ある程度学習が進むと、ランダムの方が安定する
◦ 疑似UCTのサンプルの少なさ
◦ ランダムの多様化の広さが悪手ノイズの影響を上回る

序盤UCTによって他の多様化手法よりも良い学習を
行うことができた

疑似UCTの妥当性の検討
◦ 統計的信頼性と時間のバランス

まだ人手による調整には敵わない(強化学習の課題)
◦ 特徴要素の検討
◦ 学習法の検討