ゲーム木は、探索で調べる局面のつながりを木構造として表したものである。 根は現在局面、枝は指し手、ノードは各局面を表す。 コンピュータ将棋では、ミニマックス法やアルファベータ法が、この構造をたどりながら最善手を探す。
ゲーム木では、現在局面を根として、
という形で局面を展開する。
ただし実際の将棋AIでは、同じ局面に別の手順から到達することがある。 このような現象はトランスポジションと呼ばれ、厳密には単純な木というより有向グラフとして扱う方が実態に近い。 それでも説明上は「ゲーム木」と呼ぶことが多い。
将棋は分岐数が大きいため、深く読むほどノード数が急激に増える。 この爆発を抑えるために、手の並べ替え、置換表、静止探索などの工夫が必要になる。
将棋では持ち駒を打つ手もあるため、局面によっては合法手数が非常に多い。 そのため、単純な全幅探索はすぐに計算量の限界へ達する。
手順が違っても同じ局面になることがあり、これを再利用できると探索を大きく節約できる。 このため、実装では置換表とゾブリストハッシュがよく使われる。
千日手や連続王手の千日手のように、局面が繰り返されるケースもある。 そのため、探索木をそのまま木として扱うだけでは不十分で、履歴情報や反復検出が必要になる。
教育用には、木を明示的に持たずに再帰でたどる形が分かりやすい。
struct Node {
Position pos;
int depth;
};
void dfs(const Position& pos, int depth) {
if (depth == 0 || pos.isTerminal()) {
return;
}
for (Move move : generateMoves(pos)) {
Position next = doMove(pos, move);
dfs(next, depth - 1);
}
}実際の将棋AIでは、ノード全体をヒープ上に木として構築するより、 局面を進めて戻す形で深さ優先探索を行うことが多い。