CFRとは
最適戦略を見つける手法です。
主にポーカーAIに用いられ、プロポーカー４人相手に大差をつけ勝利した"Libratus"がCFRにモンテカルロ法を適用したMCCFRを利用しています。
#どんなアルゴリズムなのか
CFRではゲーム中の選択肢に関してどれを選べば勝率が一番高いかを計算します。
例えば、ポーカーにおいて、あなたは以下の選択肢を持っているとしましょう。
- 賭けに出る
- 賭けを降りる
あなたの手札かブタ（価値なし）なら賭けを降りるべきでしょう。手札がまぁまぁの強さなら、賭けに出ても良いかもしれません。
どちらの選択肢を選べば良いか、CFRではシミュレーションを行い学習します。シミュレーション中、CFRは「効用」と「後悔」に着目します。「効用」とはゲームの勝敗結果を数値で表わしたもので、買ったら1点負けたら−1点という具合に設定できます。「後悔」とは(自分が選択しなかった選択肢の効用)-(自分が選択した選択肢の効用)という式で計算されます。つまり、CFRでは選択しなかった選択肢を選択したらどうなるのかを計算するのです。
学習は以下のステップを踏んで行われます。
- 後悔を計算するプレイヤーを一人選択する。ただし、他のプレイヤーはこれまでの学習結果を利用する。
- 選択されたプレイヤーがゲーム中に選択を求められる場面に達すると、プレイヤーはこれまでの学習結果を利用し選択を行う。
- プレイヤーが選択しなかった選択肢を選択した場合の効用をサンプリングする。
- プレイヤーが選択しなかった選択肢の効用に比例する値を後悔の値とする。
- 後悔の値の累積値を更新し、和１に正規化し新たな戦略とする。
終わりに
今回の説明では多分に省略された部分があります。ですので、大筋を掴んでもらえればと思います。より詳細を知りたい方は、以下に示す今回参考にした文献を参照してください。