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

2019-06-29

強化学習のチュートリアルとして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法)では

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

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

施行

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

  • 学習率 :0.5
  • 割引係数 :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 で初手にランダムな手を選ぶ

参考