■

モンテカルロ将棋（３）

とりあえず最終的な結果です。カッコ内の数値は詰将棋を除いた問題の正答数。モンテカルロ法の方は、平均して上位何割に正解手を挙げたかも示しています。

将棋タウン棋力判定問題集コンピュータ将棋の進歩２
遠見（ＭＣ）30（27） / 0.11016（15） / 0.136
遠見（選手権ver）38（31）22（17）
モンテカルロ法のシミュレーション回数は100,000回。実行時間は選手権版が最大40秒なのに対して、モンテカルロ法の方は60〜150秒程かかっているので全然違います。まぁ今回は速度の話はなしということで。加えた改良は、

    • レーティングによる指し手の選択
    • 途中から終局しやすいシミュレーションに切り替え
    • UCTのノードの選択にレーティングによる指し手の強さを考慮に入れる

といったあたりです。将棋の場合は、囲碁やオセロと比べ終局条件（詰）を満たすことが難しく、ランダムだとシミュレーションに長手数かかってしまうので、とりあえずは多少いい加減でもシミュレーションの終局性を上げることが性能向上につながると思います。いくらそれらしい指し手を選択するシミュレーションが実現できたとしても、例えば1,000手以上先の勝敗と現在の局面の優劣の関連性は（感覚的にですが）かなり低いと思います。*1
　あと、モンテカルロ法のプログラムは詰将棋はあまり得意ではないですね。UCTの性質上、駒損を連続するような手順にはなかなかシミュレーションが割り振られないので、強力な指し手の絞り込みをするなどしない限り、かなりのシミュレーション回数がないと正解できないと思います。ルートでの詰将棋だけなら証明数系の探索を使えばいいわけで、いまさらモンテカルロ法の出番はないわけですが、終盤の問題の中には探索中でそこそこ複雑な詰でもみつけなければならない問題も多いので、もう少し改善したいところではあります。


といったあたりで一区切り。年明けは卒論を書きながら選手権用プログラムの開発をしていこうと思います。

*1:もちろん一般的には予測率を上げれば終局性も良くなるのですが