強化学習について学んでみた。（その20）

昨日はSarsa法とQ学習の説明をした。

今日からは実際にこれらのアルゴリズムを使って○×ゲームのAIを作ってみる。

○×ゲーム

まぁ、○×ゲームの説明は不要だよね・・・

とりあえずは、○×ゲームをCUIで遊べるようにするところから。

モジュールと定数の定義

とりあえず、名前空間としてのモジュールと、必要な定数を定義しておく。

#====================
# tic_tac_toe.rb
#====================

module TicTacToe
  EMPTY = '.'
  MARU = 'o'
  BATSU = 'x'
end

Stateクラス

状態を表すために、Stateクラスを実装する。

#====================
# state.rb
#====================

require './tic_tac_toe'

module TicTacToe
  State = Struct.new(:p1, :p2, :p3, :p4, :p5, :p6, :p7, :p8, :p9)

  class State
    @@start = self.new(EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY).freeze

    def self.start
      return @@start
    end

    def rotate_once
      new_state = self.dup
      new_state.p1 = self.p3
      new_state.p2 = self.p6
      new_state.p3 = self.p9
      new_state.p4 = self.p2
      new_state.p6 = self.p8
      new_state.p7 = self.p1
      new_state.p8 = self.p4
      new_state.p9 = self.p7
      return new_state.freeze
    end

    def rotate(time)
      new_state = self.dup
      time.times do
        new_state = new_state.rotate_once
      end
      return new_state
    end

    def mirror()
      new_state = self.dup
      new_state.p1 = self.p3
      new_state.p4 = self.p6
      new_state.p7 = self.p9
      new_state.p3 = self.p1
      new_state.p6 = self.p4
      new_state.p9 = self.p7
      return new_state.freeze
    end

    alias :original_eql? :eql?

    def original_hash()
      hash = 1
      (1..9).each do |i|
        mark = EMPTY
        eval "mark = self.p#{i}"
        case mark
        when MARU
          hash *= 2 ** i
        when BATSU
          hash *= 3 ** i
        when EMPTY
          hash *= 5 ** i
        end
      end
      return hash
    end

    def hash()
      hashes = Array.new
      4.times do |i|
        rotated = self.rotate(i)
        hashes.push(rotated.original_hash)
      end
      mirror = self.mirror()
      4.times do |i|
        rotated = mirror.rotate(i)
        hashes.push(rotated.original_hash)
      end
      return hashes.min
    end

    def eql?(other)
      if other.instance_of?(State)
        4.times do |i|
          rotated = other.rotate(i)
          if self.original_eql?(rotated)
            return true
          end
        end
        mirror = other.mirror()
        4.times do |i|
          rotated = mirror.rotate(i)
          if self.original_eql?(rotated)
            return true
          end
        end
        return false
      else
        return false
      end
    end

    def ==(other)
      self.eql?(other)
    end

    def valid_actions
      valid_actions = (1..9).each_with_object(Array.new) do |i, array|
        if eval "self.p#{i} == EMPTY"
          array.push i
        end
      end
      return valid_actions
    end

    def set(index, mark)
      new_state = self.dup
      if index
        eval "new_state.p#{index} = mark"
      end
      return new_state.freeze
    end

    def win?(mark)
      if (self.p1 == mark && self.p2 == mark && self.p3 == mark) ||
         (self.p4 == mark && self.p5 == mark && self.p6 == mark) ||
         (self.p7 == mark && self.p8 == mark && self.p9 == mark) ||
         (self.p1 == mark && self.p4 == mark && self.p7 == mark) ||
         (self.p2 == mark && self.p5 == mark && self.p8 == mark) ||
         (self.p3 == mark && self.p6 == mark && self.p9 == mark) ||
         (self.p1 == mark && self.p5 == mark && self.p9 == mark) ||
         (self.p3 == mark && self.p5 == mark && self.p7 == mark)
        true
      else
        false
      end
    end

    def lose?(mark)
      opposite = (mark == MARU) ? BATSU : MARU
      win?(opposite)
    end

    def print
      bar = "-+-+-"

      puts ""
      puts [self.p1, self.p2, self.p3].join('|')
      puts bar
      puts [self.p4, self.p5, self.p6].join('|')
      puts bar
      puts [self.p7, self.p8, self.p9].join('|')
      puts ""
    end
  end
end

Stateクラスは（Rubyの）構造体として定義した。

ちょっと注目したいのは、State#hash()とState#eql?()メソッドを定義しているところ。
これは、回転や対称移動して同じになる状態同士は等しいとして扱った方が状態の総数が減るので、学習の進みが早くなると考えたから。
実際、これによって必要な学習の回数は減っている感じだった。
（なお、1回1回の処理は重たくなるので、トータルで学習にかかる時間が減ったかというと、微妙なところ・・・）

HumanPlayerクラス

次は人間プレイヤーの実装。

#====================
# human_player.rb
#====================

require './tic_tac_toe'
require './state'

module TicTacToe
  class HumanPlayer
    def initialize(mark)
      @mark = mark
    end

    attr_reader :mark

    def select_index(state)
      state.print
      puts "<player: #{self.mark}>"
      actions = state.valid_actions
      select_index = loop do
        puts "select index [#{actions.join(',')}]"
        index = $stdin.gets.chomp.to_i
        if actions.include?(index)
          break index
        end
      end
      return select_index
    end

    def learn(reward, finished=false)
      # 何もしない
    end
  end
end

特に説明することもないかな？

なお、Rubyはダックタイピングに対応しているので、Swiftのようにプロトコルを定義したりはしていないけど、select_index()やlearn()がプレイヤーに共通のインタフェースとなるようにしている。

Gameクラス

そして、ゲームの進行を行うGameクラス。

#====================
# game.rb
#====================

require './tic_tac_toe'
require './state'

module TicTacToe
  class Game
    def initialize(player1, player2)
      @player = [player1, player2]
    end

    def start(verbose=false)
      state = State.start
      current_player_index = 0
      loop do
        current_player = @player[current_player_index]
        current_mark = current_player.mark

        index = current_player.select_index(state)
        state = state.set(index, current_mark)
        state.print if verbose

        if state.win?(current_mark)
          current_player.learn(1, true)
          @player[(current_player_index + 1) % 2].learn(-1, true)
          puts "player #{current_mark} win." if verbose
          break
        elsif state.valid_actions.empty?
          @player.each do |p|
            p.learn(0, true)
          end
          puts "draw." if verbose
          break
        else
          current_player.learn(0, false)
        end

        current_player_index = (current_player_index + 1) % 2
      end
    end
  end
end

これで、次のようなコードで人間プレイヤー同士の対戦が出来る：

#!/usr/bin/env ruby

require './tic_tac_toe'
require './state'
require './human_player'
require './game.rb'

maru_player = TicTacToe::HumanPlayer.new(TicTacToe::MARU)
batsu_player = TicTacToe::HumanPlayer.new(TicTacToe::BATSU)
game = TicTacToe::Game.new(maru_player, batsu_player)
game.start(true)

今日はここまで！

強化学習