Source of Minimax Tree Optimization

  # Minimax Tree Optimization

Minimax Tree Optimization（MMTO）は、探索木の局面評価を教師として評価関数の重みを学習する考え方である。
将棋AIの文脈では、Bonanza method と強く結び付いた話題である。

## 概要

古典的な[評価関数](/shogi/shogiwiki/search/evaluation-function/)では、
特徴量の重みを人手で調整する必要があった。
MMTO では、

- 探索木の中で得られた値
- あるいは最善手選択の整合性

を用いて、評価関数の重みを学習する。

これにより、人手調整より大規模なパラメータ最適化が可能になる。

## Bonanza method との関係

Bonanza は将棋AIにおける大規模評価学習の転換点として有名であり、
Chessprogramming Wiki でも MMTO と関連づけて説明されている。

Bonanza method の重要性は、

- 強い探索器の出力を教師に使う
- 大量の特徴量重みを自動調整する
- 手作り評価から学習評価への橋渡しになった

点にある。

## 直感的なイメージ

ある局面で探索器が

- 手 A を最善
- 手 B はそれより悪い

と判断したなら、その序列と整合するように評価関数の重みを動かす。

単純化した更新イメージは次のようになる。

```cpp
for (Feature f : bestMoveFeatures) {
    weight[f] += eta;
}
for (Feature f : worseMoveFeatures) {
    weight[f] -= eta;
}
```

もちろん実際の MMTO はもっと体系的で、目的関数や最適化の設計が重要である。

## 将棋AIでの位置づけ

将棋AIでは、

- 人手の評価関数設計
- Bonanza 系の機械学習
- [NNUE](/shogi/shogiwiki/search/nnue/)

という流れがある。

MMTO は、その中で
「探索を活用して評価関数を学習する」
という発想を代表する歴史的に重要な技術である。

## 注意点

- 強い探索器を教師に使うため、計算コストが高い
- 目的関数と探索設定に強く依存する
- 現在の NNUE 学習とは方法がかなり異なるが、歴史的な橋渡しとして重要

## 関連項目

- [評価関数](/shogi/shogiwiki/search/evaluation-function/)
- [ニューラルネットワーク](/shogi/shogiwiki/search/neural-networks/)
- [NNUE](/shogi/shogiwiki/search/nnue/)
- [Bonanza](/shogi/shogiwiki/softs/bonanza/)
- [Kunihito Hoki](/shogi/shogiwiki/kunihito-hoki/)

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

- [Chessprogramming Wiki: Minimax Tree Optimization](https://www.chessprogramming.org/Minimax_Tree_Optimization)
- [arXiv: 1710.10967](https://arxiv.org/abs/1710.10967)
- [やねうら王公式サイト: 機械学習エンジニアのための将棋ai開発入門その2](https://yaneuraou.yaneu.com/2020/05/27/%E6%A9%9F%E6%A2%B0%E5%AD%A6%E7%BF%92%E3%82%A8%E3%83%B3%E3%82%B8%E3%83%8B%E3%82%A2%E3%81%AE%E3%81%9F%E3%82%81%E3%81%AE%E5%B0%86%E6%A3%8Bai%E9%96%8B%E7%99%BA%E5%85%A5%E9%96%80%E3%81%9D%E3%81%AE2/)
Minimax Tree Optimization minimax-tree-optimization
