shogi686は、僕（ハンドルネーム：merom686）が開発した将棋ソフトである。
探索
そういえば、どこまでが探索なのか知らない。指し手生成は探索に含まれるだろうか。まあ、大きく機械学習以外ってことで。
search()
まず、search関数について。Aperyを参考に、なるべく工夫をせずに書いた。通常探索と静止探索を同じ関数にしたりして、見た目は全然違うけど、やってることはほぼApery（WCSC25）と同じはず。ただし、時間がかかると思ったので並列化はしていない。選手権のときは、高速1手詰めで詰んだとき置換表に書くスコアが間違っていた（と思う）。
工夫（強くなったとは言っていない）した点は、詰めろ回避を王手と同様に延長するようにしたこと。Null Moveで負けになれば詰めろとわかるし、その局面で読んだ手の2/3以上が負けなら詰めろと推測できる。特定局面では強くなった。
Aperyはcounterやfollowupを入れていないようだが、まあ、入れてみた。あとmate killerも入れたが、駒損する取る手のみ登録し、兄弟ノードが詰んだときだけ読むようにしている。通常のkillerでは駒損する取る手を救済できない。
置換表でカットするのは普通にNonPVのみ。何か信頼できるとしてPVで使ってもわずかに遅くなるだけのような。謎。まあPVは少ないからな。高速1手詰めは、PVでは置換表のエントリがあったときでも読み直している。それがまあまあ許容できるくらいPVは少ない。
王手（詰めろ回避）延長は、0.5手（1手だと遅くなる局面がある）。SEEが1以上のときのみ延長している（普通は0以上だけど、うーん）。こういうとこ変えたくなっちゃうのは何なんだろうね。
その他search.cpp内
fail-highなどは、将棋所以外でも動作するようにinfo stringで送っている（動作確認はしていない）。あまりたくさん表示させると少し遅くなるんだけど、まあきれいだしいいか。デフォルトではたくさん表示しないようにしている。本番では、ログを見たいこともあると思い、わずかの速度低下と引き換えにたくさん表示させた。
perftは指し手生成のデバッグにとても役立った。
置換表
並列化したときのために、128bitまとめて読み書きするようにしている。さすがに最近のCPUならアトミックだと思ったんだけど、ダメかな。
高速1手詰め
高速1手詰めは、まず玉周辺の利きを取得している。玉周辺への利きを持つ駒の利きだけを取得することで高速化している。例えば玉の逃げ場所が5か所あるのに銀を打って詰むということはないので、逃げ場所をpopcntして省いている。王手となりうる移動元のBitboardから王手を試し、逃げ場所がなくなれば詰む可能性がある。こうして詰み候補の条件を絞ることで、ここから先はそこそこ重い処理をしてもいいことになる。
だから、最初に利きを取得した。詰みそうなときはpinを見ているので、近接王手の1手詰みはかなりカバーできるようになった。速度的にも、短いコードで十分なものができたと思う（工夫の余地はある）。
王手判定・自殺手判定
選手権のときから思っていたのだが、Stockfish式にpin情報を取得していると遅くなるような気がする。pinの処理を自分がちゃんと書けてない可能性もあるけど。簡単な方法としては、attackersTo()でその都度玉への利きを得るというのがある。これも、AperyのattackersTo()は思ったより高速だったので、普通に実用レベルだ。
今回のshogi686では、指し手毎にpinを見ている。別にまとめてpinnerを取得しなくてもいいわけで。簡単だし速いしpin処理は高速1手詰めなどでも流用できるし、いいことづくめだと思っている（穴があったらすみません）。
局面のデータ構造
金と同じ動きをするBitboardはまとめて持っている。データも小さくなるし、少し速くなった。
持ち駒は1byte*7で64bitに収まり、そのままxorすれば持ち駒のハッシュを持たなくて済む。何より、ビットレイアウトをテーブル引きしなくていいというのが速度に貢献する。優越関係もわかる。持ち駒だけが異なる局面で、置換表の保存場所が被る可能性が高くなるが、特に対策していない（PEXTとかで何とかなるんじゃないかと）。
SEEも、けっこう速くなったと思う（遅かったらすんません）。
局面は深さ毎に場所が決まっていて、Stockfishで言うとSearchStackに全てを入れている感じ。よってundoMove()は必要ない。メモリコピーは必要になるが、最近のCPUならちまちま更新するより遥かに速いので、どちらにしろundoMove()は必要ない（升にある駒を入れておく81byteの配列が含まれるから以前は躊躇していた）。
現在の局面やRootからの手順を、SFENで出力するデバッグ用の関数を持っている。当たり前だけどこういうのを後回しにしてはいけない。まずこういうのを書いてから開発を始めるべきだ（自戒）。
手生成
手生成のときにSEEやHistoryを計算して指し手の上位に入れている（SEEはシフトして9bitに収めている）。ソートが楽になり、少し高速化したはず（単純なケースでしか測定していない）。
（11/27追記）上でSEEと書いていたのはMVV-LVAの間違いでした。
成れるかどうかで分けて生成すると、1bitくらいしか立っていないBitboardを何回も舐めることになるからか、遅くなった（いいやり方を知らないだけかも）。なのでもうループの内側で敵陣かどうかを判定して、成る手を生成している。これはもちろん、敵陣判定と行きどころのない駒判定が高速であることに支えられている。僕が縦型Bitboardを知っても移行しないのはこのためだ（横型なら定数との比較で済む）（縦型のメリットもあるので悩ましい）。
王手回避は、合駒とそれ以外を分けて生成している。取る手や玉が動く手はSEEで並べ替え。合駒は味方の利きのある場所へ玉に近いところから、同じく利きのない場所へ。ここはソートなし。
オーダリングを安定ソートにすることで、手生成の順番に意味を持たせ、高速にそこそこのオーダリングができないかと考えていたが、何もやっていない。
Stockfish式なので、不成も含め合法手を漏らさず生成できるようにしている。普段は角不成などは読まない（打ち歩詰めに関する不成の機能は、勝率が下がると思い外してしまった）。
評価関数
オーソドックスな3駒関係（手番なし利きなし）。玉が移動したときの差分計算もしている。玉が移動しないときの差分計算は、駒の移動をまとめてやっている（取る手なら2回、それ以外は1回の処理）。まとめてやっているせいか、同一PのKPPは飛ばしたほうが少し速かった（気がする）。ぎゃざー使いたいよお。
Bitboardは横型だが、次元下げを簡単にするため行きどころのない駒の節約をしていない（速度的にもわずかに遅くなったと思う（ただ、tanuki-のパディングを考えるとたまたまかもしれない））。
駒（▲78金など）のインデックスを得るのに、テーブルを使わず直接計算することも試したが、速くならなかった。先後反転や左右反転のテーブルを持っている（学習用だったかな）。
評価関数が左右対称か、駒リストが正常かを確認する関数を持っている。
置換表に静的評価値を入れていない。選手権のときは必要性がわからなかったからだが、なるほど少し速くなるかもなあと思ったので後で試したい。
駒割はテキストファイルで持っているので、閲覧や編集が簡単にできる。
評価ベクトルをそのまま保存すると巨大なので、対称性を使って1/4強に可逆圧縮（5筋はそのままなのでわりと手抜き）して保存している。これは配布を考えてのことだが、学習がすごくやりやすくなったので、やってよかったと思う。
学習
floodgateの棋譜のうち、棋譜の中にレーティングが書かれるようになった2015年2月（だったかな？）以降のものを使った。R3000以上を含む対局で、勝った側の指し手のみを使っている（定跡も大体そういう感じ）（会場ではR3000以上に勝った指し手と言ってしまった気がする、すみません）。73万局面程度。棋譜の数にすると1万も行かないので、3駒関係の学習には足りない。しかし、2駒関係よりは強くなると（勝手に）判断して普通の3駒関係を選んだ。経験を積みたかったというのもある。
（性格的に）短時間で学習させたいので、次元下げをまとめてやる方法を考えた（結果的にはダメだった）。具体的には、例えばKPP相対なら、該当するKPPの平均からKPP相対の値を求め、その値を基準にペナルティをかけるようにした。KPP相対の更新は、該当するKPP全体に変動幅を足した（これはもっとダメだったので最終的に外した）（KPPはでかいし一列37要素だしで薄く足すのが無理）。
基本的にはボナンザメソッドを使うつもりだった。慣性項など、選手権のときの数々の（高速化のための）工夫を実装する時間がなく困っていたが、やねうら王のブログでSGDやASGDという単語を知り、よくわからないけどそれっぽいものを「自分で考えて（これは弱くなる原因になる）」実装した。勾配を計算するとき、単に前回の勾配の0.94倍を足すだけ。絶対やり方違うけど、こうするしかなかったんや。
1回に5000局面を使い、深さ2で探索する。反復深化のように深さ1の探索も行い、深さ1と深さ2のスコアが近くなるようにもした。初期の実験では、深さ1を深さ2に近づけるよりも、深さ1と深さ2が歩み寄ったほうが滑らかな値が付いた。それで今は歩み寄るようにしているが、学習部のバグのせいかもしれない。また、前日の準備からは深さ2と深さ3で学習させた。
ここはシグモイド関数が使えない（スコアが同じなら動かす必要がない）ので困っていたが、x - log(x + 1.f) という式で計算される関数を使うことで落ち着いた（何かそれっぽいのを考えて、そこから次数を下げたというか）。
慣性項を実装せずに少しでも早く収束させたかったので、変動幅は勾配の対数みたいなのにした（これも次元下げとは相性が悪そうだ）。
玉から離れるほど価値が下がる縛りも入れてみたが、これはどうも強くならず、選手権のときの実装から致命的なミスがあったことがわかった。KPの値を一方的に下げちゃイカんよねっていう（あるKPを下げたら隣のKPを上げればよかったのかなあ）。よってこの機能は外した。ただし、KPでPが敵陣にあるときの価値があまり低くない（そこには大抵相手玉がいるから）というのは、学習の精度を上げようと思ったら絶対に避けるべきだと（間違っている可能性は高いけど今の自分は）思っているので、今後代替案を考えたい。
1回90秒（うち探索は60秒で、あとの30秒は勾配の次元下げ）で回るので、大きい値もそこそこの時間で付く。出てきた評価ベクトルは非常に弱いものだったが、とりあえず短時間で学習することはできた（それ意味あるんか）。
ここからはひたすらバグと戦っていた。間際に学習を書いたので、じっくり考えることができない。考えないプログラミングは楽しくないし結果も出ない。それでも、バグはアルゴリズムレベルでだけ存在し実装は完璧だと信じ、できるだけ棋力が上がるような妥協の仕方を考えた。最終的には次元下げを少し外して変動幅1で一晩回し、当初の理想よりは劣るが強い評価関数を作ることができた（Bonanza6.0には何回かやって1勝もできなかったので、1日目は悲観していた）。
あと、持ち駒の次元下げもやっている。ここで、持ち駒を"H"で表すこととする。KKPのうちKKHは玉の位置を使わず持ち駒の価値専用とし、単にそのHの値を入れている。持ち駒は多いほど最後の1枚の価値が下がるというやや乱暴な縛りも入れている（これは総和を変えないようにちゃんとやっている）。それ以外の持ち駒に関する評価は、KHP相対のみとした。
駒割は選手権のときと同じような感じだが、あまり最善の方法という感じがしない。
KPPが巨大すぎて嫌気がさした。次は、2駒+玉周辺の利きなどの小さいものを試してみたい。
