強化学習の第1回ではTic-Tac-Toe（三目並べ、○×ゲーム）というゲームでQ学習の動作を見ました。
Tic-Tac-Toeは強化学習を使わなければ解けないわけではなく、人間が少し考えれば最善の戦略を見つけることができます。
今回はTic-Tac-Toeに少し変更を加えたTic-Tac-Toe Reverseというゲームを創作して、Q学習で攻略する様子を見てみます。
目次
Tic-Tac-Toe Reverse
Tic-Tac-Toe Reverseは、Tic-Tac-Toeの基本ルールに「書き込んだマスの周囲8マスの○と×の状態を反転する」というルールを追加したゲームです。
通常のTic-Tac-Toeは、相手のマークが2つ並んだらその先を止めるという方針が見えやすいのですが、反転のルールを入れることで人間の直感では形勢が分かりづらくなるような効果を与えています。
ただ、これだけではまだ最善手が簡単に見つかってしまうので（複雑ですが少し考えると後手必勝になることがわかります）、更にパス可能のルールを追加しました。
ルールの詳細は以下のとおりです。
Tic-Tac-Toe Reverse
Tic-Tac-Toe Reverseのルールを以下のように定めます。
- 盤面は縦横3マスずつの9マス
- 最初は全てのマスが空の状態
- 先手は×を、後手は○を交互に空のマスに書き込んでいく
- 書き込んだマスの周囲8マスの○と×の状態を反転する
- パス可能。ただし、相手がパスした直後のパスは不可能。初手のパスも不可能
- 自分のマークを縦横斜めのいずれか一列で3つ並べた方が勝ち
- 同時に自分と相手のマークが一列に3つ並んだ場合は引き分け
- 勝敗が決せずに9マス全てが埋まったら引き分け
図1. Tic-Tac-Toe Reverseの動きの例
実験
前回同様、パラメーター\(\gamma=0.9, \alpha=0.1, \varepsilon=0.5\)で同じエージェント同士の10万回のゲームで学習しました。
以下のグラフはランダムなエージェントと1000ゲーム前のエージェントそれぞれとの対戦結果です。
青が勝ち、橙が引き分け、緑が負けです。
図2: 実験結果
学習の初期の段階で既にランダムエージェントには後手でも先手でもほとんど勝てるようになっています。
より細かく見ると、後手の場合は学習7万ゲーム以降は100%勝っており、先手の場合は6万ゲーム以降は勝率97.5%以上で安定していますが、負けがなくなることもありませんでした。
図3: 実験結果(拡大)
過去のエージェントとの対戦はわかりやすく、学習の初期を除いて先手が負け・後手が勝ちの結果になりました。
この結果を見る限り、どうやらこのゲームは互いに最善手を取った場合、後手が必勝になるようです。
ソースコード
今回もPythonで実装したソースコードを以下の場所で公開しています。
（Github）informatix-inc/q-tic-tac-toe: 強化学習(Q学習)でTic-Tac-Toeを攻略する実装例
まとめ
今回はTic-Tac-Toe Reverseというゲームを作り、Q学習させた様子を確かめました。
強化学習は、Tic-Tac-Toe Reverseのように事前情報がない創作ゲームに対しても威力を発揮することがわかりました。
より複雑なゲームの場合は\(Q\)関数をニューラルネットワークで実装することで、状態の数が膨大である問題を解決できます。
例えばDeepMindのAlphaGo [2]やAlphaZero [3]はニューラルネットワーク（CNN）で実装された\(Q\)関数と、Monte Carlo木探索という手法を用いて実装されており、AlphaZeroは2017年において囲碁・将棋・チェスそれぞれの最高レベルのAIを特定条件下で破った実績を残しています。
物体検出などAI機械学習を活用したシステムの構築に関するご相談（無料）を承っています
参考文献
[1] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press A Bradford Book, 2018.
[2] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel & Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature volume 529, pages484–489, 2016.
[3] David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy Lillicrap, Karen Simonyan, Demis Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 07 Dec 2018: Vol. 362, Issue 6419, pp. 1140-1144, 2018.
