Qhapaq Lab

Static Exchange Evaluation

Static Exchange Evaluation（SEE）は、ある升で駒の取り合いが続いたとき、最終的な損得がどうなりそうかを静的に見積もる手法である。 静止探索や手の並べ替えでよく使われる。

概要

駒取りの手があるとき、

  • 本当に得な取りなのか
  • すぐ取り返されて損なのか

を判断したい場面が多い。

SEE では、ある升に対して

  1. 最も安い駒から順に取り返すと仮定する
  2. 駒得の増減を交互に並べる
  3. 最適応手を前提に後ろから畳み込む

ことで、その取りの損得を近似的に求める。

何に使うか

実装例

単純化した擬似コードは次のようになる。

int see(Position pos, Square sq) {
    int gain[MAX_SWAP];
    int depth = 0;

    gain[depth] = pieceValue(pos.pieceOn(sq));

    while (hasAttacker(pos, sq, pos.sideToMove())) {
        Move capture = leastValuableAttacker(pos, sq, pos.sideToMove());
        doMove(pos, capture);
        ++depth;
        gain[depth] = pieceValue(capturedPiece(capture)) - gain[depth - 1];
    }

    while (--depth > 0) {
        gain[depth - 1] = -std::max(-gain[depth - 1], gain[depth]);
    }

    return gain[0];
}

実際には pin や成り、将棋特有の利きの更新も考える必要がある。

将棋AIでの位置づけ

将棋では、

  • 大駒の取り合い
  • 歩や香の安い駒からの取り返し
  • 成りを伴う取り

が多く、単純な 駒を取る手だから良い という判断では不十分である。 そのため SEE は、特に捕獲手の品質管理に役立つ。

注意点

  • SEE は戦術探索そのものではないので、王手や詰み筋は扱えない
  • pin や X 線の利きを正しく扱う必要がある
  • 将棋では持ち駒化や成りの扱いがチェスより少し複雑になる

関連項目

参考にしたホームページ