ミニマックスアルゴリズム
1. 概要
人工知能とゲーム理論の領域では、検索の問題に遭遇することがよくあります。 このような問題は、相互接続されたノードのグラフで説明できます。各ノードは、考えられる状態を表しています。
インテリジェントエージェントは、各ノードを評価して「良好な」（最適ではない場合）状態に到達することにより、グラフをトラバースできる必要があります。
ただし、一般的なグラフ検索アルゴリズムを適用できない特定の種類の問題があります。
このチュートリアルでは、そのような問題について説明し、考えられる解決策の1つであるミニマックスアルゴリズムを評価します。
2. 序章
このチュートリアルでは、敵対的な問題に対処するためのかなり単純なアプローチであるミニマックスアルゴリズムについて説明します。 「敵対的」とは、マルチエージェントシステムを指し、各エージェントは、対戦相手の考えられる行動を考慮して戦略を選択します。
3. 例
アルゴリズムがどのように機能するかを理解するための例を考えてみましょう。 下の画像に示すように、MaxとMinの2人のプレーヤーが、ツリーで表すことができるゲームをプレイしています。
丸はそれがマックスの動きであることを示し、四角はミンの動きを示します。 ターミナル（リーフ）ノードに到達すると、ゲームは終了します。 最終値は、リーフノードの下に書き込まれる効用関数の値です。
MaxとMinの両方が最適に再生される設定では、Maxがどちらの動きをとっても、Minはユーティリティスコアが最も低いカウンタームーブを選択します。 したがって、トップダウンのアプローチに従うことで、最善の動きを決定できます。
最初にツリーの深さをトラバースして、ターミナルノードに到達し、その親ノードに、移動する順番のプレーヤーに最適な値を割り当てます。
この状況で、Maxがを選択した場合、それが可能な限り低い値であるため、Minが選択します。 したがって、を割り当てます。 Maxがを選択した場合、Minは次のように選択します。
最小の動きを計算したら、次のように表すことができる最大の最適な動きの選択に進むことができます。
したがって、Maxが選択し、Minが選択し、このゲームの最終値はになります。
4. 実装の詳細
アルゴリズムの基本的な機能を理解したので、より正式な用語で説明しましょう。 Minimaxは、その性質上、深さ優先探索であり、再帰関数として便利にコーディングできます。手順は次の擬似コードに要約されています。
状態ツリーのすべてのノードには、少なくとも1回はアクセスする必要があります。 ノードごとに子を持つ深さのツリーの場合、これは計算の複雑さになります。
5. 改善
簡単にわかるように、すべての単一ノードにアクセスする必要があるアルゴリズムはあまり効果的ではありません。 実際のアプリケーションで発生する木は、非常に深く、幅も広くなっています。 この良い例は、TicTacToeです。 これは確かに単純なゲームですが、それに関連する状態グラフは非常に複雑で、アクセスする必要のあるノードがあります。
この問題を完全に解決することはできませんが、冗長であり、より良い解決策を提供しないノードのサブツリーを破棄することで軽減できます。 このプロセスはアルファベータプルーニングと呼ばれます。
前の例をもう一度確認してみましょう。
ノードをチェックした後、それが最適な選択であるため、Minが選択することがわかります。 したがって、ノード。
ノードを評価しようとすると、最初の子ノードがであることがわかります。 ミンは効用スコアを最小化したいと考えているので、さらに低い値が出ない限り、彼は間違いなく選択します。したがって、ノードの最終的な値はであると言えます。
ただし、ノードの値は。よりも大きいため、ノードの方がMaxに適しています。 したがって、残りの子はそれ以上の動きを提供しないため、完全にスキップできます。 ノードに向かうと、より良い解決策が見つかる可能性を排除できないため、その子のそれぞれが評価されます。
2ノードの評価をスキップすることに成功し、問題の計算要件を軽減しました。 これは大きな成果とは思えないかもしれませんが、より複雑なアプリケーションでは、メリットがかなり大きくなる可能性があります。
6. 制限事項
アルファベータ法は計算コストを軽減しますが、アルゴリズムが妥当な時間の制約内にとどまりながら、数層深くチェックすることしかできません。 指数関数的な計算の複雑さは、アルゴリズムの能力を非常に少ない層のゲームに制限します。
信じられないほど深いステートツリーを持つゲームやチャンスを伴うゲームは、アルゴリズムの機能の範囲外になる傾向があります。 このような問題では、ノードをターミナルノードであるかのようにヒューリスティックに評価する必要があります。 これにより、アルゴリズムは有限の深さで状態を調べ、適切ではあるが最適ではないソリューションを選択できます。
7. 結論
この記事では、Minimaxアルゴリズムの機能と、それが通常適用されるドメインについて説明しました。 次に、その弱点を確認し、それらに取り組むために一般的に使用される剪定手法を紹介しました。 最後に、アルゴリズムの制限と、より高度で計算上実行可能なアルゴリズムの基盤を形成するソリューションについて説明しました。
