(2010.3.24更新)
Daemonshogi の思考エンジンの現在の状況、内部の概要について。
このページは、第20回世界コンピュータ将棋選手権 参加者募集のお知らせ で要求されている「プログラム開発の際に工夫したことをアピールする文書」を兼ねます。2010年3月現在の状況です。
Daemonshogiは、いかなる他の思考エンジン実装も引用、使用しておらず、また他の実装の派生物ではなく、すべて独自に開発しています。
もっとも大きな特徴は、プロジェクトがopenである (開かれている) ことです。世界コンピュータ将棋選手権は、第20回で次のようなルールが加わり、実質的に、将棋ライブラリの使用が全面的に禁止されました。
使用可能ライブラリの使用に関して、いわゆる「分家」の予選通過数が１次予選は４、２次予選は２に制限されました。
思考エンジン (に限りません。) の制作に興味がある方なら誰でもプロジェクトに参加することができます。上記の制限とは無縁です。
Daemonshogiは、思考エンジンだけではなく、GUIも備えた将棋プログラムです。
Daemonshogiは、C++で制作しています。いわゆるスクリプト言語に比べて生産性は低いですが、実行速度を優先しています。
一方で、ループのunrollなど、ソースーコードの読みやすさが犠牲になるような、アルゴリズムの改良ではない高速化には力をいれておらず、できるだけ、単純かつ読みやすいソースコードの維持に努めています。
思考エンジンは、はっきり言って、非常に弱いです。主に、静的評価関数がよくないことによります。
特徴としては、通常探索、詰み・必至探索ともに、最良優先探索で作っています。短い時間で、非常に深くまで読めることがあります。
2010年3月現在、次の機能は備えていません。
特に、静的評価関数の機械学習は、次回 (来年) 以降の課題です。
思考エンジンは、オーソドックスな構造だと思います。だいたい、次の機能に分けられます。
局面は、盤上の駒、持ち駒および手番からなります。
Daemonshogi の局面クラスは、盤面、双方の持ち駒をそれぞれ配列で持つ、非常に単純なものです。
千日手の検出のため、指し手の履歴を保持します。また、同一局面の判定を素早くするため、ハッシュ値 (盤面のみ、持ち駒も含める、の2種類) を持ちます。
手の生成は、合法手すべて、王手のみ、王手の受けのみ、の3種類用意しています。
局面の評価値のキャッシュとして置換表を利用します。
置換表は、局面のハッシュ値をキーとし、評価値を得る map です。
Daemonshogi では、局面のハッシュ値として盤面と手番のみを利用し、持ち駒のみが異なる局面で評価値を共有しています。
あふれた場合は、単純な LRU (Least Recently Used) でエントリを削除します。
局面と良い指し手のペアをあらかじめファイルに保存しておき、対局中に利用します。
Daemonshogiでは、棋譜を持つやり方ではなく、局面をキーとしたmapとしています。局面ごとに複数の指し手を持てるようになっていて、ランダムに選択します。
単純なdf-pn法をベースにしています。
合い駒処理による枝刈り、子ノードの簡単な事前評価による展開順序の修正などを入れています。
TODO: 必至は、単独では探索できるようになっていますが、まだ通常探索には組み込んでいません。
基本的なアイディアは、詰め将棋探索の epoch である df-pn法を通常探索にも使えないか、というものです。置換表を最大限利用しつつ、最良優先探索をおこないます。
限られた時間で非常に深いところまで読める場合があります。
ある局面について、形勢判断をおこないます。
今回は、機械学習はできませんでした。人手でちょぼちょぼ作っています。