minimax法の系列が良く分かってなかったので調べて整理した。 minimax自体は分かるのだが、その派生が多すぎて混乱があったため。

この手の話の最大手はChess Programming Wikiに見えるのでlinkはこれに向けて貼った。 適切な教科書があればそれを出典としたいのだが、そのようなものを知らないためわざわざ自分で調べているため、できない。誰か良い本を紹介してほしい。

  • minimax法
    • ゲーム木探索法。損失の最大値を最小化。お互いに最適に動くと仮定して最適値を全探索。
    • 対象とするゲームは二人零和交互ゲーム。その他の性質は基本的に要求しない。
    • 以下は基本的に全てminimax法の高速化である。
  • negamax法
    • minimax法の実装手法。手番ごとに正負をひっくり返すことで実装の共通化をする。
    • 追加で対称ゲームでもある必要がある。
    • 以下で名前にprefixとして “nega” を持つalgorithmはすべてこれと同様の派生である。
  • alpha-beta法
    • minimax法を改良したalgorithm。分枝限定法を導入したもの。
    • 最大化したい側と最小化したい側が両方存在する分枝限定法なので下限alphaと上限betaを持つ。alphaとbetaの作る区間を探索窓と呼ぶ。
  • negaalpha法
    • alpha-beta法の実装手法。negamax法と同様の修正をする。
    • 検索しても日本語の資料ばかりでてくる。alpha-beta法の記事中にNegamax Frameworkという形での言及ならある。
  • null window search
    • alpha-beta法を利用した技法。探索窓の幅を0にしてalpha-beta法をすると、区間内に値がないので範囲外の値が返ることがあるが、探索窓の位置より真の値が上か下かは分かるというもの。探索窓の幅が広い場合より当然高速。
    • zero-window searchなど名前に揺れがある。
  • negaC*
    • minimax法と同じ結果を得るalgorithm。null window search を用いて二分探索をするもの。
    • 元々は単に C* というのがあり、negamaxの風味を加えたものが negaC* である。
  • fail-soft
    • alpha-beta法に加える修正。子を試した結果が探索窓の範囲外だった場合に、窓の境界値でなく実際に出てきた値を返すようにする。
  • negascout
    • alpha-beta法を改良したalgorithm。
    • 遷移を評価が良さそうな順に並べ、最も良さそうなものについて探索して結果を得て、残りについてはzero-window searchをしてその結果より悪いことを確認する。 確認の結果より良い遷移があればその遷移を元の探索窓で再度探索し修正をする。
    • knapsack問題を分枝限定法で解くときは「大きい方から試していく」「線形緩和解を上限とする」のが普通だが、これと似たものと思えばよさそう。
    • principal variation search とは厳密には違うらしい。英Wikipediaでは実質的に同義として書いてる。もしかしたら上の文章も逆になってたりするかも。
    • 元々は単に scout という名前で導入され、negamaxによって拡張され negascout となった。
  • MTD-f
    • minimax法と同じ結果を得るalgorithm。minimax法の推定値を使ってzero-window searchをすることを繰り返す。
    • 推定値が正しければzero-window searchでその値は不変。そうでなければもとの推定値より真の値に近い値が得られるのでこれで推定値を修正。
    • 反復法のひとつ。Newton法を思い出せばよい。

なお minimax theorem は同時ゲームについての双対定理なので別物。