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

アルファベータプルーニング（Alpha beta pruning）は、minimaxアルゴリズムの最適化手法である。 このブログのコースを通じて、我々はアルファベータプルーニングが何を意味するのか、我々はミニマックスアルゴリズム、良い順序を見つけるためのルール、およ

1. はじめに
2. Minimaxアルゴリズム
3. アルファベータプルーニングのキーポイント
4. アルファベータプルーニングの作業
5. プルーニングで順序を移動
6. Pythonで良い順序を見つけるためのルール
7. コード
8. コード
9. コード
10. コード
11. コード
12. コード
13. コード
14. コード
15. コード
16. コード

はじめに

“剪定”という言葉は、枝や葉を切ることを意味します。 データサイエンスでは、剪定は、決定木とランダムフォレストでのポストとプレ剪定を指す多くの使用される用語です。 アルファ-ベータ剪定は、意思決定木の無駄な枝の剪定に過ぎません。 このアルファベータプルーニングアルゴリズムは、1900年代に研究者によって独立して発見されました。

アルファベータプルーニングは、次のセクションで議論されているミニマックスアルゴリズムの最適化手法です。 剪定の必要性は、場合によっては決定木が非常に複雑になるという事実から来た。 そのツリーでは、いくつかの役に立たない枝はモデルの複雑さを増加させます。 だから、これを避けるために、アルファ-ベータ剪定は、コンピュータがツリー全体を見る必要がないように再生されます。 これらの異常なノードは、アルゴリズムを遅くします。 したがって、これらのノードを削除することにより、アルゴリズムは高速になります。

a*アルゴリズムについて学ぶ。

Minimax algorithm

Minimaxは、シーケンシャルな二人プレイゲームのための古典的な深さ優先検索技術です。 二人のプレイヤーは、最大と最小と呼ばれています。 Minimaxアルゴリズムは、ルートノードのプレイヤーであるMAXの最適な動きを見つけるために設計されています。 検索ツリーは、ゲームの終了または最大検索深度に達するまで、ルートからすべてのノードを深さ優先の方法で再帰的に展開することによって作成されます。 このアルゴリズムを詳細に調べてみましょう。

既に述べたように、ゲームには二人のプレイヤー、すなわち最大と最小があります。 マックスは最初のステップを果たしています。 Maxの仕事は報酬を最大化することですが、Minの仕事はMaxの報酬を最小化し、同時に自分の報酬を増やすことです。 ゲームが終了したときにMaxに最高の報酬を与えるのはどれですか？ この質問に答えるには、ゲームツリーを十分な深さまで探索し、MinがMaxの報酬を最小限に抑えるために最適にプレイすると仮定する必要があります。

ここに例があります。 四つのコインが行にあり、各プレイヤーは彼/彼女のターンに一つのコインまたは二つのコインを拾うことがで 最後のコインを拾ったプレイヤーが勝ちます。 Maxが最初にプレイすると仮定すると、Maxは勝つためにどのような動きをする必要がありますか？

マックスが二つのコインを選んだ場合、二つのコインだけが残り、ミンは二つのコインを選んで勝つことができます。 したがって、1コインを拾うことは、Maxの報酬を最大化するものとする。

お気づきのように、下の図のツリーのノードにはいくつかの値が刻まれており、これらはminimax値と呼ばれています。 ノードのminimax値は、ノードが端末ノードである場合のノードの効用です。

ノードが非終端のMaxノードである場合、ノードのminimax値は、ノードのすべての後続ノードのminimax値の最大値になります。 一方、ノードが非終端の最小ノードである場合、ノードの最小値は、ノードのすべての後継者の最小値の最小値になります。

ここでは、アルファベータプルーニングの背後にある考え方について説明します。 標準的なminimaxアルゴリズムにalpha-beta pruningを適用すると、標準的なアルゴリズムと同じ決定が与えられますが、決定木では珍しいノード、すなわちアルゴリズムによって行われた最終的な決定に影響を与えていないノードをプルーンまたはカットダウンします。 これは、複雑なツリーの解釈の複雑さを避けるのに役立ちます。

KNNアルゴリズムの仕組みを参照してください。

ここで、この手法の背後にある直感について説明しましょう。 下のツリーでminimaxの決定を見つけようとしましょう :

この場合,

ここで上記の結果では、欠損値から最大値をどのように見つけることができるかという疑問があなたの心にある必要があります。 だから、ここにあなたの疑問の解決策もあります：

2番目のノードでは、最小値を2以下のc、つまりc<=2として選択します。 ここで、c<=3で、3、c、2の最大値を選択する必要がある場合、最大値は3になります。

これらのノードを見ずに決定に達しました。 そして、これがalpha-beta pruningが登場する場所です。

アルファ-ベータ剪定のキーポイント

• アルファ：アルファは、Maximizerのパスに沿った任意のインスタンスで見つかった最良の選択または最高値です。 Alphaの初期値は-πです。

• Beta：Betaは、Minimizerのパスに沿った任意のインスタンスで見つかった最良の選択または最低の値です。 アルファの初期値は+∞です。

• Α-βプルーニングの条件は、α>=βである。

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

• MAXはアルファ値のみを更新し、MIN playerはベータ値のみを更新します。

• ノードの値は、ツリーの逆に移動中にalphaとbetaの値ではなく上位ノードに渡されます。

• アルファ値とベータ値は子ノードにのみ渡されます。

アルファ-ベータ剪定の作業

1. 最初の動きから始めます。 最初に、αとβの値を最悪の場合、すなわちα=-γとβ=+γとして定義します。 Alphaがbeta以上になった場合にのみ、ノードをプルーンします。

2. アルファの初期値はベータよりも小さいので、私たちはそれを剪定しませんでした。 今ではマックスのためのターンです。 したがって、ノードDでは、アルファの値が計算されます。 ノードDのalphaの値はmax(2,3)になります。 したがって、ノードDのアルファの値は3になります。

3. これで、次の動きはノードBになり、MIN nowのターンになります。 したがって、ノードBでは、alpha betaの値はmin（3、π）になります。 したがって、ノードBの値はalpha=-πになり、betaは3になります。

次のステップでは、アルゴリズムは、ノードBの次の後続ノードEをトラバースし、α=-γ、およびβ=3の値も渡されます。

4. 今ではマックスのためのターンです。 したがって、ノードEではMAXを探します。 Eにおけるαの現在の値は–πであり、5と比較されます。 したがって、MAX(-∞,5)は5になります。 したがって、ノードEでは、alpha=5、Beta=5です。 これで、alphaがbetaよりも大きいことがわかりますが、これは剪定条件を満たしているため、ノードEの正しい後継者を剪定でき、アルゴリズムは走査されず、

6. 次のステップでは、アルゴリズムは再びノードBからノードAに来ます。ノードAでは、アルファはMAX(-π,3)として最大値に変更されます。 したがって、ノードAのalphaとbetaの値はそれぞれ（3、+∞）になり、ノードCに転送されます。 ノードFでは、alphaの値が0である左の分岐と比較されます。 したがって、MAX(0,3)は3になり、1である右の子と比較され、MAX(3,1)=3はまだα3のままですが、fのノード値は1になります。

8. これで、ノードFはノード値1をCに返し、Cのベータ値と比較します。 したがって、MIN(+∞,1)は1になります。 ここで、ノードCでは、α=3、β=1であり、αはβよりも大きくなり、再び剪定条件を満たす。 したがって、ノードCの次の後継者、すなわち Gは剪定され、アルゴリズムは部分木G全体を計算しませんでした。

これで、Cはノード値をAに返し、Aの最良の値はMAX(1,3)3になります。

上記の表現されたツリーは、計算されるノードと計算されないノードを示している最後のツリーです。 したがって、この例では、マキシマイザの最適値は3になります。

オープンソースのPythonライブラリを見てください。

プルーニングにおける移動順序

アルファ–ベータプルーニングの有効性は、ノードが検査される順序に基づいています。 移動の順序付けは、アルファベータプルーニングで重要な役割を果たしています。

アルファベータプルーニングには二つのタイプの移動順序があります:

1. 最悪の順序付け：アルファベータプルーニングのいくつかのケースでは、アルゴリズムによってプルーニングされたノードのどれもが標準のminimaxアルゴ これは、アルファとベータの要因のためとして多くの時間を消費し、また、任意の効果的な結果を与えることはありません。 これは、剪定における最悪の順序付けと呼ばれます。 この場合、最良の動きはツリーの右側で発生します。
2. 理想的な順序付け：アルファベータ剪定のいくつかのケースでは、アルゴリズムによって剪定されたノードの多く。 これは、剪定における理想的な順序付けと呼ばれます。 この場合、最適な移動はツリーの左側に発生します。 したがって、dfsを適用して、最初にツリーの左を検索し、同じ時間内にminimaxアルゴリズムの2倍の深さに移動します。

良い順序を見つけるためのルール

• 最高の動きは、最低ノードから発生します
• 最高の動きを見つける間にドメインの知識を使用します
• ノードの順序は、最6956>
  

  pythonのコード

  class MinimaxABAgent: """ Minimax agent """ def __init__(self, max_depth, player_color): """ Initiation Parameters ---------- max_depth : int The max depth of the tree player_color : int The player's index as MAX in minimax algorithm """ self.max_depth = max_depth self.player_color = player_color self.node_expanded = 0 def choose_action(self, state): """ Predict the move using minimax algorithm Parameters ---------- state : State Returns ------- float, str: The evaluation or utility and the action key name """ self.node_expanded = 0 start_time = time.time() print("MINIMAX AB : Wait AI is choosing") list_action = AIElements.get_possible_action(state) eval_score, selected_key_action = self._minimax(0,state,True,float('-inf'),float('inf')) print("MINIMAX : Done, eval = %d, expanded %d" % (eval_score, self.node_expanded)) print("--- %s seconds ---" % (time.time() - start_time)) return (selected_key_action,list_action) def _minimax(self, current_depth, state, is_max_turn, alpha, beta): if current_depth == self.max_depth or state.is_terminal(): return AIElements.evaluation_function(state, self.player_color), "" self.node_expanded += 1 possible_action = AIElements.get_possible_action(state) key_of_actions = list(possible_action.keys()) shuffle(key_of_actions) #randomness best_value = float('-inf') if is_max_turn else float('inf') action_target = "" for action_key in key_of_actions: new_state = AIElements.result_function(state,possible_action) eval_child, action_child = self._minimax(current_depth+1,new_state,not is_max_turn, alpha, beta) if is_max_turn and best_value < eval_child: best_value = eval_child action_target = action_key alpha = max(alpha, best_value) if beta <= alpha: break elif (not is_max_turn) and best_value > eval_child: best_value = eval_child action_target = action_key beta = min(beta, best_value) if beta <= alpha: break return best_value, action_target

  このドキュメントでは、ゲーム理論の重要な要素を見てきました。 Minimaxアルゴリズムのパフォーマンスは良いですが、アルゴリズムは遅いですが。 そのため、高速にするために、決定木から異常なノードを削減してパフォーマンスを向上させるアルファベータプルーニングアルゴリズムを使用します。 今日では、高速でよく実行されたアルゴリズムが広く使用されています。

  これらの人工知能と機械学習のコースをチェックしてください偉大な学習からドメイン内のアップスキルとマスターアルファベータプルーニングと他のそのようなアルゴリズムに。

  さらに読む

  1. 人工知能（AI）におけるA*検索アルゴリズム
  2. 決定木アルゴリズムは、例で説明
  3. AI|概念、実装、利点、欠点における最高の最初の検索アルゴ AIはどのように機能し、その種類と将来を予測しますか？