UCT勉強中

下準備が出来てきたので、MC(モンテカルロ)法による木探索を実装していくために勉強中。

棋譜データにおける勝率を利用したモンテカルロ木探索の性能評価手法
http://www.graco.c.u-tokyo.ac.jp/~takeuchi/pdf/gpw08.pdf

要点をメモ

モンテカルロ木探索の基本的なモデルでは，深さ 1
の探索を行い，各ノードのスコアの期待値を計算し，
値が最大の手を選ぶ．局面のスコアの期待値は，その
局面から始めた全ランダムゲームの終局局面における
スコアの平均値によって定義される．以下，これらの
ランダムゲームのそれぞれをプレイアウト と呼ぶ．
(中略)
終局時のスコアとして目差を利用するよりも勝敗を利用し
た方が適切であることが多くのプログラムで確認されている．
最も大きな改良は，それまでの 1 手探索モデルを，
再帰的にノードを展開し，効果的な手に多くのプレイアウ
を割り振る手法へと改良したことである

このあとUCTの説明が来ます。

UCTを簡単に説明すると、スロットマシーンが複数あるとき、そのなかで一番当たりそうなスロットマシーンをどうやって選ぶかという話です。

その方法は、少しずついろんなスロットマシーンをやってみて、ある程度リターン率が高かったマシーンにさらにお金をつぎ込みましょうと。

モンテカルロ将棋の場合、
1) 探索開始局面で1手深さですべてのノードを展開する。
2) いま展開されているノードすべてに対して、均等に3)の作業をする。
3) 開始ノードから乱数で指し手を選び、プレイアウトまでシミュレーションをする。
4) 勝率の高いノードがあればそのノードを1手深さでさらに展開する。
5) 2)へ。
というアルゴリズムになります。4)の選び方に「多腕バンディット問題の理論」が使えます。

4)は、最も有効なノードを最良優先で展開していくので、最良優先探索に似ています。

4)の「勝率の高いノード」の選び方としてUCB1と、その改良版であるUCB1-Tunedがあります。

UCB1は、次の式を最大化するノードを選びます。
Pi + sqrt( (2 log N) / Si )

N : そのノードでのplayoutの回数
Pi : ノードのなかのi番目の指し手のプレイアウト時の勝率
Si : ノードのなかのi番目の指し手のプレイアウトの回数

「Piの手を指したあと局面(ノード)を選ぶ」という話ではなく、このようなPiの手を持つノードを選ぶという話のようです。

この式をどうやって導いたのかはこの論文には書かれていないので、あとで詳しく調べます。

UCB1-Tunedは次の式のようです。
Pi + sqrt( log N / Si min ( 1/4 , Pi - Pi**2 + sqrt( (2logN)/Si) )

この式を計算すること自体はすこぶる簡単なので、この式通りに実装するのは難しいことではありません。
(その他の部分が出来ているなら、ですが…。)

さらに，最先端のプログラムでは，より信頼でき
る結果を得るためにパターンや Progressive Widening,
RAVE など多くのヒューリスティックを利用している

自分向けメモ : あとで調べる
・Progressive Widening
・RAVE