不完全情報下のRegret最小化(CFR)の論文を読む
ランニングできず 英語できず
(1) 不完全情報下のRegret最小化(CFR:Counterfactual Regret Minimization)の論文を読む
「An Introduction to Counterfactual Regret Minimization」 http://modelai.gettysburg.edu/2013/cfr/cfr.pdf
現状の強化学習は「完全情報下のReret最小化」と看做せます。
何故なら強化学習は、情報が完全に見え累計した罰則の最小化モデルだからです。
しかしポーカの様な相手の情報が一部見えない強化学習は
「不完全情報下のRegret最小化」となります。このモデルはCFR(反作用的後悔最小化)
と呼ばれています。
現在モデルは下図の様に本格的Porkerゲームのプロに勝つレベルに達しており、
モデルの正しさが実証されています。(Libratusがモデル)
http://triblive.com/local/allegheny/11865933-74/rematch-aaron-aupperlee
この論文はCFRの理論をToy Porkerでのプログラムで解説をしたものでです。
この論文の貴重な点は、下記の様なCFRの理論記述が強化学習に比べ格段に難解である所を
ここで
:累計最大Regret
:自分の最適戦略
:自分以外の戦略
:戦略の価値
:情報で行動を採った戦略
:情報で戦略での方策
プログラムで具体的に解説しています。
現在のプロPorkerではに達する場合が存在しており、この成功は
モデルの高速化と効率化がある程度旨く行っているからです。
本論文ではJavaでのソースコードを解説していますが、C言語で書き直しました。
GitHubに入れました。
https://github.com/mabonki0725/regret_cfr
(2)デモ結果の説明
・ゲームの内容
2人での対戦 カード1~3までの内各々がランダムにカードを取る
大きいカードを持つ方が勝つ
bit と poseが選択でき、bitして勝てば +2点 負ければ -2点
双方がposeの場合、cardを見せ 勝てば +1点 負ければ -1 点
相手がbit時にposeを選ぶと -1 点で負ける
上記のルールでは下記の遷移図になる
配布 -- pose -- pose (開示)
| -- bit -- pose (降りる)
| -- bit (勝負)
- bit -- pose (降りる)
- bit (勝負)
・デモ結果
自分のcardの値と各遷移での次の選択での得点できる価値を示している。
例えば下記の3poseは 自分のカードが3で相手がposeの場合で
自分がposeを選ぶと価値は79%でbitを選ぶと21%となっている。
何故なら、3は最強のカードなので安心してbitしても相手が降りる可能性があり
その場合は1点しか獲得できないからである。ならば確実に得点できるposeの方が
価値が高い
3
action=Pose avrage=0.000491
action=Bet avrage=0.999509
3pose
action=Pose avrage=0.788462
action=Bet avrage=0.211538
3pose - bit
action=Pose avrage=0.153846
action=Bet avrage=0.846154
3bit
action=Pose avrage=0.000076
action=Bet avrage=0.999924
1
action=Pose avrage=0.999848
action=Bet avrage=0.000152
1pose
action=Pose avrage=0.999924
action=Bet avrage=0.000076
1pose - bit
action=Pose avrage=0.999924
action=Bet avrage=0.000076
1bit
action=Pose avrage=0.500000
action=Bet avrage=0.500000
2
action=Pose avrage=0.056895
action=Bet avrage=0.943105
2pose
action=Pose avrage=0.998704
action=Bet avrage=0.001296
2pose - bit
action=Pose avrage=0.998704
action=Bet avrage=0.001296
2bit
action=Pose avrage=0.000078
action=Bet avrage=0.999922
・