KomoringHeights v1.0.0 に対する詳しめのリリースノート。
利用者向け#
解答手順構成の安定性向上#
v0.5.0 の探索部は、大きく分けてMain SearchとPost Searchの2つに分かれていた。Main Searchは、与えられた局面が詰みかどうかを調べる本探索である。一方、Post SearchはMain Searchで見つけた詰み局面のグラフ構造を再探索して双方最善を尽くしたときの詰み手順を構成する探索である。
探索部が2つに分かれていた理由は、Main Searchだけでは自然な詰み手順が構成できないからだった。Main Searchではdf-pnアルゴリズムと呼ばれる詰将棋と相性が良い探索を用いていた。df-pnアルゴリズムは詰みの判定自体は高速なのだが、見つけた手が必ずしも最善手と一致するとは限らない。最善手ではない手をベースに詰み手順を構成すると、人間から見て不自然な手順になってしまう。
そのため、Main Searchの後のPost Searchで経路の再探索を行い、手順の再構成を行っていた。Post SearchはMain Searchと比べてあまり時間がかからず、Main Searchの補助的な位置づけだった。
しかし、Post Searchにより手順を再構成する方法は、稀に手順の構成に失敗するケースがあった。探索失敗の原因はいくつかあり、Post Searchの千日手回避のフローで無限ループに陥ってしまったり、Garbage Collectionにより必要な探索結果が置換表から消されてしまったりなどである。このように、Post Searchを用いる手順は見た目ほど簡単ではなく、詰み手順の構成にはより高度なアルゴリズムが必要だと分かってきた。
そのため、v1.0.0ではMain Search自体を拡張して詰み手順の改良を行うようにした。Main Searchの探索において、「与えられた局面が詰むかどうか」を調べる代わりに、「与えられた局面がM手以下で詰むかどうか」を調べる。これにより、「ちょうどM手で詰むかどうか」を「M手以下で詰む」かつ「M-2手以下では詰まない」により判定できるようになった1。
無駄合検知の削除#
v0.5.0では無駄合を出力手順から消す機能があったが、v1.0.0では削除された。無駄合探索はPost Search内で行っていた機能で、詰将棋の一般的なルールに則り無駄な合駒を手順から消す機能だった。
v0.5.0の無駄合の判定は、さまざまな問題を抱えていた。まず、一般的な詰将棋のルールに沿っておらず、利用者の混乱を招いていた。特に、駒がたくさん余る実戦形の詰将棋では、人間的には不自然な手順を返していた。それに加え、無駄合探索の実現のために、コード的にはだいぶ険しい実装をしていた。このように、v0.5.0の無駄合探索は手間がかかる割に恩恵の少ない機能だった。
それゆえ、v1.0.0では無駄合機能を削除した。合駒が無駄合かどうかは全く考慮されず、無駄合を含めた最短手順を返す挙動に変わった。
なお、この機能削除は今後の無駄合探索の再実装を否定するものではない。今後、正しい詰将棋のルールに沿った無駄合の検出機能を実装を予定している。
開発者向け#
実は、探索方法の変更に伴い、コードをほぼ全て書き直している。それに伴い、Doxygenコメントと単体テストの整備を行った。
Doxygenコメント整備#
全体リファクタリングのついでに、すべての公開インターフェースに最低限のDoxygenコメントを追加した。最新版に対するドキュメントは komoring-heights-docs にて公開している。この公開ドキュメントは本体リポジトリのCIで自動生成している。またローカル環境でも、source/engine/user_engine/tests で make docs を実行することで同様のドキュメントを生成できる。
単体テスト整備#
探索部以外のほぼ全てのコンポーネントに対し、単体テストを追加した。単体テストの追加に伴い、クラスの分割粒度やファイル分割粒度についても見直しを行った。現在、Line Coverageが96%程度、Branch Coerageが91%程度のテストが書かれている。
今後の展望#
まず、盤面の初期評価については大きな改善の余地があると考える。KomoringHeightsの盤面の初期評価は initial_estimation.hpp に集約されている。このファイルには謎のマジックナンバーがいくつか定義されている。実は、この数値を少しいじるだけで詰将棋エンジンの挙動が大きく変わってしまう。このようにとても重要なパラメータであるのだが、あまり真面目に検討ができていない。今後は機械学習により最適値を設定したい。
また、df-pnアルゴリズム以外のアルゴリズムについても試してみたいと考えている。というのも、df-pnアルゴリズムは裸玉局面を極端に苦手としているためである。df-pnは分岐の少ない局面を優先して探索するアルゴリズムである。手数にとらわれず分岐の少ない経路を深く細く読むことができるため、長手数の詰将棋と相性が良い。一方で、裸玉のように王手の選択肢が多い局面の探索には向かない。なぜなら、兄妹局面が無数に存在しており、分岐数だけでは局面の優劣をうまく測れないためである。そのため、裸玉局面に強いアルゴリズムが作れないか試してみたい。
なお、次回のリリース時期については見通しが立っていない。いろいろ余裕ができたら開発を再開したい。
細かい話をすると、「M手以下で詰み」には持ち駒の優等性と同様に半順序関係があり、その優等関係を探索に活用できる。 ↩︎