[Shatar]


Table of Contents

ゲームの探索空間

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

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

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

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

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

Mini-Max法

分割nimのゲーム木 - クリックで拡大

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

図1は、nimの一種で分割nimと呼ばれる種類のゲームを使った、ゲーム木の例です。手番のプレーヤーは、棒を1または2本取り、最後の1本の棒をとったプレーヤーが勝ちというルールです。ゲーム木は、すべてのプレーヤーの選択肢と局面の繊維を樹形図として書き表しています。

分割nimのゲーム木 - クリックで拡大

図2は、図1に先手が勝つ末端のノードに1、後手が勝つ末端のノードに-1を値として割り振り、前の手番での価値を計算して作ったゲーム木です。このゲームは、単純なゲームなので、すべての場合を探索しつくすことが容易で、勝ちと負けで二元的にすべてのノードを評価できました。

一般のMini-Max法では、ゲームが複雑な場合は、勝ちに+∞を、負けに-∞を与え、引き分けノードに0として計算します。ゲーム木は、ゲーム開始時からに限らず、任意の局面からの木を作ることができますので、手番のプレーヤーをMax、相手プレーヤーをMiniと呼んで各ノードを評価します。

決着がつかない状況での途中の局面での評価は、評価関数を作成して、手番(Maxノード)のプレーヤーにとって有利な場合に正の値を、相手(Minノード)プレーヤーが有利な場合に負の値を割り振ることで、評価値が最も高い手を選択します。

Mini-Max法は、このようにゲーム木を作成して、価値の高い手を選択するアルゴリズムです。

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

α-β法

α-βカットの例1 - クリックで拡大
α-βカットの例2 - クリックで拡大
α-βカットの例3 - クリックで拡大

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とMooreの改善

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]