※ChatGPT作、”ポーカーで大損して後悔している人”
概要
市販されているポーカーのソルバー（筆者は購入したことないけど）で最適な混合戦略を計算する際、反実仮想リグレット最小化（CFR: Counterfactual Regret Minimalization）というアルゴリズムが用いられているようである。このアルゴリズムについて、基本的な考え方を紹介しようというのが本稿の趣旨である。
反実仮想リグレット最小化
多腕バンディット問題の稿では、プレイヤーが実際に行動を選択して得られた情報をのみを活用できるものとし、それぞれの行動のリグレットを最小化するように意思決定を行うことで、不完全情報ゲームの最適な意思決定を求めることができるということを述べた。現実には、プレイヤーが実際に行動を選択していないにもかかわらず、その選択をした場合に得られた利得を知ることができる場合もあるだろう。典型的には、じゃんけんやポーカーなど、最終的には対戦相手が選んだ行動とそれに対する結果を知ることができるゲームがそれに該当する。
例えば、テキサスホールデムではリバーにおける特定のハンドで対戦相手のベットにコールした場合、対戦相手の手札を見ることができるため、フォールドした場合の利得も同時に知ることができる。言い換えれば、実際に選択した行動（Factual）で得た利得の他に、実際には選択しなかった行動（Counterfactual）の利得も知ることができる。この実際の行動とは異なる行動をとった場合の利得をすべて計算し、リグレットが最も小さい選択肢を選ぶ確率を高くするように混合戦略を定めることで、この試行を繰り返せば最適な戦略、すなわち、均衡戦略に収束することを期待することができるだろう。これが反実仮想リグレット最小化といわれるアルゴリズムの基本的な考え方である。
多腕バンディット問題では、事後的な最適行動における利得から実際に選択した行動から得られた利得を差し引いた値をリグレットとして定義したが、反実仮想リグレット最小化ではすべての選択肢について、実際には選択しなかった行動（Counterfactual）の利得から混合戦略に基づいて実際に選択した行動（Factual）の利得を差し引いた値をリグレットとして定義する。形式的には、以下のような式で表される。自分の行動を\(\small a\)と表し、対戦相手の行動を\(\small \dot{a}\)と表すと
\[ \small R_i(T) = \frac{1}{T}\sum_{t=1}^T u(a_i,\dot{a}_{\text{mixed}}) – u(a_{\text{mixed}},\dot{a}_{\text{mixed}}) \]
で定義される。お互いに混合戦略を採用しているが、自分が特定の戦略を必ず採用した場合で、かつ、対戦相手が戦略を変えない場合の利得との差をリグレットとして定義する。先ほどのテキサスホールデムの例では
\[ \small \begin{align*} &R_{\text{Call}}(T) = \frac{1}{T}\sum_{t=1}^T u(a_{\text{Call}},\dot{a}_{\text{mixed}}) – u(a_{\text{mixed}},\dot{a}_{\text{mixed}}) \\ &R_{\text{Fold}}(T) = \frac{1}{T}\sum_{t=1}^T u(a_{\text{Fold}},\dot{a}_{\text{mixed}}) – u(a_{\text{mixed}},\dot{a}_{\text{mixed}})
\end{align*} \]
とそれぞれの選択肢の反実仮想リグレットを計算することができる。
この試行のたびに計算できる反実仮想リグレットを用いて、プレイヤーの混合戦略でそれぞれの戦略を選ぶ確率を
\[ \small \begin{align*} &p_{\text{Call}}(T+1) = \frac{\max\{R_{\text{Call}}(T), 0\}}{\max\{R_{\text{Call}}(T), 0\}+\max\{R_{\text{Fold}}(T), 0\}} \\
&p_{\text{Fold}}(T+1) = \frac{\max\{R_{\text{Fold}}(T), 0\}}{\max\{R_{\text{Call}}(T), 0\}+\max\{R_{\text{Fold}}(T), 0\}} \end{align*} \]
と置いて、毎回更新していけば、最終的には一定の値に収束することになるだろう。分母が0である場合は2つの戦略を確率1/2で選択すればよい。この反実仮想リグレットを用いた戦略の更新を自分自身と対戦相手について同時に行うことで、両者の期待反実仮想リグレットを最小化する混合戦略を求めることができる。プレイヤーが二人である場合、この収束した戦略がナッシュ均衡戦略に一致することが数学的に証明されているということであるらしい。上記では、行動の選択肢を2つとしたが複数にした場合にも同様にナッシュ均衡戦略を求めることができる。この場合、各選択肢を選ぶ確率は
\[ \small p_i(T+1) = \frac{\max\{R_i(T), 0\}}{\sum_{j=1}^m\max\{R_j(T), 0\}} \]
と計算すればよい。分母が0である場合は選択肢の数を\(\small |A|=m\)と表して、
\[ \small p_i(T+1) = \frac{1}{|A|} \]
と表現しているようである。
プレイヤーが3人以上の場合
前節の説明で、”プレイヤーが二人である場合”は反実仮想リグレット最小化で求めた戦略がナッシュ均衡戦略に一致することが数学的に証明されているということを述べた。テキサスホールデムはほとんどの場合で多人数のゲームであるから、プレイヤーが3人以上である場合どうなるのかというのが気になるだろう。反実仮想リグレット最小化自体はアルゴリズムとしてプレイヤーが複数の場合についても適用することが可能であるし、収束した戦略を求めることも多くの場合において可能であると推測される。それでは何が問題であるかということであるが、一般的に3人以上の不完全情報ゲームではナッシュ均衡戦略は無数に存在して、一意に決定できないという問題が生じる。言い換えれば、反実仮想リグレット最小化で求められる解はナッシュ均衡戦略である可能性が低くないが、それは無数に存在するナッシュ均衡戦略のうちの一つに過ぎないという形式になる。
例として、じゃんけんを考えるとプレイヤーが2人の場合はナッシュ均衡戦略はグー・パー・チョキを1/3ずつの確率で出すことが唯一のナッシュ均衡戦略であり、この戦略と異なる戦略を用いるプレイヤーはエクスプロイト可能であるということになる。しかし、プレイヤーが3人である場合、各プレイヤーの戦略が非対称なものであるものでナッシュ均衡戦略になる戦略が無数に存在する。例えば、プレイヤー1,2,3がグー・パー・チョキをそれぞれ
\[ \small [p_1^{\text{Rock}},p_1^{\text{Paper}},p_1^{\text{Scissors}}] = [0.4, 0.3, 0.3] \\ \small
[p_2^{\text{Rock}},p_2^{\text{Paper}},p_2^{\text{Scissors}}] = [0.3, 0.4, 0.3] \\
\small [p_3^{\text{Rock}},p_3^{\text{Paper}},p_3^{\text{Scissors}}] = [0.3, 0.3, 0.4] \]
の確率で出す混合戦略を採用していると仮定する。これらの戦略もナッシュ均衡戦略であり、すべてのプレイヤーは他のプレイヤーが戦略を変えない限り、この戦略を変更することで期待利得を上げることができない。もちろん、すべてのプレイヤーがグー・パー・チョキを1/3ずつの確率で出す戦略もナッシュ均衡戦略であるが、これは無数に存在するナッシュ均衡戦略のうちの一つに過ぎないということになるだろう。
以上のことから、プレイヤーが3人以上いる不完全情報ゲームでは”これが唯一無二の最強戦略”というものが存在せず、対戦相手の戦略を読み解き、その裏をかくような戦略（人読み）を採用していく必要があるということになるだろう。しばしば、テキサスホールデムにおけるGTO戦略について過信が過ぎているといった批判をする人たちがいるが、ヘッズアップでない限りにおいては、必ずしもGTO戦略が最適な戦略ではないという意味で、対戦相手の戦略を考慮する必要がないかのような宣伝文句はGTO戦略の誇大広告であるというのが批判の趣旨であるのだろう。実際に、市販されているポーカーのソルバーの多くはプレイヤーが2人である場合の戦略のみしか計算できなかったり、プレイヤーが3人以上いる場合は一定の仮定を置いて計算している（対戦相手の戦略を固定してしまい、厳密にはナッシュ均衡ではない解を求めている）ことが多いようである。
反実仮想リグレット最小化の例題
反実仮想リグレット最小化の例題として簡単なゲームを思いついたので示そう。0～100までの数値が書かれたカード（テキサスホールデムにおける勝利確率をイメージすればよいかもしれない。）がランダム、かつ、重複がないように\(\small n\)人のプレイヤーに1枚ずつ伏せて配られるものとする。\(\small n\)人のプレイヤーのうち最も大きいカードを持っているプレイヤーが勝ちとする。各プレイヤーは他のプレイヤーに知られないように手札の値を確認して、賭ける（ベット）と賭けを降りる（フォールド）を選ぶことができるものとする。すべてのプレイヤーは同時にベットするか、フォールドするかを宣言するものとする。それぞれの状況で利得が以下の表で与えられるものとする。
| ベット勝者 | ベット敗者 | フォールド | |
|---|---|---|---|
| すべてのプレイヤーがフォールド | — | — | 0bb |
| 1人のみがベット、その他フォールド | +(n-1) bb | — | -1bb |
| m人ベット、n-m人フォールド | +\(\small \alpha\)×(m-1)+(n-m) bb | -\(\small \alpha\) bb | -1bb |
-1bbの損失を受け入れることでフォールドを選ぶことができる一方で、賭けに参加する場合は\(\small \alpha > 1\)のチップを支払う必要がある。\(\small \alpha\)はオッズと呼ぶことにする。このとき、配られた手札に応じた最適な戦略（ベット or フォールド）が異なることになるだろう。プレイヤーの人数は最大で10人とする。状態変数は自分の手札\(\small h\)とプレイヤーの人数\(\small n\)のみであり、
\[ \small \pi(s,a), \;a\in \{\text{bet}, \text{fold} \},\;s = \{h,n | h \in \{0, 1 \cdots, 100 \},n \in \{2,3\cdots, 10 \} \} \]
に対応する戦略関数を決定すればよいだろう。このゲームの最適な戦略関数\(\small \pi(s,a)\)を求めよ、というのが問題である。
すべてのプレイヤーは同時に意思決定を宣言するため対称であり、最適な戦略（ナッシュ均衡戦略）はすべてのプレイヤーで共通であると仮定しよう（これは仮定であり、現実には\(\small n>2\)では非対称な均衡がありえるがここでは無視する）。この仮定により、各プレイヤーについて個別の戦略を考える必要がなく、すべてのプレイヤーは同じ戦略関数\(\small \pi(s)\)からベットかフォールドを決定することになる。戦略関数は各意思決定から観測される反実仮想リグレットの平均値を計算し、
\[ \small \begin{align*} &\text{Pr}[\pi(s) = \text{bet}] = \frac{\max\{R_{\text{bet}}(s),0\}}{\max\{R_{\text{bet}}(s),0\}+\max\{R_{\text{fold}}(s),0\}} \\
&\text{Pr}[\pi(s) = \text{fold}] = \frac{\max\{R_{\text{fold}}(s),0\}}{\max\{R_{\text{bet}}(s),0\}+\max\{R_{\text{fold}}(s),0\}} \end{align*} \]
と計算すればよいだろう。具体的なアルゴリズムを記述すると以下の通りである。
- \(\small n\)人のプレイヤーにランダムにカードを配布する。
- 戦略関数のテーブル\(\small \pi_{\text{bet}}[h][n]\)に従って、各プレイヤーのアクション（ベット or フォールド）を決定する。
- カードと決定されたアクションから利得\(\small r_i\)を計算する。
- 各プレイヤーのリグレットを以下の式で計算し、集計値に加算する（仮定からプレイヤーごとに区別する必要がなく、すべてのプレイヤーのリグレットを集計して共通の戦略関数を更新する。）。
\[ \small \begin{align*} &R_{\text{bet}}(h) = \frac{1}{T} \sum_{t=1}^Tr_{i,\text{bet}}(h, t)-r_{i}(h, t) \\ &R_{\text{fold}}(h) = \frac{1}{T} \sum_{t=1}^Tr_{i,\text{fold}}(h, t)-r_{i}(h, t) \end{align*} \]
\(\small r_{i,\text{bet}},r_{i,\text{fold}}\)は戦略関数が出した決定にかからわず、ベットを選択した場合、フォールドを選択した場合の利得である。戦略関数と一致する行動では0であるが、戦略関数と異なる行動では異なる利得が生じる。 - 1.から4.までの手続きをシミュレーション回数分繰り返し、最適な戦略関数を決定する。
このゲームでは、同時に行動を宣言するためブラフのような行動は意味がない。手札の値が一定値以上の場合ベットし、それ以下である場合フォールドするのが最適な戦略になる。\(\small n\)が2～10人について、オッズ\(\small \alpha\)が2,3,4倍の場合における最適な境界値を計算してみよう。pythonで実装したプログラムは以下の通りである。
import random
import math
import copy
class Card:
def __init__(self, rank):
self.rank = rank
class Deck:
#Build a 101-card deck
def __init__(self):
self.cards = []
for i in range(0, 101):
c = Card(i)
self.cards.append(c)
#Draw a random card from the cards remaining in the deck
def draw(self):
idx = random.randrange(0, len(self.cards), 1)
return self.cards.pop(idx)
class Game:
def __init__(self, nPlayers, odds, blind):
self.deck = Deck()
self.nPlayers = nPlayers
self.odds = odds
self.blind = blind
self.hand = []
self.winner = []
def play(self):
self.hand = []
for i in range(0, self.nPlayers):
self.hand.append(self.deck.draw())
#Decide on the winner
max_hand = self.hand[0].rank
self.winner = 0
for i in range(1, self.nPlayers):
if self.hand[i].rank > max_hand:
self.winner = i
max_hand = self.hand[i].rank
def getWinnerAfterAction(self, action):
#Decide on the winner based on actions
idx = -1
for i in range(0, self.nPlayers):
if action[i] == 1:
idx = i
break
if idx == -1:
return -1
max_hand = self.hand[idx].rank
winner = idx
for i in range(idx + 1, self.nPlayers):
if action[i] == 1:
if self.hand[i].rank > max_hand:
winner = i
max_hand = self.hand[i].rank
return winner
def getRewardAfterAction(self, action):
pot = 0
reward = [0] * self.nPlayers
winner = self.getWinnerAfterAction(action)
if winner > -1:
for k in range(0, self.nPlayers):
if action[k] == 1:
pot = pot + self.odds
reward[k] = -self.odds
else:
pot = pot + self.blind
reward[k] = -self.blind
for k in range(0, self.nPlayers):
if action[k] == 1:
if k == winner:
reward[k] += pot
return reward
class RewardStatistics:
nAction = 2
nHand = 101
def __init__(self):
self.trial = 0
self.regret = [[0 for j in range(RewardStatistics.nAction)] \
for i in range(RewardStatistics.nHand)]
def addRewardPure(self, hand, action, reward):
self.regret[hand][action] += reward;
def addRewardMixed(self, hand, action, reward):
self.regret[hand][0] -= reward;
self.regret[hand][1] -= reward;
##action by mixed strategy
def actionMS(self, hand):
regretFold = max(self.regret[hand][0], 0)
regretBet = max(self.regret[hand][1], 0)
if regretFold + regretBet > 0:
threshold = regretFold / (regretFold + regretBet)
else:
threshold = 0.5
if (random.random() < threshold):
return 0;
return 1
def getStrategy(self):
ret = [];
for i in range(0, 101):
regretFold = max(self.regret[i][0], 0)
regretBet = max(self.regret[i][1], 0)
if regretFold + regretBet > 0:
ret.append([i, regretBet / (regretFold + regretBet)])
else:
ret.append([i, 0.5])
return ret
if __name__ == "__main__":
nPlayers = 5
odds = 3
blind = 1
rs = RewardStatistics()
for j in range(0, 100000):
game = Game(nPlayers, odds, blind)
game.play()
##action by mixed strategy
action = []
for k in range(0, nPlayers):
action.append(rs.actionMS(game.hand[k].rank))
## factual reward
reward = game.getRewardAfterAction(action)
for k in range(0, nPlayers):
rs.addRewardMixed(game.hand[k].rank, action[k], reward[k])
##counterfactual regret(fold)
for k in range(0, nPlayers):
actionFold = copy.deepcopy(action)
actionFold[k] = 0
reward = game.getRewardAfterAction(actionFold)
rs.addRewardPure(game.hand[k].rank, 0, reward[k])
##counterfactual regret(bet)
for k in range(0, nPlayers):
actionBet = copy.deepcopy(action)
actionBet[k] = 1
reward = game.getRewardAfterAction(actionBet)
rs.addRewardPure(game.hand[k].rank, 1, reward[k])
strats = rs.getStrategy()
for strat in strats:
print(str(strat[0]) + ',' + str(strat[1]))
プログラムで計算した境界値は大体以下の数値である。手札の値が以下の表の値以上である場合にベットすることが最適な戦略になる。オッズが高くなるほど強い手札が無ければベット出来ないし、人数が多いほどベットするためには強い手札が必要になることが見て取れるだろう。
| n | α=2 | 3 | 4 |
|---|---|---|---|
| 2 | 49 | 65 | 72 |
| 3 | 57 | 70 | 77 |
| 4 | 64 | 74 | 79 |
| 5 | 68 | 76 | 81 |
| 6 | 71 | 78 | 83 |
| 7 | 73 | 80 | 84 |
| 8 | 75 | 82 | 85 |
| 9 | 77 | 83 | 86 |
| 10 | 79 | 84 | 87 |
まとめ
本稿の内容でポーカーのソルバーの仕組みは大枠で理解できたのではないかと思う。一般的なシチュエーションにおけるソルバーの開発は容易ではないだろうし、筆者はやるつもりがないが、テキサスホールデムの特殊な条件における最適戦略を求めるプログラムを開発することはできそうな気がしてきた。これを次回は試してみようと思う。
