Alpha beta pruning

概要

  • 別名 Alpha betaアルゴリズム
  • 検索木内のMinmaxアルゴリズムによって評価されるノードの数を減らす検索アルゴリズム
    （Minmaxアルゴリズムの改良版ともいえる）
  • Maximizerの経路およびMinimizerの経路におけるそれぞれの最良値を評価するAlphaおよびBetaというパラメータを用意し、あるノードからそれより深く探索を続けても意味がない条件の場合、そこからの探索を中断することで検索時間を短縮する
  • 1950年代から研究が行われていた
  • メリット（Minmaxアルゴリズムに比べて）
    • 高速
    • 効率的
    • 軽量
  • デメリット
    • Minmaxでしかたどり着けない解もある

AIでMinimaxアルゴリズムを利用する場合

https://www.javatpoint.com/ai-alpha-beta-pruning
  • Minmaxアルゴリズムの最適化技法という位置づけになる
    • 総当たり的なMinmaxアルゴリズムではコンピュータの負荷が高すぎるためそれを軽減する効果を狙う
  • Alpha beta pruningが注目されだした頃の研究
    • 1956年　John McCarthyがDartmouth WorkshopでAlpha betaアルゴリズムのアイディアを提案
    • 1958年　Allen Newell、Herbert SimonのApproximation
    • 1959年　Arthur SamuelのApproximation
    • 1961年　Daniel Edwards、TimothyのApproximation

Pseudocode

function minimax(node, depth, alpha, beta, 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, alpha, beta, False)  
  maxEva= max(maxEva, eva)   
  alpha= max(alpha, maxEva)      
   if beta<=alpha  
 break  
 return maxEva  
    
else                         // for Minimizer player  
   minEva= +infinity   
   for each child of node do  
   eva= minimax(child, depth-1, alpha, beta, true)  
   minEva= min(minEva, eva)   
   beta= min(beta, eva)  
    if beta<=alpha  
  break          
 return minEva

参考

その他

Posted by ttnt