0.前言
上篇我们简单介绍了CFR算法和一种非常简单的双人博弈游戏Kuhn牌。我们发现CFR算法在这种很简单的环境下能给出一个纳什均衡策略，但是似乎并不是能很有力地证明它比一个随机策略玩家做得更好，在这一篇中，我首先会介绍MCCFR算法并给出有所改进的Outcome-Sampling MCCFR的代码。接下来会介绍一个作者自己随便设计的一个类似麻将的游戏，在这个游戏中，我们可以很自信地说MCCFR训练速度比CFR快许多，并且，训练足够的轮次后可以和CFR表现得一样好。
1.Outcome-Sampling MCCFR算法介绍
理论请看这篇博客https://www.jianshu.com/p/600f5b0d1e85。
MCCFR听着名字是不是和MCTS有点关系，没错，这是因为二者都使用蒙特卡洛采样方法。
同样的，受限于我个人能力，我不具体给出算法讲解了，我还是仅给出直觉上怎么理解MCCFR，或者说为什么MCCFR会有效。
MCCFR改进了CFR算法需要采样整个决策树，耗时太多的问题。MCCFR主要是在更新节点的后悔值时。一次只更新一个动作的后悔值，简单来说就是除以了该节点的到达概率，只要采样够多就可以更新的完全。
但这样还是不够快，下面介绍的是Outcome-Sampling MCCFR算法。
Outcome-Sampling MCCFR按照概率去选择动作来进行扩展，并且在更新节点遗憾值按计算出的权重（收益/该节点到达概率）作为一个乘法因子参与计算。具体来说，照常更新选中的动作的遗憾值（权重*（1-该动作概率））（注意这里实际上就是选择该动作的反事实值减去按照策略的反事实值，具体请看推导），而将其他动作更新相反（-权重*该动作概率）的。
上述段落加粗斜体有两个词，之所以有“权重”，在我的理解中是这毕竟不是采样所有动作，我们得到的收益不是所有动作的加权收益。为了保证后悔值的更新仍然与到达该节点的概率相关，所以我们需要使用到达这个节点概率来放大收益。至于相反则很好理解，此消彼长嘛，收益要是是正的，那没采取这个动作不就亏了，要是负的，那没采取这个动作就赚了——这里的亏和赚只是对于这个采样的动作来说的，不是和要更新的动作本身的盈亏比的。
2.Kuhn环境下的MCCFR
具体环境代码请看上篇。
# 蒙特卡洛CFR（Monte Carlo CFR）算法的递归方法，用于训练玩家策略
def mccfr(self, history, cards, reach_probs):
# 确定当前玩家ID（0或1），根据历史行动的长度来判断
player_id = len(history) % 2
# 确定对手的ID
opponent_id = 1 - player_id
# 检查当前历史和手牌是否是终止节点
maybe_payoff = kuhn.get_payoff(history, cards)
# 如果是终止节点，返回收益
if maybe_payoff is not None:
# 根据当前玩家ID确定收益的符号
payoff = maybe_payoff if player_id == 0 else -maybe_payoff
return float(payoff)
# 创建信息集，包含当前历史和当前玩家的手牌
info_set = InformationSet(history, cards[player_id])
# 如果该信息集不存在于cfr_info中，初始化一个新的CfrNode，初始值设为0.06
if info_set not in self.cfr_info.keys():
self.cfr_info[info_set] = CfrNode(0.06) #MCCFR有探索率，但没看出来有什么用
# 获取当前信息集的行动概率
action_probs = self.cfr_info[info_set].get_action_probability()
# 从概率分布中随机选择一个行动ID，在CFR中要遍历所有
chosen_action_id = self.cfr_info[info_set].sample(action_probs)
# 根据选定的行动ID获取具体的行动
chosen_action = kuhn.Action.from_int(chosen_action_id)
# 获取选定行动的概率
chosen_action_prob = action_probs[chosen_action_id]
# 克隆当前历史以记录下一步的行动
next_history = history.clone()
# 在历史中添加选定的行动
next_history.raw.append(chosen_action)
# 复制当前的达到概率
next_reach_probs = reach_probs.copy()
# 更新当前玩家的达到概率
next_reach_probs[player_id] *= chosen_action_prob
# 递归调用mccfr，获取最终收益（将其反转，因为是对手的收益）
final_payoff = -self.mccfr(next_history, cards, next_reach_probs)
# 获取当前信息集的CfrNode
node = self.cfr_info[info_set]
# 更新累积遗憾值
for action_id, action_prob in enumerate(action_probs):
action = kuhn.Action.from_int(action_id)
# 计算权重，用于更新遗憾值
weight = final_payoff / reach_probs[player_id] / action_prob #除reach_probs[player_id]
if action == chosen_action:
# 如果是选定的行动，更新遗憾值
node.cum_regrets[action_id] += weight * (1.0 - action_prob)
else:
# 否则，按相反的方式更新遗憾值
node.cum_regrets[action_id] += -weight * action_prob
# 更新当前信息集的累积策略,这个变量用于打印策略信息，不影响
for action_id, action_prob in enumerate(action_probs):
node.cum_strategy[action_id] += action_prob * reach_probs[player_id]
# 返回最终的收益
return final_payoff
经过测试，MCCFR与CFR表现相近且速度明显更快。
3.柒玖麻将
柒玖麻将分为 东、南、西、北、中、发、白、旗、酒 九张牌。每张牌四张，所以总共有36张牌 。
游戏开始两个玩家每人获得七张牌，随后一个玩家一个回合，每个玩家回合开始摸一张牌，如果此时手上的八张牌正好符合“胜利条件”则游戏结束， 否则该玩家需要打出一张牌，如果此牌和对手玩家手上的七张牌组成的八张牌符合“胜利条件”了，那么游戏也结束。
如果所有牌都抽完了还没人胜利的话，视为流局，每个玩家得0分。
胜利条件如下： 1.手上有同花色的2组牌，每组4张，得8分 2.手上有同花色的2组牌每组3张，并且有同花色的1组牌每组2张，得6分 3.手上有同花色的4组牌，每组两张，得4分 在这里用1-9表示东、南、西、北、中、发、白、旗、酒九张牌。
但是聪明的读者读到这就已经发现不对劲了，手牌有7+1张，作为公共历史的牌堆，可以看做一个长度为9的向量用来表示什么牌已经打过了。那么状态粗略估计，居然有4^9*8^9（事实上没有那么多，因为每张牌上限四张），这无疑是训练不出来的。所以我们做出如下简化：
1.总共4种牌，每张4张。
2.胜利条件为凑齐一个炸弹或两个对子。
3.公共历史大小为2，两个玩家共4，使用队列记录
4.结语
经过训练和测试，MCCFR在简化的环境下训练速度很快，且能很好地战胜随机策略玩家和没有认真玩的我。胜率甚至比CFR还高一点（训练相同时间，非相同轮次），大概将近60%，并且在测试中从未出现运气极好的随机策略玩家取胜的情况。
代码开源在github了，环境类中有些超参数可以修改麻将类别数量和初始手牌，感兴趣可以去看看。
对于完整的问题，我们很容易可以想到可以训练一个神经网络来解决状态过多的问题，这就是Deep-CFR 和SD-CFR的思想，有空我会写成博客分享的。