Bonanzaが無謀な角打をしなかったワケ

山田@CSAさんWRITE:

>全体としても上質なドキュメンタリーだったと思います。
>かなりいいイメージでコンピュータ将棋を取り上げてもらえたのではないでしょうか。』 (2007/04/22 23:07)

 かなり良い番組でしたね。あれから5回ぐらい見ましたが、
 解説も的確でわかりやすいものでした。


>「選択的探索」は、Singular Extensionのことだったのではないかと思われます。
 自分では気づかなかったんですが、
 指摘されて見直したらそれっぽいですね(・∀・)
 そのまま解説すると内容的に高度すぎるので、あえて判る人には判るという見せ方かも。
 NHKはさすがですね。


>ボナンザの角切りは(中略)
>駒損したときだけ、立て直されないかどうかを深く読んでみる、というアルゴリズムなのかもしれません。


 きっとそれだと思います。
 番組でbonaのログに注目して見てみると、
 EXTENTION->の項目に、
 recap、chk、1repに混じって、「patk」というのがありました。
 まさに「角打延長」だと思います。


 Yさんからコメントを頂きましたが、
 patkは、pawn-attackで、「歩のたたき」らしいです。
 駒を打つことはputらしいので、少なくともpatじゃなさそうです(^^;



> 山田剛@CSA 『もうひとつ、▲8一馬に代えて▲6四歩を「見切り発車した」と説明された部分が目をひきました。
>Singular Extensionが探索限界8分30秒で打ち切られて満足に読めなかったとき、評価値の現在値でなく、
>打ち切らずに読んだ場合に期待される評価値>を何らかのヒューリスティクスによって推定し採用した、というふうに聞こえました。
>探索の末端でそういう工夫をすることって良くあるのでしょうか?
>これは多くのコンピュータ将棋開発者に訊いてみたい気がします。』 (2007/04/23 00:45)


 これは自分も目から鱗でした。
 bonaの評価値で「+数字!」と表記される!がよく判らなかったのですが、見切り発車みたいですね。
 反復進化で、あの場面は16回まで確定して81馬なのが、17回の探索中に、81馬を上回る64歩が見つかった、
 ただし、17回は終了してないうちに、時間が来た。
 本来は17回は終了してないので、64歩は捨てるはずですが、
 少なくとも、81馬よりは良いことは保証されてると思います(もっと良い17回の解が見つかる可能性があるにせよ)
 ということで、確定している指し手が否定されている場合は、暫定の指し手を採用しても良さそうに思います。
 というか、さっそく自分も取り入れました(笑

bonanzaの反復回数の謎

凄いですね。
NHKの番組を見ていると、4分46秒で12億ノードの探索。
19回反復進化が進んでて、取り合い延長6回で都合三手延長で、最善応手列は19+3の22手先読み。
npsは400万ノード・秒、1coreあたり約50万ノード。
判ったのが、bonaの探索ノード数は、静止探索は含んでませんね。
12億を286秒で割るとだいたい400万npsになります。静止探索も10億ぐらいしてるので入れると倍近くなる。


ということで、自分はnpsは静止探索を入れて計算していたので、実際は序盤ですら20万ノードしか出てませんでした……
(中盤から終盤にかけては10万ノード・秒に落ちる( ´Д`)


あと探索効率を見てみると、12億で19回というのは、
およそ3の19乗です(3^19=1162261467)
ということは、bonanzaは3^nのオーダーで探索してることになります。
保木さんがGPWのスライドで、
将棋の平均指し手は80と仮定した上で、探索効率を


minmax:将棋空間=80^n
minmax+beta cut+nullMove+hashCut:(1/4 * SQRT(80) )^n = (2.23)^n


という式で表現しています。
futilityCutはあまりたいしたことがなくて、


minmax+beta cut+nullMove+hashCut+Fcut:1/4 * (1/4 * SQRT(80) )^n = 1/4 * (2.23)^n
n乗オーダーを変えるまでの力はないようです(全体を4分の一にする程度)
nullmoveは探索木が浅いところからカットできますが、
Fcutはあくまで終端の近くだけ狩るだけなので、それもそうかと思います。


で、結論として将棋は限りになる2^nオーダーに近いということですよ(・∀・)
しかし、現実はオーダリングの不備などもあり、
序盤3^n、終盤5^n程度と、スライドにはある。


で、実際のbonaは3^nで探索していた(あの場面は互いにあまり持ち駒も無く駒当たりも無かったので)
12億で反復進化19回ってことは、
100万で13回回る計算になります。これは効率が良い。1coreでも50万npsですから、1coreでも2秒で13手読める。


自分の開発中の将棋ソフトは、序盤は20万npsで30秒で600万ノード読めますが、
そのときで反復進化は12回しか回らない。
3^nオーダーなら、14回回るはずなのに……2回も少ない。
これはnpsは関係が無くて、探索ノード数に対する反復回数によります。
計算してみると、4^nオーダーだと12手読むのに1677万ノード。さすがにここまでひどくない。
ということで、4^nまで行かないまでも3^nにはほど遠い効率になってるようです。


しかし、nullmoveCutも70%台ですし、hashMoveCutも90%以上あります。
たとえnpsが低くても反復回数/探索ノード数には関係ありません。


ということは、スライドにもある静止探索やオーダリングの不備による効率低下か、
バグが残っているということだろうと思います( ´Д`)