期待ミニマックス

期待ミニマックスアルゴリズムは、ミニマックスアルゴリズムの変種であり、バックギャモンなどの2人対戦ゼロサムゲームをプレイする人工知能システムで使用されます。バックギャモンでは、結果はプレイヤーのスキルとサイコロの出目などの偶然要素の組み合わせに依存します。従来のミニマックスツリーの「min」ノードと「max」ノードに加えて、この変種には、ランダムなイベントが発生する期待値を取る「chance」（「 move by nature」）ノードがあります。 ^{[ 1 ]}ゲーム理論の用語では、期待ミニマックスツリーは、完全だが不完全な情報の展開形式ゲームのゲームツリーです。

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

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

例えば、各ラウンドが1回のサイコロ投げと、まずAIプレイヤーによる決定、次に別の知的な対戦相手による決定から構成されるゲームを考えてみましょう。このゲームにおけるノードの順序は、「確率」、「最大」、「最小」が交互になります。^{[ 1 ]}

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

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

ランダムノードの場合、各子ノードに到達する確率が既知でなければならないことに注意してください。（ほとんどの確率ゲームでは、子ノードは均等に重み付けされるため、戻り値はすべての子ノードの値の平均で済みます。）

Expectimax探索は、 Tom EverittとMarcus HutterによるUniversal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability (2005)で説明されている変種である。

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

標準的な反復検索がスコアリングしようとしている場合${\displaystyle i}$チャンスノードの 番目の子${\displaystyle N}$同じくらい可能性が高い子供たち、その検索はスコアを計算しました${\displaystyle v_{1},v_{2},\ldots ,v_{i-1}}$子ノード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{スコア}}\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をfail-hard alpha-beta剪定で拡張するための擬似コードは次のとおりです。

function *-minimax(node, depth, α, β) node が終端ノードまたはdepth = 0 の場合、node のヒューリスティック値 を返します。 node が最大または最小ノードの 場合、 node の minimax 値 を返します。 let N = numSuccessors(node) // 子のα、βを計算します。 A = N * (α - U) + U 、 B = N * (β - L) + L、 sum = 0、 ノードの各子について // 子要素α、βを有効な範囲に制限する AX = max(A, L) BX = min(B, U) // 新しいカットオフ値で子要素を検索する let score = *-minimax(child, depth - 1, AX, BX) // α、β カットオフ条件をチェック スコアがA以下 の場合はα を返し、スコアがB以上 の場合はβを返す 合計 += スコア // 次の子要素に合わせてα、βを調整する A += U - v B += L - v // カットオフが発生しなかったため、スコアを返す 合計 / Nを返す

この手法は、CHANCEノードとその子ノードの探索範囲を、探索中に子ノードの下限値と上限値を収集することで制限できるアルゴリズムの派生アルゴリズム群の一つです。パフォーマンス向上に貢献する他の手法としては、各子ノードに対して完全な探索を実行する前に、ヒューリスティックを用いて最小値または最大値を各子ノードに対してプローブする方法などがあります。

• ミニマックス
• アルファベータ枝刈り
• ネガマックス
• 期待値