Edited at

AlphaGoを模したオセロAIを作る(1): SLポリシーネットワーク


はじめに

研究で,ある探索問題を解くためにAlphaGoの勉強をしています.

学んだアルゴリズムを自分で実装をしようと思ったのですが,囲碁だととてつもない計算資源が必要になるので,スケールを落としてオセロで試してみました.

本記事では,ChainerでAlphaGoのSLポリシーネットワークを実装し,ターミナル上でプレイできるようにします.

今のところ,このAI(IaGoという名前を付けました)は先読みを一切していませんが,結構強いです.

今後,強化学習やモンテカルロ木探索も実装していくつもりです.ご期待ください!

2018年8月23日追記: 全記事公開しました.


AlphaGoの背景

囲碁の難しさは第一に,そのパターンの多さにあります.探索空間の広さは$10^{360}$と言われており,表のとおり他のゲームよりも広いことがわかります.

ゲーム
探索空間の広さ
AIが人間に勝った年
AI
対戦した人

オセロ
$10^{60}$
1997
NEC Logistello
世界チャンピオン 村上健

チェス
$10^{120}$
1997
IBM Deep Blue
世界チャンピオン Garry Kasparov

将棋
$10^{220}$
2013
 東京大学 GPS将棋
三浦弘行 八段

囲碁
$10^{360}$
2016
DeepMind AlphaGo
李世乭 九段

$10^{360}$というと,もう「億」や「兆」のような名前すらない規模でイメージもできませんが,観測可能な宇宙に存在する原子の総数と言われている$10^{80}$よりもずっと大きいのですから驚異的です.

ちなみに,情報の世界では「天文学的数字」よりも大きい数字がしばしば出てくるので,「組合せ論的数字」なんて言い方も耳にすることがあります.

この膨大なパターン数が原因で,AlphaGoが開発されるまでは「AIが囲碁で人間に勝利するまであと10年はかかる」と言われていましたが,2016年にディープラーニングを応用したAlphaGoが李世乭九段を破り世界を驚かせました.

AlphaGoのすごさを感じていただけたでしょうか?でも,$10^{360}$の世界で戦う人間の棋士もすごいですよね.

ともあれ,囲碁は難しいので私はオセロにしました.


必要なもの

ディープラーニングの基礎とChainerの基本的な使い方に関する知識を前提とします.

訓練から試す場合はGPUが無いと厳しいと思います.


完成したAIと対戦してみる

IaGoという名前をつけてソースコードを公開しています.

ターミナルで次のコマンドを順に実行すればゲームが始まります.詳しくはリンク先のREADMEを読んでください.

$ pip install chainer

$ git clone git@github.com:shionhonda/IaGo.git
$ python ./IaGo/game.py

*Iago: Shakespear『オセロ』の登場人物


AlphaGoの全体像

AlphaGoで用いられているアルゴリズムは,SLポリシーネットワークRLポリシーネットワークバリューネットワークモンテカルロ木探索の4つに分けることができます.

AlphaGo.png


SLポリシーネットワーク

畳込みニューラルネットワーク(CNN; convolutional neural network)によって,ある局面から最適な次の一手を選択します.先読みはしません.

今回実装したのはこのSLポリシーネットワークです.

なお,AlphaGoでは,SLポリシーネットワークを単純化・高速化したロールアウトポリシーというものを用意して,モンテカルロ木探索のプレイアウトに使っています.

*SLは教師あり学習(supervised learning)の略


RLポリシーネットワーク

SLポリシーネットワークを元にして,自己対戦による強化学習でパラメータを調整したものです.

自己対戦の勝敗を報酬としてフィードバックを与えてあるので,極めて近視眼的なSLポリシーネットワークに「ゲームの勝敗」という大局的視点が加わっています.

バリューネットワークの教師データ生成に使いますが,AlphaGoそのものには使いません.

*RLは強化学習(reinforcement learning)の略

こちらは第2回で取り上げます.

AlphaGoを模したオセロAIを作る(2): RLポリシーネットワーク - Qiita


バリューネットワーク

ある局面から「勝てる見込み」を算出する評価関数です.

まず,入力された局面からRLポリシーネットワークによるプレイアウト(自己対戦を終局まで行うこと)を繰り返し,局面と勝率のデータセットを作ります.

このデータセットをCNNで学習し,局面から勝率を出力するネットワークを作ります.

こちらは第3回で取り上げます.

AlphaGoを模したオセロAIを作る(3): バリューポリシーネットワーク - Qiita


モンテカルロ木探索

囲碁やオセロを上手にプレイするには,「自分が次Aに打ったら盤面がこうなって,そうすると相手はBかCに打って…」と先読みすることが必要です.

しかし,囲碁では探索空間が膨大なので,全ての可能性を探索することは現実的な時間では不可能です.

この問題を解決するのがモンテカルロ木探索で,バリューネットワークにより局面の勝率を評価しながら,勝率の高い局面は深く探索し,勝率の低い局面をなるべく探索しないというアルゴリズムです.

こちらは第4回で取り上げます.

AlphaGoを模したオセロAIを作る(4): モンテカルロ木探索 - Qiita


データの用意

それではIaGoの実装に入ります.

まずはデータを用意しましょう.


データ取得

約23万対局分のオンラインオセロの棋譜がこちらで公開されています.

が,そのうち勝った方だけのデータをtxtファイルにまとめてくださった方がいるので,以下のリンク先で入手しdata.txtとして保存してください.

オセロの教師データ公開【ディープラーニング】 - Deeplearning とか 人工知能とか


データ読込み

リンクの説明に従って,「盤面」と「石を置く位置」の配列を作成します.


load.py

# data.txtを1行ずつ展開してstate(盤面)とaction(石を置く場所)を返す

def transform(string):
flat = string.replace("\n", "").split(" ")
state = np.array([int(flat[j]) for j in range(64)]).reshape(8,8)
action = (int(flat[65])-1)*8 + int(flat[64])-1
return state, action

def main():
print("Loading data... (it might take a few minutes)")
with open("../policy_data/txt/data.txt", "r") as f:
data = f.readlines()

# 白黒分けて保存する
B_data = [] # 黒
W_data = [] # 白
for line in data:
if 'B' in line:
B_data.append(line)
elif 'W' in line:
W_data.append(line)
len_B = len(B_data)
len_W = len(W_data)

# listをndarrayに変換
states = np.zeros([len_B+len_W, 8, 8]) # 盤面
actions = np.zeros(len_B+len_W) # 石を置く位置
for i in range(0, len_B):
states[i,:,:], actions[i] = transform(B_data[i])
for i in range(len_B, len_B+len_W):
st, actions[i] = transform(W_data[i-len_B])
# 白の手は黒の手として読み込む(AIは黒番)
st[np.where(st==0)] = 3
states[i,:,:] = 3-st
del B_data, W_data # メモリ解放
'''後略'''


このAIは白番で後手なので逆になっていることに気づきましたが,おそらく大きな影響はないでしょう.

2018年8月14日追記: 元データと数字の割り当てを逆にしているので問題ありませんでした.


データ拡張

stateとactionの組が約607万セットできました.3GBくらいになると思います.

ここで,オセロの盤を90度回転・反転することによりデータを8倍に拡張することができます.メモリに余裕のある方は欲張ってみましょう.

stateの回転と転置はnumpyの組込み関数で簡単にできるので,actionが示す座標を回転・転置する関数を作ります.

rotate関数の式の導出は省略しますが,回転行列と平行移動の組合せです(高校数学を思い出しましょう!).


load.py

# 反時計回りに90度回転

# actionは0-63の数字で盤上の位置を表す
# 回転するときは,中心が原点,左上のマスが(-3.5, -3.5)になるように軸をずらす
def rotate(action):
y, x = action//8-3.5, action%8-3.5
y_, x_ = -x+3.5, y+3.5
return y_*8+x_

# 転置
# 転置するときは,中心が原点,左上のマスが(-3.5, -3.5)になるように軸をずらす
def transpose(action):
y, x = action//8-3.5, action%8-3.5
y_, x_ = x+3.5, y+3.5
return y_*8+x_


これらの関数をmain関数に追加します.


load.py

def main():

with open("../policy_data/txt/data.txt", "r") as f:
'''中略'''
del B_data, W_data #メモリ解放

print("Augmenting data... (it might take a few minutes)")
S = states # 拡張した盤面
A = actions # 拡張した位置
# 90度回転を3回
for i in range(3):
states = np.rot90(states, k=1, axes=(1,2))
S = np.concatenate([S, states], axis=0)
actions = rotate(actions)
A = np.concatenate([A, actions], axis=0)
# 転置
states = states.transpose(0,2,1)
S = np.concatenate([S, states], axis=0)
actions = transpose(actions)
A = np.concatenate([A, actions], axis=0)
# 90度回転を3回
for i in range(3):
states = np.rot90(states, k=1, axes=(1,2))
S = np.concatenate([S, states], axis=0)
actions = rotate(actions)
A = np.concatenate([A, actions], axis=0)
del states, actions # メモリ解放
'''後略'''

これで,stateとactionの組が約4856万セットできました.

このままだとデータが対局の順番になっているので,シャッフルしたうえで訓練データとテストデータに分割し,保存します.


load.py

def main():

with open("../policy_data/txt/data.txt", "r") as f:
'''中略'''
del states, actions

print("Saving data...")
data_size = A.shape[0]
test_size = 1000
rands = np.random.choice(data_size, data_size, replace=False)
S_test = S[rands[:test_size],:,:] # 1000個はテスト用
A_test = A[rands[:test_size]]
np.save('../policy_data/npy/states_test.npy', S_test)
np.save('../policy_data/npy/actions_test.npy', A_test)
del S_test, A_test # メモリ解放
S_train = S[rands[test_size:],:,:] # 残りは訓練用
A_train = A[rands[test_size:]]
np.save('../policy_data/npy/states.npy', S_train)
np.save('../policy_data/npy/actions.npy', A_train)
del S, A, S_train, A_train # メモリ解放



モデル構築

次はモデルの構築です.

AlphaGoのSLポリシーネットワークを元にして,図のようなモデルをChainerで書きました.

実際のAlphaGoは特徴抽出をして入力を48チャネルとしていますが,IaGoでは「黒石が存在するか」と「白石が存在するか」の2チャネルのみとしました.

その他は,層やチャネル数を減らすなどの小さな変更しか与えていません.


network.py

import chainer

import chainer.functions as F
import chainer.links as L

# 畳込みとReLUをブロックにまとめる
class Block(chainer.Chain):
def __init__(self, out_channels, ksize, pad=1):
super(Block, self).__init__()
with self.init_scope():
# 入力チャネル数をNoneとすると自動で設定される
self.conv = L.Convolution2D(None, out_channels, ksize, pad=pad)

def __call__(self, x):
h = self.conv(x)
return F.relu(h)

# SLポリシーネットワーク
class SLPolicy(chainer.Chain):

def __init__(self):
ksize = 3
super(SLPolicy, self).__init__()
with self.init_scope():
self.block1 = Block(64, ksize)
self.block2 = Block(128, ksize)
self.block3 = Block(128, ksize)
self.block4 = Block(128, ksize)
self.block5 = Block(128, ksize)
self.block6 = Block(128, ksize)
self.block7 = Block(128, ksize)
self.block8 = Block(128, ksize)
self.conv9 = L.Convolution2D(128, 1, 1, nobias=True)
self.bias10 = L.Bias(shape=(64))

def __call__(self, x):
h = self.block1(x)
h = self.block2(h)
h = self.block3(h)
h = self.block4(h)
h = self.block5(h)
h = self.block6(h)
h = self.block7(h)
h = self.block8(h)
h = self.conv9(h)
h = F.reshape(h, (-1,64)) # -1にした要素は自動で設定される
h = self.bias10(h)
h = F.softmax(h, axis=1)
return h



学習

図のように,盤面(state)を2チャネルに分けた入力から,64通りの打つ場所(action)に分類するモデルを学習させます.

process.png

損失関数は交差エントロピー,最適化アルゴリズムはAdamとしました(AlphaGoではSGD).


train_policy.py

import argparse

import numpy as np
from tqdm import tqdm
import chainer
import chainer.functions as F
import chainer.links as L
from chainer import serializers, cuda, optimizers, Variable
import network

# 教師データをGPU用に変換する
def transform(x, y):
x = np.stack([x==1, x==2], axis=0).astype(np.float32)
X = Variable(cuda.to_gpu(x.transpose(1,0,2,3)))
Y = Variable(cuda.to_gpu(y.astype(np.int32)))
return X, Y

def main():
# エポック数とGPU番号の指定
parser = argparse.ArgumentParser(description='IaGo:')
parser.add_argument('--epoch', '-e', type=int, default=30, help='Number of sweeps over the dataset to train')
parser.add_argument('--gpu', '-g', type=int, default="0", help='GPU ID')
args = parser.parse_args()

# モデル定義
model = network.SLPolicy()
optimizer = optimizers.Adam()
optimizer.setup(model)
optimizer.add_hook(chainer.optimizer_hooks.WeightDecay(5e-4))
cuda.get_device(args.gpu).use()
'''後略'''


次が学習部分です.

繰り返しになりますが,入力はstateそのものではなく,黒石が存在するかどうか,白石が存在するかどうかのbool配列を2チャネルで入力しています.

学習ループをtrainerで実装できればよかったのですが,わかりませんでした.

また,進捗状況を示すためにtqdmを利用しました.

1エポックの計算に1時間ほどかかります.


train_policy.py

def main():

parser = argparse.ArgumentParser(description='IaGo:')
'''中略'''
cuda.get_device(args.gpu).use()

X_test = np.load('../policy_data/npy/states_test.npy')
y_test = np.load('../policy_data/npy/actions_test.npy')
X_test, y_test = transform(X_test, y_test)
X_train = np.load('../policy_data/npy/states.npy')
y_train = np.load('../policy_data/npy/actions.npy')
train_size = y_train.shape[0]
minibatch_size = 4096 # 2**12

# 学習ループ
for epoch in tqdm(range(args.epoch)):
model.to_gpu(args.gpu)
# 訓練データのシャッフル
rands = np.random.choice(train_size, train_size, replace=False)
X_train = X_train[rands,:,:]
y_train = y_train[rands]

# ミニバッチ学習
for idx in tqdm(range(0, train_size, minibatch_size)):
x = X_train[idx:min(idx+minibatch_size, train_size), :, :]
y = y_train[idx:min(idx+minibatch_size, train_size)]
x, y = transform(x, y)
pred_train = model(x)
loss_train = F.softmax_cross_entropy(pred_train, y)
model.cleargrads()
loss_train.backward()
optimizer.update()
# ロスと正解率の計算
with chainer.using_config('train', False):
with chainer.using_config('enable_backprop', False):
pred_test = model(X_test)
loss_test = F.softmax_cross_entropy(pred_test, y_test).data
test_acc = F.accuracy(pred_test, y_test).data
print('\nepoch :', epoch, ' loss :', loss_test, ' accuracy:', test_acc)
# ログ
with open("../log/sl.txt", "a") as f:
f.write(str(loss_test) + ", " + str(test_acc) + "\n")
# モデル保存
model.to_cpu()
serializers.save_npz('../models/sl_model.npz', model)
serializers.save_npz('../models/sl_optimizer.npz', optimizer)


長めに学習させてロスと正解率を出力してみました.

5-15エポックくらいで十分そうですね.ちなみに,AlphaGoの正解率は57%程度だそうです.

loss.png


ゲームの実装

ターミナル上で対話形式でプレイできるようにしました.

ルールを実装する部分が地味に大変でした.

詳細はソースコードのgame.pyとself_play.pyをご覧ください.


人間 vs AI

まずは,ゲームに必要な盤面などを定義します.

gamelogには棋譜を保存します.


game.py

class Game:

def __init__(self):
# 盤面の初期化
self.state = np.zeros([8, 8], dtype=np.float32)
self.state[4, 3] = 1
self.state[3, 4] = 1
self.state[3, 3] = 2
self.state[4, 4] = 2
# ゲーム内変数
self.stone_num = 4 # 盤上の石の数
self.play_num = 1 # 何手目か
self.pass_flg = False # 前の手がパスならTrue
self.date = datetime.now().strftime("%Y-%m-%d-%H-%M") # ログのファイル名に使う
self.gamelog = "IaGo v1.3\n" + self.date + "\n"
# モデル読込み
self.model = L.Classifier(SLPolicy.SLPolicyNet(), lossfun=softmax_cross_entropy)
serializers.load_npz('./models/sl_model.npz', self.model)


次に重要なのは,手を選択するインターフェイス部分です.

ここで,先ほど学習したSLポリシーネットワークが利用され,確率分布action_probabilitiesに従って手を選択します.

colorは石の色を表す変数で,1なら白番,2なら黒番を示します.


game.py

class Game:

def get_position(self, color, positions):
# 人間のターン(白番)
if color==1:
position = [int(e) for e in self.safeinput()]
if not position in positions:
print("This position is invalid. Choose another position")
return self.get_position(color, positions) # ルール違反の場合はもう一度選ばせる
# AIのターン(黒番)
else:
# SLポリシーネットワークで次の手を選択する
X = np.stack([self.state==1, self.state==2], axis=0).astype(np.float32)
state_var = chainer.Variable(X.reshape(2,1,8,8).transpose(1,0,2,3))
action_probabilities = self.model1.predictor(state_var).data.reshape(64)
action_probabilities -= np.min(action_probabilities) # 確率に変換するために,すべての要素を正にする
distrib = action_probabilities/np.sum(action_probabilities)
idx = np.random.choice(64, p=distrib) # 確率的に選択
position = [idx//8+1, idx%8+1]
if not position in positions:
# ルール違反の場合はもう一度選ぶ
return self.get_position(2, positions)
return position


次に,石を置いて挟まれた石を裏返すplace_stoneや,盤面を表示するshow,合法手の選択肢を返すvalid_posなどの関数を定義してから,1ターンで行う処理をturn関数にまとめます.


game.py

class Game:

def turn(self, color):
players = ["You", "AI"]
positions = self.valid_pos(color) # 合法手の座標
print("Valid choice:", positions)
if len(positions)>0:
# 合法手が存在するなら,石を置く座標を選択する
position = self.get_position(color, positions)
self.place_stone(position, color)
self.show()
self.pass_flg = False
self.gamelog += "[" + str(self.play_num) + "]" + players[color-1]\
+ ": " + str(position) + "\n"
self.stone_num += 1
else:
# 合法手が存在しないならパス
if self.pass_flg:
self.stone_num = 64 # パスが2回続いたらゲーム終了
print(players[color-1] + " pass.")
self.pass_flg = True
self.gamelog += "[" + str(self.play_num) + "]" + players[color-1] + ": Pass\n"
self.play_num += 1


最後に,ゲームの開始から終了までの処理をmain関数にまとめます.


game.py

def main():

print("\n"+"*"*34)
print("*"*11+"Game Start!!"+"*"*11)
print("*"*34+"\n")
game = Game()
game.show()

while(game.stone_num<64): # 盤が埋まるまで繰り返す
game.turn(1)
game.turn(2)

print("\n"+"*"*34)
print("*"*12+"Game End!!"+"*"*12)
print("*"*34)
jd = game.judge()
print(jd)
game.gamelog += jd + "\n"
game.save_gamelog()


game.pyを実行すると,こんな感じで対戦が進みます.

game.PNG

途中でaction_probabilitiesを取り出し,カラーマップで表示してみました.

AIが各マスに白石を置く確率が色で示されています.

[5,3]を除いて,他のマスはほぼ確率0になっています.[3,3]や[3,5]も悪手なのでしょうか.

action_prob_3.png

色を対数スケールにしてみると,小さい値の差がはっきりします.

action_prob_4.png

おもしろい結果ですね!

[2,2]や[7,7]のような「四隅の1つ内側」は確率が非常に低くなっていて,悪手であることが学習されています.

また,同じ合法手でも[3,3]と[3,5]はかなり違いがあります.


AI vs AI

game.pyのget_position関数で,人間のターンのところもSLポリシーネットワークで手を選択させれば,AIの自己対戦ができます.

コードがうまく動くかのテストにも使えるので,実装しておくと便利です.


self_play.py

from game import Game

class SelfGame(Game):

def get_position_self(self, color, positions):

# AIが黒番のときは黒と白を入れ替えたものを入力する
if color==1:
tmp = 3*np.ones([8,8], dtype=np.float32)
self.state = self.state*(tmp-self.state)*(tmp-self.state)/2

# SLポリシーネットワークで次の手を選択する
X = np.stack([self.state==1, self.state==2], axis=0).astype(np.float32)
state_var = chainer.Variable(X.reshape(2,1,8,8).transpose(1,0,2,3))

if color==1:
action_probabilities = self.model1.predictor(state_var).data.reshape(64)
else:
action_probabilities = self.model2.predictor(state_var).data.reshape(64)

action_probabilities -= np.min(action_probabilities) # 確率に変換するために,すべての要素を正にする
distrib = action_probabilities/np.sum(action_probabilities)
idx = np.random.choice(64, p=distrib) # 確率的に選択
position = [idx//8+1, idx%8+1]
if not position in positions:
# ルール違反の場合はもう一度選ぶ
return self.get_position_self(color, positions)
return position


最後までお読みいただきありがとうございました!

次回記事はこちら.

AlphaGoを模したオセロAIを作る(2): RLポリシーネットワーク - Qiita


参考文献

[1] D. Silver et al., "Mastering the game of Go with deep neural networks and tree search," nature, Vol. 529, No. 7587, pp. 484-489, 2016.

DeepMindによるAlphaGoの論文です.

[2] 大槻知史, 三宅陽一郎, 『最強囲碁AI アルファ碁 解体新書 深層学習,モンテカルロ木探索,強化学習から見たその仕組み』, 翔泳社, 2017.

原著論文[1]の解説書です.非常にわかりやすかったです.

[3] 720万手をディープラーニングで学習したオセロAIをChainerで作ってみた - Qiita

モデルの構築やルールの実装などで参考にさせていただきました.

[4] AlphaGoの論文解説とAIが人間を超えるまで - A Successful Failure

無料で読めるものだとこれがわかりやすいです.