思考エンジンの概要

Daemonshogi の思考エンジンの現在の状況、内部の概要について。

このページは、第20回世界コンピュータ将棋選手権参加者募集のお知らせで要求されている「プログラム開発の際に工夫したことをアピールする文書」を兼ねます。

概要

Daemonshogiは、いかなる他の思考エンジン実装も引用、使用しておらず、また他の実装の派生物ではなく、すべて独自に開発しています。

もっとも大きな特徴は、プロジェクトがopenである (開かれている) ことです。世界コンピュータ将棋選手権は、第20回で次のようなルールが加わり、実質的に、将棋ライブラリの使用が全面的に禁止されました。

使用可能ライブラリの使用に関して、いわゆる「分家」の予選通過数が１次予選は４、２次予選は２に制限されました。

思考エンジン (に限りません。) の制作に興味がある方なら誰でもプロジェクトに参加することができます。上記の制限とは無縁です。

Daemonshogiは、今のところ高速化には力をいれておらず、単純かつ読みやすいソースコードになっています。

通常探索、詰み・必至探索ともに、最良優先探索で作っています。

TODO: 評価関数を作り直した後に書く

次のクラス (構造体) または機能を持ちます.

局面は、盤上の駒、持ち駒および手番からなります。

Daemonshogi の局面クラスは、盤面、持ち駒をそれぞれ配列で持つ、非常に単純なものです。千日手の検出のため、指し手の履歴を保持します。

手の生成は、合法手すべて、王手のみ、王手の受けのみ、の3種類用意しています。

局面の評価値のキャッシュとして置換表を利用します。

置換表は、局面のハッシュ値をキーとし、評価値を得る map です。

Daemonshogi では、局面のハッシュ値として盤面と手番のみを利用し、持ち駒のみが異なる局面で評価値を共有しています。

あふれた場合は、単純な LRU (Least Recently Used) でエントリを削除します。

局面ごとに指し手をファイルに保存しておき、対局中に利用します。

局面ごとに複数の指し手を持てるようになっていて、ランダムに選択します。

単純な df-pn法をベースにしています。

合い駒処理による枝刈り、子ノードの簡単な事前評価による展開順序の修正などを入れています。

TODO: 必至はまだ通常探索に組み込んでいない

基本的なアイディアは、詰め将棋探索の epoch である df-pn法を通常探索にも使えないか、というものです。置換表を最大限利用しつつ、最良優先探索をおこないます。

限られた時間で非常に深いところまで読める場合があります。

TODO: 作り直してから書く