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