1. 序章


このチュートリアルでは、非決定論的なゲームをプレイするのに適した敵対的な検索アルゴリズムであるExpectimaxを紹介します。






特に、サイコロを投げるなどのランダムな要素を含む確率的な2人用ゲームに焦点を当てます。 ただし、Expectimaxは決定論的ゲームをプレイするためのアルゴリズムであるMinimaxの修正版であるため、最初に後者を紹介します。


2. 敵対的検索


従来の検索では、AIエージェントは、ある目標を達成するための最適なアクションのシーケンスを探します。 エージェントは、その環境内でアクションを実行できる唯一のエンティティであるため、すべての変更はそのアクションを通じて行われます。 そこにあるのはそれだけなので、エージェントは環境についての信念の状態のみをモデル化します。 次に、一連のアクションが状態間のパスになります。


敵対的検索では、エージェントは依然として最適なアクションシーケンスを検索しますが、環境は異なります。 従来の検索とは対照的に、ここではそれだけではありません。 共有環境で動作できる他のAI（または人間）エージェントが少なくとも1つあります。 さらに、エージェントは相反する目標を持っているため、互いに競争します。したがって、エージェントが見つけたい最適なシーケンスは、対戦相手に対する勝利につながるシーケンスです。


したがって、エージェントは、自分の状態だけでなく、競合する他のすべてのエージェントの状態もモデル化します。 敵対的検索の良い例は、チェスやポーカーなどの2人用またはマルチプレーヤーゲームです。


3. ゲーム


AIゲームのプレイでは、状態を位置と呼び、アクションを動きと呼ぶことがよくあります。 従来の検索における一般的な問題の場合と同様に、ゲームの定義には複数のコンポーネントが含まれます。


    

  • 開始位置：最初の動きの前のゲームの初期状態を指定します
    • 

  • ：どのプレイヤー（エージェント）がその状態で動くかを教えてくれる関数 
    • 

  • ：状態で合法的なすべての動きを返す関数 
    • 

  • ：状態にアクションを適用することにより、どの状態に入るのかを指定する遷移モデル 
    • 

  • ：ゲームオーバーの状態を識別する関数
    • 

  • ：端末状態のプレーヤーに数値を割り当てる効用関数 
    • 



この記事では、各端末状態のすべてのプレーヤーのユーティリティの合計が定数になるゲームに焦点を当てます。 その定数はほとんどの場合0です。そのため、このようなゲームを「ゼロサム」と呼びますが、「コンスタントサムゲーム」の方がより正確な用語です。 したがって、プレイヤーはゲームの最後にユーティリティを最大化することでゲームに勝とうとします。


4. 決定論的ゲーム


決定論的ゲームでは、環境、状態で実行可能なアクション、およびアクションを適用した後に取得する状態について不確実性はありません。 したがって、ゲーム定義のすべてのコンポーネントは完全に決定論的です。


たとえば、tic-tac-toeは決定論的なゲームです。 どのボードの状態でも、誰の順番でプレイするのか、プレーヤーがどのセルにマークを付けることができるのか、可能な移動ごとにボードがどのように見えるのかは間違いありません。


決定論的でゼロサムの2人用ゲームをプレイするには、Minimaxと呼ばれるアルゴリズムを使用します。


4.1. ミニマックス


2人のプレーヤーはMAXとMINという名前で行きます。 MAXは、AIエージェントがMinimaxを実行するプレーヤーであり、MINは対戦相手です。 MAXはその有用性を最大化するために動きを選択しますが、MINはMAXの結果を最小化しようとします。 ゲームはゼロサムであるため、MINはMAXの効用を最小化することによってその効用を最大化します。


検索ツリーは現在の状態（最初は）で開始し、可能なすべての移動シーケンスによって分岐します。 ツリー内のノードは、からへの移動のパスをたどることによってエージェントが到達する状態を指します。


したがって、従来の検索と同様に、ノードはその状態へのパスを表す構造であり、その親（）へのポインターが含まれています。 ただし、簡単にするために、セクション3のゲーム定義の関数はノードでも機能すると考えます。


Minimaxは、ゲームをシミュレートし、各ノードのミニマックス値を計算することにより、ツリーを探索します。


      




ミニマックスは、MAXがプレイする番になったときにノードから開始して、ミニマックス値が最も高い子につながる移動を選択します。  それがあの子だとしましょう。 次に、MINはMinimaxのインスタンスをで実行することで動き、MAXの効用を最小限に抑えます。 その後、再びMAXが動き出す番なので、から始まります。


4.2. 擬似コード


これはMinimaxの擬似コードです。




したがって、Minimaxはゲームツリー全体を葉までトラバースし、手元のプレーヤーに最適な動きを返します。 ツリーが深すぎる場合は、ある程度の深さで検索を中断します、非終端記号を新しいリーフにします。 次に、実際の葉の効用を計算して上方に伝播するのではなく、ミニマックス値を推定して葉を評価します。 アルファベータ検索でツリーを整理することもできます。


推定に使用する評価関数は、実際のミニマックス値と相関する数値を返す必要があります。 また、計算が軽量で、実装が簡単である必要があります。 ただし、品質評価関数の設計が難しい場合は、モンテカルロ木探索（MCTS）を使用してノードを評価できます。


5. 期待値


決定論的ゲームとは異なり、確率的ゲームには少なくとも1つの確率的要素があります。 たとえば、サイコロを投げるなどのランダムなイベントの結果に応じて、呼び出すたびに異なる一連の法的措置を返す場合があります。 または、アクションの結果が複数の状態につながる可能性があり、それぞれに特定の確率があります。


たとえば、バックギャモンのゲームでは、各移動の前にサイコロを振ります。 私たちが得る数字は、私たちが行うことができる動きを決定します。 MAXは、ゲームのどの時点でもどの動きから選択するかを事前に知りません。MINのアクションについても同じことが言えます。  AIエージェントが持っているすべての分岐点は、可能な動きの確率分布です。


5.1. チャンスノード


したがって、確率ゲームの検索ツリーには、追加のノードタイプであるチャンスノードがあります。 チャンスノードは、ノードがの親であるプレーヤーが利用できる一連の動きの確率分布を表します。


ミニマックス値の代わりに、ノードには期待値があります。 これらは、MINノードとMAXノードのミニマックス値と同じですが、チャンスノードの場合、expectimax値はその子の期待値です：


または、再発として：


      


 は偶然ノードでのランダムイベントの結果であり、はその確率です。


5.2. 擬似コード


ExpectiMaxアルゴリズムは、MiniMaxと非常によく似ています。




それでも、2つのことに注意する必要があります。 1つ目は、関数がMinimaxのように相互に呼び出さないことです。 代わりに、両方ともを呼び出します。


2つ目は、がチャンスノードの場合、戻るための単一の動きはないということです。 その期待値は、考えられるすべての動きの結果に対する期待値です。 他の場合との一貫性を保つために、空の動きと組み合わせます。


5.3. カットオフと評価関数


ミニマックスツリーで行ったのと同様に、おそらく、ある時点で検索を切断することによって、エクスペクティマックスツリーの深さを制限する必要があります。 ただし、非終端記号のリーフノードを推定する評価関数を設計するには、特別な注意を払う必要があります。


ミニマックスの評価関数は、勝つ確率とのみ相関させる必要があります。 より正確には、移動の順序を保持する必要があります。 たとえば、プレイヤーが勝つチャンスがある状態にリードを移動し、確率がである状態にリードを移動します。 次に、Minimaxは、評価関数がより高い値を：に割り当てることだけを要求します。これにより、それを使用して勝つことができます。


ただし、Expectimaxのでは、評価関数は勝つ確率の正の線形変換である必要があります。 したがって、順序が同じままであっても、評価値にわずかな変更を加えると、エージェントは別の動きを選択する可能性があります。


優れた評価関数の設計が難しすぎることが判明した場合は、MCTSを選択できます。


5.4. 剪定


一見直感に反するかもしれませんが、Expectimaxにアルファベータ法を適用することができます。 剪定の目的は、特定の移動を考慮する必要がないことを証明することです。これにより、それらの移動によって導かれるノードに根ざしたサブツリーを完全に無視できます。 ただし、expectimax値では、チャンスノードのすべての子を訪問し、それらのexpectimax値を計算する必要があります。 したがって、剪定はExpectimaxと互換性がないようです。


しかし、この問題を回避する方法があります。 評価関数の範囲を上下から制限すると、すべての子とそのサブツリーを評価しなくても、チャンスノードのexpectimax値の範囲を決定できます：


6. 結論


この記事では、確率ゲームのExpectimaxアルゴリズムを紹介しました。 Minimaxから派生し、ゲームツリーの深さを制限することと検索ツリーを剪定することの2つの最適化戦略について話しました。