「BirdHead」の思考ルーチンを作ってみた。（その3）

昨日はグリーディAIを実装した。

今日からは強化学習を使ってAIを作っていく。

方針

まず、方針について。

強化学習にはいくつかのアルゴリズムがあるけれど、今回はSarsa( $\lambda$ )法を使う。
これは強化学習について学んでみた。（その19） - いものやま。で説明したSarsa法を拡張したもので、価値の差分に対する学習を直前の状態行動対に対してだけでなく、より前の状態行動対にも行わせるようにしたもの。（そのうち取り上げる予定）

そして、関数近似としてはシンプルな線形手法を使う。
まず、そもそも関数近似ってなんやねんって話だけど、状態をそれぞれ個別のものとして扱い、状態とその価値を1対1対応で記憶しているのだと、その数は膨大になるので、メモリがいくらあっても足りないということになる。
そこで、状態とその価値との対応をパラメータを持った関数として表現し、そのパラメータを学習していく手法を、関数近似と呼ぶ。
そのとき、その関数として何を使うかというのでいろいろな方法が考えられ、一つはニューラルネットワーク、あるいはサポートベクターマシン（サポートベクターリグレッション）、最近だと（ニューラルネットワークの一種の）ディープラーニングが使われたりする。
その中で、シンプルに1次関数を使う方法を線形手法と呼ぶ。
線形手法はシンプルな方法ではあるのだけれど、計算も軽く、学習も簡単というメリットがある。
もちろん、所詮線形なので、表現力に限界があるというのはあるのだけれど。

SarsaComクラス

さて、Sarsa( $\lambda$ )法を使うので、このAIをSarsaComとしておく。

//==============================
// BirdHead
//------------------------------
// SarsaCom.swift
//==============================

import Foundation

class SarsaCom: Player {
  // 詳細は以降で
}

特徴ベクトルへの変換

まずは、状態を特徴ベクトルへと変換するメソッドを用意する。

特徴ベクトル $\boldsymbol{\phi}$ というのは、状態 $s \in \mathcal{S}$ を、その状態を表現する特徴 $f \in \mathcal{F}$ （たとえば、手札の2の枚数は何枚だとか、自分はトリックの何番目だとか）ごとの値に変換する写像 $\boldsymbol{\phi} : \mathcal{S} \rightarrow \mathbb{R}^{\mathcal{F}}$ 、あるいは、それによって変換されたあとのベクトル $\boldsymbol{\phi}(s)$ のことをいう。
とくに、特徴 $f \in \mathcal{F}$ が、その特徴に当てはまる/当てはまらないの2択になっているものをバイナリ特徴と呼び、それを1/0で表現する特徴ベクトル $\boldsymbol{\phi} : \mathcal{S} \rightarrow \{0, 1\}^{\mathcal{F}}$ のことを、バイナリ特徴ベクトルと呼ぶ。
（本とはちょっと表現が違う感じもするけど、とりあえずここではこう呼ぶことにする）

SarsaComでは、次のようなバイナリ特徴の集合 $\mathcal{F}$ を考えることにした：

手札に関する特徴の集合
- 手札に2を持っていない
- 手札に2を1枚持っている
- 手札に2を2枚持っている
- 手札に2を3枚以上持っている
- 手札に3を持っていない
- 手札に3を1枚持っている
- 手札に3を2枚持っている
- 手札に3を3枚以上持っている
- ...
- 手札に11を持っていない
- 手札に11を1枚持っている
- 手札に11を2枚持っている
- 手札に11を3枚上持っている
（手札を除いて）残っているカードに関する特徴の集合
- 手札以外に2が残っていない
- 手札以外に2が残っている可能性がある
- 手札以外に3が残っていない
- 手札以外に3が残っている可能性がある
- ...
- 手札以外に11が残っていない
- 手札以外に11が残っている可能性がある
最後にプレイされたカードの組（ディスカードは除く）に関する特徴の集合
- 最後にプレイされたカードの組の1枚目は2
- 最後にプレイされたカードの組の1枚目は3
- ...
- 最後にプレイされたカードの組の1枚目は11
- 最後にプレイされたカードの組の2枚目はない
- 最後にプレイされたカードの組の2枚目は2
- 最後にプレイされたカードの組の2枚目は3
- ...
- 最後にプレイされたカードの組の2枚目は11
- 最後にプレイされたカードの組の3枚目はない
- 最後にプレイされたカードの組の3枚目は2
- 最後にプレイされたカードの組の3枚目は3
- ...
- 最後にプレイされたカードの組の3枚目は11
ポジションに関する特徴の集合
- ポジションは1番目（=リード）
- ポジションは2番目
- ポジションは3番目
- ポジションは4番目
最後のアクションに関する特徴の集合
- ディスカードした
- プレイした

これは、全部で98個のバイナリ特徴の集合になっている。
（4 x 10 + 2 x 10 + 10 + 11 x 2 + 4 + 2 = 98）

もちろん、手札の11の価値とかは、最初の方と最後の方で異なってくるだろうから、実際にはもっと細かく分けたり、あるいは組合せを作った方がいいのだろうけど、とりあえずはこれで。

プレイヤー・ビューをこのバイナリ特徴ベクトルへ変換するメソッドを実装したものが、以下。

  /* NOTE:
   * [ 0:97] feature vector
   * - [ 0:39] hand feature
   *   - [ 0: 3] the number of  2 is (0 / 1 / 2 / 3 or more)
   *   - [ 4: 7]                3
   *   -   ...
   *   - [36:39]               11
   * - [40:59] remaining card feature
   *   - [40:41]  2 is (not left / left) except my hand
   *   - [42:43]  3
   *   -   ...
   *   - [58:59] 11
   * - [60:91] last played cards feature
   *   - [60:69] last played card[0] is (2 / 3 / ... / 11)
   *   - [70:80]                 [1] is (nil / 2 / 3 / ... / 11)
   *   - [81:91]                 [2] 
   * - [92:95] position feature
   *   - [92:95] position is (1 / 2 / 3 / 4)
   * - [96:97] action feature
   *   - [96:97] (discard / play)
   */
  private func toFeature(view: GameInfo.PlayerView, action: Action) -> [Double] {
    let newView = try! view.tryAction(action)

    var feature: [Double] = [Double](count: 98, repeatedValue: 0.0)

    /* hand feature */
    var handCount: [Int: Int] = [Int: Int]()
    for card in Deck.MinCard...Deck.MaxCard {
      handCount[card] = 0
    }
    var i: Int = 0
    while i < newView.hands.count {
      let card = newView.hands[i]

      var j = i + 1
      while (j < newView.hands.count) && (card == newView.hands[j]) {
        j += 1
      }
      handCount[card] = j - i

      i = j
    }
    for (card, count) in handCount {
      let index = (card - Deck.MinCard) * 4 + count
      feature[index] = 1.0
    }

    /* remaining card feature */
    for card in Deck.MinCard...Deck.MaxCard {
      var index = 40 + (card - Deck.MinCard) * 2
      if (newView.usedCardCount[card]! + handCount[card]!) != Deck.CardCount {
        index += 1
      }
      feature[index] = 1.0
    }

    /* last played cards feature */
    var lastPlayedCards: [Int] = []
    for action in newView.actionsInTrick {
      if case .Play(let cards) = action {
        lastPlayedCards = cards
      }
    }
    feature[60 + (lastPlayedCards[0] - Deck.MinCard)] = 1.0
    for i in 1..<GameInfo.PlayMax {
      if i < lastPlayedCards.count {
        let index = 70 + (i - 1) * 11 + 1 + (lastPlayedCards[i] - Deck.MinCard)
        feature[index] = 1.0
      } else {
        let index = 70 + (i - 1) * 11
        feature[index] = 1.0
      }
    }

    /* position feature */
    feature[91 + newView.actionsInTrick.count] = 1.0

    /* action feature */
    if case .Play = action {
      feature[97] = 1.0
    } else {
      feature[96] = 1.0
    }

    return feature
  }

なお、事後状態を扱うので、現在のプレイヤー・ビューにアクションを実行して得られるプレイヤー・ビューに対して、バイナリ特徴ベクトルを作っている。
（事後状態については強化学習について学んでみた。（その21） - いものやま。を参照）

価値の計算

特徴ベクトルへの変換が出来たら、それを使って価値の計算を行う。

線形手法を使う場合、事後状態 $u \in \mathcal{S}$ の価値 $Q_u$ は、特徴に対する重みのパラメータ $\boldsymbol{\theta} \in \mathbb{R}^{\mathcal{F}}$ を使って、次のように計算される：

${ \displaystyle Q_u = \boldsymbol{\theta}^{\mathrm{T}}\boldsymbol{\phi}(u) = \sum_{f \in \mathcal{F}} \theta_f \phi(u)_f }$

よって、次のような実装になる。

  private(set) var weight: [Double]

  // 省略

  private func valueOfFeature(feature: [Double]) -> Double {
    var value: Double = 0.0
    for i in 0..<feature.count {
      value += self.weight[i] * feature[i]
    }
    return value
  }

ここで、特徴に対する重みのパラメータweightがプロパティになっているのは、学習することでこの値を改善していくことになるから。
この値が改善されれば、それに応じて価値の推定も正確になっていく、という仕組み。

今日はここまで！