マルバツゲーム

マルバツゲームを考える。両者が完璧な手を指すと引き分けになる。片方のプレイヤーは、ほぼ完璧なプレイをするが、特定の仕方で誤った手をうつ。このプレイヤーに対して最善手を自動で導き出すにはどうしたら良いか？ というのが、典型的に強化学習が生きる問題設定。同じ相手と何度も対戦することで、最適な行動基準を学習することができる。

  • 盤面 → 勝利確率というテーブルを用意する
    • 勝敗が確定している盤面の値は1 or 0
    • それ以外は0.5に初期化する
  • 実際にプレイを行う
    • 現在の盤面から到達可能な盤面で最善の手を選ぶ
    • ただし、一定の確率で他の手を選ぶ
  • 勝敗がついたあと、テーブルを以下のルールで更新する
    • \[V(S_t) \leftarrow V(S_t) + \alpha (V(S_{t+1}) - V(S_t))\]
    • ここで、\(S_t\)は、\(t\)ターン目の状態の価値
    • 最終ターンは、1 or 0.5 or 0のどれかになるはずなので、そこからbackwardに値が更新されていく

この手順で、任意の相手に対して \(\alpha\)を十分ゆっくりと小さくしていけば、必ずテーブルの値が真の勝利確率に収束することが証明できる。

バックギャモン

上と同じようなアルゴリズム + NNで、バックギャモンで人間の最強プレイヤーに勝てる(Gerry Tesauro, 1992, 1995)。 バックギャモンは、状態数が\(10^{20}\)程度。