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

昨日は貪欲法のAIを作成。

今日はミニマックス法のAIを作成する。

ミニマックス法

昨日の貪欲法は、「1手読んで、その中で一番いいと思われる手を選ぶ」というもの。
ただ、実際には1手読むだけだと、簡単に取り返されてしまうということがよく起こる。
そこで、もっと深く読んで、数手進んだ先で一番いい盤面になっていそうな手を選ぶ必要がある。

ところで、その場合に必要になってくるのが、「相手の手を読む」ということ。
実際のところ、相手がどう打ってくるのかは不確定なので、そのさらに先を考えるのは難しいように思える。
相手が自分にとって都合のいい手を打ってくれればいいけど、そうでないとたちまち困ってしまうことも考えられる。

じゃあ、どうすればいいのか？

ジャンケンポイ♪ポイ♪

そこで、ちょっと簡単な例で考えてみる。

考えるのは、「ジャンケンポイ♪ポイ♪　どっち出すの♪　こっち出すの♪」っていう遊び。
これは、「ポイ♪ポイ♪」のタイミングで両手をクロスさせて、グー、チョキ、パーのいずれかをそれぞれ両手に用意させ、「こっち出すの♪」のタミングで、そのいずれかを出してジャンケンを行うという遊びだ。

例えば、自分が右手にグー、左手にチョキを用意し、相手は右手にチョキ、左手にパーを用意したとする。
その場合、右手と左手のどちらを出すべきか？

もし、右手のグーを出したとする。
その場合、相手がチョキを出してくれば勝てるけれど、相手にパーを出されると負けてしまう。
つまり、相手が自分にとって都合のいい手を出してくれれば勝てるけど、そうでない場合には負けてしまう。

一方、左手のチョキを出した場合はどうだろう。
相手がチョキを出してきた場合は引き分け、パーを出してきたときには勝ちになる。
つまり、相手が自分にとって都合のいい手を出してくれれば勝てて、さらに、そうでなくても最悪引き分けにはなる。

したがって、基本的には左手のチョキを出した方がいい。

ここで「基本的には」と書いたのは、その裏をかいて右手のグーを出すことがありえるからだ。
というのも、相手も自分と同じ考え方をしてきているなら、チョキを出してあいこを狙ってくる可能性が高い。
なので、そこを狙ってあえて右手のグーを出すことで、勝ちを狙うわけだ。

しかし、仮に自分が先に右手か左手を選ばなければならないとしたら、どうだろう？
その場合、右手のグーを出すということは、絶対にありえない。
というのも、相手は自分の出した手を見て反応すればいいので、自分が右手のグーを出したら、絶対に左手のパーを出すからだ。
なので、「相手は絶対に自分にとって都合の悪い手を出してくる」ということを前提にして、その中で一番いい結果になる手を出す必要がある。
これが「ミニマックス法」の基本的な考え方だ。

ミニマックス法の考え方

先程の例のように、相手は自分にとって一番都合の悪い手を打ってくることを前提に考えるようにする。
その上で、その中で一番マシな手を選ぶというのが、ミニマックス法の考え方だ。
相手が自分に最大（マックス）の被害を与えようとしてくるので、それを最小化させる（ミニマイズ）から、ミニマックス法という名前になってる。
評価値という観点からこれを言い直すと、相手は評価値を出来るだけ低くしようとしてくるので、その中で一番評価の高いものを選ぶとも言える。
（個人的には、こっちの表現の方が直感的だと思うのだけど・・・）

ミニマックスAI

ということで、このミニマックス法を実装した思考ルーチンが、以下。

module YWF
  class MinMaxCom
    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
      board.legal_actions.each do |action|
        value = calculate_action_value(board, action, @depth)
        if value > current_select_value
          current_select = action
          current_select_value = value
        end
      end

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

    private

    def calculate_action_value(board, action, depth)
      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 very low and update value
        # only if (value > current_value).
        # otherwise, set initial value very high and update value
        # only if (value < current_value), its equivalent to
        # (-value > -current_value).
        #
        # by setting 'sign' to 1 if new board turn is player's color
        # and to -1 otherwise,
        # set initial value to very low (or very high) by
        #   current_value = (very low value) * (sign)
        # and update value only if
        #   (value * sign) > (current_value * sign)

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

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

        current_value
      end
    end
  end
end

ポイントとなるのは、calculate_action_valueメソッド。
ここで手の価値を計算して、その中で一番価値が高いと思われる手を選択している。
引数として渡しているdepthは、その手も含めて何手先まで読むのかを表している。

depthが1であったり、あるいは勝敗が決しているときには、それ以上先は読まないで、盤面の評価を返す。

そうでない場合、

新しい盤面が自分の手番の場合、自分の打てる手の中で、一番評価が高くなる手の価値を返す。
新しい盤面が相手の手番の場合、相手の打てる手の中で、一番評価が低くなる手の価値を返す。

ここで、ちょっとしたトリックを使っていて、普通に書くなら

if new_board.turn == @color
  current_value = -1000
  new_board.legal_actions.each do |action|
    value = calculate_action_value(new_board, action, depth - 1)
    if value > current_value
      current_value = value
    end
  end
  current_value
else
  current_value = 1000
  new_board.legal_actions.each do |action|
    value = calculate_action_value(new_board, action, depth - 1)
    if value < current_value
      current_value = value
    end
  end
  current_value
end

というふうに、素直に「自分の手番なら評価の高い手を探し、相手の手番なら評価の低い手を探す」とするのだけど、このコードをよく見てみると、自分の手番のときの処理と相手の手番のときの処理は、current_valueの初期値の設定とその更新の条件しか違わず、しかも、符号が反転しているという違いでしかない。
（value < current_valueと-value > -current_valueが同等というのがポイント）
そこで、signという変数を用意し、自分の手番ならsignを+1、そうでなければ-1として、それを初期値の設定と更新の条件に掛けることで、同等のコードが簡単に書ける。
（可読性はちょっと落ちるけど・・・）

なお、このトリックをさらに進めたネガマックス法というのもある。
ただし、ネガマックス法の場合、評価値の意味がプレイヤーの視点で固定されていないので、ちょっと分かりにくい気も。

実行例・・・

さて、実行例を・・・としたところで、ちょっと問題が。

3手読みのミニマックスAI同士を対戦させようとしたら、やたらと時間がかかる。
遅い・・・

Rubyを使っていて遅いと感じることはあまりないのだけど、やはりこういったゲームプログラミングになってくると、どうしても遅いと感じることが出てきてしまう。
もちろん、いろいろ工夫をすることで、パフォーマンスは大分改善できるのだけど。

ということで、実行例を出す前に、まずはパフォーマンスの改善を行っていく。

今日はここまで！

いものやま。

雑多な知識の寄せ集め