「タイトル未定」というタイトル

Entries

実現確率打ち切り探索の拡張

　実現確率打ち切り探索は激指が大元なんですが、私は遷移確率の計算方法を少し違う形で実装しようと考えています。

　で、その激指は手の表面的な性質を元に遷移確率を計算しています。

　その “表面的な性質” というのは、手の選択的生成や評価関数と密接に関連しているのではないでしょうか？

　ならば、手を一括生成している上に評価関数も異なる自分のプログラムには、そのまま適用出来ません。

　また、手の表面的な性質に基づいた計算は、色々と面倒です。

　まず、表面的な性質を正しく定義するのが面倒。特に自分の場合は評価関数が複雑なので顕著だと思います。

　次に、コーディングが面倒。まぁこれは頑張れば何とかなるでしょうが（実際WILDCATさんは実装したらしいですし）。

　最後に、生成した手がどの様な性質なのか判断するルーチンが面倒（重くなりそう）。これは、探索ノード削減の為の処理自体にかえって時間がかかってしまいそうなので、かなり重要なポイントだと思います。

　で、面倒な事を頑張ってやるのは自分のスタイルとは合わないので、何とか楽に遷移確率を計算する方法を考えてみました。

　まず考えたのは“評価値が高くなる手は最善手になる可能性が高いので、遷移確率も高くすると良いだろう。逆に、評価値が低くなる手は最善手になる可能性が低いので、遷移確率も低くすると良いだろう。”という事です。

　（実際、激指の遷移確率を見ると駒得する手や駒の連携を良くする手には高い確率が与えられていますし。）

　そこで、去年（第16回）のバージョンでは手を指した後の静止探索値を元に遷移確率を計算しました。

　が、これが全くうまく行きませんでした。

　原因はおそらく二つあって、一つは静止探索値を元に計算している事。もう一つは静止探索値を遷移確率に変換する式が悪かった事だと思います。

　静止探索値を元に計算すると、歩の突き捨ての様にいったん駒損してから評価値が良くなる手の遷移確率が低くなり、深く探索して欲しいノードなのにさっさと終端してしまう、という現象がありました。

　二つ目の原因については、もう何も言う事はありません。式自体が適当すぎたので、うまく行かないのは当然です。

　という訳で今年はちゃんと遷移確率を計算しようと思い、色々検討していました。もちろん楽して何とかする方針で。

　そうこうしながら三目並べの強化学習のプログラムで遊んでいる時に、ふと“ボルツマン分布を用いて評価値を遷移確率に変換するのは、MinMaxの探索でもうまく行くんじゃないだろうか”と思い、実際に実験してみるとそこそこうまく行ったようです（ここ参照）。

　後は元になる評価値をどうするかですが、これは反復深化＋MTD(f)だから同じノードを何度も何度も探索します。なので、前回探索時の評価値を用いて遷移確率を計算すれば良いでしょう。

　ただ、評価値は大抵の場合上界・下界なので、そのまま使用すると問題がありそうです。

　そこで、局面の探索結果の上界が局面の静的評価値を下回る場合（パッと見よりも悪くなるのが明らかな場合）、または、局面の探索結果の下界が局面の静的評価値を上回る場合（パッと見よりも良くなるのが明らかな場合）のみ探索結果を元に遷移確率を計算し、それ以外の場合は静的評価値を元に計算する事にします。

　ついでに、単なる静的評価値だと大駒が特攻する手の遷移確率が高くなってしまいそうなので、二段階目の静止探索（直前に移動した駒を取る手のみを生成）での評価値を元に計算する事にします（上界・下界を利用するか否かの判定にも、こちらの評価値を用います）。

　で、ここまで書いて何なのですが、これらの改良点はまだ実装していません。なので、うまく行くかどうかはさっぱり不明です。

　近々（遅くとも二月中番頃までには）実装する予定なので、具体的な成果等はその時に書きます。

この記事に対してトラックバックを送信する（FC2ブログユーザー）: http://streakeagle.blog15.fc2.com/tb.php/850-eecb86e7

0件のトラックバック

0件のコメント

コメントの投稿

Appendix

QRコード

プロフィール

アベント

@author アベント
@mail murakumo_xp@yahoo.co.jp
アセンブラなんて分からないニュージェネレーションのJAVAプログラマ。
でもJAVA実習の単位は落とした経験あり。二回目もC判定。＜だめジャン
でもJAVAが好き。
2ch プログラム板にも出没。
- おまいら最強の将棋プログラムしてみろよ
- すれ立てるまでもない質問はここで
- Java質問・相談スレッド
- クラス名・変数名に迷ったら書き込むスレ