モンテカルロ探索の小ねた

しばらくいじらないと誓ったモンテカルロ探索ですが、
テスト対戦を繰り返していると、ここで致命的なミスが出て負けることが結構多いのに気づきました。
で、そのたびに手直し。

最近入れた修正はこんな感じです。

「確定勝利優先アルゴリズム」の実装

GPWで発表があったもので、playout中に詰みを見つけたら、その情報を親ノードに伝播していき、詰みが分かっている手は二度と指さないようにするやり方。
と書くと分かりづらいんですが、以前小宮日記さんでも取り上げられていた内容です。

親ノードへ伝播させるところの実装が大変そうだったので二の足を踏んでたんですが、詰みを見つけた直後にリアルタイムに伝播させなくてもいいことに気が付いて、半日くらいで実装できました。
とりあえず詰みを見つけたすぐ親のノード(A)に勝ちフラグを立てておく。
で、その後のplayoutで、Aの親ノード(B)を訪れたとき、Bの全子ノードを調べ（その中にはAも含まれる）、全部が勝ちになっていたら、Bに負けフラグを立てる。
全部の子ノードを調べるのは、どうせUCBを調べるのでやってるから、そのついでにフラグを調べればよく、コストはほとんどかからない。

3手詰めを見つけてくれるのは感動ですが、さすがに5手詰め以上は無理そうです。
なので、今までやっていたやり方（通常探索のハッシュを参照）も併用しています。
55将棋だと合法手が少ないので、5手詰めでもさくっと見つけられるのでしょうね。

最善手を選ぶとき、勝率最大の手ではなく、選択回数が最大の手を選ぶように

勝率が最大でも、十分なplayoutが行われていないケースがあって、解決策に悩んでいたので、それへの対応。
たしかgg加藤さんの自戦記で、そんな内容の記述があったので。
さらっと書かれてますが、自分には思いつきませんでした。
（ym将棋では、ルートでの指し手選択は、基本的にはUCB-TUNEDなのですが、一度も選択されていない手は、UCB値を一律にせず、静止探索の結果によって若干差をつけています。
すると、数千playoutを超えてから初めて選ばれる手とかあったりするんですが、そういう手が初期に高い勝率をあげて、たまたまそこで制限時間が来たりすると、十分playoutが行われていないのにその手を選んでしまうことがありました。）

Progressive Wideningで、選択可能な手の数を増やす条件を変えた

GPWで「棋理」の佐藤さんが発表されていたのを参考に。
今まで、囲碁のやりかたそのままに、ノード訪問回数（だけ）をキーにして「上
位何手まで選択可能か」を決めていました。
このやり方だと、上位の手がどれもダメで、下位の手を試さないといけない場合でも、硬直的に上位の手だけを選んでしまうので、条件を指定して、選択できる手の数を臨時に増やすとかしていました。
うまい解決法がないか悩んでいたのですが…
改めて論文を見直すと、UCB値の算出に指し手の評価を利用することで、Progressive Wideningを実現していました。
このやり方なら指し手の数を固定しないので、ノード毎の状況に応じて（しかも余計なコストをかけずに）対応できますね。

実装した後まだ対局させていないので、これから練習対戦させてみます。