強化学習でマルバツゲームAI（Q学習）

#machine learning #reinforcement learning

強化学習のチュートリアルとしてOpenAI Gymで棒が倒れないようにする課題の解説のページを読んで動かしているうちにQ学習がなんとなくわかってきたので、次の題材としてマルバツゲームの思考ルーチンのAIを作ることにした。

マルバツゲームの状態数

マルバツゲームを学習させるにあたって、状態を見積もってみる：

盤面のサイズ：3行×3列
各マスの状態：なし／マル／バツの3通り
盤面の状態数：3の9乗＝19,683通り（ゲームとしてはありえない状態も含む）

これに、各状態での行動を掛け合わせてみる：

行動数：9（盤面のどこに自分のコマを置くか、状態によって無効な行動もあり）
状態×行動の総数：19,683×9＝177,147通り

Qテーブル

状態と行動が離散的の場合、各状態での各行動に対する価値を配列として用意してやることで判断できるようになる（それをQテーブルと呼ぶ）。エージェントが行動する際には現在の状態での一番高い価値の行動を取ればいい。

Python/numpyを使う場合にはnp.arrayが使える。

Qテーブルの学習（Q学習）

どうやってQテーブルを獲得するかというと、エージェントを実際に行動させてみてその結果によって徐々に改善していく、という方法で行う。ある行動を試してみてよい手だったら（報酬が得られたら）価値を高めてやる。逆に悪い手だったら価値を下げてやる。ということを何度も繰り返してやることで、徐々に正しい価値が推定される。（理論的にはベルマン方程式だのなんだのから導かれるということなんだけど、よく理解していないので割愛…。）

Q学習（TD法）では

$\begin{align} Q(s, a) & \mathrel{+}= \alpha (r + \gamma Q(s^\prime, a^\prime) - Q(s, a)), \\ a^\prime & = \mathop{\rm argmax} Q(s^\prime) \\ \end{align}$

という式になる。日本語にすると、現在の状態 $s$ で行動 $a$ をとった場合の価値は、報酬 $r$ と次の状態 $s^\prime$ での最適な行動 $a^\prime$ の価値 $Q(s^\prime, a^\prime)$ を割引係数 $\gamma$ で割り引いたものと考えられるので、その値に向けて現在の値との差を学習率 $\alpha$ で近づけてやる、ということになるかな。

最適な行動だけをしていると行き詰まってしまうので、他にいい手がないか探すために一定の確率でランダムな行動を選択する（ε-貪欲法）。

施行

空いているマスのうちのどれかに打つというのを対戦相手として、

学習率 $\alpha$ ：0.5
割引係数 $\gamma$ ：0.999
探索割合ε：5%

で10万回ほどトライアウトしたところ、ほぼ完全に学習できた。

win-rate-history

学習したQテーブルを使って人間相手に対戦できるようにしてみると、ほぼミスせずに勝ちか引き分けに持ち込むことが確認できた。

追試

対戦してもランダム要素がないからつまらないな…と思って、ちょっと試しに初手だけランダムに打たせてみたところ、全然弱かった。 ε-貪欲法で学習させてるんだからそういうケースも学習できてるんじゃないのか…と思ったが、10万回の試行じゃ足りないだけなのかも。

探索の確率を上げて試行回数を1000万回とかに増やしてみるとようやく負けないようになった。

ソース

盤面：

import numpy as np
import random
import sys

from functools import reduce

piece = ['.', 'O', 'X']

lines = [
  [0, 1, 2], [3, 4, 5], [6, 7, 8],
  [0, 3, 6], [1, 4, 7], [2, 5, 8],
  [0, 4, 8], [2, 4, 6],
]

class Board:
  def __init__(self):
    self.buf = [0] * 9

  def reset(self):
    for i in range(len(self.buf)):
      self.buf[i] = 0

  def get_state(self):
    """Returns board state as an integer"""
    return reduce(lambda a, x: a * 3 + x, self.buf)

  def set(self, x, y, c):
    i = x + y * 3
    if self.buf[i] != 0:
      return False
    self.buf[x + y * 3] = c
    return True

  def get_spaces(self):
    """Returns open spaces"""
    return [i for i in range(9) if self.buf[i] == 0]

  def is_over(self):
    """None=Not yet, 1=Player1, 2=Player2, 3=Draw"""
    for line in lines:
      c = self.buf[line[0]]
      if c == 0:
        continue
      if all([self.buf[i] == c for i in line]):
        return c
    if all([c != 0 for c in self.buf]):
      return 3  # Draw
    return None

  def disp(self):
    """Debug display"""
    for i in range(3):
      print(''.join([piece[self.buf[j + i * 3]] for j in range(0, 3)]))

Board#get_state メソッドで、盤面の配置を強化学習の状態を表す数値に変換できる

環境：

class TicTacToeEnvironment:
  def __init__(self, opponent):
    self.board = Board()
    self.opponent = opponent

  def get_state_count(self):
    return 3 ** 9

  def get_action_count(self):
    return 9

  def get_board(self):
    return self.board

  def reset(self):
    self.board.reset()
    self.opponent.reset()
    self.winner = None
    return self.board.get_state()

  def get_possible_actions(self):
    return self.board.get_spaces()

  def step(self, action):
    #print('step: action={}'.format(action))
    if not self.board.set(action % 3, action // 3, 1):
      print('Invalid action: {}'.format(action), file=sys.stderr)
      self.board.disp()
      sys.exit(1)
    winner = self.board.is_over()
    #print('====')
    #self.board.disp()
    if winner:
      self.winner = winner
      #print('  winner={}'.format(winner))
    else:
      while True:
        oa = self.opponent.get_action(self, self.board.get_state())
        if self.board.set(oa % 3, oa // 3, 2):
          break
      #print('  opponent-action={}'.format(oa))
      #print('====')
      #self.board.disp()
      winner = self.board.is_over()
      if winner:
        #print('  winner={}'.format(winner))
        self.winner = winner

    done = False
    reward = 0
    if self.winner:
      done = True
      if self.winner == 1:
        reward = 1.0
      elif self.winner == 2:
        reward = -1.0
      # Draw: reward = 0

    return self.board.get_state(), reward, done, ()

対戦相手も環境の一部として扱う
reset, step はOpenAI Gymの環境と同様にした
報酬は、勝ち+1、負け-1、引き分け0とした

エージェント：

class BaseAgent:
  def reset(self):
    pass

  def get_action(self, env, _observation):
    pass

class RandomAgent(BaseAgent):
  def get_action(self, env, _observation):
    return random.choice(env.get_possible_actions())

class EGreedyAgent(RandomAgent):
  def __init__(self, epsilon, agent):
    self.epsilon = epsilon
    self.agent = agent

  def get_action(self, env, observation):
    r = np.random.uniform()
    if r < self.epsilon:
      return super().get_action(env, observation)
    else:
      return self.agent.get_action(env, observation)

  def learn(self, discount_factor, observation, action, reward, next_observation):
    # Pass to the actual agent.
    self.agent.learn(discount_factor, observation, action, reward, next_observation)

class QLearningAgent(BaseAgent):
  def __init__(self, state_count, action_count, learning_rate):
    self.learning_rate = learning_rate
    self.QTable = np.zeros((state_count, action_count))

  def get_action(self, env, observation):
    state = observation
    possible_actions = env.get_possible_actions()
    while True:
      best_action = self.QTable[state].argmax()
      if best_action in possible_actions:
        return best_action
      self.QTable[state, best_action] = min(self.QTable[state]) - 1.0

  def learn(self, discount_factor, observation, action, reward, next_observation):
    learning_rate = self.learning_rate
    q_table = self.QTable
    state = observation
    next_state = next_observation

    next_action = q_table[next_state].argmax()
    gain = reward + discount_factor * q_table[next_state, next_action]
    estimated = q_table[state, action]
    q_table[state, action] += learning_rate * (gain - estimated)

  def save(self, filename):
    np.save(filename, self.QTable)

  def load(self, filename):
    self.QTable = np.load(filename)

class InteractiveAgent(BaseAgent):
  def get_action(self, env, _observation):
    print('====')
    env.get_board().disp()

    possible_actions = env.get_possible_actions()
    while True:
      line = sys.stdin.readline()
      action = int(line)
      if action in possible_actions:
        break
      print('Invalid', file=sys.stderr)
    return action

ここでは観測結果＝状態となる
打てない場所が選ばれた場合にはQ値をいじって選ばれないようにして再度行動を選択する

訓練：

class Trainer:
  def run_episode(self, env, agent, discount_factor):
    observation = env.reset()
    while True:
      action = agent.get_action(env, observation)
      next_observation, reward, done, info = env.step(action)
      agent.learn(discount_factor, observation, action, reward, next_observation)
      if done:
        break
      observation = next_observation

  def battle(self, env, agent, first_random):
    """No learning"""
    observation = env.reset()
    first = True
    while True:
      if first and first_random:
        action = random.choice(env.get_possible_actions())
        first = False
      else:
        action = agent.get_action(env, observation)
      next_observation, reward, done, info = env.step(action)
      if done:
        break
      observation = next_observation

実際の学習はエージェント側で処理するので、呼び出すだけ
最初の一手をランダムに選択する battle も用意

メイン：

if __name__ == '__main__':
  import matplotlib
  import matplotlib.pyplot as plt
  import optparse

  SAVE_FILE_NAME = 'tictactoe.qtable.npy'

  parser  = optparse.OptionParser()
  parser.add_option('--episode', type='int', default=1000)
  parser.add_option('--learning-rate', type='float', default=0.5)
  parser.add_option('--discount-factor', type='float', default=0.999)
  parser.add_option('--epsilon', type='float', default=0.05)
  parser.add_option('--load', action='store_true', default=False)
  parser.add_option('--test-play', action='store_true', default=False)
  parser.add_option('--test-first-random', action='store_true', default=False)
  options, _ = parser.parse_args()

  env = TicTacToeEnvironment(RandomAgent())
  q_agent = QLearningAgent(3 ** 9, 9, options.learning_rate)
  e_agent = EGreedyAgent(options.epsilon, q_agent)
  trainer = Trainer()

  def training(episode_count, agent, win_counts):
    for i in range(episode_count):
      trainer.run_episode(env, agent, options.discount_factor)
      winner = env.winner
      win_counts[winner - 1] += 1

  def test_play():
    env2 = TicTacToeEnvironment(InteractiveAgent())
    trainer.battle(env2, q_agent, options.test_first_random)
    #trainer.run_episode(env2, q_agent, options.discount_factor)
    print('=== Result')
    env2.get_board().disp()
    winner = env2.winner
    if winner == 1:
      print('COM win!')
    elif winner == 2:
      print('You win!')
    else:
      print('Draw')

  if options.load:
    q_agent.load(SAVE_FILE_NAME)
  else:
    history = [0.0]
    print('### Training')
    batch = 100
    for i in range(options.episode):
      win_counts = [0] * 3
      training(batch, e_agent, win_counts)
      win_rate = win_counts[0] / batch
      print('Win count',  win_counts, win_rate)
      history.append(win_rate)

    q_agent.save(SAVE_FILE_NAME)

    print('### Examine')
    win_counts = [0] * 3
    training(1000, q_agent, win_counts)
    print('Win count',  win_counts, win_counts[0] / 1000)

    plt.figure(figsize=(5, 4))
    plt.plot(history)
    plt.axhline(y=0.0, color='gray', linestyle='--', linewidth=0.5)
    plt.axhline(y=1.0, color='gray', linestyle='--', linewidth=0.5)
    plt.xlabel('x {} game'.format(batch))
    plt.ylabel('Win rate')
    plt.title('Q-learning for Tic Tac Toe')
    plt.savefig('tic-tac-toe-qlearning.png')
    plt.show()

  if options.test_play:
    print('### Play with human')
    test_play()

いろいろオプションでハイパーパラメータを変更できる
--test-play で学習後に対戦できる
- --test-first-random で初手にランダムな手を選ぶ

参考

PhD Thesis: Learning from Delayed Rewards, Watkins, C.J.C.H., 1989　Q学習の論文

マルバツゲームの状態数

Qテーブル

Qテーブルの学習（Q学習）

施行

追試

ソース

参考

関連記事

AutoEncoder

MNISTにバッチ正規化を適用

誤差逆伝播法の導出

クロスエントロピー

Deep Learning?

新着記事