今回から機械学習に入ります。まずは、アルファベータ法で実装したAIを用いて棋譜を生成し、それを用いてDNN (Deep Neural Network)を教師あり学習することを試みます。
ソースコードのバージョンは以下の通りです。
https://github.com/select766/codingame-othello/tree/9cf25088aa2756f68bd4b3a096978d7842a0e0ce
DNNの入出力
学習したいDNNは、盤面を入力とし、打つべき手(policy)と、勝率(value)の2種類の値を出力するものです。入力はオセロの盤面の形状に合わせた二次元画像の形態とし、形状は(高さ=8, 幅=8, チャンネル=3)としました。チャンネル0は自分の石が置いてある位置の要素に1を代入、チャンネル1は相手の石が置いてある位置の要素に1を代入します。チャンネル2はすべて1で埋めます。盤外のパディングを含めた畳み込みを行うため、盤の中か外かが判定できるようにするための情報です。出力のうち打つべき手は(高さ=8, 幅=8, チャンネル=1)の画像とします。各要素がマスを表しており、そのマスに石を置くべきであれば大きな値を出力するように学習します。Softmax関数によって、全マスの値の合計が1になるようにし、マスごとの着手確率として扱います。勝率はスカラーの値で、tanh関数で-1~+1の範囲に収め、与えられた盤面が手番側の勝ちであれば+1、負けであれば-1、引き分けであれば0を出力するように学習します。
教師データの生成
アルファベータ法によるAIを自己対局させて、DNNの教師データを作成します。前節で定めた入出力を学習できるような学習サンプルを表現するMoveRecord
型を定義しました。少なくとも、盤面の状態のほか、AIが選んだ指し手、終局時の勝敗が必要です。設計指針として、学習に用いるPythonコード側では合法手生成などオセロのルールを実装しなくてよいようにしています。勝敗は+1,-1,0だけで表してもよいですが、何かに使えるかもしれないので終局時の石の数の差(-64~64)をそのまま格納しました。勝敗の学習の際にはただ符号を取ればよいです。また、合法手が1つだけ、または1つもない(パス)状態は学習に不要ですが、対局の進行を復元できるよう保存しています。その局面の合法手の数を格納するフィールドn_legal_moves
を設けており、この値を確認することで合法手生成をせずにスキップできます。BoardPlane(=uint64_t)
の8バイト境界に合うパディングを含め、1サンプル24バイトです。なお、AIのパラメータ設定で、指し手がばらけるように評価関数に比較的大きな乱数(標準偏差が石の数の差×2となる正規乱数)を加えています。
// 学習サンプル1つを表す struct MoveRecord { BoardPlane planes[N_PLAYER]; uint8_t turn; // BLACK / WHITE uint8_t move; // 選んだ指し手 int8_t game_result; // 終局時の石の数の差。手番側が多い(勝ち)で正、負けで負、引き分けは0 uint8_t n_legal_moves; // 合法手の数(0はパス) uint8_t pad[4]; // BoardPlaneのアライメント }; void run_one_game(SearchBase *ai, ofstream &fout) { vector<MoveRecord> records; Board board; board.set_hirate(); while (!board.is_gameover()) { ai->board.set(board); string msg; Move move = ai->search(msg); // 合法手が1個の場合も、ゲームの流れを記録するために出力 // シャッフルを行うツールで削除する BoardPlane lm; board.legal_moves_bb(lm); auto n_legal_moves = __builtin_popcountll(lm); MoveRecord record; record.move = static_cast<decltype(record.move)>(move); record.planes[0] = board.plane(0); record.planes[1] = board.plane(1); record.turn = static_cast<decltype(record.turn)>(board.turn()); record.n_legal_moves = static_cast<decltype(record.turn)>(n_legal_moves); memset(record.pad, 0, sizeof(record.pad)); records.push_back(record); UndoInfo undo_info; board.do_move(move, undo_info); } // 終局後に勝敗を全MoveRecordに書き込む int8_t stone_diff_black = static_cast<int8_t>(board.piece_num(BLACK) - board.piece_num(WHITE)); for (auto &record : records) { record.game_result = record.turn == BLACK ? stone_diff_black : -stone_diff_black; } fout.write((char*)&records[0], records.size() * sizeof(MoveRecord)); } int main(int argc, const char* argv[]) { // 出力ファイル(ファイルを開く処理は省略) ofstream fout; // 教師データ生成に使うAI SearchBase *ai = new SearchAlphaBetaConstantDepth(5, 2.0); for (int i = 0; i < n_game; i++) { run_one_game(ai, fout); } }
Tensorflowを用いた学習
前節で生成した学習データを用いて、深層学習フレームワークTensorflowによりDNNを教師あり学習します。Tensorflowを選んだ理由は、私が普段PyTorchばかり使用しているため、新しい技術を習得するためです。技術的にはどちらを選んでもよいと思います。Tensorflowのバージョンは2.11.0です。
入出力テンソルの生成
MoveRecord
はビットボードが格納されており、DNNの入出力として利用できるテンソルへ変換する必要があります。この処理にはnumpyを用います。
まず、numpyのStructured arraysによりMoveRecord
を表現します。例えば、('board', 'B', (16,))
は、名前がboard
、要素がuint8_t
、要素数が16の配列を表しています。
move_record_dtype = np.dtype([('board', 'B', (16,)), ('turn', 'B'), ('move', 'B'), ('game_result', 'b'), ('n_legal_moves', 'B'), ('pad', 'B', (4,))])
盤面を表すビットボードは、numpy.unpackbits
を用いることで1ビット=1要素(値は0か1)のテンソルに変換することができます。実装時は盤面の向きなどが正しくなるよう、Jupyter Notebookで変換結果を目視確認しながら進めます。
np.unpackbits(packed[:,np.newaxis],axis=1,bitorder="little").reshape(N_PLAYER,BOARD_SIZE,BOARD_SIZE)
手の出力は、以下のコードでone-hot vectorに変換します。
def move_to_pos(move: int) -> Tuple[int, int]: """ y, x座標に変換 MOVE_PASSは渡さないこと """ assert move < BOARD_AREA return move // BOARD_SIZE, move % BOARD_SIZE def move_to_onehot(move: int) -> np.ndarray: """ (8, 8), dtype=np.uint8の配列を作り、Moveに対応する位置だけ1、それ以外を0にして返す """ a = np.zeros((BOARD_SIZE, BOARD_SIZE), dtype=np.uint8) a[move_to_pos(move)] = 1 return a
これらを用いて、データセット全体を以下のように読み込みます。テンソルの形状は、Tensorflowで標準となっているNHWCに合わせます。N=バッチサイズ、H=高さ、W=幅、C=チャンネルです。PyTorchではNCHWが標準となっています。当初はNCHWで実装していたのですが、CPU上での畳み込み処理が未実装であるとのエラーが発生しました。
def make_feat_nhwc(record): # 手番から見た盤面を作る # 盤の内側かどうかを判定するための、1で埋めたチャンネルを用意 ba = board.get_board_array(record["board"]) if record["turn"] == board.WHITE: # 手番側がチャンネル0 ba = ba[::-1] feat = np.zeros((8, 8, 3), dtype=np.float32) feat[:, :, 0] = ba[0] feat[:, :, 1] = ba[1] feat[:, :, 2] = 1 # チャンネル2を1で埋める return feat def load_dataset(path): records = np.fromfile(path, dtype=board.move_record_dtype) # MoveRecordが格納されたファイル all_feats = np.zeros((len(records), 8, 8, 3), dtype=np.float32) # NHWC all_moves = np.zeros((len(records),), dtype=np.int32) all_game_results = np.zeros((len(records),), dtype=np.float32) for i, record in enumerate(records): all_feats[i] = make_feat_nhwc(record) all_moves[i] = record["move"] all_game_results[i] = np.clip(record["game_result"], -1, 1) # もとは手番からみた石の数の差。勝ち=1,負け=-1,引き分け=0に変換 return all_feats, all_moves, all_game_results
学習の実行
学習するDNNは、畳み込み5層ののち分岐し、policyヘッドは畳み込み1層、valueヘッドは全結合2層で構成しました。以下にモデル定義コードを示します。
class MyModel(Model): def __init__(self): super(MyModel, self).__init__() self.conv1 = Conv2D(32, 3, activation='relu', padding="same") self.conv2 = Conv2D(32, 3, activation='relu', padding="same") self.conv3 = Conv2D(32, 3, activation='relu', padding="same") self.conv4 = Conv2D(32, 3, activation='relu', padding="same") self.conv5 = Conv2D(32, 3, activation='relu', padding="same") self.conv6 = Conv2D(1, 3, activation=None, padding="same") self.value_flatten = Flatten() self.value_fc_1 = Dense(16, activation='relu') self.value_fc_2 = Dense(1, activation=None) self.policy_flatten = Flatten() def call(self, x): x = self.conv1(x) x = self.conv2(x) x = self.conv3(x) x = self.conv4(x) x = self.conv5(x) p = x v = x p = self.conv6(p) p = self.policy_flatten(p) v = self.value_flatten(v) v = self.value_fc_1(v) v = self.value_fc_2(v) return p, v
データセットの前処理は、自己対局プログラムを2回実行してtrainデータとvalidationデータを作成したうえで、合法手が2個以上の局面のみ抽出しシャッフルしました。
学習ループは、Tensorflowのクイックスタートを参考に実装しました。
エキスパートのための TensorFlow 2 クイックスタート | TensorFlow Core
サンプルコードからの重要な変更箇所は、policyとvalueの2種類の出力を扱う点です。そのため、各出力に対応する損失関数を定義します。
policy_loss_object = tf.keras.losses.SparseCategoricalCrossentropy(from_logits=True)
value_loss_object = tf.keras.losses.MeanSquaredError()
学習ループ内で、モデルから出てきた2種類の出力を対応する損失関数に入力し、その結果を合計して最終的な損失とします。学習させた結果、valueの損失の重みを上げないと、policyだけが学習されてしまうことがわかったため重みづけを行っています。
predictions_policy, predictions_value = model(images, training=True) policy_loss = policy_loss_object(moves, predictions_policy) # 手を表すone-hot vectorとのsoftmax cross entropy value_loss = value_loss_object(game_results, tf.nn.tanh(predictions_value)) # 勝敗を表す+1,-1の値との二乗誤差 loss = policy_loss * 0.5 + value_loss # 1:1の比率だとvalueがchance rateから動かない
対局10000回分の学習データで学習させたところ、train value loss=0.60、train policy accuracy=42%、validation value loss=0.83、validation policy accuracy=41%となりました。value lossは、常に0を出力するモデルで1.0、policy accuracyは合法手からランダムに選んだ場合は16%となる(局面ごとの合法手数の分布から計算)ため、学習ができていることがわかります。valueはtrainに対してvalidationの結果が悪く、過学習しています。policyでは局面ごとに着手できる位置が異なるため対局数×対局の手数だけの独立したデータがあるといえます。一方でvalueは勝敗予測のため、類似した局面は同じ対局のものであり、類似局面間で勝敗が一致する可能性が高く、実質的に対局数分しか独立したデータがありません。これが過学習の起こりやすさに影響していると予想されます。
以上のように教師あり学習に成功しましたので、次回は学習したDNNを対局に用いられるように探索部を実装します。
実際の開発では、モデルの学習の前にMCTSの実装を始めてしまったのですが、実装が完了したとしても動作確認ができるモデルがないことに気づきました。そのため、先に教師あり学習に着手するのが妥当です。また開発の時系列的には、ここでCodinGame上の実行環境チェックも行いました。