AI・機械学習

強化学習で○×ゲーム 第2回|実装例で学ぶQ学習:Tic-Tac-Toe Reverse

11月 10, 2020

強化学習の第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で実装したソースコードを以下の場所で公開しています。

informatix-inc/q-tic-tac-toe: 強化学習(Q学習)でTic-Tac-Toeを攻略する実装例

まとめ

第2回ではTic-Tac-Toe Reverseというゲームを作り、Q学習させた様子を確かめました。Tic-Tac-Toe Reverseのように事前の情報が全くない創作ゲームに対しても、強化学習は威力を発揮するということがわかりました。

より複雑なゲームの場合は\(Q\)関数をニューラルネットワークで実装することで、状態の数が膨大であるという問題を解決することができます。

例えばDeepMindのAlphaGo [2]やAlphaZero [3]はニューラルネットワーク(CNN)で実装された\(Q\)関数と、Monte Carlo木探索という手法を用いて実装されており、AlphaZeroは2017年において囲碁・将棋・チェスそれぞれの最高レベルの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.

記事の評価をお願いします!

-AI・機械学習
-,

© 2020 株式会社インフォマティクス