コンピュータ将棋ソフトウェアの時間制御

　Yaneuraou+Apery評価関数版god whaleがあるというのを書き込みで教えてもらったのに放置してしまったのだが、理由がある（いきなり言い訳）

　理想的には、YaneuraOuはStockfishのバグ無しバージョンであるという話なのでStockfish丸パクリのように見えるSILENT MAJORITYより強いはずで、実際0.1秒だとSILENT MAJORITYがかなり弱いのだが、２秒超えるとSILENT MAJORITYのほうが強いという結果が出てしまった。

　計測方法が悪いのかと思ってたが、公式でも0.1秒ではYaneuraOuのほうが勝ち越すようだし、コメントを見るとやはりSILENT MAJORITYのほうが強いんじゃないかという書き込みもある。

http://yaneuraou.yaneu.com/2016/06/04/%E3%82%84%E3%81%AD%E3%81%86%E3%82%89%E7%8E%8B2016-mid%E3%81%AE%E9%96%8B%E7%99%BA%E3%81%AE%E9%80%B2%E6%8D%97/

　自分がやった限りでも、SILENT MAJORITYで0.1秒対戦を行うと、大変弱いので自己対戦の結果が信用出来ない。以下は前にも乗っけた対Apery WCSC26とのグラフ（横軸btime設定時間、縦軸対Aperyレーティング）



　上記のように1秒未満だと「ふーん、ま、こんなもんじゃね？」って感じなのだが、2秒を超えてからのレーティングが「んまぁ～い」というぐらい凄まじい。しかも読めば読むだけ味が出ているというか頭打ち感が無い。YaneuraOuにしろAperyにしろ時間を伸ばす＝探索局面数が増えるごとに常識的なレーティングの伸びを見せているが、それを上回るSILENT MAJORITYの伸びは異常で、その秘訣を探ろうといろいろやってみたが結局わからなかった。

　丸ごともってきたほうが少しずつ持ってくるよりも大幅に強くなるというのはかなり衝撃だった。この点においてSILENT MAJORITYはコンピュータ将棋の強さには相当貢献した（orする）と思う。

　で、R200も変わるような自己対戦の結果に対する疑問点の一つに「そもそも時間制御がうまくいってないんじゃないの？」というのがあって、気になったので少し調べてみた。

　以下、環境構築

　やねうら王自己対戦フレームワーク
　　サブディレクトリに対応：技巧やnozomiが実行ファイルと同じフォルダにbook.binが必要なため
　　時間計測：サーバ側で計測するように修正。あと高精度タイマに変更した。

　自己対戦フレームワーク用アプリ（自作）
　　時間設定とログ保存がメイン
　　秒読みマージンを技巧に対応

　計測条件
　　１コア（スレッド）、時間指定１秒、その他のマージン０での結果、Ponder off（のつもり）

　定跡を使ってるのと詰みを見つけた時は目視で除外したので試行回数はそれぞれ１回。
　サンプルの手数は同じソフトウェアでの自己対戦なので70手ぐらい
　結果は以下のとおり



　YaneuraOu：ルールを守る気が少しだけあるが、最大値が100ms以上オーバーするというルール無用っぷり
　Apery WCSC26：そんな早指ししなくてよいのにたまに勝手に早指しする 　SILENT MAJORITY：Aperyより早指しする場合がある。
　nozomi：Aperyを参考にしているのか傾向としては似ている。ただ最小値になる確率は低いのと、1000ms超えることがなかったのが好印象。ルールに則った正統派といえる。
　技巧：安定性ではPC上のアプリケーションが制御できる限界レベルといって過言ではない。しかし必ずオーバーするのは完璧超人じゃないからだろうか。
　
→Apery関係は追記で修正しました

　技巧のソースは部分的にしか見てないから適当だが、あくまでも一般的な話としてWindows上でSleepやイベントを使用した場合、アプリケーションに起こりうる変動は10msなのでそれ以下なら十分だと思っている。なので直感的には1000ms指定して1000+-10msなら合格だと思ってたが、自己対戦する上では期待通りに動いているのが技巧だけという結果だった。ここまで精度が高いのになぜ1000msを超える場合があるのかは謎。また、ユーザー視点では将棋所の厳格な時間チェックをいれてまともに動くのは多分nozomiだけだろう。

　0.1秒にすると誤差がさらに明確になる



　nozomiは内部的に１秒が最小になるようにしているようで、外部から0.1秒に設定できなかったので未計測。

　シングルスレッドの結果なので、マルチスレッドによる変動はないことを考えると、0.1秒自己対戦をやる前に、技巧を見習って時間制御をまともにするべきであろうと思う。技巧はこの精度出すために何か工夫してるのだろうか。

Aperyの思考時間がばらつく原因

SLIENT MAJORITY が強すぎる (2)

　SILENT MAJORITYが短時間で妙に弱かったのが幻かやり方がまずかったのか気になったので、自己対戦ツールでさくっと調べてみた。

　以下はWCSC26と同じ時間で１コア対局させた場合の比較。縦軸はレーティング。



　１コア２秒以下では明らかに弱くなる一方で基本的に持ち時間が増えればレーティングが上がる。また１コアでの比較なのでLazy SMPは今回は影響がない。

　上記のレーティング差は１コアでの差なので、今どきの４コア以上の環境では１秒対戦でも、まずAperyには負け越さないと思われる。

　ソースコードをいろいろ調べたが、このようになる理由は静止探索中の枝刈りなどが影響していると思われる。AperyはStockfishが2015年ごろに入れた静止探索中の枝刈りなどのコミットが入っていないのだが、素のAperyにこれを入れると探索局面数が減って速くなる代わりに相当弱くなる。これは重要な指し手が枝刈りされてしまうことが多いためと思われるが、良い確認方法が思いつかない。

　今の探索では重要な枝を刈ってしまって弱くなりっぱなし（時間掛けても強くならない）のだが、多分Counter MoveやMovePickerなどの様々な修正が混ざるとこのデメリットがほぼ払拭されるのだろうと思う。（結果がそうだからってだけで確認するのも結構難しい）

　やねうら王の探索はかなり煮詰められてると思うので比較したいが、評価関数に手番があるかどうかの差でR200ぐらい差が開いているので、やねうら王ｖｓAperyを行ってもあまり参考にならない。やねうら王探索＋Apery評価関数があれば最強の可能性は高いと思うのだがどうだろうか。

やねうら王の連続自動対局フレームワーク

　やろうやろうと思って放置してるうちにまったく手を付けられていなかった自己対戦フレームワークを連休中に使えるようにした。

　ある程度はマニュアルに書いてあるのでコピペ＋補足。


・バイナリのビルド

　shogi.hの
　#define LOCAL_GAME_SERVER
　を有効にしてビルド。

　通常のやねうら王に昨日を追加するという形で実装しているので、マクロ切り替えてビルドするだけ。ただ、作成されたファイル名がYaneuraOu.exeなので適当（local-game-server.exe）にリネームする。


・他に用意するファイル

　通常の対局用ファイルとは別に設定ファイルを２個用意する。

engine-config1.txt : 1つ目の思考エンジン
engine-config2.txt : 2つ目の思考エンジン

1行目にengineの実行ファイル名(同じフォルダに配置)
2行目に思考時のコマンド
3行目以降にsetoption等、初期化時に思考エンジンに送りたいコマンドを書く。

例)
YaneuraOu.exe
go btime 100 wtime 100 byoyomi 0
setoption name Threads value 1
setoption name Hash value 128

　ここでスレッドとハッシュ値はちゃんと設定する。他にもPonder止めるだとかなんやかんやと必要になるので、usiコマンドでパラメータを確認する。

　スレッドは並列対局数との兼ね合いで決める必要がある。

　またマニュアルではハッシュ値を1024MBも確保しているが、0.1秒対局の場合、1%も使わないので128MBも確保すれば十分。（デフォルトの16MBだと流石に小さいと思うので増やす）。1024MB設定では１秒対局で良くて1%程度。


・対局開始

goコマンドで対局が開始できる。

　local-game-server.exe go btime 500

　とやると、何も設定しなければ論理CPUコア数/2*500回の対局が始まる。
　スレッド数が同時対局数になる。

setoption name Threads value 6
のようにして実行すると6スレッド(×2プロセス)が起動して、6局並列で対局が進行する。
btimeで指定した数の6倍の数の対局数が行われる。

　最初これの意味がわからず、3000を指定してしまい、12000回対局していた。

　btimeとか使ってるのはUSIインターフェイス的な話で、本来は思考エンジン動かすところにただ乗りしてるので名称が適当になっている。

stopもしくはquitで終了するまで対局結果が出力される。

win : engine1勝ち
lose : engine1負け
draw : 引き分け

　マニュアルだと○、×だったが、コンソールだと文字になっている謎。
　また終了時のSFENが出てくるが、終了時だけだとあまり意味が無いと思われるが、ここらへんはやりたいことがあったら改良する形になるだろう。

対局回数の指定など)
go btime [対局回数] wtime [定跡の手数] byoyomi [予約]

定跡はbook.sfenとしてsfen形式のファイルを与える。1行に1局が書かれているものとする。
このなかからランダムに1行が選ばれてその手数は上のwtimeのところで指定した手数まで進められる。
デフォルトでは対局回数は100回。定跡の手数は32手目から。

　定跡はやねうら王は自動対局用としてはうまく散らばらせているので特に手を加えなくて良い。
　Aperyの場合妙に偏る場合がある気がするが、数をこなせばなんだかんだで平均化される。


・その他

　コマンドラインから入力した文字列を連結して、USIコマンドとして実行する機能があるので、
　これを用いて、次のような.batファイルを作ってそれを実行すれば連続自己対局が簡単に開始できる。

> local-game-server.exe go btime 500

　このときにgoを打ち忘れるとかやるとダミープロセスが残ったりするので開始したらちゃんと動いているかタスクマネージャーで確認したほうが良い。


・やねうら王以外で使う場合の検討

　対局時間
　　0.1秒で探索させた場合でも自分のCore i7で探索深さ10ぐらいまでは動くので時間としては十分
　　評価関数が重いとかいう理由で3とか5だったら0.2秒とかのほうがよいかもしれない

　定跡
　　やねうら王の定跡は十分ランダムに思えるので、１秒対戦と0.1秒対戦であまり差が出にくいように思える（単に圧倒的に不利な方に突っ込んでるのが互いに出るのでどっちに転ぶかわからない局面が少ないのかもしれないが）
　　Aperyの定跡は妙に偏る場合がある気がするが、数をこなせば結果的に平均化される気もするので今のところ放置

　計測できない部分
　　LazySMPの効果
　　深いDepthが影響するパラメータ
　　　「Depthの３乗ボーナスがやりすぎではないか」というのを進言したことがあるが、これは自己対戦の結果だけ見てるとわかりにくい。たまたま将棋所の局面で大逆転かまされてたのを見たら、Fail-Lowでどの手を選んだらよいか選びあぐねてるときにボーナスがでかすぎると何でも無い手をさくっと選んでしまう（ように見えた）
　　
　こういうのもあるので、地ならしはlocal-game-serverで行い、ある程度安定したら将棋所で１秒とか３秒で変なところがないかを確認するのが良いと思われる。


・改良

　自己対戦フレームワークを使ってると以下の面が不満になってきた

　エンジンの切り替えが面倒
　持ち時間の設定を変えるのも面倒
　自動でログが残らないので保存が面倒
　勝率とレーティングを出してくれないので計算が面倒
　あとどれぐらいで終わるかわからないので予定が立てにくい

　特にファイルを書き換えるのはミスが起こりそうで、気軽さがない気がしたので、GUIを作ってみた。



　これによって上記の不満が全部解消された。
　さくっと実験して、さくっとログが取れて紛失することもないし、再現性もある。

SILENT MAJORITYがかなり強い

　くじらちゃんのメインで使われているというSILENT MAJORITYが強いと評判で、それはどうも以下のやつらしい

　https://github.com/Jangja/apery

　色んな人が使えるようにSSE2のバイナリが添付されているが、多分AVX2でビルドしたほうが評価関数の速度が10%ぐらい上がると思う（未確認）

　とりあえず自分でビルドしてみたが、MSYS2だと何箇所か修正しないとビルドが通らなかった。（元の人はVisualStudioでビルド通していた模様）
　一応MSYS用修正いれてプッシュした

　https://github.com/woodyring/apery/commits/silent_majority

　これのコミットは大胆で、Aperyの評価関係以外を完全にStockfish7で乗っ取るように作られている。

　自分が１月ぐらいにやってみたときはApery残したまま取り入れようとしたのだが、結構差異があり、特にCounterMoveは入れるのが面倒だったので断念してすっかり放置してたのだが、これを作った人はがっつり入れ替えている。

・Searcher（Aperyが学習のために使うクラス）はStockfish7にないので入れない
・Stats（HistoryHeuristicなどに使う）のDropもStockfish7（Chess）に無いので入れない
・平岡流の命名規則もStockfish7に乗り換え

　というすがすがしさ。

　ところが、これで４コア１秒で大樹の枝と対戦させてみると７割近く勝っている。
　４コア１秒２００戦ぐらいだと　132-13-54

　LazySMP４コアぐらいだとNPSはほとんど同じで速度的にはメリットがない。
　Apery_WCSC26と大樹の枝を同じ評価関数(20151105)を使って１秒４スレッドのときは98-14-95と勝率５割程度。

　速度的にNPSはほぼ同等の場合、勝率はほとんど変わらないと思っていたので、Apery同士の対局の勝率はわかるのだが、SILENT MAJORITYの勝率は正直理解できない。
　将棋所のグラフを見てると妙に逆転率が高い気がする。
　結構Apery食いしてる気がしてて自分だけの（何か設定による）現象かと思ってたが、そうでもないようだ

http://wdoor.c.u-tokyo.ac.jp/shogi/view/show-player.cgi?event=LATEST&filter=floodgate&show_self_play=1&user=Apery_WCSC26_6700K%2Be733237ce43ff50e9b128d6c1b20e0d2

http://wdoor.c.u-tokyo.ac.jp/shogi/view/show-player.cgi?event=LATEST&filter=floodgate&show_self_play=1&user=SILENT_MAJORITY_4770K%2Bf6bb59406cd0bc087f6797840e553ddc

　Apery_WCSC26の成績が悪いのはSILENT MAJORITYに負けまくってるからで、全体としてSILENT MAJORITYのほうが強いことになる。

　そこで、やねうら王フレームワークで0.1秒１コアで対戦させる。もしLazy SMP以外に良いところがあればここでも７割勝つはずであるが、この場合、大幅に負け越した。（データ失念）

　また2chのスレでも2000～3000局対戦させて、55%程度という話もあり、何が要因か絞りかねている。

　まあ、とにかく現状ではSILENT MAJORITYはオープンソース最強ではないかと思われるので、鉱脈がどこにあるかぼちぼち見ていきたい。

Apery WCSC 26 公開

早いですね。ざっと見たやつ。

https://github.com/HiraokaTakuya/apery/commits/master

commit ccd3055296d9ac65fe886758afba79c8532622ef
Author: HiraokaTakuya 
Date:   Thu May 5 08:56:18 2016 +0900

    評価関数更新。WCSC26 バージョン。

評価関数のファイルが変わってる

commit d1bc181ef4b0c1cabc24b7f1a94c360b64c1d0ae
Author: HiraokaTakuya 
Date:   Fri Feb 5 00:55:59 2016 +0900

    並列化アルゴリズムを Lazy SMP に変更した

    300ms 8cores
    ( 1448/999999) W:   734 L:   648 D:    66  WR:  52.97 +-  2.57
    300ms 18cores
    (  635/999999) W:   415 L:   194 D:    26  WR:  67.40 +-  3.65

LazySMPについて、自分でBlogを書いたが、すっかり忘れていたのでさっき読みなおした。昔の自分偉い。
なんでもAkiさんによれば6コアvs20コアで勝率７割だという。

20スレッドvs6スレッドで1手1秒で対局させた結果、現在556戦して395勝150敗11引き分け(256手超過)。勝率7割くらい、R150点くらいだろうか。NPSは9.3Mと3.7Mで2.5倍ほど。Lazy SMPすごい。

— aki. (@ak11) 2016年5月4日

個人レベルだとせいぜい４コアだし８スレッド使うとPCが完全に固まるしと、あまりうれしくない。
ただ、無差別級のコンピュータ将棋選手権でAWSでLargeを借りて４０コアとかでやるとかなり勝率が上がっていたと思われる。

あと、このコミット、Lazy SMPというよりは、ほとんどStockfish 7化といってよいぐらい関係ないコミットが割りと入っているような気もする。

Aperyでは学習のためにグローバル変数がsearcherに入っているのだが、LazySMP化するのにあたって一部の参照の変更がめんどくさい。そのハック方法が参照のローカル変数を宣言すると少ない変更で済むのだが、似たような事をやっていたので安心した。

commit d7fca7036ca4a047e14907b9ad7ccfacd08245d1
Author: HiraokaTakuya 
Date:   Tue Mar 1 08:44:39 2016 +0900

    L2 peanlty

    追加学習で2%程度勝率向上。

前に追加学習させるときにL1よりもL2のほうが良いのではないかというのを書いた記憶がおぼろげながらあるのだが、Aperyでは2%ぐらい勝率が上がったらしい。

強化学習する際は80億局面から学習させる意味の一つにL1による値の消滅を防ぐ意味合いがあるだろうとは思ってていたが、NDFの金澤さんがくじらちゃん放送に出た時のコメントで確信を得た。

ただ、追加をやるにはL2のほうが少ない棋譜でも値が消えないので下手なハイパーパラメーター（減衰率）の調整をやらなくて済むだろうというのはあるが、ここらへんはまだ鉱脈がありそうな気はするなぁ～と思った。

commit b3770e65884b3c6621526adfba20974a8d563670
Author: HiraokaTakuya 
Date:   Sun Feb 21 19:26:29 2016 +0900

    静止探索で ttMove を使う深さを制限。recapture の開始深さも変更。

    ( 5638/90000) W:  2817 L:  2663 D:   158  WR:  51.37 +-  1.30

ここらへんは怪しいと思ってたが、こういう修正方法もあったのか。なるほどと思った。流石本家。

commit 4f35eed60da41f6da04938a25ad6ce7c9275a04c
Author: HiraokaTakuya 
Date:   Wed Feb 17 03:27:56 2016 +0900

    transposition table 効率化

    200ms, Threads 2
    ( 7063/90000) W:  3491 L:  3282 D:   290  WR:  51.48 +-  1.17

ハッシュ値が32->16bitになるので衝突が激しい。上の静止探索のときに使わないというのもこれが少なからず関係していると思う。

commit 650be8e13cfa07faa4ccc729d81d5c2ddcca2cbc
Author: HiraokaTakuya 
Date:   Thu Feb 18 09:05:48 2016 +0900

    transposition table から取得した move の合法手判定が甘かったので修正。

　合法手判定をより厳しくやらないといけない理由は、おもにKillerMoveが関係してくる。Transposition Tableから読み込んだ時に、手番や動かす駒の色が一致していることが保証されているからで、そうでない場合はより厳密にやる必要がある。
　やねうら王で検証した時は、benchコマンド（depth9当時）に３局面しか現れなかったので、確率が低い。よってこの変更は入れないほうが勝率では高い可能性がある。

commit 6c393277036fdaab1d066a80ad6adce7e122b4c2
Author: HiraokaTakuya 
Date:   Mon Feb 15 22:19:59 2016 +0900

    depth < Depth0 で search() を呼んでいたバグを修正

    ( 9706/90000) W:  4710 L:  4697 D:   299  WR:  50.07 +-  0.99

Stockfishでもやってたバグ

commit d08b15adb3fb38af1a01f1ba20ec4308ecb335bd
Author: HiraokaTakuya 
Date:   Tue Jan 19 08:17:51 2016 +0900

    futilityMargin と reduction 調整

    ( 1330/ 3000) W:   700 L:   595 D:    35  WR:  53.95 +-  2.68

これによって逆転率が結構下がると思う。
自分のローカルコミットにもこれと同等のものがあったが、短時間だと１０局に１局ぐらい。R20ぐらいは影響があった。

あと、確証はないが、Statsのところの配列宣言する部分で、Score table_[2][PieceNone][SquareNum]となっている部分をScore table_[SquareNum][32 * 2]とやねうら王ライクにすると少し高速化(2%ぐらい？）できる気はする。

個人向け（４コア以下）にはLazySMPはイマイチだと思ってるので、後で検証してみる。

やねうら王 v.2.21～ の日記

　もう更新ペースには追いつけて無いので日記。


■棋力
　今のclassic-tceでやねうら王2015とほぼ同等らしい

　電王戦のときの評価値の並びをちらっと見たところ
　やねさんが「公開処刑や」とぼやいているのを見たが

　技巧＞大樹の枝＞やねうら王＝nozomi

　みたいな感じで評価値が出てて、H/Wも同一で探索した結果なので
　純粋に評価関数の質の差だと思われる

　効きの数＞手番有りKPP（次元下げあり）＞手番なしKPP（次元下げあり）

　みたいな感じだと思った。
　ここにさらにNDF強化学習メソッドのPonanzaが加わると

　NDF強化学習＞？効きの数＞手番有りKPP（次元下げ）＞手番なしKPP（次元下げ）

　みたいな感じなのかなと思った。

　ここに序盤の定跡や探索性能も加わるが、探索はStockfishだとして、定跡まで完全に生成してるのはPonanzaぐらいしかしらない。序盤の定跡生成も結構マシンパワーを使わないといけないと思うのだが。既存の定跡を絞り込むやねうらメソッドの定跡ですら一ヶ月かけて精査したぐらいなので、終盤の強化学習だけでなく序盤にもマシンパワーかけてるものに追いつくのは相当難しい気はしている。

　あとPonanzaは評価関数を序盤と終盤に分けるというのもやってたような。


■技巧のアピール文章

　収束が２２時間と聞いて、数年前にはてなブログに１日で収束させていた人がいたのを思い出した。その人はニューラルネットワークだかそれっぽいやり方をしていたので、てっきり習甦の人だと思ったが、アピール文章見てたら技巧の人だったのかなと思ったけど、どうなんだろう。
　KPP全盛で二週間とか一ヶ月かけて収束させるのが当たり前みたいなときに、ぜんぜん違う方法でやってたので覚えてたけど昔みたはてなBlogはことごとく消えてしまった。


■AkiさんのCV失敗の話

　PonanzaのAkiさんが、「進行度学習したときにうまくいかなかったのが、CVに学習データ使ってたから」というようなツイートしてて、あのAkiさんがそんな初歩的なミスをしたのかとツイート読んだ時は思ったが、翌々考えてみると５年ぐらい前だと棋譜＝プロの４，５万局が全てみたいな時代で、CVやるのも難しい。どうやるんだろう。今だとPonanzaは強化学習用に大量のデータを蓄積してるので、変な心理的なハマり方をしないのだとふと思った。こういうところもまともにPonanzaに追いつこうとすると結構辛いところかなぁと思う。

更新履歴と自分の調査のまとめというか日記。

やねうら王のバグ修正まとめました

　AtCoderが終わると思ってたら今週末ぐらいまでは続きそうなので、前回の「やねうら王のバグまとめ」に書いたコード＋αを綺麗にしてアップした。

　https://github.com/woodyring/YaneuraOu/tree/bug_fixes

　SEEのバグはやねうら王Blogのコメント欄にかかれていたもの。

　SEE以外の修正はほとんど勝率に影響しない。
　勝率は１秒対戦で１００－１２－８８だったので、微増ぐらいだと思いたい。

commit e0f31bb140423f8b61f7e04390ea6943d679d3a2

update ver. 2.17

　なぜかUSIのバージョンがあがらないのでアップした



commit e20edfccb16b384beb0de4b0604d740b1c5c20e3

fix crash without NEW_TT

　NEW_TTなしの時にすぐにクラッシュする問題の修正
　Bit0を保存するようにしただけ。
　ハードコーディングしているので念のためstatic_assertを入れておいた。


commit 43a8770ab77f215e53d1d895d8954091a6fe3534

fix crash by illegal drop move

　Drop側にも違法手チェックを入れるべき

commit fd2faf079063e2abea6790310bb4ec307386b7f7

fix mate1ply

　コメントにも書いたが、自玉に王手がかかってるかどうか調べずに王手を調べてしまうので、終盤に評価値グラフが暴れる。
　勝率にもろに影響しそうに思えるが、そもそも王手が両方にかかるような一手差に見える場合、必勝か必敗局面であることが多いので、グラフの見た目が悪くなる程度の影響しか無かった
　他のソフトと戦うときは少し事情が変わるかもしれない


commit 67a49c9e0420fbc43cbd25d00b7f46bb7c0fc1e2

fix SEE bug

　やねうら王Blogにかかれていた大変素晴らしいバグ修正
　最近のC++コンパイラでこんな不具合が混入するのかと思って少し調べてみたが、コンパイルを通すためにほとんどポインタ渡しと同等のコードになってるので、配列数をコンパイラが解釈してくれないためだと思われる。


　置換表にデータが沢山入っている時に、盛大な悪手を指すことがしばしばあるので、まだ何かバグってそうな感じはする。

やねうら王のバグなどまとめ

　そろそろAtCoderも終わってしまいそうなので、現状までわかったことをまとめ。新規なところは特に無い。

■バージョン
　やねうら王 classic v2.17

■落ちる原因
　「pseudoLegalが相手番の違法手（多分Dropのみ）を弾くことが出来ない」

　旧置換表の場合は、（多分実装ミスによって）Sideビット(bit0)が落ちてしまうため、相手番のハッシュキーを参照する。このため、Dropのコメントに書かれているように違法手チェックを省くと先手が１段目に歩を打つようなことが発生する。旧置換表でもSideビットを保存するように変更すると、置換表を参照するときはクラスタが自分の手番側のものであることが保証されるので落ちなくなる。
　実際に違法手の数をカウントしたところ、ベンチマークコマンドで３回程度発生していたものが発生しなくなる。（歩、香、桂のDropの違法手のみの数）

　この問題は旧置換表だけでなくCounter Moveでも発生する。Counter Moveの場合、ハッシュキーに関係なく盤面だけを見るので、手順前後などで違法手が発生する確率がかなり高い。
　試しにStockfishのbenchコマンドで計測してみたところ、約４割程度は違法手だった。

　Counter MoveでのDropには手番が入っていないので、手番を取り違えるとpseudoLegalを抜けてしまうので違法手を指してしまう。Dropするための要件には「手駒を持っているかどうか」という条件が入っているため、自分だけ持っている駒では発生しないが、終盤になって互いに歩を持っている場合などは頻繁に発生するためpseudoLegalをすり抜ける。

　以下の局面はCounterMoveとして先手が１段目に歩を打ったとして処理される。

　+R7l/2K1+N1+S1s/p1+P2gnpp/6+b2/2+SGG4/3P1+b3/P5+pPP/5+r3/+n1+pk4L w SL2Pgnl6p 160

　KILLER(COUNTERMOVE)によって７１に歩が出現して、さらに移動して６９にいる玉をキャプチャーして発覚した。（実際にはその２，３手前にも先手と後手の金を取り違えてるような気もするが・・・）

　Dropの対策以外も必要そうな気がするが、ひとまずDropの対策を入れたところ落ちなくなった。レーティング的には誤差の範囲でほぼ互角（若干マシになったかもしれないが）

■置換表
　基本的にSidebitは保存したほうが良い。これによって手番が保証されるので、ある程度はpseudoLegalのお世話にならなずに済む。

　置換表の参照回数はNPSの1.2倍程度だった。

　16bit/32bit/48bitの書き換え回数なども調べてみたが、程度の差がある程度で基本的にbitが大きいほどハッシュ衝突的には少ない。ただ、旧置換表48bitと新置換表16bitのほうがキャッシュ参照速度的には１４％ほど新置換表のほうが速く、読む深さに差が出てくるため、強さ的には新置換表のほうが良かった。

　また手を間違えるようなハッシュの衝突が出るのはハッシュサイズが小さい場合ではなく、大きい場合だった。一瞬小さいほうが現象が出やすいのではないかと思っていたが、ある程度大きい方がハッシュキーがぶつかって違法酒が出る確率があがる。（多分256MB以上と以下で確率が結構変わる）。これはよく考えれば当たり前で、ハッシュキーを保存する空間が大きいほど、同値になるハッシュが出てくるので、ぶつかる可能性があがる。

■Counter Move
　上記のようにCounter MoveをいれることでpseudoLegalをすり抜ける違法手が出てきてしまうのであれば、使わなければよいではないかという話もあり、無効化してみると落ちなくなる代わりにすごく弱くなる。
　Counter Moveがあると超高速で読みが深くなるため、勝率的にはかなり差があるように思われる。

■一手詰め判定
　自玉に王手がかかってなくても王手チェックをしてしまうので最後のmateのところで、負け局面で盛大に勝ちを確信するようなことがある。
　表示上はバグなのだが、他の要因がいろいろあってレーティングには直接影響しない。

■やねうら王２０１５に負け越す理由
　バグで落ちる要因はわかったが、落ちなくなったところでレーティングがあがるわけではないので、原因は全然わからなかった。

やねうら王 classic v2.17 にある不具合２個

　新旧置換表どちらでも発生するので探索周りだと思って調べたもの。


・１手詰めをするタイミングが早い
　再現するsfenがあったと思うのだが、どっかいってしまったので、これはあまり自信がない。
　search()の中で置換表の手を参照する前に自玉に王手がかかっているかチェックする必要がある（気がする）
　これのせいで、「詰-1」になったり、自玉が詰んでるのに、相手が詰むとして急に勝ちを宣言する場合がある。

・Counter Moveに違法手が混入する
　これは明らかなバグ
　"+R7l/2K1+N1+S1s/p1+P2gnpp/6+b2/2+SGG4/3P1+b3/P5+pPP/5+r3/+n1+pk4L w SL2Pgnl6p 160"

　この局面を探索すると、７１に先手の歩がいることになってて、しかも元々違法手だからチェックをせずに前に進んでしまい６九にいって、しかも上記局面ではたまたま、そこにいた玉を補足する。
　本当にたまたま玉がとられるアサートに引っかかって発見した。

　なんでcounter moveに違法手が入るかは不明だが、先後の手が入れ替わる可能性がありそうで、そうするとpseudoLegalのコストが跳ね上がるので使わないほうがよさそう。

　そもそも露骨に違法手が混入するのでcounterMove周りはなにかおかしい気がする。

やねうら王 classic 2.15 新旧置換表の調査（未完成）

　明らかなバグは１つ直したが、要因が１つじゃ無さそうなので忘れないようにまとめる。


■前条件

・仕様ソフト
　やねうら王 classic 2.15 NEW_TT（ありなし）

commit c967423d23fe07a695f1de1bf2b4385165d67976
Author: yaneurao 
Date:   Mon Mar 7 11:31:40 2016 +0900

    古い置換表のメモリ確保のバグ修正。

　48bit時に異常に遅くなっていたのが直ったが、確かに直る理由がわからない。（要確認）
　この現象は本当に謎。


■致命的なバグ

・局面ハッシュキーの最下位ビットを消している
　NEW_TTなし（以下OLD_TT）では、１６バイト＊４つのエントリを１クラスタとして管理している。そのため、クラスタの先頭エントリを返すfirst_entry()では、局面のハッシュキーにhashMaskというビットマスクによって下位２ビットを消して４の倍数にしている。

　ところが、局面ハッシュキーの最下位ビットは手番を表現しているため、このマスクによって手番が消されてしまい、後手番が先手番のハッシュ値を書き換えることが起こりうる。これによって後手が８九歩を打つというようなことが発生してしまっていた。

　試しにbenchコマンドでこのような場合が発生するか確認したところ、３局面程度発生した。また、ハッシュキーのビット数があまり関係なく、置換表の大きさが関係していることがわかった。（小さいほど保持されるキーの種類が少ないので発生しづらい）

　置換表のクラスタがどちらかの手番であることが保証されたことにより、position.cppのpseudoLegalあたりで違法手のチェックを省くことができる。また、ハッシュ衝突によって上書きされてしまうことによる精度の低下の影響が少なくなるように思える。

・解決方法
　一番容易な解決方法は、first_entryのkeyを２ビット左にシフトすることである。

 inline TTEntry* TranspositionTable::first_entry(const Key key) const {

   //:  return table + ((uint32_t)key & hashMask);
+  static_assert(ClusterSize == 4,"ClusterSize must be 4");
+  return table + ((uint64_t)(key<<2) & hashMask);

　この修正を入れることで、OLD_TTとNEW_TTの勝率はほぼ５割になることが期待されるのだが、実際は少し負け越している。綺麗に１：２の割合なのでレーティングでいうと１００差ちょい。置換表以外は全く同じなのでこれほど差がでるのは旧置換表がおかしいとしか言いようが無い。

以下気になるところ

・メモリ効率

　クラスタサイズが片や６４バイト、片や３２バイトなのでクラスタインデックスだとNEW_TTのほうが２倍の空間があることになる。だからメモリを倍にしてレーティングが同等になるのではないかという予測も立つ。
＞メモリを倍にしたらレーティングが同等になるか

・置換条件
　上記の修正を入れた場合の差を見てみると、probe時に再配置する場所を決定するかどうかという以外に、store条件がある
　→あまり関係がない。今の探索速度だと置換表サイズが8G/16Gとかあって初めて意味があると思われる。上書き回数などを調べたところ、上書きは１％にも満たない程度の数なので、勝敗にはあまり関係ない

・トン死がひどい
　結構な割合で１０００を超えている状態から頓死する
　これはどっちかの現象ではなく、両方にあるので基本的な部分で何か不具合がありそう。
　これがやねうら王２０１５と対局して全く勝てない理由の可能性はある。
　→当たり。自玉に王手がかかっている場合でも、相手玉に王手が掛けられる場合はそちらを優先してしまうようになっている。探索中の一手詰め判定は王手がかかっていない場合に限定することで、かなりトン死確率が下がり、勝率があがった。（暫定スコア１：０：２ -> ４：１：５）
　新置換表にこれを入れれば相当ではないか。

＜追記＞

・メモリ探索速度
　はるか昔BonanzaのNPSはキャッシュ込み、GPSFISHはキャッシュ無し（do moveのみ）みたいなので、NPSをどう定義したらええんや、みたいなことを書いていたのはLS3600氏だった気がするが、これを直接確認する指標がないので、プログラムにカウンタつけて調べてみた。（ローテク）
　すると、メモリ探索速度が１７％ほどNEW_TTのほうが多かった。しかし、探索時間はほとんど変わらない。この結果が有効かどうかは正直よくわからないが、速度的に速い分有利なのではないかという気はしている。ただ、置換表上は１７％多く読んでるはずなのに探索深さなどが変化がないこと。１秒でDepth20とかかいくので影響がないのかもしれないが、調べてみた方はよい。