はじめに

人生の目標の一つに、自分で作ったAIに敗北したいというのがある。
（自分で育てたAIに負けてみたくないですか？「強く・・・なったな・・」的な親心というか・・）

この記事では、connect 4 というゲームの簡易版を題材に、DQN (Deep Q-Networks) を用いた強化学習で対戦AIを作ることを目標にする。

コードはclaude頼みなので、自力では全く書いていない・・・が、それでも理解は諦めないようにしたいと、人間で解説・解釈をつけていくのがこの記事の目標。

以下で遊べます↓

この記事での題材

世界のアソビ大全51に収録されている↓これ。

ただ、本家のconnect 4 (6*7マス)は状態空間が広すぎて学習が終わらなかったため、ここでは簡易版のconnect 3 (5*5マス) を題材にする。

以下簡易版をconnect 3と呼ぶ。

そもそも強化学習とは

強化学習の文脈では、「エージェント」と「環境」の２つの登場人物でものごとを整理する。

エージェント：今の状態から、自身が持つ方策に従って次の行動を選ぶ
環境：エージェントの行動に対して、報酬と次の状態を返却する

というループを繰り返す、という枠組みで最適化対象をとらえる。

以下、簡便のため、将棋やconnect 4のようなゲームを想定して、

「状態」を、「局面」や「状況」
「行動」を、「手」　　等と呼ぶことがある。

方策

ここで、最適化したいことは、エージェントが持つ方策、つまり、「どの局面でどう行動するのが一番"よい"のか」あるいは、「どのような方策に従って手を選ぶのが一番"勝てる"のか」ということである。つまり、状態$s$ が与えられたとして、どのような行動$a$ を選ぶのが良いか、という意味で、入力を$s$として、出力を$a$とする関数と見ることができる。これを方策$\pi(a|s)$と呼ぶ。特に、いわゆる「一番よい」方策、つまり、任意の状態について、常に他の手を"上回る"方策を、最適方策と呼ぶ。最適方策を求めることが、強化学習のゴールである。

Q値

上記の方策$\pi(a|s)$、つまり、どの局面でどの手を取れば勝てるのか、を直接学習することは難しい。環境が返すのは報酬$r$であり、どの手が勝ち筋かを直接正解ラベルとして受け取ることができないためである。

強化学習の文脈では、$\pi(a|s)$を直接求めることはせず、次のQ値から間接的に行動を決定する、という見方を取る。すぐ後で書くように、Q値は、「この状況でこの手を打ったら勝率何パーセント」とかいった情報を表す値であり、「"この状況$s$でこの手$a$を打ったら勝率何パーセント"、といった情報が全点でわかるなら、一番勝率が高い手を各点で選んでいけば勝ちに最も近づけるだろう」、という考え方である。

すぐ上で「どの局面でどう行動するのが一番"よい"のか」と書いたが、"よい"の定義が何かを考えたい。

例えば、ある状態$s$から出発して、

直後に行動$a_1$を取ると+1の報酬がもらえる
直後に行動$a_2$を取ると-1の報酬が返されるが、その次の状態$s'$からさらに行動$a_3$を取ると+5 の報酬が返される

とすると、後者を選びたくなる。

これを念頭に置くと、一番良い、とは、「報酬の総和 $\Sigma r_t$ が最大であること」であり、最適方策とは、「報酬の総和 $\Sigma r_t$ を最大化する方策」と言える。

また、もう一歩踏み込んで、「将来もらえる報酬より今すぐもらえる報酬を重視する」という機構として、割引率$\gamma (<1)$という概念を導入すると、

割引率を考慮した報酬の総和は、$r_t + \gamma r_{t+1} + \gamma^2 r_{t+2}+ ...$ と書ける。

これは、

「1年後の11万円より今すぐもらえる10万円」的な概念であり、
早く勝つ方が好ましい　という意図を込めるものでもあり、
強化学習が発散しないテクニックでもある。

一般的な強化学習では、この、将来の報酬の割引率を考慮した報酬の総和、つまり

$$
Q_\pi = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2}+ ...
$$

を最大化したい対象と置く。これをQ値と呼ぶ。式の通り、Q値は「割引率を考慮した累積報酬の期待値」を表している。強化学習はこれを最大化する対象と置く。

Q値は、状態$s$と行動$a$の関数、$Q(s,a)$であることに注意する。つまり$Q$値は、「ある局面でこの手を打ったらどのくらい勝てそうか/勝率何パーセント」といった意味を持つ量である。先ほどの定義と対応させると、次のように対応する。（この対応については、次の章でもう少し議論する）
$$
\begin{aligned}
Q(s,a) &= 行動aの結果として受け取る報酬
&&+\ それ以降にもらえる報酬の総額 \
&= r_t
&&+\ \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots
\end{aligned}
$$

このQ値を用いると、先ほどの「最適方策とは報酬の総和 $\Sigma r_t$ を最大化する方策」という表現は、「最適方策とは$Q(s,a)$を最大にする方策」、と言い換えることができる。つまり、どう行動を選ぶか、という方策の自由度は、「一番Q値が高くなる行動を選ぶ」、という形で、方策そのものはgreedyな形で固定化され、Q値の大小にその自由度が押し込めらられることになる。同時に、学習すべき対象は、方策$\pi(s|a)$そのものではなく、Q値の大小に移ることになる。

改めて、強化学習の文脈では、

「どの局面でどう行動するのが一番"よい"のか」という問いに対して、

局面$s$が与えられたときに、どの行動$a$を取るのが適切か、という方策$\pi(s|a)$を直接学習する。
局面$s$に直面した際に、この方策$\pi(s|a)$に従って行動$a$を選ぶ

という世界観ではなく、

局面sが与えられたときに、次にこの手を打つと将来の見込み報酬はどれほどになるか、という量、$Q(s,a)$を学習する。
局面sに直面した際に、$Q(s,a)$、つまり将来の見込み報酬が最大となる行動$a$を選ぶ(というgreedyな方策を取る)

というように読み替えることになる。

上記の考え方のシフトは、実際のゲームを思い浮かべるとイメージを掴みやすい。例えば将棋を指していて、ある盤面で次の一手を考えていて、ここに置いたら次の次くらいで取られるだろうからやめた方がいいな、ここに置くことは相手は想定していなさそうだから勝ち筋になりそうだな、等々を考えるだろうが、この局面でこの手を打った時の見込み勝率、この局面であの手を打ったときの見込み勝率、みたいなものをすべて見通すことができるなら、毎回のターンで一番勝率が高い手を選ぶ、という方策を取るのが一番良いだろう、という考えかたである。

実際のゲームでの例

相手がいないゲーム、例えばすごろくのようなゲームの場合、

agentが、今の状態$s$をもとに、自分が持つ$Q(s,a)$に従って次の行動$a$を決める
環境は、それに応じて、その行動に対する報酬と、次状態を返す

というシンプルな世界観が成り立つが、

これを、今回のconnect 4 のような対戦ゲームに当てはめる場合、相手の行動も環境の中に含まれる必要がある点に注意する。環境は、相手の手も打って進めたうえで、agentに次の状態を返す、つまりagentの次の手番を返す必要がある。

Q値の実装・学習

強化学習の世界観を整理したところで、次に課題になるのが、

この$Q(s,a)$をどのような関数として持つのか？
この$Q(s,a)$をどうやって学習するか？

という2点である。

それぞれ以下で議論する。

Q(s,a)をどのような関数として持つのか？

表形式で持つ案

一つの方法は、表形式で持つ方法である。

つまり、以下のような表を持っておく、というやり方である。素朴には、盤面ごとにどの手を打ったらどれだけ勝てそうか、をすべての状況で丸暗記するような方法と解釈できる。

	$a_1$	$a_2$
$s_1$	$Q(s_1,a_1)$	$Q(s_1,a_2)$
$s_2$	$Q(s_2,a_1)$	$Q(s_2,a_2)$
$s_3$	$Q(s_3,a_1)$	$Q(s_3,a_2)$

このやり方は、実装が簡単な反面、状態数が増えると管理できなくなる、というデメリットがある。

例えば、connect 4では、$10^{12}$ のオーダーの状態数(盤面の種類の数)が存在し、到底表形式でこれを持つことはできない。

今回題材とする、connect 3 であっても、$10^{6}$のオーダーの状態数である。これは表で持てなくもないが、表形式がスケールしない手法であることは変わりなく、次のアイデアに移る。

ニューラルネットで持つ案

今回は、この$Q(s,a)$をニューラルネットとして持つことを考える。特に今回はCNNを使う。これにより、必要な次元数が大幅に削減できるほか、似たような盤面で似たような値を返すように学習することが期待される。この手法はDQN(Deep Q-Network)と呼ばれる。

この$Q(s,a)$をどうやって学習するか？

次に考えるべきことは、この$Q(s,a)$をどうやって学習するのか？ということである。ここまでは、「もし仮にこんなのがあったらいいな」、つまり、「盤面と次の手を入れたらその後の見込み報酬が返る関数がもしあれば、それが一番高くなる手を毎回打っていけば勝てるのにな」という話だったが、そもそもその「盤面と次の手を入れたらその後の見込み報酬が返る関数」をどうやって作るのか？という話になる。

これは、物理計算で言うところの、self-consistent calculation、自己無撞着計算で実現される。つまり、$Q(s,a)$がランダムな状態から始めて、「$Q(s,a)$が正しく盤面と次の手を入れたらその後の見込み報酬が返る関数になっていれば満たしているはずの性質」を各点で順々に適用していくと、最終的に$Q(s,a)$全体が盤面と次の手を入れたらその後の見込み報酬が返る関数になっていく、というものである。

ここで使う「$Q(s,a)$が正しく盤面と次の手を入れたらその後の見込み報酬が返る関数になっていれば満たしているはずの性質」は次の内容である。少し前の記載を発展させる形で書くと、次のようになる。
$$
\begin{aligned}
Q(s,a) &= 行動aの結果として受け取る報酬
&&+\ それ以降にもらえる報酬の総額 \
&= r_t
&&+\ \gamma r_{t+1} + \gamma^2 r_{t+2} + \cdots \
&= r_t
&&+\ \gamma (\max_{a'} Q(s', a'))
\end{aligned}
$$
これは、

$Q(s,a)$の値、つまり、ある盤面である手を打った時のその後の報酬の総和というものは、その手の結果として直接的に環境から受け取る報酬(第一項)と、その後の報酬の総和(第二項)に分かれるが、
後者の「その後の報酬の総和」というものは、仮に$Q(s,a)$が期待通りの性質を満たし、かつ自分が最適方策を取り続けるなら、「次状態$s'$から、その後最適な方策を選ぶ(=その後、$Q(s',a')$を最大とする$a'$を選ぶ)」ことを続けた結果得られる累積報酬、と読み替えることができる。

ということを意味している。これはベルマン方程式と呼ばれる。

DQNでは、このベルマン方程式をもとにニューラルネットを訓練していく。つまり、学習として対局をこなす中で登場する、盤面と、それに対して打った手に対して、

その時点でのDQNから得られた$Q(s,a)$をモデルの出力、
正解データ(教師信号)を$r_t + \gamma (\max_{a'} Q(s', a'))$

として、誤差逆伝搬を行ってニューラルネットの重みの改善を行い、$Q(s,a)$を学習させる。

ここで、報酬rは、最後の勝った手、あるいは、負けた手にのみ値が付き、他の途中経過ではすべて0である点に注意する。学習過程では、まず勝敗が決まりかけている盤面が学習データとして選ばれると$r=\pm 1$ が$Q(s,a)$に反映され、その後、初期の棋譜が選ばれた場合にも$\max_{a'} Q(s', a')$を通じて値が根元まで伝わっていく・・・といった具合で学習が進んでいく。

学習におけるテクニック

ターゲットネットワーク
DQNは、教師信号$r+\gamma (\max_{a'} Q(s', a'))$がニューラルネット自身に依存することが特徴である。つまり、自分と自分を比較して自分を改良していくことになる。これは計算が不安定になりやすく、この対策として、ニューラルネットを２つコピーして持っておいて、
- NN①：学習をせずどこかの断面で固定し、教師信号を計算するためだけに使うニューラルネット
- NN②：モデルの出力を計算し、①で得た教師信号と比較して誤差逆伝搬法で学習を進めるニューラルネット
とすることで、NN①から教師信号が安定して渡され、結果安定した学習に繋がる、というテクニックがある。この「重み固定のNN①」を、あるいはそれを用いた学習手法をターゲットネットワークと呼ぶ。
経験再生
- 学習においては、対局を繰り返して、途中に現れる盤面と、その時に打った手を材料として学習を進めていくが、対局中の棋譜をそのままなぞる形で学習を進めると、前後の学習データが似通った盤面であることから、直近の展開に過剰に適合してしまう問題がある。これを回避するには、対局データをあらかじめたくさん貯めたプールの中からランダムに取り出して学習させる手法が望ましい。これを経験再生と呼ぶ。
e-greedy
- 学習初期においては、モデルの重みはランダムであり、モデルに従って動いてもまともな方策にならない。そのため、学習初期は、探索、つまりランダムに動く割合を多く取り、学習が進むにつれて探索を減らし、学習が進んだモデルに従って次の手を選ぶ、という具合にする。

実装

これを実装して遊べるようにしたものが以下。

コードは以下。

概要

$Q(s,a)$を担うCNNは以下の構成にした。

入力 (3, 5, 5)
  ↓ Conv2d(3→32, 3×3, padding=1) + ReLU
  ↓ Conv2d(32→64, 3×3, padding=1) + ReLU
  ↓ flatten (64×5×5 = 1600)
  ↓ Linear(1600→256) + ReLU
  ↓ Linear(256→5)
出力 (5,)  ← 各列に打った時のQ値

主なハイパーパラメータは以下。

項目	値	補足
学習率	5e-4	Adam
割引率 γγ	0.99
εε (開始→終了)	1.0 → 0.10	減衰率 0.99990
バッファ容量	20,000	経験再生のプール
バッチサイズ	128
ターゲット更新間隔	500ステップ
学習エピソード数	20,000

学習の流れ

学習は、

①推論：今の$Q(s,a)$を使って対局をこなす
②学習：対局をこなして得られた棋譜を使って、学習を行い、$Q(s,a)$を改善する

というステップで進む。

①推論

「①推論：今の$Q(s,a)$を使って対局をこなす」に対応するコードは以下。学習中は、このコードに沿って、状態に応じた次の行動を決めて、エピソードを進める。

基本的にはQ値が最大の手を取るのが最適方策だが、学習中は、Q自体の学習が荒いため、最初はランダムな手を多めにして探索を進め、Q値が収束し始めるにつれて、Q値を尊重した手を取るようにする。

def get_action(self, state, valid_actions):
    # ε の確率でランダムな手（探索）
    if np.random.rand() < self.epsilon:
        return random.choice(valid_actions)

    # それ以外は Q 値が最大の手（活用）
    with torch.no_grad():
        q_values = self.qnet(state_t)[0].numpy()

    # 打てない列を -inf でマスクしてから argmax
    masked_q = np.full(self.action_size, -np.inf)
    masked_q[valid_actions] = q_values[valid_actions]
    return int(np.argmax(masked_q))

②学習

「②学習：対局をこなして得られた棋譜を使って、学習を行い、$Q(s,a)$を改善する」に対応するコードは以下。これが学習の中核で、

①：リプレイバッファから盤面を取り出し、
②：モデルの出力$Q(s,a)$と
③：ターゲットネットワークから計算した、ベルマン方程式に基づく教師信号$r+\gamma (\max_{a'} Q(s', a'))$ を比較し、
④：誤差逆伝搬する

の順に処理が進む。実装の都合上、$Q$は、状態$s$を入力として、各行動に対する$Q$値：Q[s,a_1], Q[s,a_2]...を出力としている点に注意する。

def _train_step(self):
    # ① 経験再生: バッファからランダムに128件取り出す
    states, actions, rewards, next_states, dones = \
        self.replay_buffer.sample(self.batch_size)

    # ② モデルの出力: 実際に打った手 a のQ値だけを取り出す
    current_q = self.qnet(states_t).gather(1, actions_t.unsqueeze(1)).squeeze(1)

    # ③ 教師信号: r + γ・max Q(s', a')  ← ターゲットネットワークで計算
    with torch.no_grad():
        max_next_q = self.qnet_target(next_states_t).max(dim=1).values
        target_q   = rewards_t + self.gamma * max_next_q * (1 - dones_t)

    # ④ 二乗誤差を取って誤差逆伝搬
    loss = self.loss_fn(current_q, target_q)
    self.optimizer.zero_grad()
    loss.backward()
    self.optimizer.step()

    return loss.item()

対戦相手について

対戦相手については、ルールベースの方策を採用した。ただし、完全にルールベースとすると、学習時に到達可能な盤面が強く限定され特定の状況のみに適合してしまうため、時々ランダムに打たせるようにすることで、到達可能な盤面を広げて、多種多様な盤面に対して学習が進むようにしている。

1.自分が即勝てる列があれば打つ
2.相手が次に勝てる列があれば防ぐ
3.フォーク（1手で2箇所以上リーチ）を狙う
4.相手のフォークを防ぐ
5.打った上に相手が置くと勝たれる列を避ける（トラップ回避）
6.リーチ（2連で両端が空き）を作る手を優先
7.中央寄りの列を優先

おわりに

気を抜くと実際負けてしまうような対戦AIが作れた。

無事にAIに敗北(ま)けることができて大変満足です。