Source of ゲーム木 - Computer Shogi Wiki

  # ゲーム木

ゲーム木は、[探索](/shogi/shogiwiki/search/)で調べる局面のつながりを木構造として表したものである。
根は現在局面、枝は指し手、ノードは各局面を表す。
コンピュータ将棋では、[ミニマックス法](/shogi/shogiwiki/search/minimax/)や[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)が、この構造をたどりながら最善手を探す。

## 概要

ゲーム木では、現在局面を根として、

- 自分の指し手で1手先の局面へ進む
- 相手の応手でさらに次の局面へ進む
- これを深さぶんだけ繰り返す

という形で局面を展開する。

ただし実際の将棋AIでは、同じ局面に別の手順から到達することがある。
このような現象は[トランスポジション](/shogi/shogiwiki/search/transposition/)と呼ばれ、厳密には単純な木というより有向グラフとして扱う方が実態に近い。
それでも説明上は「ゲーム木」と呼ぶことが多い。

## 主な構成要素

- ルートノード
  現在評価したい局面
- 内部ノード
  まだ先の局面へ展開される途中のノード
- 葉ノード
  終局または探索打ち切り地点
- 枝
  ある局面から次の局面への指し手
- 深さ
  ルートから何手先まで読んだか
- 分岐数
  その局面で候補となる合法手の数

将棋は分岐数が大きいため、深く読むほどノード数が急激に増える。
この爆発を抑えるために、[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)、[置換表](/shogi/shogiwiki/search/transposition-table/)、[静止探索](/shogi/shogiwiki/search/quiescence-search/)などの工夫が必要になる。

## 将棋AIで重要になる点

### 分岐数が大きい

将棋では持ち駒を打つ手もあるため、局面によっては合法手数が非常に多い。
そのため、単純な全幅探索はすぐに計算量の限界へ達する。

### 同一局面への合流がある

手順が違っても同じ局面になることがあり、これを再利用できると探索を大きく節約できる。
このため、実装では[置換表](/shogi/shogiwiki/search/transposition-table/)と[ゾブリストハッシュ](/shogi/shogiwiki/search/zobrist-hashing/)がよく使われる。

### 反復局面を考慮する必要がある

千日手や連続王手の千日手のように、局面が繰り返されるケースもある。
そのため、探索木をそのまま木として扱うだけでは不十分で、履歴情報や反復検出が必要になる。

## 探索アルゴリズムとの関係

- [ミニマックス法](/shogi/shogiwiki/search/minimax/)
  ゲーム木の葉の値を根へ逆伝播させて手を選ぶ基本原理
- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
  読まなくてよい枝を省く
- [negamax](/shogi/shogiwiki/search/negamax/)
  ミニマックス法を実装しやすく書き換えた形
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
  浅い深さから順に木を繰り返し読む

## 実装例

教育用には、木を明示的に持たずに再帰でたどる形が分かりやすい。

```cpp
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では、ノード全体をヒープ上に木として構築するより、
局面を進めて戻す形で[深さ優先探索](/shogi/shogiwiki/search/)を行うことが多い。

## 注意点

- ゲーム木は説明概念として便利だが、実装ではトランスポジションや反復のため木そのものではない
- 将棋では分岐数が大きく、枝刈りなしでは深く読めない
- 木の形だけでなく、どの順で枝を調べるかも性能に大きく効く

## 関連項目

- [探索](/shogi/shogiwiki/search/)
- [ミニマックス法](/shogi/shogiwiki/search/minimax/)
- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [negamax](/shogi/shogiwiki/search/negamax/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)

## 参考にしたホームページ

- [Chessprogramming Wiki: Search](https://www.chessprogramming.org/Search)
- [Chessprogramming Wiki: Search Tree](https://www.chessprogramming.org/Search_Tree)
- [コンピュータ将棋のアルゴリズム HTML版](http://usapyon.game.coocan.jp/ComShogi/index.html)
ゲーム木 search-tree
