変種オセロの思考ルーチンを作ってみた。（その6）

昨日の記事は、以下から。

今日は、ミニマックスAIのさらなる高速化を目指す。

アルファベータ法

アルファベータ法の基本的な考え方は、ミニマックス法と同様、「相手が自分にとって一番都合の悪い手を打ってくる前提で、その中で一番マシな局面になる手を選ぶ」なんだけれど、その中で「この手はこれ以上読んでもムダ」という判断をすることで読む量を減らし（枝刈り）、高速化を図る手法だ。

具体的には、アルファ値という値とベータ値という値を使ってこの判断を行う。
（なので「アルファベータ法」という名前になっている）

では、アルファ値とベータ値というのは、何なのか？

直感的な説明をすると、それぞれ

• アルファ値とは「自分の手のうち、今のところもっとも評価値を高くする値」
• ベータ値とは「相手の手のうち、今のところもっとも評価値を低くする値」

となる。

これらの値がどのように使えるのかというと、

• もし、自分のある手を評価したときに、その評価値が「相手の手のうち、今のところもっとも評価値を低くする値（ベータ値）」よりも高かったとする。
  そうすると、その盤面での自分の最善手は今評価した手以上の評価値があるわけだから、相手はその盤面になるような手を選ばない。
  なので、それ以上他の手を読んでも意味がないので、探索を打ち切ってしまって問題ない。
• もし、相手のある手を評価したときに、その評価値が「自分の手のうち、今のところもっとも評価値を高くする値（アルファ値）」よりも低かったとする。
  そうすると、その盤面での相手の最善手は今評価した手以下の評価値になるけだから、自分はその盤面になるような手を選ばない。
  なので、それ以上他の手を読んでも意味がないので、探索を打ち切ってしまって問題ない。

という判断を行うことが出来る。

これを具体的なコードにすると、以下。

module YWF
  class AlphaBetaCom
    def initialize(color, depth=3)
      @color = color
      @opponent = (color == Board::BLACK) ? Board::WHITE : Board::BLACK
      @depth = depth
    end

    def select(board)
      current_select = nil
      current_select_value = -1000
      opponent_best_value = 1000
      board.legal_actions.each do |action|
        value = calculate_action_value(board, action, @depth, current_select_value, opponent_best_value)
        if value > current_select_value
          current_select = action
          current_select_value = value
          if current_select_value >= opponent_best_value
            break
          end
        end
      end

      puts "#{current_select[0].to_s} #{current_select[1]}."
      current_select.flatten
    end

    private

    def calculate_action_value(board, action, depth, self_best_value, opponent_best_value)
      command, place = action
      new_board = case command
                  when :pass
                    board.pass
                  when :play
                    board.play(*place)
                  when :change
                    board.change(*place)
                  end
      if (depth == 1) || new_board.game_end?
        if new_board.win?(@color)
          100
        elsif new_board.win?(@opponent)
          -100
        else
          new_board.count(@color) - new_board.count(@opponent)
        end
      else
        # NOTE:
        # if new board turn is player's color,
        # the player should make action value higher.
        # otherwise, the player should make action value lower.
        # so, if new baord turn is player's color,
        # set initial value to current best value, which is
        # opponent_best_value of original board, and update value
        # only if (value > opponent_best_value).
        # otherwise, set initial value to current best value,
        # which is opponent_best_value of original board,
        # and update value only if (value < opponent_best_value),
        # its equivalent to (-value > -opponent_best_value).
        #
        # by setting 'sign' to 1 if new board turn is player's color
        # and to -1 otherwise, update value only if
        #   (value * sign) > (current_value * sign)

        sign = (new_board.turn == @color) ? 1 : -1

        new_board.legal_actions.each do |action|
          value = calculate_action_value(new_board, action, depth - 1, opponent_best_value, self_best_value)
          if (value * sign) > (opponent_best_value * sign)
            opponent_best_value = value
          end

          # if (opponent_best_value * sign) >= (self_best_value * sign),
          # real opponent_best_value, which means this action's value,
          # is equal to or higher than current opponent_best_value,
          # so the turn player of original board cannot select this action
          # because this inequality means
          #   (self_best_value * original board sign)
          #       >= (this action's value * original board sign).
          # (note that opponent_best value is equal to this action value
          # and original board sign is equal to -sign)
          if (opponent_best_value * sign) >= (self_best_value * sign)
            break
          end
        end

        opponent_best_value
      end
    end
  end
end

「自分の手のうち、今のところもっとも評価値を高くする値（アルファ値）」をself_best_value、「相手の手のうち、今のところもっとも評価値を低くする値（ベータ値）」をopponent_best_valueとして、calculate_action_valueの引数に追加している。
なお、次の盤面を生成してその盤面での手の評価をするときには、手番が逆になっているので、引数に渡している値も逆になっていることに注意。

そして、肝心なのは、次の部分。

if (opponent_best_value * sign) >= (self_best_value * sign)
  break
end

opponent_best_valueというのが、新しい盤面で今のところ相手のもっとも評価の高い評価値だけど、これがself_best_valueを上回るなら、元の盤面で自分はより評価の高い手を見つけているわけだから、それ以上相手の手を読む必要はないので、そこで探索を打ち切ってる。
（ちょっとややこしいのだけど、元の盤面のsignをoriginal_signとしたとき、original_sign = -signなので、(opponent_best_value * sign) >= (self_best_value *sign)なら、(opponent_best_value * original_sign) <= (self_best_value * original_sign)となり、元の盤面で自分はより評価の高い手を見つけていることになる）

プロファイルの比較

実行例自体はミニマックスAIと同じなので、重要なのは、どれくらいスピードが改善されるのかということ。
そこで、それぞれの実行をプロファイルして、比較してみた。

ミニマックスAI

$ ruby -r profile minmax_com.rb 1> /dev/null
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
〜省略〜
  0.26  9486.87     25.26  1014494     0.02    40.93  YWF::MinMaxCom#calculate_action_value
〜省略〜
  0.00  9688.88      0.00        1     0.00 9688880.00  #toplevel

アルファベータAI

$ ruby -r profile alphabeta_com.rb 1> /dev/null
  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
〜省略〜
  0.23  2356.02      5.61   188674     0.03    48.26  YWF::AlphaBetaCom#calculate_action_value
〜省略〜
  0.00  2406.23      0.00        1     0.00 2406230.00  #toplevel

肝心なのは、calculate_action_valueがそれぞれ何回呼ばれているかなので、そこだけ抜き出してある。
見てみると、ミニマックスAIでは1,014,494回呼び出されているのに対し、アルファベータAIでは188,674回しか呼び出されていない。
つまり、呼び出し回数が約1/5に減ってることになる。
実際、プログラム全体でかかった時間も、約9600秒から約2400秒に減ってる。
（※なお、プロファイルしている関係で、全体的に遅くなってる。プロファイルしないで実行すれば、どちらも実際にはもっと速い。ミニマックスAIで約130秒、アルファベータAIだと約30秒程度）

アルファベータ法を使うことで、かなりスピードが改善されていることが分かると思う。

ランダムAIとの対戦成績

さて、いよいよランダムAIと戦わせてみて、戦績を調べてみる。

黒	白	黒の勝ち数	白の勝ち数	アルファベータAIの勝率
アルファベータAI（3手読み）	ランダムAI	98	2	98%
ランダムAI	アルファベータAI（3手読み）	1	99	99%
アルファベータAI（5手読み）	ランダムAI	100	0	100%
ランダムAI	アルファベータAI（5手読み）	0	100	100%

ランダムAI相手なら、3手読みでもほぼ100%、5手読みなら100%勝ちだった。 いい感じ♪

今日はここまで！