更新日 : 5/1

・自己紹介
ソフト名 : shogi686
開発者 : @merom686 将棋クエスト(5分)で2級
第2回将棋電王トーナメント後、Twitterのコンピュータ将棋クラスタの盛り上がりが続いていた。
その影響を受けて11月後半から開発を開始。4年前に開発していたプログラムを元にしている。

・定跡と評価関数
開発者自身が将棋クエスト(5分切れ負け)で指した600局あまりの棋譜から生成。
(自分の指し手のみを使っているが、これは対戦相手がいたからこそ生まれた棋譜である)
評価関数は、駒割と2駒関係(回りくどい言い方をすると、KK絶対+KP絶対+PP絶対)をボナンザメソッドで学習。
信頼できない指し手が少数ある場合でも、勾配に応じて小さな値は付くようなペナルティ。
棋譜が少ないので、2駒相対で学習したり、玉から離れるほど価値が低くなる縛りを入れたりしている。
玉を含まない2駒関係で駒同士が離れている場合は値を付けない(0にする)。
駒リストと評価値は差分計算している。

・探索
探索中、同一局面に合流したり持ち駒だけ変わっていたりしたら、できるだけその情報を利用するようにしている。
飛び利きにはRotated Bitboardsを使用。これは十分高速だし、将来のPCではBMI2が使えるはずなので、他の手法は試していない。
手を戻すとき、頻繁に高コストで更新される小さいデータはメモリコピーで戻す。(→Stockfish方式のほうがよさそう？)
打ち歩詰めは、王手されていて合法手がなく前の手が歩打ちであったときに勝ちを返すことで対応。
静止探索は深さ5で、取る手等がなくなったら終了(王手がかかっていたら残り深さに関係なく全ての回避手を読む)。(→リキャプチャーも読むようにした)
高速1手詰めを載せているが、あまり高速でない。(→少し高速化・詰み逃しを減らした)
置換表のエントリは1つ16byte。64bitのハッシュキー(局面と手番)に持ち駒をxorして局面を特定する。
並列化は実装したが、危険なので使わない予定。置換表はlockせずにSSEでアクセスしている(気休めにしかならないか)。
枝刈り手法を中心に、Stockfishの実装を参考にしている。パラメータ(残り深さ3以下なら刈るとか)は多くを真似している。
「負けが確定したらなるべく王手をかけない」というのを実装してみた。(→外した)
しかし、負けを読み切ったなら、角不成などでなりふり構わず勝ちに行ったほうがいい気がする。(→未実装)

・その他、探索で使っている手法
Principal Variation Search
Aspiration Windows
Null Move
Static Exchange Evaluation
Killer Heuristic
History Heuristic
One Reply Extensions
Late Move Reductions (Stockfish式)
Futility Pruning (Stockfish式)
Countermove Heuristic
Mate Killers

・参考にしたURL(主なもの、リンク先の手法を使っているとは限らない)
@merom686/shogi-com
https://twitter.com/merom686/lists/shogi-com

PVS探索 (Principal Variation Search)
http://www32.ocn.ne.jp/~yss/pvs.txt

64bit環境向けBitboard、RBBの提案 - Bonanzaソース完全解析ブログ
http://d.hatena.ne.jp/LS3600/20091225

GHI問題 : へっぽこプログラマのザコ板
http://program2re.exblog.jp/3900512

将棋：ＳＥＥ - スズメレンダラー・クマ将棋の開発日記
http://d.hatena.ne.jp/suzume_r/20110910

【将棋】オーダリングメモ - スズメレンダラー・クマ将棋の開発日記
http://d.hatena.ne.jp/suzume_r/20120226

PinCheck機構つきのMakeMoveの提案 - Bonanzaソース完全解析ブログ
http://d.hatena.ne.jp/LS3600/20091229

置換表に経路に依存する局面のスコアを書き込まない - Bonanzaソース完全解析ブログ
http://d.hatena.ne.jp/LS3600/20111205#p1

chessprogramming - home
https://chessprogramming.wikispaces.com/

局面評価の学習を目指した探索結果の最適制御
http://www.geocities.jp/bonanza_shogi/gpw2006.pdf

分散計算環境における並列パーセプトロンの将棋評価関数への適用
http://www.logos.ic.i.u-tokyo.ac.jp/~ura/papers/IPSJ-GI2014.pdf

(Killerなど)
https://twitter.com/sakurapyon3/status/283947965146611712

Seeing a Capture と MVV-LVA
http://d.hatena.ne.jp/sakurapyon/20120301

Online学習におけるL1正則化
http://www.r.dl.itc.u-tokyo.ac.jp/~oiwa/upload/FOBOS.pdf

広く知られているinsertion sortのコードは駄目すぎる - やねうらお−ノーゲーム・ノーライフ
http://d.hatena.ne.jp/yaneurao/20091126#p1

GPS将棋の発表から得たヒントなど: 「うさぴょん」「ねこにゃ」開発日記
http://usapyon.cocolog-nifty.com/shogi/2009/05/gps-a7ce.html

HiraokaTakuya/apery GitHub
https://github.com/HiraokaTakuya/apery

thread (C++11) - cpprefjp C++日本語リファレンス
http://cpprefjp.github.io/reference/thread.html