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

アルファ碁解体新書より
## コメント
- Wは勝ち数
- Nはこの枝の総プレイアウト数
- 兄弟ノードや横
- 親ノードは上
- 子ノードは下

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

$$
UCB1 = (w/n) + (2 (\log t)/n)^{1/2}
$$

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

## フローチャート

st=>start: root node
e=>end: simulation end

ifleaf=>condition: sはリーフノードであるか？
select=>subroutine: 選択：勝率＋バイアス(UCB1)が一番大きい手を選択
next_move=>operation: s<=move(s,a)
ifnthr=>condition: 試行回数>=Nthr
expand=>subroutine: 展開：子ノードを追加してノード情報を初期化
evaluate=>subroutine: 評価：プレイアウトを実行し、勝敗をzに格納(勝ち1,負け0)
ifroot=>condition: sがルートノードか？
update=>subroutine: 更新：N<=N+1,W<=W+z
back_move=>operation: s<=unmove(s,a)

st->ifleaf
select->next_move->ifleaf
evaluate->ifroot
update->back_move->ifroot
expand->ifleaf

ifleaf(yes)->ifnthr
ifleaf(no)->select
ifnthr(yes)->expand
ifnthr(no)->evaluate
ifroot(yes)->e
ifroot(no)->update

## 各処理について

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

1. 選択
　勝率＋バイアス(UCB1)が一番大きい手を選択。
　これは、リーフノードまで繰り返せばよし、ナイーブにやるとO(N)、PQを使用するとO(NlogN)。丸ごと関数化して、リーフノードのポインタ（位置情報でよし実際にポインタである必要はなし）を返す。
相手の手の場合は相手基準のUCB1を返すようにする。

2. 展開
　Nthr以上に読み込まれたら展開する。展開時は勝率情報などは全て0にする。ＵＣＢ１の式の計算時に工夫をして無限でエラーを吐かないようにするかつ、最優先でキューが割り当てられるようにする。（選択）

3. 評価
　なるべく早くプレイアウトを終わらせる工夫が必要。とりあえずは既存手法を用いてよい。

4. 更新
　きちんと子ノードから親ノードを更新させるのを忘れないようにする。

5. 終了
　最終的にUCB1が最も高い値を手として打つ。

## 実際の設計

0. クラスについて
MonteCarloPlayerを大本のクラスとする。
ゲーム木の情報を保存するものとしてMonteCarloTreeを使用する。
ノードは、MonteCarloNode
エッジは、特に情報を持たせるつもりも現状ないため、ノードからノードの配列番号参照による。
インスタンス変数　MonteCarloNode
- TurnPlayer: 相手自分情報、先攻後攻
- parent: 親ノードの番号
- children: 子ノードの番号
- プレイアウト数
- 勝ち数（引き分けは負け）
-
インスタンスメソッドとして以下の機能を実装。　MonteCarloNode
- init: 開始時に相手の駒を近い順から青に決め打つ。相互に駒の種類は見えないようにする。
- search: 大本。
- select: 展開されているノードをUCB1でたどっていって、、、
- expand: Nthrは随時いい感じにする。デバッグのため結果のグラフを表示する機能が欲しい。
- evaluate: 既存手法の移植
- update: 子ノードの数、親ノードの数はN＋１、W＋１で何とかなるが。兄弟ノードのプレイアウト数という情報が必要のため、既に通ってきた子ノード以外のノードに加算する。

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

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

$$
UCB1 = (w/2n) + 0.5 + (2 (\log t)/n)^{1/2}
$$

5. 更新

## 知見

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

## 便利情報

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