tomohxxの日記

麻雀プログラミング

Suphx論文を読んだ感想など

麻雀AI

はじめに

先日、Microsoftが開発した麻雀AI「Suphx」の論文が公開されました。天鳳で最高十段に到達したという強さが麻雀以外のコミュニティでも話題となりました。その強さゆえ麻雀研究界隈に与える影響は大きいと思われます。今後、Microsoftが囲碁でのAlphaZeroのような人間を圧倒するAIを開発するのか注目したいと思います。

さて、本記事ではSuphx論文を読んでアイデアついての簡単なまとめと感想などを記載します。

arxiv.org

Suphx論文のまとめ

1 Intoroduction

麻雀AIの開発は困難である

麻雀AIの開発が困難である理由は3つ。

  1. 麻雀が1局の繰り返しゲームであるので一局での得点が最終的なポイントに直結しないこと。
  2. プレイヤが観測できない情報が多いため意思決定を行うことが難しいこと。
  3. プレイヤがとれる行動(打牌、リーチ、ポン、チー、カンなど)の種類が多く、手番が鳴きにより固定されないのでゲームの木を構築してそれを探索するという手法が使えないこと。
採用した技術について

Suphxには畳み込みニューラルネットワーク(deep convolutional neural network)が用いられ、まず人間の上位プレイヤの牌譜を教師に訓練された。その後、方策勾配法を用いた自己対戦によってさらなる強化が行われている。自己対戦では、前述の困難さを克服するために以下の3つの技術が採用された。

  1. Global reward prediction
  2. Oracle Guiding
  3. parametric Monte-Carlo policy adaption (pMCPA)

2 Overview of Suphx

このセクションではSuphxの意思決定のフローとCNNの構造および特徴量が述べられている。意思決定には行動(打牌、リーチ、チー、ポン、カン)に応じて5つのモデルが使用されている。あがるかどうかの判断はルールベースとなっている。CNNのインプットには牌の組み合わせのデータ(手牌(門前/副露)、ドラ)と牌の順序のデータ(河)、整数データ(持ち点、山の残り枚数)、カテゴリカルデータ(何局目か、親は誰か、何本場か、リーチ棒の数)が用いられた。これらの直接観測できるデータに加えて、どれくらいの点数であがれそうかを表す将来的な特徴量も用いられている。この特徴量は深さ優先探索で相手の存在を無視して計算される(いわゆる一人麻雀)。CNNの構造についてはTable 2とFigure 4, 5を参照。

3 Leaning Algorithm

3.1 Distributed Reinforcement Learning with Entropy Regularization

学習には方策勾配法(policy gradient method)と重点サンプリング(importance sampling)が用いられている。後者は分散環境で学習するために使うテクニックらしい(要勉強)。また、学習のスピードと安定性を調整するために正則化されたエントロピー項が勾配に含まれている。学習の進捗に応じてエントロピー項の係数が調整される。

3.2 Global Reward Prediction

麻雀は局の繰り返しゲームである。一局の得点あるいはゲーム終了時のポイントは強化学習において良いシグナル(訳が微妙)にはならない。なぜなら、うまくプレイできた局、悪かった局が同じポイントを共有すること、そしてオーラスなどで一局の得点をマイナスにすることが必ずしも悪い戦略とは言えないからである。それで強化学習に良いシグナルを与えるために最終的なゲーム報酬(global reward)を各局に適切に割り当てる必要がある。Suphxでは、この報酬の予測器はリカレントニューラルネットワークとなっている(Figure 7を参照)。訓練データには天鳳の牌譜が用いられた。

3.3 Oracle Guiding

麻雀にはプレイヤに隠された情報が多い。この情報なくして良い行動を選択することは難しい。これが麻雀AIを開発するのが困難な基本的な理由である。強化学習を使えば(情報が隠されたままでも)戦略を学習することは可能であるが学習スピードは遅い。そこで学習を速めるためにOracle Guidingが導入された。このテクニックは完全な情報が見えるエージェントから学習を始めて、徐々に見える情報を減らして最終的に通常のエージェントとするものである。見える情報を徐々に減らす方法については式(5)を参照。ここで \delta_tが見える情報を調整する行列である。その行列要素がベルヌーイ分布に従う変数となる、すなわち P(\delta_t (i, j) = 1) = \gamma_t。 \gamma_tは学習開始時には1であるが最終的に0となる。 \gamma_tが0となるとエージェントは隠された情報を利用できなくなり普通のエージェントに移行する。

3.4 Parametric Monte-Carlo Policy Adaption

上位プレイヤの戦略は配牌によって大きく変わる。例えば配牌が良ければ攻撃的にプレイし、配牌が悪ければ保守的にプレイするというように。モンテカルロ木探索(MCTS)は囲碁のようなゲームで確立されたテクニックであるが、残念ながら麻雀のように手番が固定されないゲームでは通常のゲームの木を構築することが難しい。つまりMCTSを直接麻雀に適用することはできない。そこで本研究ではparametiric Monte-Carlo policy adaption (pMCPA)が開発された。pMCPAでは配牌に応じた戦略の調整を以下のように行う。

  1. シミュレーション: 自分の手牌を固定して、対戦相手の手牌と壁牌をランダムに生成する。ここからオフライン環境で訓練された戦略に基づいてゲームを進める。これを繰り返し多数のトラジェクトリ(一連の牌譜)を得る。
  2. 適応: 得られたトラジェクトリを使って戦略を更新する。
  3. 推測: 更新された戦略を使って局をプレイする。

戦略の更新は式(6)に基づく。生成されたトラジェクトリに対して最大の報酬を得るようにパラメータを調整する(たぶん）。注意点として戦略の更新は各局で独立して行われる。つまり更新された戦略は次の局に引き継がれず、次の局ではオフライン環境で訓練された戦略からまた始める。

4 Offline Evaluation

このセクションでは各テクニックのオフライン環境での有効性について議論している。

4.1 Supervised Learning

5つの行動モデルの学習結果について述べられている。モデルは牌譜一致率によって評価された(Table 3を参照)。

4.2 Reinforcement Learning

強化学習の計画について述べられている。

  • SL: 牌譜から学習しただけのエージェント。
  • SL-weak: 訓練されていないSL。他エージェントの評価用。
  • RL-basic: 方策勾配法で訓練された基本バージョンのエージェント。
  • RL-1: RL-basicをglobal reward predictionにより強化したエージェント。
  • RL-2: RL-1をoracle guidingによってさらに強化したエージェント。

Figure 8から前述のテクニックを段階的に導入することで安定段位が上昇していることがわかる。

4.3 Evaluation of Run-Time Policy Adaption

pMCPAの評価について述べられている。

  1. データ生成: 自分の手牌を固定して100Kトラジェクトリを生成する。
  2. 方策適応: 得られた100Kトラジェクトリに対して方策を微調整する。
  3. 調整された方策のテスト: 別に10Kトラジェクトリを生成して調整された方策でプレイする。ここでも自分の手牌は固定される。

ランタイムでの方策適応には時間がかかる。そのため現段階では数百回の初めの局(=東一局？)でのみテストされた。方策適応が用いられたエージェントの(方策適応が用いられていないエージェントに対する)勝率は66%となった。これによりランタイム方策適応の有効性が実証された。

5 Online Evaluation

天鳳の特上卓でプレイした結果について述べられている。成績はTable 4を参照。Suphxは天鳳の特上卓で5760試合プレイし安定段位8.74を記録した。また、他の麻雀AI(爆打、NAGA)と上位プレイヤと成績を比較している。爆打、NAGAの安定段位はそれぞれ6.59と6.64、上位プレイヤの安定段位は7.46である。安定段位の観点ではSuphxは他の麻雀AIや上位プレイヤよりも強いことが明らかになった。

また、Suphxの打ち方の特徴についても述べられている(Table 5)。

  • 低い放銃率(10.06%)。これは天鳳の上位プレイヤに指摘された。
  • 低い4位率(18.7%)。これは高い安定段位を記録する上で重要。

6 Conclusion and Discussions

今までのところSuphxは最強の麻雀AIである。しかし麻雀の持つゲームの複雑さゆえ、まだ多くの改善の余地がある。

  • 好配牌であがるのが容易な局では報酬を戦略に反映させるべきではない。対照的に難しい局であがった場合はより高い報酬が与えられるべきである。つまりゲームの難しさを考慮すべきである。
  • 完全な情報を利用する他のアプローチの実践。1つ目のアプローチはオラクルエージェント(完全な情報が見えるエージェント)と通常のエージェントを同時に訓練し、2つのエージェント間の距離を制限しながらその知識を蒸留する(=見えない情報への依存をなくす？)こと。2つ目のアプローチはオラクルクリティック(oracle critic)を導入すること。これは局単位のフィードバックの代わりに状態レベルの即時のフィードバックを与えることで訓練を加速させる効果がある。
  • ランタイム方策適用を各局開始時だけでなく各プレイヤの打牌直後にも行うようにする。

感想

気になった点を箇条書きで記載します。

  • 打牌モデルの特徴量に深さ優先探索で計算した得点が用いられている

IPSJの論文などでは探索よりも手牌データを画像データのようにエンコードしてCNNにより打牌を選択する事例が多いです。私は専門家ではないので詳しい事情は知りませんが、専門家の間では探索を使わないのが自然なアイデアなのでしょうか。効率的に探索をしようとするとシャンテン数のような麻雀固有の知識を必要とします。これが嫌われているのではないかと推測します。本研究で探索が使われているということは見たままのデータを用いた学習はうまくいかないことを示唆しているのではないかと考えます。

  • Global reward predictionの新規性

最初にこの部分の解説を読んだとき、「期待最終順位でもよいのでは？」と思いました。期待最終順位の概念は爆打の論文(https://www.logos.ic.i.u-tokyo.ac.jp/~mizukami/paper/GPW_paper_2015.pdf)で登場します。本研究では自己対戦での順位を報酬としていないようですが、どちらの手法が効果的なのか気になりました。

この手法は他の不完全情報ゲームでも通用するのではないかと思いました。より詳しい解説が欲しいです。今後の発展に期待しています。

  • parametric Monte-Carlo policy adaption (pMCPA)の効果

素人意見ですが、pMCPAを採用する必要があるのか疑問に思いました。pMCPAを採用する前段階までで「配牌が良ければ攻撃的に打つ」、「配牌が悪ければ守備よりに打つ」という戦略は学習できないのでしょうか。

おわりに

やはりSuphxが天鳳で十段を達成したという事実は今後の麻雀研究界隈やゲームAIの業界に確実に影響を与えると思います。今後、Suphxで採用された手法の中でどれが特に有用だったのか明らかになっていくでしょう。近いうちに例えば将棋におけるボナンザメソッドのような「定番」の手法が確立されるのではないしょうか。そうなれば麻雀AIの研究は加速度的に進むでしょう。今後1~2年の研究動向は特に目が離せないですね。