虚拟遗憾最小化算法(Counterfactual Regret Minimization)

• 如果不能遍历计算机所有节点的遗憾值，那么可以采用虚拟遗憾最小化算法来进行模拟计算。

• 假设：

  • 集合是博弈中所有玩家所能采用的行为集(如在石头-剪刀-布游戏中出石头、出剪刀或出布三种行为)
  • 为信息集，包含了博弈的规则以及玩家采取的历史行动，在信息集下所能采取的行为集合记为。

• 玩家在第轮次采取的行动反映了其在该轮次所采取的策略。包含玩家在内的所有玩家在轮次采取的行动构成了一组策略组合。

• 在信息集下采取行动所反映的策略记为。

• 在第轮次所有玩家采取的行动是一条序列，记为。采取某个策略计算行动序列出现的概率记为。

• 每个信息集发生的概率，表示所有能够到达该信息集的行动序列的概率累加。

• 给定博弈的终结局势，玩家在游戏结束后的收益记做。

• 在策略组合下，施加博弈行动序列后达到最终局势的概率为。

  有了这些定义之后，我们现在来计算虚拟遗憾：

• 当采取策略时，其所对应的行动序列的虚拟价值(Counterfactual Value)如下计算(注：行动序列未能使博弈进入终结局势)：

  我们首先去计算其他玩家在产生行动序列中他们的概率值是多少，乘以在这个策略下，从行动序列进入到终止局势的概率，最终再乘以玩家在终止局势的概率。之后对终止局势做一个遍历，把它的乘积做一个累加。

• 玩家采取行动所得到的虚拟遗憾值：

• 行动序列所对应的信息集遗憾值为：

• 玩家在第轮次采取行动的遗憾值为：

• 同样，对于遗憾值为负数的情况，我们不予考虑，记：

• 在轮次，玩家选择行动的概率计算如下：

• 玩家根据遗憾值大小来选择下一时刻行为，如果遗憾值为负数，则随机挑选一种行为进行博弈。

例子-库恩扑克(Kunh's pocker)

• 库恩扑克是最简单的限注扑克游戏，由两名玩家进行游戏博弈，牌值只有1，2和3三种情况。
• 每轮每位玩家各持一张手牌，根据各自判断来决定加定额赌注。
• 游戏没有公共牌，摊牌阶段比较未弃牌玩家的底牌大小，底牌牌值最大的玩家即为胜者。
• 游戏规则：

游戏规则表

库恩扑克(Kunh's pocker)：以先手玩家(定义为玩家)为例的博弈树：

博弈树

  从初始节点开始，1、2、3分别表示玩家手中的牌，当玩家拿了1之后，玩家只能拿2或者3。玩家选择过牌还是加注，玩家也可以选择过牌还是加注。依次进行下去，就构建了博弈树。

• 在这个博弈树里面，总共的信息集与12个：{1,1P,1B,1BP,2,2P,2B,2BP,3,3P,3B,3BP}。
• 每个信息集由不同路径可以到达。如信息集1PB可通过如下路径到达：

  可见信息集所对应的行动序列为{P,B}

• 在该问题中，到达每个信息集的路劲均唯一，因此所有信息集仅对应一个行动序列。

有了上述定义之后，我们可以采取如下算法进行策略选择：

1. 初始化遗憾值和累加策略表为0
2. 采用随机选择的方法来决定策略
3. 利用当前策略与对手进行博弈
4. 计算每个玩家采取每次行为后的遗憾值
5. 根据博弈结果计算每个行动的累加遗憾值大小来更新策略
6. 重复博弈若干次
7. 根据重复博弈最终的策略，完成最终的动作选择

计算1PB的遗憾值

• 假设初始情况下，两个玩家都以随机选择的策略进行决策，即在任一节点，都以50%的概率分别选择过牌和加注
• 若第一轮中，玩家的博弈过程为，收益为。
• 计算玩家针对信息集选择“过牌”行动的遗憾值：
  • 在当前策略下，行动序列产生的概率：
    

  由于在 节点选择加注和过牌的概率均为50%，所以当前策略下，从行动序列到达终结状态和的概率分别为：

  又已知，，可知当前策略的虚拟价值：

• 若使用过牌策略，即，此时玩家促使行动序列达成的概率仍然为，由于最终抵达的终结状态只有，所以。
• 则最终选择过牌的虚拟价值为：

• 在信息集上采取“过牌”的遗憾值

• 库恩扑克的博弈共有12个信息集，对应上图中的正方形和三角形
• 通过反复迭代计算，可以得到到达各个信息集应采取行动的概率：

image

• 对于玩家而言，库恩扑克的混合策略纳什均衡的理论解如下()：

image

  可见，算法得到的解与理论得到的解之间较为接近，验证了算法的有效性。

微信公众号

公众号介绍：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！