東京大学三木理斗三輪誠田浦健次朗近山隆  新興のゲームや研究の浅いゲームの機械学習 ◦ 棋譜や対戦サーバがない  自己対戦による強化学習を利用 ◦ TD(λ)学習など ◦ 局所解から抜け出しにくい  どのようにして学習局面の多様化を図るか ◦ 従来手法：ε-greedy法  TD(λ)学習における新しい局面多様化手法を提案 ◦ 題材としてブロックスデュオを使用  序盤の手をUCTによって決定 ◦ 勝率に基づいた着手 ◦ 完全ランダムよりも、明らかな悪手を選びにくい ◦ TD(λ)学習のバックアップが途切れにくい  他の手法と比較して評価  ゲームプレイヤの強化学習 ◦ TD(λ)学習 ◦ ε-greedy法  UCT  新しいゲームでも適用可能なぜ？  棋譜（教師信号）が不要なぜ？    報酬をもとに評価関数を調整ゲームでの報酬＝勝敗結果つまり評価関数は勝敗を推定する修正修正報酬ｒ評価値局面 s1 s2 s3 s4 s5（終局）いっきに修正報酬ｒ評価値局面 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   １４×１４マスの正方形の盤面に２１種類のピースを置いていく。自分のピースと角同士が接し、辺同士が接しない位置にしか置けない。 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の妥当性の検討 ◦ 統計的信頼性と時間のバランス  まだ人手による調整には敵わない(強化学習の課題) ◦ 特徴要素の検討 ◦ 学習法の検討