将棋方程式を発見した!(7)


前回、コンピュータが局面の静的な評価を大きく誤る可能性が高い局面を「激しい局面」と定義した。その逆が「静かな局面」である。完全に静かな局面は、コンピュータが局面の静的な評価を100%誤らない局面である。そのような局面とは何か?


言うまでもなく「1手詰み」の局面である。1手詰みの局面は、プログラムのバグでもない限り*1100%間違えない。


つまり、詰む可能性が高い局面は詰むのか詰まないのかという結論によって評価値が、プラス無限大になるかマイナス無限大になるか大きく揺れることがあり、この意味において詰む可能性が高い局面は「激しい局面」であると言える。


よってこのような局面は評価を大きく誤りやすい局面であり、延長してでも徹底的に調べるだけの価値がある。


「王手された時の合法手をすべて生成」するように改良することによって強くなるのは、この理由による。(あと、無駄な王手で損する局面を先送りする水平線効果対策の意味がある?)


王手された局面が「激しい局面」だと理解出来ていれば当然延長すべきだとわかるはずで、私はそう実装するのが当たり前だと思っていたから「マイムーブ」が最近まで実装していなかった*2と言うことを知って驚いた。


気になって小谷善行先生の「コンピュータ将棋の頭脳」(サイエンス社。アマゾンで取り扱っていない。)を確認したが、静止探索時の「捕獲探索」の話題が出てきて、「駒を取る手がたいてい重要であることから、そうしたものだけを先読みする」と書かれている。


しかし、これはあまり適切な説明ではないと思う。「重要」と言うのを「その局面の静止評価値がその後のmin-max探索によって変動を受けやすい不安定なノードである」と読み替えればこの記述は正しいのだが、初心者がノーヒントでそう読み替えることは出来そうにない。


アマ4段を超える―コンピュータ将棋の進歩〈4〉には、KFEndの静止探索が出てくるが「(KFEndの)静止探索は通常の探索と異なり、生成する着手は取る手のみである」と書かれているのみで、ここ以外には「コンピュータ将棋の進歩」シリーズでは静止探索についての言及がほとんど無い。


うさ親さんのコンピュータ将棋のアルゴリズム―最強アルゴリズムの探求とプログラミング (I・O BOOKS)では、「末端局面での駒の取り合いの評価」(捕獲探索)を水平線効果対策として実装したほうが良いと言う程度の記述にとどまっている。


これらの文献から、どうもコンピュータ将棋では、歴史的に見ても実装レベルで見ても「静止評価」についてきちんと言及されて来なかったということがわかる。またうさ親さんの本のように「静止探索」は「水平線効果が起きやすい局面」と関連して語られることが多いが(そのように解説することは悪くはないが)、「水平線効果が起きやすい局面」が(ここで私の言う)「激しい局面」ではないし、それらは異質のものである。(全くの無縁でも無いが)


このことを理解してもらうためにもう一つだけ静止評価が難しい局面の例を挙げる。


それは「攻めがつながっているのか(駒不足のため)切れているのかが微妙」と言う局面である。この場合、人間であっても先を読まずに正確に判定することは難しいし、評価の難しいと言う意味で、「激しい局面」に分類される。(もちろん駒が一つもぶつかっていなくとも)


攻めが切れているなら受けきられて負けなので、評価値はマイナス無限大に近くなるべきだ。攻めが切れているのかを判定するためにもきっちり先まで延長して読みたいし、そのノードを先まで読まなければならない。


局面の静的な評価には誤差がつきまとうので、その誤差を何らかの形で評価出来ると良いことがわかる。


例えば、想定される誤差の大きさもわかっているとする。そして、評価値が 0 と -4±5 と -10±30の3つの局面があるとする。この時点で時間が無いなら一番良さそうな 評価値0の局面を選ぶべきだが、時間があるなら -4±5の局面や-10±30の局面も掘り下げてみたい。-4±5のほうは最大でも+1にしかならないから 0 より大幅に良いわけではないのでまずは -10±30から調べてみたい。


このように評価の誤差を何らかの形で見積もることが出来るなら、それを静止探索時の探索の延長に生かすことが出来る。


それでは「評価の誤差を何らかの形で見積もる」ことはどれくらい難しいのだろう?実装自体がとても複雑で、また同時に現在のコンピュータでは計算コストに見合わない可能性だってある。もし十分な成果が出せれば、私はこの誤差つきの静止評価を用いる探索方法を論文のような形で発表したいと考えているのだが…。


このようにコンピュータ将棋には数々のアイデアが考えられるが、残念なことにその時代の計算機アーキテクチャに迎合するアイデアは極々わずかである。

*1:最近、1手詰みを逃がすのが流行っているようだけどとか言ってみる。→ http://d.hatena.ne.jp/mkomiya/20080424/1208990629

*2:http://chocobo.yasuda-u.ac.jp/~nisimura/mymove/index.cgi?no=1194