• ミニマックス アルゴリズムは、意思決定やゲーム理論で使用される再帰的アルゴリズムまたはバックトラッキング アルゴリズムです。相手も最適なプレーをしていると仮定して、プレイヤーにとって最適な手を提供します。
• Mini-Max アルゴリズムは再帰を使用してゲーム ツリーを検索します。
• Min-Max アルゴリズムは主に AI でのゲームプレイに使用されます。チェス、チェッカー、三目並べ、囲碁、さまざまな牽引ゲームなど。このアルゴリズムは、現在の状態のミニマックス決定を計算します。
• このアルゴリズムでは 2 人のプレーヤーがゲームをプレイします。1 人は MAX と呼ばれ、もう 1 人は MIN と呼ばれます。
• 両プレイヤーは、相手プレイヤーが最小限の利益を得て、自分が最大の利益を得られるように戦います。
• ゲームの両方のプレイヤーは互いに対戦相手であり、MAX は最大化された値を選択し、MIN は最小化された値を選択します。
• ミニマックス アルゴリズムは、完全なゲーム ツリーを探索するために深さ優先探索アルゴリズムを実行します。
• ミニマックス アルゴリズムはツリーの終端ノードまで進み、その後、再帰としてツリーをバックトラックします。

MinMax アルゴリズムの疑似コード:

 function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva 

最初の呼び出し:

ミニマックス(ノード、3、真)

Min-Max アルゴリズムの動作:

• ミニマックス アルゴリズムの動作は、例を使用して簡単に説明できます。以下に、2 人用ゲームを表すゲーム ツリーの例を示します。
• この例では、2 つのプレーヤーがあり、1 つは Maximizer と呼ばれ、もう 1 つは Minimizer と呼ばれます。
• Maximizer は可能な最大スコアを取得しようとし、Minimizer は可能な最小スコアを取得しようとします。
• このアルゴリズムは DFS を適用するため、このゲーム ツリーでは終端ノードに到達するまでに葉をずっとたどる必要があります。
• 終端ノードでは終端値が与えられるので、それらの値を比較し、初期状態が発生するまでツリーをバックトラックします。 2 人用ゲーム ツリーを解決する際の主な手順は次のとおりです。

ステップ1： 最初のステップでは、アルゴリズムはゲーム ツリー全体を生成し、ユーティリティ関数を適用して最終状態のユーティリティ値を取得します。以下のツリー図で、A がツリーの初期状態であるとします。マキシマイザーが最悪の場合の初期値 = - 無限大を持つ最初のターンを実行し、ミニマイザーが最悪の場合の初期値 = + 無限大を持つ次のターンを実行すると仮定します。

ステップ2： さて、最初にマキシマイザーのユーティリティ値を見つけます。その初期値は -∞ なので、最終状態の各値をマキシマイザーの初期値と比較し、より高いノードの値を決定します。すべての中から最大値を見つけます。

• ノード D の場合、max(-1,- -∞) => max(-1,4)= 4
• ノード E の場合、max(2, -∞) => max(2, 6)= 6
• ノード F の場合 max(-3, -∞) => max(-3,-5) = -3
• ノード G の場合、max(0, -∞) = max(0, 7) = 7

ステップ 3: 次のステップでは、ミニマイザーの番です。そのため、すべてのノードの値を +∞ と比較し、3 つのノードを見つけます。^rdレイヤーノードの値。

• ノード B の場合 = min(4,6) = 4
• ノード C の場合 = min (-3, 7) = -3

ステップ 4: 次は Maximizer の番で、再びすべてのノード値の最大値を選択し、ルート ノードの最大値を見つけます。このゲーム ツリーでは 4 つのレイヤーしかないため、すぐにルート ノードに到達しますが、実際のゲームでは 4 つ以上のレイヤーが存在します。

• ノード A の場合、max(4, -3)= 4

これがミニマックス 2 プレイヤー ゲームの完全なワークフローでした。

Mini-Max アルゴリズムのプロパティ:

完了-Min-Max アルゴリズムが完了しました。有限探索ツリー内で、解決策 (存在する場合) が確実に見つかります。最適な-Min-Max アルゴリズムは、両方の対戦相手が最適にプレイしている場合に最適です。時間の複雑さ -ゲームツリーに対して DFS を実行するため、Min-Max アルゴリズムの時間計算量は次のようになります。 O(b^メートル) ここで、b はゲーム ツリーの分岐係数、m はツリーの最大深さです。空間の複雑さ -ミニマックス アルゴリズムの空間複雑性も DFS と似ています。 について 。

ミニマックス アルゴリズムの制限:

ミニマックス アルゴリズムの主な欠点は、チェスや囲碁などの複雑なゲームでは非常に遅くなるということです。このタイプのゲームには大きな分岐要素があり、プレイヤーには決定すべき選択肢がたくさんあります。ミニマックス アルゴリズムのこの制限は、次の方法で改善できます。 アルファベータ枝刈り これについては次のトピックで説明します。