Alpha-beta pruningを使ったMinimaxアルゴリズム|HackerEarth Blog

人工知能(AI)の登場以来、ゲームプレイはAIの最も興味深いアプリケーションの1つでした。

最初のチェスプログラムは、1950年にクロード-シャノンとアラン-チューリングによって書かれた。

チェス、三目並べ、囲碁などのゲームは、両軍間の競争の純粋な抽象化を提供するため興味深いものです。

この抽象化は、ゲームをプレイすることをAI研究にとって魅力的な領域にしています。

この記事では、Minimaxアルゴリズムの基本とアルゴリズムの機能について説明します。

また、minimaxアルゴリズムの最適化、alpha-beta pruningについても見ていきます。

ミニマックスアルゴリズムとは何ですか？
用語
アルゴリズムはどのように機能しますか？
Psuedocode:
最適化
アルファベータプルーニング
いくつかの定義：
アルファベータプルーニングはどのように機能しますか？
結論

ミニマックスアルゴリズムとは何ですか？

Minimaxは、他のプレイヤーも最適にプレイしていると仮定して、プレイヤーに最適な動きを選択するために使用される再帰的なアルゴリズムです。

三目並べ、囲碁、チェス、イゾラ、チェッカー、および他の多くのツープレイヤーゲームなどのゲームで使用されています。

このようなゲームは、特定のゲームのすべての可能な動きを見ることができるので、完璧な情報のゲームと呼ばれています。

相手の動きが予測できないため、スクラブルなどの完璧な情報ではないツープレイヤーゲームが存在する可能性があります。

“この動きをすれば、相手はこの動きしかできない”など、ゲームをプレイするときの考え方に似ています。

Minimaxは、他のプレイヤーが最大損失を持つ戦略を選択したときに損失を最小限に抑えるのに役立つので、そう呼ばれています。

用語

ゲームツリー：ゲームの状態から次の状態に移動することを可能にするすべての可能な動きからなるツリーの形の構造です。

ゲームは、次のコンポーネントで検索問題として定義できます:

初期状態：それはボードの位置とそれが誰の動きであるかを示すもので構成されています。
: これは、プレイヤーが作ることができる法的な動きが何であるかを定義します。＜9804＞＜2705＞端末状態：ゲームが終わったときのボードの位置です。＜9804＞＜2705＞効用関数：ゲームの結果に数値を代入する関数です。たとえば、チェスまたは三目並べでは、結果は勝利、損失、または引き分けのいずれかであり、これらはそれぞれ+1、-1、または0の値で表すことができます。例えば、バックギャモンのユーティリティは+192から-192まで変化します。効用関数は、ペイオフ関数とも呼ばれます。

アルゴリズムはどのように機能しますか？

ゲームには、MINとMAXと呼ばれる二人のプレイヤーが関わっています。プレイヤー MAXは可能な限り最高のスコアを取得しようとし、MINは可能な限り低いスコアを取得しようとします。

Minimaxアルゴリズムの一般的なプロセスは次のとおりです。

ステップ1：最初に、ゲームの現在の位置から端末の状態までのゲームツリー全体を生成します。これは、ゲームツリーがゲームtic-tac-toeのように見える方法です。

三目並べゲームツリー

上の図で定義された用語を理解しましょう。

初期状態は、ボードが空白であることを定義する最初のレイヤーです。
Successor function可能なすべてのsuccessor movesを一覧表示します。これは、ツリー内のすべてのレイヤーに対して定義されます。
端末状態は、最終状態を示すツリーの最後の層、すなわちプレイヤー MAXが勝つか、負けるか、または相手と結びつくかどうかです。
この場合の端末状態のユーティリティは、前述したように1、0、および-1であり、他のノードのユーティリティを決定するためにも使用できます。

ステップ2：効用関数を適用して、すべての端末状態の効用値を取得します。
ステップ3:端末ノードのユーティリティの助けを借りて、上位ノードのユーティリティを決定します。たとえば、下の図では、正方形に書かれた端末状態のユーティリティがあります。

ミニマックス-アルゴリズム-ステップ2

端末の上のレイヤーの左ノード（赤）の効用を計算しましょう。それはプレイヤー分の動きであるので、我々はすべてのユーティリティの最小値を選択します。この場合、MIN{3,5,10}を評価する必要がありますが、これは確かに3であることがわかります。したがって、赤いノードのユーティリティは3です。

同様に、同じレイヤーの緑のノードでは、MIN{2,2}を評価する必要があります。

ミニマックスアルゴリズム

ステップ4: ツリーのルートまで一度に一つの層を考慮した葉の助けを借りて、ユーティリティ値を計算します。
ステップ5：最終的には、すべてのバックアップされた値がツリーのルート、つまり最上位のポイントに到達します。その時点で、MAXは最高値を選択する必要があります。

この例では、3つのレイヤーしかないので、すぐにルートに到達しましたが、実際のゲームでは、さらに多くのレイヤーとノードがあります。したがって、3であるMAX{3,2}を評価する必要があります。

したがって、MAXのための最良の開口部の動きは、左のノード（または赤いノード）です。この動きは、相手もそれを最小限に抑えるために最適にプレイしているという仮定に従って、効用を最大化するため、ミニマックス決定と呼ばれます。

要約すると、

ミニマックス決定=MAX{MIN{3,5,10},MIN{2,2}}
=MAX{3,2}
= 3

Psuedocode:

function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue

最適化

ゲームツリーは、一般的に構築するのに非常に時間がかかり、短時間で生成できるのは単純なゲームのためだけです。

がある場合\(b\)法的な動き、すなわち各点における\(b\)ノードとツリーの最大深さは\(m\)であり、minimaxアルゴリズムの時間複雑度は次数\(b^m(O(b^m))\)である。

この状況を抑制するために、アルゴリズムに追加できる最適化がいくつかあります。

幸いなことに、ゲームツリーのすべてのノードを見なくても、実際のminimaxの決定を見つけることは実行可能です。したがって、分析せずにツリーからノードを排除し、このプロセスを剪定と呼びます。

アルファベータプルーニング

この記事で調べる方法は、アルファベータプルーニングと呼ばれています。

標準のminimaxアルゴリズムにalpha-beta pruningを適用すると、標準のmoveと同じmoveを返しますが、最終的な決定に影響を与えない可能性のあるすべてのノードを削除（プル

最初にこの背後にある直感を理解してから、アルゴリズムを形式化します。この場合、
Minimax Decision=MAX{MIN{3,5,10},MIN{2,a,b},MIN{2,7,3}}
=MAX{3,c}
=Max{3,c}
=Max{3,c}
=Max{3,c}
=Max{3,c}
=Max{3,c}
=Max{3,c}
=Max{3,c}
=Max{3,c}
=Max{3,c}
=Max{3,c}
=Max{3,c},2}
= 3

あなたは驚くでしょう！

欠損値を持つ最大値を計算するにはどうすればよいですか？ここにトリックがあります。 MIN{2,a,b}は確かに2以下、つまりc<=2であり、したがってMAX{3,c,2}は3でなければなりません。

今の問題は、本当にcを計算する必要があるのですか？もちろんそうではありません。

これらのノードを見ずに結論に達した可能性があります。そして、これはアルファベータプルーニングが絵になる場所です。

いくつかの定義：

アルファ：それはプレイヤー MAXのために、これまでのところ最良の選択です。ここでは、可能な限り最高の値を取得したいと考えています。
: これはMINにとってこれまでのところ最良の選択であり、可能な限り低い値でなければなりません。

注:各ノードは、そのアルファ値とベータ値を追跡する必要があります。 AlphaはMAXのターン時にのみ更新でき、同様にbetaはMINのチャンス時にのみ更新できます。

アルファベータプルーニングはどのように機能しますか？

可能な限り最悪の場合としてalpha=-infinityとbeta=infinityを初期化します。ノードをプルーンする条件は、alphaがbeta以上になる場合です。
まず、alphaとbetaの初期値をrootに割り当てることから始めます。alphaはbetaより小さいので、それを剪定しません。
これらのアルファとベータの値を左側の子ノードに運びます。そして今、端末状態の効用値から、alphaとbeの値を更新するので、betaの値を更新する必要はありません。条件が同じままであるため、再び、我々は剪定しません。同様に、第三の子ノードも。そして、ルートにバックトラッキングすると、alpha=3に設定されます。
ここで、alpha=3、beta=無限大です。だから、私たちは剪定しません。これを中央ノードに運び、MIN{2、infinity}を計算すると、alpha=3とbeta=2が得られます。
alphaがbetaより大きいため、2番目と3番目の子ノードを削除します。
根のアルファは2より大きいため3のままです。これを右端の子ノードに運び、MIN{infinity,2}=2を評価します。ベータ版を2に更新し、アルファ版は3のままです。
alphaがbetaより大きいため、2番目と3番目の子ノードを削除します。
したがって、左、中央、右の最小ノードにそれぞれ3、2、2が得られます。そして、最大{3,2,2}を計算すると、3が得られます。したがって、四つの葉を見なくても、minimaxの決定を正しく見つけることができました。

擬似コード（出典：NPTELコース):

evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha

結論

ゲームは非常に魅力的であり、ゲームプレイプログラムを書くことはおそらくさらにエキサイティングです。どのようなグランプリレースは、自動車業界にある、ゲームプレイはAIにあります。

レーシングカーがでこぼこ道で完璧に走ることを期待していないのと同じように、ゲームプレイアルゴリズムがあらゆる状況に完璧であることを期待すべきではありません。

ミニマックスアルゴリズムもそうです。それはAIを持っている必要があり、コンピュータゲームのすべての種類に最適な解決策ではないかもしれません。

しかし、良い実装を考えると、それは厳しい競争相手を作り出すことができます。