モンテカルロの失敗談。

　まだ懲りずに音声の研究の合間にコンピュータ将棋について考えている。一応、時間制御の部分と千日手の部分と棋譜の生成の部分を除けば、５５将棋は動く。動くというだけでものすごく弱いのだが（５５将棋だというのに５手先までしか読めない。反復深化をしない原始的なαβをしている。前向き枝刈りはしていない。言語はJava）、三手詰めの詰め将棋すら解けない私よりは強い。ダウンロードしたTohskeには簡単に負ける。

　さて、本日の日記には、先日試行錯誤して結局まともに動いてくれなかったアルゴリズムを書く。将棋にモンテカルロ法を適用するのは難しいのではないかと思ったのだが、もし適用するならどういうアルゴリズムにするだろうと私なりに考えた結果である（繰り返すが、まともな手を指してはくれなかった）。

　囲碁のモンテカルロは基本的にはランダムに打っていって、最も勝率のよかった手を選ぶというものである。これは将棋には使いづらいと思えた。一手指したあとの手によって、勝率などいかようにも変化するからである。将棋に囲碁のモンテカルロ法を適用するとノイズが多くてとてもまともに動きそうにない（ように思えたがまともに動かしている人もいる）。だから、将棋には将棋のモンテカルロ法が必要なのではないかと考えた。

　途中の思考過程は省略するが、min-maxの考え方とモンテカルロを融合させることはできないだろうかと考えた。min-maxの計算方法はmin演算とmax演算を繰り返すというものである（negaMaxは等価なので置いておく）。当たり前だが、読みの深さに応じてminとmaxを交互に使う。これをモンテカルロに使いたい。

　ここで、モンテカルロの考え方自体を少々変える。モンテカルロ囲碁は何度も終局までを試行して「その手を打ったあとの勝率」を計算していたが、「試行自体の妥当性」を計算するのもありなのではないかと思った。一秒間に一万回終局まで試行したとしたら、その一万回の中の最も妥当な試行を探して、その一手目を実際に指すのである。

　さて、どのように「ベストな試行」を選ぶのか。ここで「評価関数が作りやすい」という将棋の特性を利用する。モンテカルロ囲碁では終局時の勝ち負けのみを集計していたようだが、今回のアルゴリズムでは途中に現れた局面一つ一つの評価値を溜め込む。また、終局まで指さずに例えば三十手で試行を終える。十万回試行したとすると、三百万の評価値が出てくる。これを参考にして「ベストな試行」を選び出す。理想的な試行というのは、ほぼだいたい評価値がmaxとminを交互に繰り返しているはずである。少なくとも同じ探索の深さ同士の評価値を比べて、中央値よりは大きい（あるいは小さい）値になっているはずである。だから、同じ深さ同士の評価値の中央値と比べて妥当な不等号が成り立てば、その試行に「妥当性」のスコアを加算することにした。最も妥当性のスコアの高かった試行を「ベストな試行」とした。ここまでが今回のアルゴリズムの核となる部分である。

　アルゴリズムの穴は簡単に見つかった。少なくとも三つは見つかり、そして一つはふさぐことができる。

　一つ目は、例えば先手番が圧倒的に有利になるような差し回しがランダムな試行によって得られた場合、深さ一つ置きに妥当性のスコアが加算されてしまうということである。これを防ぐために、「深さ二連続で妥当なときのみスコアを加算する」ということにした。

　二つ目は、「中央値」が適切な閾値でないと考えられるということである。例えば、相手に駒を取られるような手を指した場合、相手がそれを取った後に合法手が増えるため、中央値がその影響を受ける。そのため、相手に駒を取ってもらう手ばかりを指すようになる。ただし、これはなんとかなるような気もする。

　三つ目は、致命的である。たかだか数百万程度の試行の中には、妥当な筋の手など存在しない確率が圧倒的に高いのである。これは私には解決できない問題なのだが、解決してしまう人もいるのだろう。

　なお、「ベストな試行」を探す際、数百万からいきなり一つを選んでしまうのではなく、最初は上位数十万を選び、「中央値を計算し直して」上位数万を選び、さらに数千を選び、数百を選び……、というふうに中央値を計算し直しながら徐々に候補を絞っていった。これに効果があるのかどうかはよく分からない（なにしろうまくいっていないのだから）。

　このアルゴリズムの利点は、計算量がいつも一定であるということと、深さを自在に制御できることにある、と思っているが、なにしろ三手詰めが解けない私よりも弱いので、なんともいえない。結局のところ、モンテカルロ将棋は難しい、というところに戻ってきてしまうのであるが、もしこのアルゴリズムに将来性を見出す人がいたら適当に改良してみてほしい。将来性を見出せない人は、本日の日記を無視してほしい。