TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

【勉強ノート】不完全情報ゲームのアルゴリズム

不完全情報ゲームのアルゴリズムについて詳しくなりたいと思い、不完全情報ゲームの基本的なアルゴリズムであるCFRについて調べた。

不完全情報ゲームのアルゴリズムは比較的新しいということもあり、日本語の書籍はないため、こちらの大学の講義の資料を参照した。
An Introduction to Counterfactual Regret Minimization

じゃんけんにおける後悔の最小化

CFRの前に、後悔の概念をじゃんけんを例に説明する。

相手の混合戦略が、( 0.4, 0,3, 0.3 ) の場合の最適な混合戦略を、後悔を最小化することによって求める。

混合戦略 ( 0.4, 0,3, 0.3 )は、Rock(グー)、Paper(パー)、Scissors(チョキ)を、それぞれ0.4、0.3、0.3の確率で出す戦略を意味する。
この場合の最適な戦略は、何になるだろうか。

後悔の最小化アルゴリズム

自分が現在の混合戦略から選んだ手の利得(utility)と、他のある手を選んだ場合の利得の差を、後悔と呼ぶ。
後悔 = 他のある手を選んだ場合の利得 - 選んだ手の利得

これを、それぞれ手ごとに求め累積後悔に加算する。
累積後悔(ある手) += 他のある手を選んだ場合の利得 - 選んだ手の利得

累積後悔を使って、現在の混合戦略を決める。
混合戦略は、正の累積後悔の比率によって求める。
つまり、累積後悔が負の場合0として、正の場合はその値を使用して、正の後悔の合計で割った値を求める。

直感的には、選んだ手よりも良い手があれば、その手をより選びやすくしている。

以上を繰り返すことで、後悔を最小とする混合戦略が得られる。

最小の後悔戦略に収束するのは、最終的な混合戦略ではなく、すべての反復の混合戦略の平均戦略になる点に注意が必要である。

個々の反復の後悔と戦略は不安定である。一時的に後悔が負になる手は選択されず、反復中にはそのような状態が起きる。

サンプルコード

上記の講義のページに、Javaで実装されたサンプルコードが提供されている。
http://cs.gettysburg.edu/~tneller/modelai/2013/cfr/RPSTrainer.java

これを実行してみると、

[3.418489010989012E-5, 0.9999614651098901, 4.349999999999999E-6]

という結果が得られた。

混合戦略(0.4, 0.3, 0.3)に対する最適な戦略は、(0, 1, 0)であることを示している。

検証

最適な戦略は(0.3, 0.4, 0.3)ではないか?と思うかもしれない。
混合戦略からランダムにサンプリングすることで確かめてみた。
cfr-cpp/RPS_test.cpp at master · TadaoYamaoka/cfr-cpp · GitHub

10,000,000回繰り返した利得の平均は、0.0999649になる。

混合戦略を(0, 1, 0)から、(0.3, 0.4, 0.3)に変更すると、0.0101261になる。

確かに、混合戦略(0, 1, 0)の方が、平均利得が高くなっている。

相手の混合戦略がナッシュ均衡の場合

相手の混合戦略が、じゃんけんのナッシュ均衡である(1/3, 1/3, 1/3)の場合に、最適な戦略を学習できるか試してみた。
サンプルコードの相手の戦略を以下の通り変更する。

oppStrategy = { 1.0/3, 1.0/3, 1.0/3 }; 

結果は、

[0.07988949151946023, 0.018809190929443522, 0.9013013175510962]

となった。
(1/3, 1/3, /3)とはかけ離れているが、本当だろうか?

サンプルコードを確認すると、getActionの実装が、累積和法になっていた。

    public int getAction(double[] strategy) {
        double r = random.nextDouble();
        int a = 0;
        double cumulativeProbability =  0;
        while (a < NUM_ACTIONS - 1) {
            cumulativeProbability += strategy[a];
            if (r < cumulativeProbability)
                break;
            a++;
        }
        return a;
    }

cumulativeProbability の加算で浮動小数の丸めが発生するため、この実装はよろしくない。
ランダムにも線形合同法が使用されている。

そこで、Walker's alias法で実装されているC++のdiscrete_distributionを使って実装し直してみた。
cfr-cpp/RPSTrainer.cpp at master · TadaoYamaoka/cfr-cpp · GitHub

これを実行すると、

[0.204437, 0.190428, 0.605135]

という結果が得られた。
やはり、じゃんけんのナッシュ均衡(1/3, 1/3, 1/3)にはなっていない。

実は相手の戦略が(1/3, 1/3, 1/3)の場合、どんな戦略であっても平均利得は同じなため、(1/3, 1/3, 1/3)には収束しない。

相手の混合戦略も学習した場合

相手の混合戦略を固定ではなく、同様に後悔の最小化アルゴリズムで混合戦略を学習させた場合、ナッシュ均衡になるか確認してみた。
cfr-cpp/RPSTrainer2.cpp at master · TadaoYamaoka/cfr-cpp · GitHub

実行結果は、

[0.339249, 0.334887, 0.325864]

となり、ナッシュ均衡(1/3, 1/3, 1/3)を学習できている。

まとめ

じゃんけんを例に、後悔の最小化アルゴリズムを実装して、最適な混合戦略を学習できるか確かめた。

次は、講義資料の3章のクーンポーカーの例で、反事実的後悔(Counterfactual Regret)の最小化を試したい。