期待ミニマックス

期待ミニマックス

クラス	検索アルゴリズム
最悪の場合の パフォーマンス	${\displaystyle {\mathcal {O}}(b^{m}n^{m})}$、ここで異なるサイコロ投げの数${\displaystyle n}$
最高の パフォーマンス	${\displaystyle {\mathcal {O}}(b^{m})}$全てのサイコロの投げ方が事前に分かっている場合

期待ミニマックスアルゴリズムは、ミニマックスアルゴリズムのバリエーションであり、バックギャモンなどの2人用ゼロサムゲームをプレイする人工知能システムで使用されます。バックギャモンでは、結果はプレーヤーのスキルとサイコロを振るなどの偶然の要素の組み合わせによって決まります。従来のミニマックスツリーの「最小」ノードと「最大」ノードに加えて、このバリアントには「偶然」（「自然による動き」）ノードがあり、ランダムなイベントの発生の期待値を取得します。 ^[1]ゲーム理論の用語では、期待ミニマックスツリーは、完全だが不完全な情報の拡張形式ゲームのゲームツリーです。

従来のミニマックス法では、ツリーの深さの限界に達するまで、ツリーのレベルは最大から最小へと交互に変化します。期待ミニマックスツリーでは、「チャンス」ノードが最大ノードと最小ノードと交互に配置されます。チャンスノードは、子ノードの効用値の最大値または最小値を取る代わりに、加重平均を取り、その重みは子ノードに到達する確率になります。^[1]

インターリーブはゲームによって異なります。ゲームの各「ターン」は、「最大」ノード（AIプレイヤーのターンを表す）、「最小」ノード（潜在的に最適な対戦相手のターンを表す）、または「チャンス」ノード（ランダムな効果またはプレイヤーを表す）として評価されます。^[1]

たとえば、各ラウンドがサイコロを1回投げるゲームで、最初にAIプレイヤーが決定を下し、次に別の賢い対戦相手が決定を下すとします。このゲームでは、ノードの順序は「チャンス」、「最大」、「最小」の順に交互になります。^[1]

期待ミニマックスアルゴリズムはミニマックスアルゴリズムの変形であり、 1966年にドナルド・ミチーによって最初に提案されました。^[2] その疑似コードを以下に示します。

関数expectiminimax(node, depth)
    ノードが終端ノードまたはdepth = 0
        の場合、敵がノードでプレイする場合のノードのヒューリスティック値
    を返します。
        // 最小値の子ノードの値を返す
        ノードの子ごとにα:=+∞
        とする
            α := min(α, expectiminimax(child, depth-1))
    そうでなければ、ノードでプレイすることになります
        // 最大値を持つ子ノードの値を返す
        ノードの子ごとにα:=-∞
        とする
            α := max(α, expectiminimax(child, depth-1))
    それ以外の場合、ノードでランダムイベントが発生する
        // すべての子ノードの値の加重平均を返す
        ノードの子ごとにα:=0
        とする
            α := α + (確率[子] × 期待ミニマックス(子、深さ-1))
    α
を返す

ランダム ノードの場合、各子に到達する確率が既知である必要があります。(ほとんどのチャンス ゲームでは、子ノードは均等に重み付けされるため、戻り値はすべての子の値の平均になります。)

Expectimax 検索は、Tom Everitt とMarcus Hutterによる「Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability (2005)」で説明されているバリエーションです。

ブルース・バラードは、期待ミニマックス木でアルファベータ剪定を可能にする*-ミニマックスと呼ばれる技術を初めて開発しました。 ^{[3] [4]期待ミニマックスアルゴリズムに}アルファベータ剪定を統合する際の問題は、各子の加重値が超えなくても、チャンスノードの子のスコアが親のアルファまたはベータ境界を超える可能性があることです。ただし、チャンスノードの子のスコアを制限し、したがってチャンスノードのスコアを制限することは可能です。

標準的な反復検索で、同等の確率の子を持つチャンス ノードの 番目の子にスコアを付けようとしている場合、その検索では子ノード 1 から までのスコアが計算されています。未検索の各子に可能な限り低いスコアと可能な限り高いスコアがあると仮定すると、チャンス ノードのスコアの境界は次のようになります。 ${\displaystyle i}$${\displaystyle N}$${\displaystyle v_{1},v_{2},\ldots ,v_{i-1}}$${\displaystyle i-1}$${\displaystyle L}$${\displaystyle U}$

${\displaystyle {\text{スコア}}\leq {\frac {1}{n}}\left((v_{1}+\ldots +v_{i-1})+v_{i}+U\times (ni)\right)}$

${\displaystyle {\text{score}}\geq {\frac {1}{n}}\left((v_{1}+\ldots +v_{i-1})+v_{i}+L\times (ni)\right)}$

チャンス ノードのスコアリングでアルファ境界および/またはベータ境界が指定されている場合、これらの境界を使用して番目の子の検索を中止できます。上記の式を並べ替えると、チャンス ノードが自身のアルファ境界およびベータ境界を超える場合に検索を中止する新しいアルファ値とベータ値を見つけることができます。 ${\displaystyle i}$

${\displaystyle \alpha _{i}=N\times \alpha -\left(v_{1}+\ldots +v_{i-1}\right)+U\times (ni)}$

${\displaystyle \beta _{i}=N\times \beta -\left(v_{1}+\ldots +v_{i-1}\right)+L\times (ni)}$

この方法で、フェイルハードアルファベータ プルーニングを使用して expectiminimax を拡張するための疑似コードは次のとおりです。

関数*-minimax(node, depth, α, β)
    ノードが終端ノードまたはdepth = 0
        の場合、ノードのヒューリスティック値
    を返します。ノードが最大または最小ノード
        の場合、ノードのミニマックス値
    を返します。N = numSuccessors(node)とします。
    // 子のα、βを計算します。
    A = N * (α - U) + U
    とし、 B = N * (β - L) + L
    とし、ノードの各子について合計を 0
    とする。
        // 子 α、β を有効な範囲に制限する
        AX = max(A, L)
        とし、 BX = min(B, U)とします。
        // 新しいカットオフ値を持つ子を検索する
        スコア = *-minimax(子, 深さ - 1, AX, BX)とします。
        // α、β カットオフ条件をチェック
        スコア <= A
            の場合はα
        を返し、スコア >= B
            の場合はβを返します。
        合計 += スコア
        // 次の子のためにα、βを調整する
        A + = U - v
        B + = L - v
    // カットオフが発生しなかったため、スコアを返す
    合計を返す/ N

この手法は、検索中に子ノードの下限と上限を収集することに基づいて、CHANCE ノードとその子ノードの検索を制限できるアルゴリズムのバリエーション ファミリの 1 つです。パフォーマンス上の利点を提供できるその他の手法には、各子ノードの完全検索を実行する前に、ヒューリスティックを使用して各子ノードを調査し、最小値または最大値を確立することなどがあります。

• ミニマックス
• アルファベータ剪定
• ネガマックス
• 期待値