[shogi perfect]


Table of Contents

ゲームの探索空間

現在、アブストラクトゲームをプレーするコンピューターの取る戦略は、 評価関数によって、ひとつひとつの局面を静的に判断し着手を決定します。 その局面に至る経緯は考慮しません。

また、合法着手について先読みをおこないます。当然、先読みの深さ(何手先まで読めるか)によって強さが異なってきます。ゲームが複雑になればなるほど、同じコンピューターのリソース(=メモリやCPU時間)を使って、先読みできる深さも少なくなります。 以下は、代表的なアブストラクトゲームでのゲーム探索空間です。*1


以下書きかけです

最適の手を求めて1 ゲーム木

二人完全情報0和ゲームでは、各手番で選択した手によって出現する局面を場合分けして、樹形図を作ることができます。現在の局面から出現するすべての局面の関係をゲーム木と呼びます。ゲーム木を用いて、最善(と思える)手を選択するアルゴリズム、 Mini-Max, α-β, Nega-Max, Nega-Alphaについて、プログラム事例を中心に紹介します。

ここで紹介するプログラム例は、いずれも、深さ優先の探索をするシンプルな実装です。 一般的なアルゴリズムの教科書にある実装方式に加えて、指定の深度になると、読みを打ちきる判断と、局面が静かになるまで探索を延長するための仕組み、また対象の経路での探索深度を返す工夫がしてあります。

Mini-Max法

二人完全情報0和ゲームで、最適の手を探索する基本的なアルゴリズムは、Mini-Max法です。 Mini-Maxでは、探索対象範囲内の起こりうる局面をすべて抽出し、ゲーム木を作り、 ゲーム木の端(node)の評価値を、先手後手、それぞれが自分にとって最良の選択をしたとして、現在局面から次の手の評価をします。

Abstract Strategy Games Online Projectでの実装例

 def minimax(mu,depth) # min-max処理汎用method
   if depth  >= @max_depth
     unless extendable?(mu,depth)
       val = value(mu,depth)
       val = -val unless label(mu)
       return val, depth
     end
   end
 
   childs = children(mu,depth)
   if childs == []
     val = value(mu,depth)
     val = -val unless label(mu)
     return val, depth
   end
 
   mdepth = depth
   unless label(mu) # minノード
     e = Max * 2
     childs.each {|u|
       m, d = minimax(u,depth+1)
       log_detail(mu,depth+1,m)
       if m < e
         e = m
         mdepth = d
       end
     }
     return e, mdepth
   else             # maxノード
     e = Min * 2
     childs.each {|u|
       m, d = minimax(u,depth+1)
       log_detail(mu,depth+1,m)
       if m > e
         e = m
         mdepth = d
       end
     }
     return e, mdepth
   end
 end

α-β法

Mini-Maxでは、木構造のすべてのnodeを評価しなければなりません。 α-βでは、明らかに選択されない手については、nodeと枝の評価をしない工夫がされています。

Abstract Strategy Games Online Projectでの実装例

 def alphabeta(mu,alpha,beta,depth) # αβ処理汎用method
   if depth  >= @max_depth
     unless extendable?(mu,depth)
       val = value(mu,depth)
       val = -val unless label(mu)
       return val, depth
     end
   end
 
   childs = children(mu,depth)
   if childs == []
     val = value(mu,depth)
     val = -val unless label(mu)
     return val, depth
   end
 
   mdepth = depth
   unless label(mu) # minノード
     childs.each {|u|
       e, d = alphabeta(u,alpha,beta,depth+1)
       log_detail(mu,depth+1,e)
       if e < beta
         beta = e
         mdepth = d
       end
       return beta, mdepth if beta <= alpha
     }
     return beta, mdepth
   else             # maxノード
     childs.each {|u|
       e, d = alphabeta(u,alpha,beta,depth+1)
       log_detail(mu,depth+1,e)
       if alpha < e
         alpha = e
         mdepth = d
       end
       return alpha, mdepth if beta <= alpha
     }
     return alpha, mdepth
   end
 end

Knuth等の改善

Nega-MaxとNega-Alphaの基本的なアルゴリズム構造は、Mini-Max, α-βと同じです。 局面の評価基準を手番プレーヤーにすることで、プログラム構造をシンプルにしています。どのようにシンプルになったかは、前述のソースと比較してみてください。

ここで用いている局面評価関数(AI#value)は、Nega-* で使うことを基準としているため、 下記methodes内のvalue呼び出しで、符号反転はおこなっていません。逆に、前述の方式内での、value呼び出しの値をminiノードのときに符号反転する処理をしています。これは、一般の解説書などと異なる実装です。

Nega-Max

Abstract Strategy Games Online Projectでの実装例

 def negamax(mu,depth) # min-max処理汎用method
   if depth  >= @max_depth
     unless extendable?(mu,depth)
       val = value(mu,depth)
       return val, depth
     end
   end
 
   childs = children(mu,depth)
   if childs == []
     val = value(mu,depth)
     return val, depth
   end
 
   mdepth = depth
   e = Min * 2
   childs.each {|u|
     m, d = negamax(u,depth+1)
     m = -m
     log_detail(mu,depth+1, m)
       if m > e
         e = m
         mdepth = d
       end
   }
   return e, mdepth
 end

Nega-Alpha

Abstract Strategy Games Online Projectでの実装例

 def negaalpha(mu,alpha,beta,depth) # αβ処理汎用method
   if depth  >= @max_depth
     unless extendable?(mu,depth)
       val = value(mu,depth)
       return val, depth
     end
   end
 
   childs = children(mu,depth)
   if childs == []
     val = value(mu,depth)
     return val, depth
   end
 
   mdepth = depth
   childs.each {|u|
     e, d = negaalpha(u, -beta, -alpha, depth+1)
     e = -e
     log_detail(mu,depth+1,e)
     if e > alpha
       alpha = e
       mdepth = d
     end
     return alpha, mdepth if beta <= alpha
   }
   return alpha, mdepth
 end

最適の手を求めて2

評価関数

深度延長

反復深化

知識を使う

SEE ALSO


*1 出典:先を読む頭脳?

TOP   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS   [Privacy Policy]