Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
8
Help us understand the problem. What are the problem?
@Intel0tw5727

Microsoftの最強麻雀AI Suphx の論文ざっくり日本語訳(導入と概要まで)

きっかけ

麻雀というドメインを知っているなら、英語論文でも大まかに読めるだろうというたかをくくった安直な考えでまとめていきます。表現のミスとか、読み間違いとかはぜひコメントください。(麻雀の専門用語つかってまとめてます)

1. 導入

ゲーム用の最強AIを作ることは長年いろんな研究者が目指してきており、完全情報型の2人用ゲーム(将棋・チェス・囲碁など)を始めとして、複雑な不完全情報型ゲームへも研究が進んでいる。

麻雀は不完全型情報ゲームの1つだが、研究にあたっては大きな課題がある。まず1つ目には麻雀の勝敗決定がある。

  1. 複雑な点数計算
  2. 複数のラウンドからなす最終順位

上記2つにより1ラウンドの結果が負けたからといって、必ずしもそのゲームの「負け」につながるとは限らない。また麻雀にはアガリのパターンが多く、パターンに対する点数計算がとても複雑である。なので単純にアガればいいというわけではなく、複数ラウンドを通して勝つための勝負手を慎重に選択する必要がある。

2つ目はプレイヤーから見えない情報が多いこと。

麻雀の場合、牌と呼ばれる手札を13個持つ状態から始まるが、それ以外の123枚の情報は見えない状態からスタートする。ゲームが始まり引いては切ってを繰り返しても約70枚ほどしか見えない。そう考えるとポーカーなどに比べて遥かに見えない情報が多く難しいゲームである。

3つ目に麻雀の複雑なルールがあげられる。

シンプルに引いて切ってだけではなく、相手の捨てた牌を奪ってアガリ形をつくる方法が複数種類(ポン・チー・カン)あるため、シンプルなゲームツリーを作ることが難しい。

これらの課題を解決して最強AIであるSuphx(Super Phoenix の略)を構築した。モデルにはCNNをベースとしたニューラルネットワークを用いて学習し、学習モデルに対して強化学習を実施することで更に強くしている。上記課題を解決するために以下の技術を導入している。

  1. Global reward prediction
    • 現在のラウンドと1つ前のラウンドの情報に基づいて、最終的な点数を予測するモデルを構築する。これによって勝ちの可能性を読み、強化学習における意思決定のサポートを行う。
  2. Oracle Agent
    • 学習時に他のプレイヤーが持っている牌や牌山と呼ばれる牌を引く場所の情報を見ることができるエージェントを追加している。これによって学習時には牌の情報をすべて持った状態で学習を行うことができ、エージェントから徐々に情報を取り除いて、最終的には観測することができる情報のみの通常のエージェントに変換する。これによって標準の強化学習よりもより高速に学習をすすめることができた。
  3. pMCPA(parametric Monte-Carlo policy adaptation)
    • 麻雀はゲームが進むたびに観測できる情報が増えていくため、pMCPAを導入することでラウンドの各状況に対応して学習を進める。

これによって最も人気のある競技麻雀プラットフォームである「天鳳」にて十段に到達し、またプレイヤーの強さを表す安定段位においても人間を上回る結果となった。

2. Suphx の概要

このセクションではSuphxの決定フローとモデルに使用されているネットワーク構造と機能について説明する。

2.1 決定フロー

麻雀の複雑なルールに対応するべく表1に示す5つのモデルで構成される。(捨て牌モデル、リーチモデル、チーモデル、ポンモデル、カンモデル)

image.png

また上記モデルに加えて、そのラウンドを勝利するべきか(ロン・ツモ)を判断するルールベースの勝負モデルを採用している。そのルールは以下で判断する。

  • 最終ラウンド(オーラス)でなければ基本的にアガる
  • 最終ラウンドであり、手元の牌で上がれる状況であっても、アガリ宣言後最下位である場合にはアガらない
  • 牌を山から積もってくる場合

    • ツモってきた牌でカン可能な状況の場合に、カンモデルによってカンの有無を決定する。カンをしない場合にはリーチステップに進む。
      • 暗槓できる場合は、暗槓を実施して、通常の牌を山からツモるフェーズに戻る。
      • 加槓したあと、他のプレイヤーがロンと宣言しなければ、通常の牌を山からツモるフェーズに戻る。
    • ツモってきた牌でリーチが可能な場合には、リーチモデルによってリーチの可否を決定する。リーチをしない場合は通常の牌を山からツモるフェーズに戻る。
    • 通常の牌を山からツモるフェーズでは、捨てる牌を選択する。牌山がなくなったらラウンド終了。

image.png

2.2 モデル構造と特徴

CNNは深層学習の中でも表現力が強く、チェスや囲碁や将棋といったゲームでも検証されていることからSuphxもCNNを利用している。

ただし囲碁やチェスのようなボードゲームとは異なり、画像の形式で入力するのではなく、入力された情報を畳み込み学習できるチャンネルへ変換するためのものである。麻雀の状態には以下の種類の情報が含まれる。

image.png

  1. プレイヤーの持つ牌(Private tiles on hand)
  2. 捨て牌(Discards)
  3. 4人のプレイヤーの累積ラウンドスコアと自風(東南西北)
  4. 現在の局(round ID)、牌の残り枚数(dealer)、本場数(count of repeat dealer)、リーチ棒の数

(画像説明にはないけど、ドラ表示牌(Dora indicator)、鳴いた牌(Melds)、リーチ宣言牌(Waiting)、ユーザー段位(level)も含まれる)

日本式麻雀は34種類の牌が4つずつあるので、プレイヤーの持つ牌を表現するには34 * 4のチャンネルで表現される(図3)。また各チャンネルは0か1のいずれかで表現される。

image.png

上記の表現からは、手牌から牌を捨てて山から牌を引き、勝つ確率とラウンドのスコアを示す。14枚の牌で構成されるアガリ形は4面子1アタマなので、面子が89種類、アタマが34種類あるため、これらの組み合わせをすべて列挙していくことが難しい。そのため計算の複雑さを軽減するため、先読みの特徴を抽出する際に簡略化を行う。

  1. 可能性のあるアガリ形を見つけるために深さ優先探索を実施する
  2. 対戦相手の行動を無視して、自分の手牌のツモと切る牌のみを考慮する

この単純化によって先読みできる100以上の特徴量が得られる。例えばある特徴はイーシャンテンからテンパイするように牌を切り、アガリ牌をツモれる(ロンできる)と仮定した予測をすることで、12000点が獲得できるような予測を行う。

Suphxでは入力層と出力層を除いて、すべての5つのモデルで同様のネットワークを使用している(表2, 図4, 図5)。捨て牌モデルは34個のユニークな牌に対応する34個の出力をもっているが、副露モデル(ポン・カン・チー)やリーチモデルは実施するか否かに対応する2つの出力ニューロンしか持たない。副露モデルの入力には状態情報と先読み機能に加えて、どのような牌がきたら副露を実施するかという情報も含まれている。

image.png

今回のSuphxのモデルにはプーリング層が含まれていない。なぜならチャンネルの各列1つ1つが意味を持っているため、プーリングすることは情報を失ってしまうことになってしまうから。

次の目標

3章の学習アルゴリズム と4章のオフライン評価 を訳しながらまとめます。
(3章の理解でクタクタになってしまったので、次は3章のみです)

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
8
Help us understand the problem. What are the problem?