アブストラクトゲームとコンピューター2 のバックアップ差分(No.4)

追加された行はこの色です。
削除された行はこの色です。
''Table of Contents''
#contents()
* ゲームの探索空間 [#g1819817]
現在、アブストラクトゲームをプレーするコンピューターの取る戦略は、
評価関数によって、ひとつひとつの局面を静的に判断し着手を決定します。
その局面に至る経緯は考慮しません。

また、合法着手について先読みをおこないます。当然、先読みの深さ(何手先まで読めるか)によって強さが異なってきます。ゲームが複雑になればなるほど、同じコンピューターのリソース(=メモリやCPU時間)を使って、先読みできる深さも少なくなります。
以下は、代表的なアブストラクトゲームでの''ゲーム探索空間''です。((出典:[[先を読む頭脳]]))
- 三目並べ: 10&super{3};未満 
- チェッカー: 10&super{30};
- オセロ: 10&super{60};
- チェス: 10&super{120};
- 将棋: 10&super{220};
- 囲碁: 10&super{360};

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

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

** Mini-Max法 [#ababa7db]
#ref(./gametree_1.jpg,right,around,分割nimのゲーム木 - クリックで拡大,60%)
二人完全情報0和ゲームで、最適の手を探索する基本的なアルゴリズムは、Mini-Max法です。
Mini-Maxでは、探索対象範囲内の起こりうる局面をすべて抽出し、ゲーム木を作り、
ゲーム木の端(node)の評価値を、先手後手、それぞれが自分にとって最良の選択をしたとして、現在局面から次の手の評価をします。

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

#clear
#ref(./gametree_2.jpg,right,around,分割nimのゲーム木 - クリックで拡大,60%)
図2は、図1に先手が勝つ末端のノードに''1''、後手が勝つ末端のノードに''-1''を値として割り振り、前の手番での価値を計算して作ったゲーム木です。このゲームは、単純なゲームなので、すべての場合を探索しつくすことが容易で、勝ちと負けで二元的にすべてのノードを評価できました。

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

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

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

#clear
[[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

** α-β法 [#s3c69344]
#ref(./gametree_3.jpg,right,around,α-βカットの例1 - クリックで拡大,60%)
#ref(./gametree_4.jpg,right,around,α-βカットの例2 - クリックで拡大,60%)
#ref(./gametree_5.jpg,right,around,α-βカットの例3 - クリックで拡大,60%)
Mini-Maxでは、木構造のすべてのnodeを評価しなければなりません。
α-βでは、明らかに選択されない手については、nodeと枝の評価をしない工夫がされています。

右の図を見ながら、下記のプログラムを確認してみてください。

#clear
[[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等の改善 [#g9aa7933]
** KnuthとMooreの改善 [#g9aa7933]
Nega-MaxとNega-Alphaの基本的なアルゴリズム構造は、Mini-Max, α-βと同じです。
局面の評価基準を手番プレーヤーにすることで、プログラム構造をシンプルにしています。どのようにシンプルになったかは、前述のソースと比較してみてください。

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

*** Nega-Max [#u7be468f]
[[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 [#j62d81d6]
[[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 [#be59960a]
** 評価関数 [#t43c3864]
** 深度延長 [#p432d5b2]
** 反復深化 [#p7a4cfc9]
** 知識を使う [#m0524d27]

* SEE ALSO [#j9f2f3fb]
- [[アブストラクトゲームとコンピューター]]
- [[アブストラクトゲームとコンピューター3]]
- [[Abstract Strategy Games Online Project]]
- [[nimをプレーするコンピューター・プログラム]]