KFEndはC++で書かれているので、C++のコードを使用してデータ構造を記述する。なお、以下に示すコードはKFEndに使用されているコードそのものではなく、説明の便宜のために一部を省略している。
struct CKoma {
Int16 ID, kind, owner, pos, nari; // ID番号, 駒の種類, 所有者(先手|後手), 位置, 状態(生|成),
CKoma *next, *pre; // リストにおける次の駒, 前の駒
}
CKoma board_head[2], mochigoma_head[2][7+1]; // [先手|後手] [駒の種類]
CKomaは各駒の情報を保持する構造体である。そのメンバ、ID, kind, owner, pos, nariは上のコードリストのコメントにあるような意味で、将棋のルール上の情報である。next, preはその駒が属するリストのための双方向リンクである。これは資料[1]吉川に書かれている「高速将棋盤」を参考にしている。リストには、先手盤上、後手盤上、先手持ち駒、後手持ち駒の4種類があり、持ち駒リストはさらに駒の種類ごとに別れている。これらのリストヘッドがboard_head[]とmochigoma_head[][]である。全ての駒はいずれかひとつのリストに属している。局面を進める（戻す）操作を行うとき、駒を打ったり、取ったりする場合にリストを付け替える。双方向リンクになっていることでリストからの削除が簡単に行なえる。このリストは、盤上の駒に対してループで処理を行うときに便利だ。例えば、ある局面で手を生成するとき、移動手は各駒ごとに生成するし、静的評価関数では、各駒ごとに玉からの相対位置や利きの具合で点を付けている。他にも盤上の駒に対してループで処理することは数多くある。また、盤上リストに駒を追加するとき、飛び利きのある駒（飛竜角馬香）はリストの後ろに、その他の駒は前に付けるようにしている（図1）。
こうしておくと、リストを後ろからスキャンすることによって、飛び利きのある駒だけに対してループ処理を行うことが効率的にでき、盤上の大駒を探すときも速く見つけられる。
CKoma *board[221]; // [位置]
CKomaへのポインタの1次元配列として定義する。board[]にアクセスするためのインデックスをzとすると、通常の将棋の記法でのますの位置{x, y}との関係は、z = 17 * x - y + 30となる。これを図示すると図2のようになる。
図2で四角で囲ったところが盤内で、その他は盤外である。盤外のますにはそれを表わす特別なポインタ（OBとする）を入れておく。盤を9×9より1周りか2周り大きくしておくことは一般的に行われる。こうすると、位置zが盤内にあるかをチェックするのに、board[z]!=OBを評価すれば良く、直接zのレンジチェックをしなくて済む。また、利き数を保持しておくためのboard[]と同じ型の変数を更新するとき、盤の端を特別扱いしなくて良い。上のコードリストでは図2に示すように左右にそれぞれ4つOB領域を設けているが、これは位置z1と位置z2の相対位置をz2-z1と表わすことを可能にするためである。例をあげて説明しよう。図3はOB領域が2つの場合である。
AからのBの相対位置をA->Bと書くことにする。図3において、A->BとC->Dは同一である。また、Bz-Az=48-68=-20、Dz-Cz=49-69=-20となり両者のzの差は同じになる。ところが、E->FはA->Bとは異なるのに、Fz-Ez=80-100=-20とzの差がBz-Azと同一になる。これではzの差が相対位置とみなせないことになる。本来、EからA->Bと同一となる相対位置は破線で示すような盤外の位置である。したがって、左右のOB領域を増やすことでこの矛盾を解決できる。左右にそれぞれ4つOB領域を作れば、盤内から盤内への全ての相対位置はユニークなzの差で表わすことができる。
図4においては、Bz-Az=62-90=-28、Dz-Cz=63-91=-28、EからA->Bと同一となる相対位置は、Ez+(Bz-Az)=130+(-28)=102で盤外になる。 相対位置は多くのところで使用されるので、これが1つの整数として表わされると、ソースコードが簡潔になり実行速度も向上する。
例をあげて説明しよう。静的評価関数で、各駒は玉からの相対位置によって点を与えられる。盤上の相対位置は全部で17*17=289通りあるので
SCORE position_table[289];
という1次元配列を定義して、これに各相対位置に対する点（SCORE）を設定しておく。玉の位置をgzとすると、位置zにある駒の点は、position_table[144 + z - gz]と簡単に計算できる。
struct CSST {
Int8 srcN1, srcN2, toriN; // 移動前, 移動後, 取った駒の状態(生|成)
Uint8 srcP, dstP; // 移動元ますの位置、移動先ますの位置
CKoma *srcK, *toriK; // 移動する駒へのポインタ, 取った駒へのポインタ
CSST *link1, *link2; // 深さ方向の次の手へのポインタ、横の手へのポインタ
Int16 key; // ソート用のキー
}
指し手は上のコードリストの構造体CSSTで表わされる。メンバsrcN1からtoriKまでは、局面を進めることと戻すことができるのに十分な将棋のルール上の情報である。link1以下のメンバは、CSSTをソートすること、及び、CSSTでツリーを構成することのためのものである。link1、あるいはlink2を使って手のリストを作り、keyにソートキーを設定してソートを行う。手をソートするのは、探索において見込みのある手から先に展開することで探索の効率を上げるためである。これは一般的に行われる。また、link1, link2と2つのリンクによって、図5の例のように任意のツリーが構成できる。
手のツリーが必要なのは以下のようなことを行うためである。詰ルーチンと必至ルーチンにおいて、解手順はツリーとして得られる。変化同手数の解手順があるときその全ての解手順を得るためには、解はツリーとして表現されなければならない。また、探索する前にツリーを与えて、それを手繰るようにツリー上の手を優先して展開して探索することを行う。これは反復深化を行うときや、水平線効果対策のための再探索のときなどに用いている。さらに、手のツリーを利用する重要な操作として、ABC探索(Alpha-Beta-Conspiracy Search)で用いる共謀深さ(Conspiracy Depth)を計算することがある。ABC探索はKFEndの基本をなす重要な概念であり、これについては改めて詳しく述べたい。
将棋のルールを実現する上では特に必要ではないが、局面を指し手によって進めたり戻したりするとき同時に更新しておくことで、プログラムが単純になったり実行効率が上がる情報がある。KFEndでは以下の情報を更新している。
駒の損得の評価点以下は静的評価関数で使用する。利き数以外の項目は簡単に更新できる。利き数は更新するルーチンが面倒になるが、様々なルーチンで頻繁に利用されるので、高速化のためには不可欠だろう。近接利きと飛び利きをそれぞれ別の変数に記録している。こうすると更新が楽になる。また、各ますの飛び利きの方向をビットに対応させて記録している。飛び利きの方向がわかると、その利きを作った駒を見つけやすくなる。
KFEndのデータ構造の第一の特徴は、盤のOB領域を広く取ることによって、相対位置を位置の差で表わせるようにしていることだろう。また、指し手に2つのリンクを設けてツリーを構成することを可能にし、探索中、頻繁に手のツリーを操作していることも珍しいかもしれない。その他は資料[1]吉川をかなり参考にしている。
効率化のため将棋ルール以外の情報を局面操作に伴って更新することは、あまり熱心にやっていない。手間をかけているのは利き数の更新だけだが、これも最低限のものだけだ。資料[2]山下では、駒交換を考慮した「間接利き」や利いている駒のIDを保持している。静的評価関数と関係するが、一般的に言ってこれらの情報を持つことは検討に値すると思う。KFEndの場合は判断に迷うところだ。
(2000.8.12)