ミニマックスアルゴリズムの長所/短所

Question

ミニマックスアルゴリズムの欠点は、各ボードの状態を二度訪れたことが を持っているということです。その子を見つけるために1時間とヒューリスティック値を評価するために二度目 を。

ミニマックスアルゴリズムには他の欠点や利点がありますか？チェスのようなゲームを言うと、より良い選択肢があるでしょうか？ （もちろん、アルファベータプルーニングのミニマックスだが、他に何か？）

Answer 1

チェスのようなゲームでは、Minimaxが遅すぎる傾向があります。各ターンについて、プレイヤーには多くの選択肢があります。チェスゲームの分岐ファクターは巨大であるため、深く進めば遅くなります。平均して、チェスの分岐要因は30になる傾向があります。これは、1ターンにつき30のサブツリーが作成されます。

特定のアルゴリズムを提供する前に、それらはすべてアルファベータプルーニングと呼ばれるものを使用しています。 Alphaベータは、展開されるノードの数を減らすため、分岐ファクタを減らします。

ミニマックスとアルファベータのさまざまなバリエーションがあることに注意してくださいしかし、最も重要なアルゴリズムは以下のとおりです。

• Negamax：ここでの考え方は、一人のプレイヤーのための移動のためのスコアが常にあるということです他のプレーヤーの-veでも同じ大きさで、max（a、b）= -min（-a、-b）を計算することができます。

シンプルな解釈：

score = -negamax(depth-1,-player) 
best = max(score,best) 

ウィンドウ表示検索アルゴリズム

次のアルゴリズムは、探索空間を削減するためにウィンドウを使用します。 ウィンドウは最初にアルファとベータの値をとることになります。

• 主な変分法：この方法は、初期のアルファおよびベータを「推測」が訪れたノードの数を減少させます。ただ1つのブランチを探索し、という候補の値を選択することでそうします。この値を使用してプルーンします。矛盾が見つかった場合、これは候補者が再び挑戦する候補者よりも高いスコアをもたらす値です。

• MTD（f）ミニマックスの別のバリエーション。ゼロウィンドウ検索を使用します。これは、候補（「v」）を見つけた後、アルファベータ値が（v-1、v）と仮定し、したがってvのみが可能な解であると仮定する。矛盾を見つけたら、候補を変更して繰り返してください。

最近、チェスコンピュータプログラムにとって最もよく使われているアルゴリズムは、MTD（f）といくつかのバリエーション/ヒューリスティックスです。

ソース：Converting Minimax to Negamax (python)