Alpha-Betaプルーニング擬似コードへのMinimaxの変更

Question

アルファベットの擬似コードを学習しています。アルファベットの枝刈りのための最も単純な疑似コードを書きたいと思います。

私はミニマックスのための擬似コードを書かれている：

function minimax(node, depth) 
    if node is a terminal node or depth ==0 
      return the heuristic value of node 
    else 
      best = -99999 
    for child in node 
      best = max(best, -minimax(child, depth-1)) 
    return best 

は、しかし、私はアルファ・ベータ法にそれを修正する方法がわかりません。誰も助けることができますか？

Answer 1

Alpha-Betaでは、1つのポジションについて保証されたスコアを記録しています。相手が既に前のポジションで保証されているスコア（1回前に移動）よりも優れた移動を見つけた場合は、すぐに停止できます。

技術的には、各側は下位スコア（アルファ）を​​追跡し、相手側の下位スコア（ベータ）にアクセスできます。

次の擬似コード

はテストが、ここでアイデアですされていません。

function alphabeta(node, depth, alpha, beta) 
    if node is a terminal node or depth ==0 
      return the heuristic value of node 
    else 
      best = -99999 
    for child in node 
      best = max(best, -alphabeta(child, depth-1, -beta, -alpha)) 
      if best >= beta 
       return best 
      if best > alpha 
       alpha = best 
    return best 

検索の開始時に、あなたは+のINFINITYに-INFINITYにαおよびβを設定することができます。厳密に言えば、スケッチされたアルゴリズムはアルファベットではなく、Negamaxです。どちらも同じですので、これは単なる実装の詳細です。

Alpha-Betaでは、移動の順序が重要であることに注意してください。ほとんどの場合、最善の動き、または少なくとも非常に良い動きから始めれば、Minimaxに対して大きな改善が見られるはずです。

制限付きアルファベータウィンドウ（-INFINITYおよび+ INFINITYではなく）から開始する追加の最適化。しかし、あなたの前提が間違っている場合は、よりオープンなsearch windowで検索を再開する必要があります。