オープンソースの詰将棋エンジン「KomoringHeights」を作った
詰将棋エンジン「KomoringHeights」を公開した。
やねうら王ベースのオープンソースの詰将棋エンジンで、df-pnアルゴリズムにより長手数の詰将棋でも短時間で詰みを見つけられる。手元の環境だと、現在最長手数の詰将棋であるミクロコスモス（1525手詰）の詰みを10分程度で読み切ることができる。
ソフトの概要
df-pnアルゴリズムをベースにして、n手詰めルーチンや証明駒／反証駒による探索ノード数の削減を行うことで、現実的な時間内で長手数の詰将棋を解くことができる。指し手生成などの基本的なデータ構造はやねうら王のコードをほぼそのまま使用している。
新たに書いたコード量は1500行弱と短いが、詰将棋探索の基本的な探索手法がすべて凝縮されている。今後、自力で詰将棋エンジンを作ろうとしている人の参考になれば嬉しい1。
細かい技術解説は最近の詰将棋技術の解説記事を参照。
実装にあたってtanuki-詰め2やdlshogiのdf-pnエンジン3、やねうら王の詰将棋エンジン4を大いに参考にしている5。
また、作成したエンジンの動作チェックにはやねうらお氏作成の詰将棋500万問を使用している6 7。
よくありそうなQA
Q. なんでこれを作ったんですか？
A. 現実的な時間、メモリサイズでミクロコスモスが解けるソフトを自分の手で作ってみたいと思ったから。オープンソースの詰将棋エンジンを探してみたが、既存のエンジンはほとんどが実戦特化型で、超長手数の詰将棋には向かない実装になっていた。長手数の詰将棋エンジンの理論自体は20年以上前からほとんど変わっていないので、自分でも作ってみたいと思い実装した8
9。
Q. 脊尾詰10の3倍ぐらい遅いのはどうしてですか？
A. これは僕の技術力不足が原因である。
探索速度についてはKomoringHeightsはやねうら王ベースのため、指し手生成速度は現在のコンピュータ将棋の中でも最速に近いはずである。しかし、詰将棋探索部の実装方法の工夫が不足しているためか、npsが想定ほど出ていない。現在のKomoringHeights実装では、実行時間の45%が置換表のLookUpに充てられているようだ。
KomoringHeightsはあくまで長手数の詰将棋が解ける実装の一例を提供することが目的なので、本将棋AIのような1%単位の高速化にはあまりこだわっていない。そのため、脊尾詰よりも高速に探索できるようにするモチベーションは今のところはない11。
Q. 脊尾詰は256MBでミクロコスモスを解けるのに、KomoringHeightsは1GB以上必要なのはなぜですか？
A. 効率的なGarbage Collection（GC）を実装していないことが原因である。なぜ実装していないかというと、なくても長手数詰将棋を解けてしまうためである。
Q. 詰み手順に無駄合が含まれていて美しくないのはなんとかならないですか？
Q. 余詰検索機能はないんですか？
A. 無駄合や余詰の検知は判定がかなり複雑なので、KomoringHeightsでは一切考慮していない。そのため、これらの用途で詰将棋エンジンを使いたい場合は脊尾詰を使うのがおすすめである。
Q. スレッド数を2以上にしても探索が並列化されないようですが、今後並列化を実装する予定はありますか？
A. 並列化の予定は今のところはない。
並列化をするためにはかなりの大改造が必要になるが、今の実装で解けない問題が解けるようになる改造ではない（n並列化ならシングルスレッドでもn倍の時間をかければ解ける）のであまり気が進まないというのが現状である。
Q. なんで「KomoringHeights」って名前なんですか？
A. 気づいたときにはこの名前になっていた。響きだけで決めているので深い理由はない。
notes
- 1500行の割にはコーディングやデバッグ作業にかなり手こずった。感覚的には6000行ぐらい書いた気分である
- YaneuraOu/tanuki-mate-search.cpp at master · yaneurao/YaneuraOu
- TadaoYamaoka/DeepLearningShogi
- YaneuraOu/yaneuraou-mate-search.cpp at master · yaneurao/YaneuraOu
- やねうら王の詰将棋探索を眺めているときにバグを見つけ、人生初めて将棋ソフトのPull Requestを出した。（– df-pnのsecond_pn,second_dnの計算が正しくない問題を修正 by komori-n · Pull Request #176 · yaneurao/YaneuraOu）将棋ソフトへのcontributionがプログラミングを始めたときからの一つの目標だったので、個人的にはこれは非常に嬉しかった。
- やねうら王公式からクリスマスプレゼントに詰将棋500万問を謹呈 | やねうら王 公式サイト
- 11手詰100万問問題集のおかげでバグを19個見つけることができた
- はじめはローカル環境でサクッと作って個人的に楽しんで終わりにしようと考えていたが、実装してみたら異常に大変だったので公開することにした
- なお、GPSshogi はdf-pnアルゴリズムを完璧に（証明駒やヒューリスティックな枝刈りを含んだ状態で）実装されているらしいが、現代はやねうら王全盛期のためやねうら王ベースでの実装にこだわった
- 脊尾詰ダウンロード
- 実は、アルゴリズム面で1つ大きな妥協している点がある。それは、末端局面のpn/dnを1/1固定にしている点だ。局面の詰みやすさをヒューリスティックに求めてpn/dnの初期値を変えるアルゴリズム（df-pn+, やねうら詰め方式）を採用することで探索局面数の削減が見込める。しかし、これを採用するとデバッグがしづらくなったり、パラメータの少しの調整で探索時間が大きく変動したりしてとても疲れるので採用を取りやめた。解図速度は間違いなく向上するので、気が向いたら実装してみようと思う。