Minimax Tree Optimization

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

概要

古典的な評価関数では、特徴量の重みを人手で調整する必要があった。 MMTO では、

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

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

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

Bonanza method の重要性は、

点にある。

ある局面で探索器が

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

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

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

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

将棋AIでは、

という流れがある。

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