DeepMindがArxivで発表したDeepNash(R-NaD)がOpenSpielに実装されたので試してみた。
※2022年12月にScienceにも掲載されました。
DeepNash(R-NaD)
DeepNash(R-NaD)は、不完全情報ゲームで探索なしでナッシュ均衡に収束するモデルフリーの深層強化学習アルゴリズムである。
海外で人気があるStrategoで人間のエキスパートレベルに達している。
クーン・ポーカー
キング・クイーン・ジャックの3枚のカードで行う単純なポーカーで、混合戦略ナッシュ均衡の解が解析されている。
プレイヤーには1枚ずつカードが配られ、残り1枚は未使用で、交互にベットかパスかを選択する。
利得表は以下の通りである。最大3手で勝負が付く。
OpenSpiel
DeepMindが開発しているオープンソースの強化学習フレームワークである。
様々なゲームと強化学習アルゴリズムが実装されている。
R-NaDも最近追加された。
クーン・ポーカーでのテストコードも用意されている。
テスト
用意されているテストコードでは、学習の結果は表示されないので、損失と平均報酬、学習した方策を表示するようにコードを追加した。
--- a/open_spiel/python/algorithms/rnad/rnad.py
+++ b/open_spiel/python/algorithms/rnad/rnad.py
@@ -928,6 +928,9 @@ class RNaDSolver(policy_lib.Policy):
"actor_steps": self.actor_steps,
"learner_steps": self.learner_steps,
})
+ logs['rewards'] = timestep['actor']['rewards'][9,:,:].mean(axis=0)
+ logs['states'] = timestep['env']['obs'][0]
+ logs['policy'] = timestep['actor']['policy'][0]
return logs--- a/open_spiel/python/algorithms/rnad/rnad_test.py
+++ b/open_spiel/python/algorithms/rnad/rnad_test.py
@@ -28,8 +28,12 @@ class RNADTest(absltest.TestCase):
def test_run_kuhn(self):
solver = rnad.RNaDSolver(rnad.RNaDConfig(game_name="kuhn_poker"))
- for _ in range(10):
- solver.step()
+ for _ in range(10000):
+ logs = solver.step()
+ data = {}
+ for state, policy in zip(logs['states'], logs['policy']):
+ data[int(state.dot(np.arange(11).T))] = policy
+ print(_, logs['loss'], logs['rewards'], data[2], data[3], data[4])
テスト結果
10000ステップ学習を行った結果、損失と平均報酬、1手目の方策は以下の通りとなった。
損失
平均報酬(移動平均100)
1手目の方策
| カード | アクション | 確率 |
|---|---|---|
| ジャック | パス | 0.824698 |
| ジャック | ベット | 0.175302 |
| クィーン | パス | 0.687148 |
| クィーン | ベット | 0.312852 |
| キング | パス | 0.478646 |
| キング | ベット | 0.521354 |
※プレイヤーは、自分のカードのみで判断することに注意
考察
損失は、500ステップくらいで下がりきっている。
平均報酬は、理論値は、−1/18(≒−0.055)になる。
グラフを見ると、−0.04あたりに収束しており、理論値よりは高めの値になっている。
1000ステップ後に学習された1手目の方策は、キングのベットの確率/ジャックのベットの確率＝2.97となっており、最適戦略の3に近づいている。
しかし、クィーンは常にパスが最適戦略であるが、パスの確率は0.687148で1からは離れている。
まとめ
OpenSpielに実装されたDeepNash(R-NaD)をクーン・ポーカーで試してみた。
結果、最適戦略に近づくことが確認できたが、理論値には収束しなかった。
ただし、モデルの構成（テストコードは中間層2層のMLP）やハイパーパラメータの調整で変わる可能性はある。
DeepNashは、行動空間が広く、手数の長い不完全情報ゲームでも適用できるアルゴリズムであり、適用できるゲームは広そうである。
大会が開催されているガイスターAIにも適用できそうなので、試してみたい。
余談
テストしているときにOpenSpielのR-NaDの実装にバグを発見したので、issueで報告したら修正された。
github.com
