#

信息不完整（CFR）游戏中的遗憾最小化

论文《信息不完整的游戏中的遗憾最小化》介绍了反事实的遗憾，以及如何利用通过自我游戏最大限度地减少反事实遗憾来达到纳什平衡。该算法称为反事实遗憾最小化（CFR）。

论文《在广泛游戏中尽量减少遗憾的蒙特卡洛抽样》介绍了蒙特卡洛反事实遗憾最小化（MCCFR），我们在其中从游戏树中进行采样并估计遗憾。

我们试图让我们的Python实现像教程一样易于理解。我们在一个名为 Kuhn poker 的非常简单的不完美信息游戏上运行它。

推特话题

简介

我们通过机会抽样（CS）实施了蒙特卡洛反事实遗憾最小化（MCCFR）。它通过尝试所有玩家动作来反复探索游戏树的一部分，但采样机会事件。机会事件就像发牌一样；每次迭代都会对它们进行一次采样。然后，它会计算每个动作遵循当前策略而不是采取该操作的遗憾。然后，它会根据这些遗憾更新策略，使用遗憾匹配进行下一次迭代。最后，它计算整个迭代期间策略的平均值，如果我们进行了足够的迭代，则该平均值与纳什均衡非常接近。

我们将首先介绍数学符号和理论。

玩家

玩家用表示 $i \in N$ ，其中 $N$ 是玩家集合。

历史

历史 $h \in H$ 是包括偶然事件在内的一系列动作， $H$ 是所有历史的集合。

$Z \subseteq H$ 是一组终端历史记录（游戏结束）。

行动

操作 $a$ ， $A (h) = a : (h, a) \in H$ 其中 $h \in H$ 是非终端历史记录。

信息集 $I_{i}$

$I_{i} \in I_{i}$ 为玩家 $i$ 设置的信息与历史记录类似， $h \in H$ 但仅包含玩家可见的动作 $i$ 。也就是说，历史记录 $h$ 将包含动作/事件，例如发给对方玩家的牌，而 $I_{i}$ 不会有。

$I_{i}$ 被称为玩家的信息分区 $i$ 。

$h \in I$ 是属于给定信息集的所有历史记录的集合；也就是说，所有这些历史在玩家眼中看起来都是一样的。

策略

玩家的策略 $i$ ， $σ_{i} \in Σ_{i}$ 是对动作的分布 $A (I_{i})$ ，其中 $Σ_{i}$ 是玩家所有策略的集合 $i$ 。 $t$ 第-th 次迭代的策略用表示 $σ^{t}_{i}$ 。

策略被定义为针对给定信息集采取行动的 $a$ 概率 $I$ ，

$σ_{i} (I) (a)$

$σ$ 是策略配置文件，由所有玩家的策略组成 $σ_{1}, σ_{2}, \dots$

$σ_{- i}$ 是所有玩家的策略 $σ_{i}$

历史概率

$π^{σ} (h)$ 是 $h$ 使用策略配置文件进入历史记录的概率 $σ$ 。 $π^{σ} (h)_{- i}$ 是在没有玩家贡献 $h$ 的情况下到达 $i$ 的概率；即玩家采取 $i$ 了要遵循的动作 $h$ 概率为 $1$ 。

$π^{σ} (h)_{i}$ 是仅通过玩家的贡献达到目标 $h$ $i$ 的概率。也就是说， $π^{σ} (h) = π^{σ} (h)_{i} π^{σ} (h)_{- i}$

达到信息集的概率 $I$ 是 $π^{σ} (I) = h \in I \sum π^{σ} (h)$

公用事业（还清）

终端实用程序是玩家 $i$ 对终端历史记录的实用程序（或回报） $h$ 。

$u_{i} (h)$ 在哪里 $h \in Z$

$u_{i} (σ)$ 是具有策略配置文件的玩家 $i$ 的预期效用（回报） $σ$ 。

$u_{i} (σ) = h \in Z \sum u_{i} (h) π^{σ} (h)$

纳什均衡

纳什均衡是一种状态，在这种状态下，任何参与者都无法仅通过改变策略来增加预期的效用（或回报）。

对于两个参与者来说，纳什均衡是一种策略配置文件，其中

u_{1} (σ) u_{2} (σ) \geq m a x_{σ_{1}^{'} \in Σ_{1}} u_{1} (σ_{1}^{'}, σ_{2}) \geq m a x_{σ_{2}^{'} \in Σ_{2}} u_{1} (σ_{1}, σ_{2}^{'})

$ϵ$ -纳什均衡是，

u_{1} (σ) + ϵ u_{2} (σ) + ϵ \geq m a x_{σ_{1}^{'} \in Σ_{1}} u_{1} (σ_{1}^{'}, σ_{2}) \geq m a x_{σ_{2}^{'} \in Σ_{2}} u_{1} (σ_{1}, σ_{2}^{'})

遗憾最小化

遗憾的是玩家因为没有遵循最佳策略或采取最佳行动而没有获得的效用（或回报）。

玩家的平均总体遗憾 $i$ 是在所有 $T$ 回合迭代中都没有遵循最佳策略的平均遗憾。

$R_{i}^{T} = \frac{1}{T} m a x_{σ_{i}^{*} \in Σ_{i}} t = 1 \sum T (u_{i} (σ_{i}^{*}, σ^{t}_{- i}) - u_{i} (σ^{t}))$

迭代中所有玩家的策略配置文件在哪里 $σ^{t}$ $t$ ，以及

$(σ_{i}^{*}, σ^{t}_{- i})$

是将玩家的策略替换为 $i$ 的策略配置文件 $σ^{t}$ $σ_{i}^{*}$ 。

平均策略是所有回合中遵循的策略的平均值 $I \in I, a \in A (I)$

$\overset{σ}{ˉ}_{i}^{T} (I) (a) = \frac{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I ) σ ^{t} ( I ) ( a )}{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I )}$

这是没有使用最佳策略的卑鄙遗憾。

如果 $R_{i}^{T} < ϵ$ 对所有玩家来说都 $\overset{σ}{ˉ}_{i}^{T} (I) (a)$ 是 $2 ϵ$ -Nash 均衡。

R_{i}^{T} R_{i}^{T} < ϵ = \frac{1}{T} m a x_{σ_{i}^{*} \in Σ_{i}} t = 1 \sum T (u_{i} (σ_{i}^{*}, σ^{t}_{- i}) - u_{i} (σ^{t})) = \frac{1}{T} m a x_{σ_{i}^{*} \in Σ_{i}} t = 1 \sum T u_{i} (σ_{i}^{*}, σ^{t}_{- i}) - \frac{1}{T} t = 1 \sum T u_{i} (σ^{t}) < ϵ

$u_{1} = - u_{2}$ 因为这是一场零和博弈，所以我们可以加 $R_{1}^{T}$ $R_{i}^{T}$ 和，第二个术语将被取消。

2 ϵ > \frac{1}{T} m a x_{σ_{1}^{*} \in Σ_{1}} t = 1 \sum T u_{1} (σ_{1}^{*}, σ^{t}_{- 1}) + \frac{1}{T} m a x_{σ_{2}^{*} \in Σ_{2}} t = 1 \sum T u_{2} (σ_{2}^{*}, σ^{t}_{- 2})

一组策略的公用事业平均值等于平均策略的效用。

$\frac{1}{T} t = 1 \sum T u_{i} (σ^{t}) = u_{i} (\overset{σ}{ˉ}^{T})$

因此，

2 ϵ > m a x_{σ_{1}^{*} \in Σ_{1}} u_{1} (σ_{1}^{*}, \overset{σ}{ˉ}_{- 1}^{T}) + m a x_{σ_{2}^{*} \in Σ_{2}} u_{2} (σ_{2}^{*}, \overset{σ}{ˉ}_{- 2}^{T})

从定义来看 $m a x$ ， $m a x_{σ_{2}^{*} \in Σ_{2}} u_{2} (σ_{2}^{*}, \overset{σ}{ˉ}_{- 2}^{T}) \geq u_{2} (\overset{σ}{ˉ}^{T}) = - u_{1} (\overset{σ}{ˉ}^{T})$

那么，

2 ϵ u_{1} (\overset{σ}{ˉ}^{T}) + 2 ϵ > m a x_{σ_{1}^{*} \in Σ_{1}} u_{1} (σ_{1}^{*}, \overset{σ}{ˉ}_{- 1}^{T}) + - u_{1} (\overset{σ}{ˉ}^{T}) > m a x_{σ_{1}^{*} \in Σ_{1}} u_{1} (σ_{1}^{*}, \overset{σ}{ˉ}_{- 1}^{T})

这是 $2 ϵ$ 纳什均衡。同样，你可以为超过 2 名玩家的游戏进行证明。

因此，我们需要最小化 $R_{i}^{T}$ 才能接近纳什均衡。

反事实的遗憾

如果@@

玩家 $i$ 尝试到达 $I$ （采取了行动）， $i$ 则反事实值 $v_{i} (σ, I)$ 是玩家的预期效用导致 $I$ 的概率为 $1$ ）。

$v_{i} (σ, I) = z \in Z_{I} \sum π^{σ_{- i}} (z [I]) π^{σ} (z [I], z) u_{i} (z)$

wh $Z_{I}$ ere 是可从中访问的终端历史记录集 $I$ ，并且 $z [I]$ 是 $z$ up 的前缀 $I$ 。 $π^{σ} (z [I], z)$ 是从到达 z 的概率 $z [I]$ 。

直接的反事实遗憾是，

$R_{i, i mm}^{T} (I) = m a x_{a \in A I} R_{i, i mm}^{T} (I, a)$

在哪里

$R_{i, i mm}^{T} (I) = \frac{1}{T} t = 1 \sum T (v_{i} (σ^{t} ∣_{I \to a}, I) - v_{i} (σ^{t}, I))$

其中 $σ ∣_{I \to a}$ 是修改为始终 $a$ 在信息集中采取行动的策略配置文件 $σ$ $I$ 。

本文证明（定理3），

$R_{i}^{T} \leq I \in I \sum R_{i, i mm}^{T, +} (I)$ 在哪里 $R_{i, i mm}^{T, +} (I) = m a x (R_{i, i mm}^{T} (I), 0)$

遗憾的配对

该策略是使用后悔匹配计算得出的。

对每个信息集和行动对的遗憾 $R_{i}^{T} (I, a)$ 仍然存在，

r_{i}^{t} (I, a) R_{i}^{T} (I, a) = v_{i} (σ^{t} ∣_{I \to a}, I) - v_{i} (σ^{t}, I) = \frac{1}{T} t = 1 \sum T r_{i}^{t} (I, a)

策略是用遗憾匹配来计算的，

σ_{i}^{T + 1} (I) (a) = ⎩ ⎨ ⎧ \frac{R _{i}^{T, +} ( I , a )}{\sum _{a^{'} \in A (I)} R _{i}^{T, +} ( I , a ^{'} )}, \frac{1}{∣ A ( I )∣}, i f \sum_{a^{'} \in A (I)} R_{i}^{T, +} (I, a^{'}) > 0 o t h erw i se

在哪里 $R_{i}^{T, +} (I, a) = m a x (R_{i}^{T} (I, a), 0)$

这篇论文《信息不完整的游戏中的遗憾最小化》论文证明，如果根据上述方程式 $R_{i}^{T}$ 选择策略，则与 $\frac{1}{T}$ ，因此达到 $ϵ$ -纳什均衡。

蒙特卡洛 CFR (MCCFR)

计算 $r_{i}^{t} (I, a)$ 需要在每次迭代时扩展完整的游戏树。

论文《在广泛游戏中尽量减少遗憾的蒙特卡洛抽样》表明，我们可以从游戏树中进行采样并估计遗憾。

$Q = Q_{1}, \dots, Q_{r}$ 是 $Z$ ( $Q_{j} \subseteq Z$ ) 的一组子集，我们在迭代 $Q_{j}$ 中只查看单个块。所有子集的联合 spans $Z$ ( $Q_{1} \cap \dots \cap Q_{r} = Z$ )。 $q_{j}$ 是选取区块的概率 $Q_{j}$ 。

$q (z)$ 是当前迭代 $z$ 中选取的概率；即 $q (z) = \sum_{j : z \in Q_{j}} q_{j}$ -where $q_{j}$ 的总和 $z \in Q_{j}$ 。

然后我们得到区块的反事实值采样 $j$ ，

$\tilde{v} (σ, I ∣ j) = z \in Q_{j} \sum \frac{1}{q ( z )} π^{σ_{- i}} (z [I]) π^{σ} (z [I], z) u_{i} (z)$

这篇论文表明

$E_{j \sim q_{j}} [\tilde{v} (σ, I ∣ j)] = v_{i} (σ, I)$

用一个简单的证据。

因此，我们可以对游戏树的一部分进行采样并计算遗憾。我们计算遗憾的估计值

$\tilde{r}_{i}^{t} (I, a) = \tilde{v}_{i} (σ^{t} ∣_{I \to a}, I) - \tilde{v}_{i} (σ^{t}, I)$

然后用它来更新 $R_{i}^{T} (I, a)$ 和计算每次迭代 $σ_{i}^{T + 1} (I) (a)$ 的策略。最后，我们计算整体平均策略 $\overset{σ}{ˉ}_{i}^{T} (I) (a)$ 。

这里有一个库恩扑克实现，可以在库恩扑克上试用CFR。

让我们深入研究一下代码！

328from typing import NewType, Dict, List, Callable, cast
329
330from labml import monit, tracker, logger, experiment
331from labml.configs import BaseConfigs, option

#

一个玩家 $i \in N$ $N$ ，玩家集合在哪里

334Player = NewType('Player', int)

#

操作 $a$ ， $A (h) = a : (h, a) \in H$ 其中 $h \in H$ 是非终端历史记录

336Action = NewType('Action', str)

#

历史

历史 $h \in H$ 是包括偶然事件在内的一系列动作， $H$ 是所有历史的集合。

这个类应该使用游戏特定的逻辑进行扩展。

339class History:

#

无论是终端历史；即游戏结束。 $h \in Z$

351    def is_terminal(self):

#

356        raise NotImplementedError()

#

终端历史记录 $i$ 的播放器实用程序。 $u_{i} (h)$ 在哪里 $h \in Z$

358    def terminal_utility(self, i: Player) -> float:

#

364        raise NotImplementedError()

#

获取当前玩家，用表示 $P (h)$ ，其中 $P$ 称为玩家函数。

如果 $P (h) = c$ 这意味着当前事件是偶然 $c$ 事件。比如发牌，或在扑克中打开普通牌。

366    def player(self) -> Player:

#

373        raise NotImplementedError()

#

下一步是否是机会步骤；比如发一张新牌。 $P (h) = c$

375    def is_chance(self) -> bool:

#

380        raise NotImplementedError()

#

在什么时候抽样机会 $P (h) = c$ .

382    def sample_chance(self) -> Action:

#

386        raise NotImplementedError()

#

在历史记录中添加操作。

388    def __add__(self, action: Action):

#

392        raise NotImplementedError()

#

获取当前玩家的信息集

394    def info_set_key(self) -> str:

#

398        raise NotImplementedError

#

为当前玩家创建新的信息集

400    def new_info_set(self) -> 'InfoSet':

#

404        raise NotImplementedError()

#

人类可读的表示

406    def __repr__(self):

#

410        raise NotImplementedError()

#

信息集 $I_{i}$

413class InfoSet:

#

标识信息集的唯一密钥

421    key: str

#

$σ_{i}$ ，玩家的策略 $i$

423    strategy: Dict[Action, float]

#

对没有采取每项行动感到非常遗憾 $A (I_{i})$ ，

\tilde{r}_{i}^{t} (I, a) R_{i}^{T} (I, a) = \tilde{v}_{i} (σ^{t} ∣_{I \to a}, I) - \tilde{v}_{i} (σ^{t}, I) = \frac{1}{T} t = 1 \sum T \tilde{r}_{i}^{t} (I, a)

我们坚持 $T R_{i}^{T} (I, a)$ 而不是 $R_{i}^{T} (I, a)$ 因为计算策略时 $\frac{1}{T}$ 术语无论如何都会被取消 $σ_{i}^{T + 1} (I) (a)$

438    regret: Dict[Action, float]

#

我们维持累积策略 $t = 1 \sum T π_{i}^{σ^{t}} (I) σ^{t} (I) (a)$ 来计算整体平均策略

$\overset{σ}{ˉ}_{i}^{T} (I) (a) = \frac{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I ) σ ^{t} ( I ) ( a )}{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I )}$

445    cumulative_strategy: Dict[Action, float]

#

初始化

447    def __init__(self, key: str):

#

451        self.key = key
452        self.regret = {a: 0 for a in self.actions()}
453        self.cumulative_strategy = {a: 0 for a in self.actions()}
454        self.calculate_strategy()

#

行动 $A (I_{i})$

456    def actions(self) -> List[Action]:

#

460        raise NotImplementedError()

#

从保存的字典中加载信息集

462    @staticmethod
463    def from_dict(data: Dict[str, any]) -> 'InfoSet':

#

467        raise NotImplementedError()

#

将信息集保存到字典中

469    def to_dict(self):

#

473        return {
474            'key': self.key,
475            'regret': self.regret,
476            'average_strategy': self.cumulative_strategy,
477        }

#

从保存的字典中加载数据

479    def load_dict(self, data: Dict[str, any]):

#

483        self.regret = data['regret']
484        self.cumulative_strategy = data['average_strategy']
485        self.calculate_strategy()

#

计算策略

使用后悔匹配计算当前策略。

σ_{i}^{T + 1} (I) (a) = ⎩ ⎨ ⎧ \frac{R _{i}^{T, +} ( I , a )}{\sum _{a^{'} \in A (I)} R _{i}^{T, +} ( I , a ^{'} )}, \frac{1}{∣ A ( I )∣}, i f \sum_{a^{'} \in A (I)} R_{i}^{T, +} (I, a^{'}) > 0 o t h erw i se

在哪里 $R_{i}^{T, +} (I, a) = m a x (R_{i}^{T} (I, a), 0)$

487    def calculate_strategy(self):

#

$R_{i}^{T, +} (I, a) = m a x (R_{i}^{T} (I, a), 0)$

506        regret = {a: max(r, 0) for a, r in self.regret.items()}

#

$a^{'} \in A (I) \sum R_{i}^{T, +} (I, a^{'})$

508        regret_sum = sum(regret.values())

#

如果 $\sum_{a^{'} \in A (I)} R_{i}^{T, +} (I, a^{'}) > 0$ ，

510        if regret_sum > 0:

#

$σ_{i}^{T + 1} (I) (a) = \frac{R _{i}^{T, +} ( I , a )}{\sum _{a^{'} \in A (I)} R _{i}^{T, +} ( I , a ^{'} )}$

513            self.strategy = {a: r / regret_sum for a, r in regret.items()}

#

否则，

515        else:

#

$∣ A (I)∣$

517            count = len(list(a for a in self.regret))

#

$σ_{i}^{T + 1} (I) (a) = \frac{1}{∣ A ( I )∣}$

520            self.strategy = {a: 1 / count for a, r in regret.items()}

#

获取平均策略

$\overset{σ}{ˉ}_{i}^{T} (I) (a) = \frac{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I ) σ ^{t} ( I ) ( a )}{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I )}$

522    def get_average_strategy(self):

#

$t = 1 \sum T π_{i}^{σ^{t}} (I) σ^{t} (I) (a)$

531        cum_strategy = {a: self.cumulative_strategy.get(a, 0.) for a in self.actions()}

#

$t = 1 \sum T π_{i}^{σ^{t}} (I) = a \in A (I) \sum t = 1 \sum T π_{i}^{σ^{t}} (I) σ^{t} (I) (a)$

535        strategy_sum = sum(cum_strategy.values())

#

如果 $\sum_{t = 1}^{T} π_{i}^{σ^{t}} (I) > 0$ ，

537        if strategy_sum > 0:

#

$\overset{σ}{ˉ}_{i}^{T} (I) (a) = \frac{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I ) σ ^{t} ( I ) ( a )}{\sum _{t = 1}^{T} π _{i}^{σ^{t}} ( I )}$

541            return {a: s / strategy_sum for a, s in cum_strategy.items()}

#

否则，

543        else:

#

$∣ A (I)∣$

545            count = len(list(a for a in cum_strategy))

#

$\overset{σ}{ˉ}_{i}^{T} (I) (a) = \frac{1}{∣ A ( I )∣}$

548            return {a: 1 / count for a, r in cum_strategy.items()}

#

人类可读的表示

550    def __repr__(self):

#

554        raise NotImplementedError()

#

反事实遗憾最小化 (CFR) 算法

我们进行机会采样（CS），其中对所有机会事件（节点）进行采样，并探索所有其他事件（节点）。

我们可以忽略该术语， $q (z)$ 因为它对所有终端历史都是相同的，因为我们正在进行机会抽样，并且在计算策略时它会被抵消（在分子和分母中很常见）。

557class CFR:

#

$I$ 所有信息集的集合。

570    info_sets: Dict[str, InfoSet]

#

create_new_history 创建新的空白历史记录
epochs 是要训练的迭代次数 $T$
n_players 是玩家的数量

572    def __init__(self, *,
573                 create_new_history: Callable[[], History],
574                 epochs: int,
575                 n_players: int = 2):

#

581        self.n_players = n_players
582        self.epochs = epochs
583        self.create_new_history = create_new_history

#

包含所有信息 $I$ 集合的字典

585        self.info_sets = {}

#

分析追踪器

587        self.tracker = InfoSetTracker()

#

返回给 $I$ 定历史记录中当前玩家的信息集 $h$

589    def _get_info_set(self, h: History):

#

593        info_set_key = h.info_set_key()
594        if info_set_key not in self.info_sets:
595            self.info_sets[info_set_key] = h.new_info_set()
596        return self.info_sets[info_set_key]

#

走树

此函数遍历游戏树。

h 是当前的历史 $h$
i 是我们正在计算后悔 $i$ 的那个玩家
pi_i 是 $π_{i}^{σ^{t}} (h)$

pi_neg_i 是

π_{- i}^{σ^{t}} (h)

它返回预期的实用程序，对于历史记录， $h$ $z \in Z_{h} \sum π^{σ} (h, z) u_{i} (z)$ 其中 $Z_{h}$ 是一组带有前缀的终端历史记录 $h$

在行走发球台时，它会更新总的遗憾 $R_{i}^{T} (I, a)$ 。

598    def walk_tree(self, h: History, i: Player, pi_i: float, pi_neg_i: float) -> float:

#

如果是终端历史记录，则 $h \in Z$ 返回终端实用程序 $u_{i} (h)$ 。

619        if h.is_terminal():
620            return h.terminal_utility(i)

#

如果是偶然事件 $P (h) = c$ 示例 a 然后转到下一步。

622        elif h.is_chance():
623            a = h.sample_chance()
624            return self.walk_tree(h + a, i, pi_i, pi_neg_i)

#

获取当前玩家的信息集 $h$

627        I = self._get_info_set(h)

#

要存储 $\sum_{z \in Z_{h}} π^{σ} (h, z) u_{i} (z)$

629        v = 0

#

$z \in Z_{h} \sum π^{σ^{t} ∣_{I \to a}} (h, z) u_{i} (z)$ 为每个动作存储 $a \in A (h)$

633        va = {}

#

遍历所有操作

636        for a in I.actions():

#

如果当前玩家是 $i$ ，

638            if i == h.player():

#

π_{i}^{σ^{t}} (h + a) π_{- i}^{σ^{t}} (h + a) = π_{i}^{σ^{t}} (h) σ^{t}_{i} (I) (a) = π_{- i}^{σ^{t}} (h)

643                va[a] = self.walk_tree(h + a, i, pi_i * I.strategy[a], pi_neg_i)

#

否则，

645            else:

#

π_{i}^{σ^{t}} (h + a) π_{- i}^{σ^{t}} (h + a) = π_{i}^{σ^{t}} (h) = π_{- i}^{σ^{t}} (h) * σ^{t}_{i} (I) (a)

650                va[a] = self.walk_tree(h + a, i, pi_i, pi_neg_i * I.strategy[a])

#

$z \in Z_{h} \sum π^{σ} (h, z) u_{i} (z) = a \in A (I) \sum [σ^{t}_{i} (I) (a) z \in Z_{h} \sum π^{σ^{t} ∣_{I \to a}} (h, z) u_{i} (z)]$

655            v = v + I.strategy[a] * va[a]

#

如果当前玩家是 $i$ ，更新累积策略和总遗憾

659        if h.player() == i:

#

更新累积策略 $t = 1 \sum T π_{i}^{σ^{t}} (I) σ^{t} (I) (a) = t = 1 \sum T [h \in I \sum π_{i}^{σ^{t}} (h) σ^{t} (I) (a)]$

664            for a in I.actions():
665                I.cumulative_strategy[a] = I.cumulative_strategy[a] + pi_i * I.strategy[a]

#

\tilde{r}_{i}^{t} (I, a) T R_{i}^{T} (I, a) = \tilde{v}_{i} (σ^{t} ∣_{I \to a}, I) - \tilde{v}_{i} (σ^{t}, I) = π_{- i}^{σ^{t}} (h) (z \in Z_{h} \sum π^{σ^{t} ∣_{I \to a}} (h, z) u_{i} (z) - z \in Z_{h} \sum π^{σ} (h, z) u_{i} (z)) = t = 1 \sum T \tilde{r}_{i}^{t} (I, a)

678            for a in I.actions():
679                I.regret[a] += pi_neg_i * (va[a] - v)

#

更新策略 $σ^{t} (I) (a)$

682            I.calculate_strategy()

#

返回玩家的预期效用 $i$ ， $z \in Z_{h} \sum π^{σ} (h, z) u_{i} (z)$

686        return v

#

迭代更新 $σ^{t} (I) (a)$

这更新了 $T$ 迭代策略。

688    def iterate(self):

#

循环几epochs 次

696        for t in monit.iterate('Train', self.epochs):

#

Walk tree 并更新每位玩家的遗憾

698            for i in range(self.n_players):
699                self.walk_tree(self.create_new_history(), cast(Player, i), 1, 1)

#

跟踪数据以进行分析

702            tracker.add_global_step()
703            self.tracker(self.info_sets)
704            tracker.save()

#

每次 $1, 000$ 迭代都保存检查点

707            if (t + 1) % 1_000 == 0:
708                experiment.save_checkpoint()

#

打印信息集

711        logger.inspect(self.info_sets)

#

信息集追踪器

这是一个小帮助类，用于跟踪信息集中的数据

714class InfoSetTracker:

#

设置追踪指示器

720    def __init__(self):

#

724        tracker.set_histogram(f'strategy.*')
725        tracker.set_histogram(f'average_strategy.*')
726        tracker.set_histogram(f'regret.*')

#

跟踪所有信息集中的数据

728    def __call__(self, info_sets: Dict[str, InfoSet]):

#

732        for I in info_sets.values():
733            avg_strategy = I.get_average_strategy()
734            for a in I.actions():
735                tracker.add({
736                    f'strategy.{I.key}.{a}': I.strategy[a],
737                    f'average_strategy.{I.key}.{a}': avg_strategy[a],
738                    f'regret.{I.key}.{a}': I.regret[a],
739                })

#

可配置 CFR 模块

742class CFRConfigs(BaseConfigs):

#

746    create_new_history: Callable[[], History]
747    epochs: int = 1_00_000
748    cfr: CFR = 'simple_cfr'

#

初始化 CFR 算法

751@option(CFRConfigs.cfr)
752def simple_cfr(c: CFRConfigs):

#

756    return CFR(create_new_history=c.create_new_history,
757               epochs=c.epochs)

信息不完整（CFR）游戏中的遗憾最小化

简介

玩家

历史

行动

信息集Ii​

策略

历史概率

公用事业（还清）

纳什均衡

遗憾最小化

反事实的遗憾

遗憾的配对

蒙特卡洛 CFR (MCCFR)

历史

信息集Ii​

计算策略

获取平均策略

反事实遗憾最小化 (CFR) 算法

走树

迭代更新σt(I)(a)

信息集追踪器

可配置 CFR 模块

信息集 $I_{i}$

信息集 $I_{i}$

迭代更新 $σ^{t} (I) (a)$