Source of 手の並べ替え - Computer Shogi Wiki

  # 手の並べ替え

手の並べ替えは、探索で候補手を調べる順番を工夫する技術である。
[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)は良い手から先に読むほど枝刈りが増えるため、
探索速度を大きく左右する。

## 概要

[ミニマックス法](/shogi/shogiwiki/search/minimax/)では手順の順番は結果に影響しない。
しかし[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)では、
有望な手を先に調べるほど早く `alpha` や `beta` の境界が更新され、
後続の枝を省きやすくなる。

そのため、現代的な将棋AIでは
「どの手を先に読むか」は探索アルゴリズムそのものと同じくらい重要である。

## よく使われる順序

典型的には次のような順に試す。

- 前回反復の Principal Variation 手
- [置換表](/shogi/shogiwiki/search/transposition-table/)に入っている hash move
- 良い駒取り
- 昇格など価値の高い手
- [killer heuristic](/shogi/shogiwiki/search/killer-heuristic/) などの非捕獲手
- その他の手

将棋では、

- 王手
- 駒取り
- 成り
- 受けの手

の扱いがチェスより少し複雑になるが、基本思想は同じである。

## 代表的な材料

### Principal Variation 手

[反復深化](/shogi/shogiwiki/search/iterative-deepening/)の前回反復で最善だった手は、次の反復でも有望であることが多い。

### hash move

[置換表](/shogi/shogiwiki/search/transposition-table/)に保存された最善手は、最も重要な順序情報のひとつである。

### 捕獲手の優先順位

駒取りについては、

- MVV-LVA
- [Static Exchange Evaluation](/shogi/shogiwiki/search/static-exchange-evaluation/)

のような方法で優先順位を付けることが多い。

### 非捕獲手の履歴

- [killer heuristic](/shogi/shogiwiki/search/killer-heuristic/)
- [history heuristic](/shogi/shogiwiki/search/history-heuristic/)
- [countermove heuristic](/shogi/shogiwiki/search/countermove-heuristic/)

などが使われる。

## 実装例

単純化した例では、各手にスコアを付けて高い順に読む。

    int scoreMove(const Move& move, const Position& pos) {
        if (move == hashMove(pos)) return 1000000;
        if (isWinningCapture(move, pos)) return 900000;
        if (isKiller(move)) return 800000;
        return historyScore(move);
    }

    void orderMoves(std::vector<Move>& moves, const Position& pos) {
        std::sort(moves.begin(), moves.end(),
            [&](const Move& a, const Move& b) {
                return scoreMove(a, pos) > scoreMove(b, pos);
            });
    }

実際には全手を完全ソートせず、取り出し時に最大のものを選ぶ形もよく使われる。

## 将棋AIでの位置づけ

手の並べ替えは単独で最善手を決める技術ではないが、
探索効率への影響が非常に大きい。

特に、

- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)

と組み合わせると重要性がさらに増す。

## 注意点

- 良い順序付けができないと、アルファベータ法の利点が大きく落ちる
- 計算コストの高い並べ替えは、節約できるノード数と釣り合う必要がある
- ルート付近と深いノードでは、使う並べ替え手法を変えることも多い

## 関連項目

- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [Static Exchange Evaluation](/shogi/shogiwiki/search/static-exchange-evaluation/)
- [killer heuristic](/shogi/shogiwiki/search/killer-heuristic/)
- [history heuristic](/shogi/shogiwiki/search/history-heuristic/)

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

- [Chessprogramming Wiki: Move Ordering](https://www.chessprogramming.org/Move_Ordering)
- [Chessprogramming Wiki: Search](https://www.chessprogramming.org/Search)
- [コンピュータ将棋のアルゴリズム HTML版](http://usapyon.game.coocan.jp/ComShogi/index.html)
手の並べ替え move-ordering
