やねうら王2016 Midが魔女(SilentMajority)と同じぐらいの強さになったところで、魔女の強さの秘密を書いていこう。というより、まずは、何故それまでのやねうら王が魔女より弱かったのかを書いておこう。あらかじめ言っておくけど、今回の記事は超長いぞ！

1手詰め判定

まず、やねうら王classic-tceでは利きを持っていた。この利きの更新コストが全体のCPU時間の15%を占めていた。当初、利きを利用した評価関数にする予定だったので、この利きを利用した超高速な1手詰め判定を用意した。

1手詰め判定については、以前もちらっと書いたが、2000年〜2005年ぐらいにちょうど詰将棋の研究が盛んだった時期があり、そのころに確立された技術である。なぜそのころ詰将棋の研究が盛んだったのかはよくは知らないが、おそらく当時は指し将棋ではまだプロ棋士に勝つのは時期尚早であり、一方で、詰将棋の解図能力では人間をはるかに上回っていたので、その分野でまずは足場を固めようとしたのかも知れない。(よく知らない)

それはそれとして、この超高速な1手詰め判定を用意出来て私はご機嫌だったわけだが、利きを使わない評価関数を採用する場合、この利きの更新のコストが重くのしかかってくる。魔女に勝てない原因はこのへんにあるのではないかと当初私は考えたので、仕方なく、利きを使わない1手詰めルーチンを書くことにしたのだ。

その利きを使わない1手詰めルーチン自体はやねうら王2014にある。Bonanza6のものを独自に改良したものである。しかし関数名やら何やらがやねうら王2016とやねうら王2014とでは異なるのでコピペで済む程度のものではなく、それなりの書き直しが要求された。実に2000行以上もある。実際に書いてあるコードも、探索部のそれよりたぶん多い。胸焼けがするような、出来れば触りたくもないような複雑怪奇なコードをいじくり回して、なんとか動くところまで持ってきた。

利きを使う1手詰めのほうは主に近接王手での1手詰めを調べていて、本来の1手詰め集合の93%程度しか網羅できていない。もっとも、ここを100%にすることはあまり意味はなく、高速に求められる範囲でなるべくたくさんの詰みが調べられることが大切である。3手詰めも近接王手から入る3手詰めなど、簡単に調べられるものに対しては調べたほうがたぶん良い。

それはさておき、このやねうら王2014の1手詰めルーチンの移植が終わり、検証してみたら、この1手詰めルーチンは離し飛車で合駒なしで詰む1手詰みなども調べており、1手詰め集合の99%以上を網羅できるようである。しかも、利きの更新コストは支払わなくて済むし、通常探索と静止探索とで呼び出してもこのルーチンの計算コストは全体の3%ちょっとである。15%にくらべると全然小さい。

これにより長い持ち時間(1手10秒〜)でのレーティングがR60ぐらい上がった。

1手詰めのバグ

1手詰めルーチンの置き換えが済んだ。1手1秒対戦などでは魔女と互角に近かったが、長い時間では依然としてずいぶん負け越していた。

これは、1手詰めルーチンがバグっていたことによるようだ。

1手詰めにバグがあると、普通は勝率は下がると思われがちだが、そう単純ではない。短い持ち時間だと1手詰めにバグがあっても勝率はあまり落ちないのだ。なぜなら、短い持ち時間だと、探索ノード数(局面数)が少ないので、1手詰めが間違ってしまうノード数も少なく、それゆえ、あまり戦績に影響が出ないのだ。逆に長い持ち時間の場合、高い確率で影響が出る。

ともかくfloodgateに流していたら1手詰めの絡むバグに気づいたので、ランダムプレイヤーを用いて1000万局面ほどテストして修正をした。もう1手詰めに絡むバグはおそらくないだろう。

see(),see_sign()の実装の違い

see()というのは、Static Exchange Evaluation(静的交換評価)の略で、特定の升で駒を取り合って、最後に自分から見ていくら駒得するかを計算する関数である。ただし、双方、途中でその升で相手の駒を取ることをキャンセルすることが出来る。飛車で歩を取って瞬間的に歩得になってもそのあと飛車を取り返されてしまうなら、最初から飛車で歩は取らないだろう。そういうことである。

see_sign()は、see()の符号だけ返す関数である。

やねうら王のsee(),see_sign()の実装は、かなり緻密に計算するようになっていた。ところが、結果的に言うとこれが良くなかったようである。探索部との相性もあるので一概に言えないが、Stockfishの探索部では、ざっくりとした計算を行なうsee(),see_sign()を想定してチューニングされているようで、see()のほうでいくら頑張っても空回りするようである。

あと、取り合いのときに、安い駒で順番に取っていかなければならないのだが、やねうら王ではPieceの定義を、
歩、香、桂、銀、角、飛、金、王
としてしまったので、この順番で駒を調べていた。金より角、飛車で取る手を先にしていたので、明らかに良くない。この部分も併せて修正したが、この部分の修正によるレーティング向上はほとんどなかった。そもそも角と金が利いている升で駒を取り合うというケースがさほどなく、実戦上はほとんど問題とならないのだろう。

ともかく、see(),see_sign()をStockfish = Apery = 魔女風に変えることで長い時間でのRが40ぐらいあがった。

評価関数の実装

評価関数の実装部分、やねうら王ではメモリアクセスの回数を極力減らすように細かく分割して差分を計算していたのだが、これがさほど効果がなく、むしろ足を引っ張っているようであった。

このへん、Apery風にしてみたところ、2%程度速くなったようである。
調子に乗って、AVX2の命令を駆使して(VPGATHERDDなどで)書きなおしてみたが、ほとんど変わらなかった。

これはVPGATHERDDがBroadwell世代では遅いというのもあるが、メモリ帯域がボトルネックになっているのでいくら計算を端折ろうと速くならないという事情があるようだ。もっとメモリまわりが速いCPU、マザーボードでは状況が変わるのかも知れない。Skylake以降に期待。(SkylakeのPC、持ってないのでよくわかりません。)

長い持ち時間に対する探索パラメーターの調整

やねうら王の探索部の探索パラメーターは長い持ち時間向きの調整になっていなかったというのがある。短い持ち時間で勝率を見ながら調整して良いパラメーターと、それだとまずいパラメーターとがある。下手な調整をするぐらいならStockfishのパラメーターそのまま(=魔女)のほうがはるかに優秀だというわけだ。

仕方ないのでいったん探索パラメーターの値をStockfishに倣うことにして、あとで再度、連続自動対局による調整を行なうことにする。

gccによるコンパイル

gccでコンパイルすると10数%速くなるようだ。Msys2上でコンパイルして同じ実行環境で比較しているので間違いない。PGOはかけてもほとんど効果がない。(1,2%あるかないか)

魔女よりnpsが出なかった原因

結論的には、利きの更新 + see()の実装の違い + evaluate()の実装の違い + gccでのコンパイルである。

この4つを解消したのだが、まだnpsには多少差があるように思われる。

魔女(≒Apery)は、探索node数のカウントをdo_move()で行なっておらず、このへんが原因でnpsのカウント方式自体が、やねうら王とは異なるので直接比較は出来ないようだ。

魔女とほぼ互角になったので、これで良しとする。

npsが上の4つの原因により差があったことに加え、魔女のほうが長い持ち時間向きのチューンだったので、この差が拡大して勝率の差として大きく現れたというのが実際のところのようである。

魔女の強さの秘密

いよいよ本題である。魔女は何故長い持ち時間において強いのか。

一言で言うと、最新のStockfishになってオーダリングの精度が上がったことがその理由に挙げられる。オーダリングというのは、指し手をよさげな順番に並び替えることである。よさげな指し手から調べていくことが出来れば深い探索を行なうときにすこぶる効率が変わってくる。なので、長い持ち時間で威力を発揮するのである。

ところが、このオーダリングがかなり重い。やねうら王2014では1スレッド当たり1Mnpsぐらい出ていたのに、やねうら王2016Midでは同じPCにおいて1スレッド650knpsぐらいしか出ない。評価関数に手番が導入されたので倍ぐらい重くなった(全体の2割程度だったのが4割程度になった)というのもあるが、オーダリング自体が重たくなったというのもある。おそらく、本家Stockfishでもここ近年のコミットによって、探索部は相当重くなっていて、npsは激減しているはずである。Stockfishの場合、評価関数は将棋にくらべるとずっとずっと軽いので、探索部の速度低下はモロにnpsに響いてくる。

それだけnpsが落ちてもなお、以前のバージョンより強いというのは驚愕すべきことだ。

ともかく、最新のStockfishの探索部においては、長い持ち時間になったとき、以前のソフトの(短い時間から長い時間にしたときの)Rの伸びとは比較にならないようである。