モンテカルロ木探索　設計仕様書

アルファ碁解体新書より

コメント

Wは勝ち数
Nはこの枝の総プレイアウト数
兄弟ノードや横
親ノードは上
子ノードは下

メモ

ゲーム木はどこか比較的にグローバルでアクセスできる、とりあえずインスタンス変数にしておく
せっかく探索したゲーム木は勝率情報の10分の１ぐらい次に使いまわせそうだから出来たらやりたいが、本質的には10分の１なので効かなさそう。

U C B 1 = (w / n) + (2 (\log t) / n)^{1 / 2}

n: 総プレイアウト
w: 勝ち数
t: 兄弟ノード全体のプレイアウト回数

フローチャート

各処理について

分かりやすさのために、この単位で関数化する。

選択
　勝率＋バイアス(UCB1)が一番大きい手を選択。
　これは、リーフノードまで繰り返せばよし、ナイーブにやるとO(N)、PQを使用するとO(NlogN)。丸ごと関数化して、リーフノードのポインタ（位置情報でよし実際にポインタである必要はなし）を返す。
相手の手の場合は相手基準のUCB1を返すようにする。
展開
　Nthr以上に読み込まれたら展開する。展開時は勝率情報などは全て0にする。ＵＣＢ１の式の計算時に工夫をして無限でエラーを吐かないようにするかつ、最優先でキューが割り当てられるようにする。（選択）
評価
　なるべく早くプレイアウトを終わらせる工夫が必要。とりあえずは既存手法を用いてよい。
更新
　きちんと子ノードから親ノードを更新させるのを忘れないようにする。
終了
　最終的にUCB1が最も高い値を手として打つ。

実際の設計

クラスについて
MonteCarloPlayerを大本のクラスとする。
ゲーム木の情報を保存するものとしてMonteCarloTreeを使用する。
ノードは、MonteCarloNode
エッジは、特に情報を持たせるつもりも現状ないため、ノードからノードの配列番号参照による。
インスタンス変数　MonteCarloNode

TurnPlayer: 相手自分情報、先攻後攻
parent: 親ノードの番号
children: 子ノードの番号
プレイアウト数
勝ち数（引き分けは負け）

インスタンスメソッドとして以下の機能を実装。　MonteCarloNode

init: 開始時に相手の駒を近い順から青に決め打つ。相互に駒の種類は見えないようにする。
search: 大本。
select: 展開されているノードをUCB1でたどっていって、、、
expand: Nthrは随時いい感じにする。デバッグのため結果のグラフを表示する機能が欲しい。
evaluate: 既存手法の移植
update: 子ノードの数、親ノードの数はN＋１、W＋１で何とかなるが。兄弟ノードのプレイアウト数という情報が必要のため、既に通ってきた子ノード以外のノードに加算する。

とりあえずはこれで実装。

選択
展開
評価
　この本では、値域が[0, 1]だが、引き分けが発生するガイスターでは、値域が[1,-1]となるため、UCB1の更新式が異なる。
　間違えやすいので注意

U C B 1 = (w / 2 n) + 0.5 + (2 (\log t) / n)^{1 / 2}

更新

知見

なるべく早くプレイアウトを迎えた方が良い。
無限ループするこのゲームでは、早く終局を迎えるために何らかの工夫をしなければならない。
200ターンで引き分け終了はありがたい。＝＞引き分けは0で処理。
よって悲観的な戦略はあまり適さない＝＞取るときは赤、ゴールは青など
ランダムプレイアウトの際に前に進む確率を上げてみた＝＞目に見えた変化はないが上下運動のループは減った。
紫駒戦略は悲観的になりすぎる。＝＞どっちにしろ負けるからゴール前の青ゴマを取らなくなる。＝＞とればワンチャンあってもなくなる。
紫駒戦略と猪突AIは相性が悪い。
かといってゴールに近い駒を青駒と決め打ちすると原始モンテカルロ（赤駒を取らせる戦略を好む）に勝てなくなる。
よって駒色の予測が非常に重要。

便利情報

重み付きグラフの表示ができるツールがあると非常にデバッグ時に便利。