Yoshiki's notes
   


About
Open source software, shogi and my life outside of workplace.

Yoshiki Hayashi

Subscribe
RSS

Flavours

  • index
  • circa 1993
  • RSS
  • May
    Sun Mon Tue Wed Thu Fri Sat
    18
           


    Categories

           
    Wed, 18 May 2005

    実現確率探索
    GPS 将棋では実現確率探索を採用していて、おおむね上手く行っていると言って よいと思うのだが、といっても問題が無いわけではない。今のところ、以下の様な 問題が発生している。

    • 実現確率の低い良い手を見逃す
    • 実現確率の低い手による水平線
    • 実現確率の高い手による無駄な探索

    まぁ、どれも実現確率探索の設計通りと言えば設計通りではあるんだが、あまりに 派手な見落としをしてくれたりするとやっぱり直したくなるのが心情ってもんである。

    最初のは GPS 将棋の実現確率の取り方が悪いような気がしなくもないが、一見 ただ捨ての手の実現確率が非常に低くなるために、3手必至やただ捨てからの 駒の素抜きなんかが読めないのはかなり問題である。後、この問題は非対称で、 当たりになってる駒は平気で見捨てるということはやったりする。だから、 きのあ将棋戦では竜を見捨ててちゃんと必至をかけられたわけだけど、竜をただ捨てして 追い込むなんてことは今の GPS 将棋には相当簡単な勝ちが見えていないと できない。2次予選の竜の卵戦では時間がなくて明確な勝ちじゃないのに やっちゃったけど。

    二つ目は、ナイーブな実現確率探索ではなく、α値更新探索延長実現確率探索で ある程度は緩和されてはいるが、例えば本当は良いはずなのに 変な受けの手で実現確率を消費してしまい、それを咎める手を生成できなくて 良い手を見送ってしまったりする。探索延長のもともとの動機は実現確率が低いために 深さが浅いところでリーフに達してしまい、そのために 良いと思ってしまっている局面をなくす、ということなので仕方が無いのだが、 実現確率が足りないために悪いと思ってしまっているのは結構ある。下手すると、 本当は良い手なのに、5手くらいで打ち切られてしまっていることもあったり、 以前は末端で相手の飛車当たりで実現確率を消費してしまい、飛車を逃げる手が 生成できずに評価値が悪くなっているのもあったりしたので、これも何とかしたい。 飛車逃げは静的探索をいじることで今は何とかなっているようである。

    三つ目も設計通りと言えなくはないと思うのだが、GPS 将棋の場合、全局通じて 同じ実現確率を用いているために、終盤では結構外れの手を延々と、しかも 終盤なのでそういう手は結構たくさんあって、全然深く読めないという問題がある。 延々と端の桂香を拾いに行く手を読まれるとそれはそれでうんざりしてしまう。 今は評価関数の仕様上、急激に相手玉に迫ることは可能だけれど、それが無理な ときは非常にじっくりと、むしろ全然迫らない、なんてことになってしまって いたりする。終盤は実現確率の値を変更する、というか進行度に応じて それなりに補正するようにした方が良いのかもしれない。

    まぁ、どれもこれも GPS 将棋の実現確率のカテゴリー分類と実現確率そのものの値が 甘いせいという気がしなくもないが、今使っている実現確率は表面的な 一部分の性質を用いた近似であるので、程度の差こそあれ、上の様な問題は常に 存在することになる。上手い解決策があれば論文になるのだろうが、そんなのは 一朝一夕には思い付かないので、とりあえずは地道に分類や値の調整をすることになる。

    少し実現確率探索について考えてみると、ナイーブな実現確率探索というのは 局面を与えると、手生成部分だけで探索木の形が一意に決まってしまうものである。 どんな評価関数を与えようと、同じ探索木を必ず辿るというのは何となく まずそうだというのは想像できると思う。そこで、α値更新による探索延長ということを 行うことにより、評価関数が探索木の形に影響を与えてくるようになる。 が、やはり探索木の形は大体実現確率の値で決まる。ある局面に対して、 変になるような実現確率の値を持っていると、その局面ではどんな評価値を 使っても話にならなくなってしまう。

    従来の仮評価による探索を考えてみると、こちらは探索木の形は手生成と 評価関数に依存している感じであり、指し手の性質というのは評価値の変動以外には あまり考慮されていない (しているのもあるだろうが)。今でも深さにより 前向き枝刈りにより残す手数を調整しているのかどうかは知らないが、残す 指し手の数はおそらく探索の深さとのバランスを考えて人間が決めた値で、 特に根拠があるわけではないように思う。

    指し手の統計的な性質を捨てるのはもったいないし、それだけに頼って 実は良くなる手が読めないのももったいない。何か良い方法がありそうな気がするのだが、 それは一体何だろうか。

    [/shogi] permanent link