虚拟遗憾最小化算法(Counterfactual Regret Minimization)
- 如果不能遍历计算机所有节点的遗憾值，那么可以采用虚拟遗憾最小化算法来进行模拟计算。
- 假设：
- 集合A 是博弈中所有玩家所能采用的行为集(如在石头-剪刀-布游戏中出石头、出剪刀或出布三种行为)
- I 为信息集，包含了博弈的规则以及玩家采取的历史行动，在信息集I 下所能采取的行为集合记为A ( I ) 。
有了这些定义之后，我们现在来计算虚拟遗憾：
当采取策略σ时，其所对应的行动序列h 的虚拟价值(Counterfactual Value)如下计算(注：行动序列h 未能使博弈进入终结局势)：
当采取策略σ 时，其所对应的行动序列h 的虚拟价值(Counterfactual Value)如下计算(注：行动序列h 未能使博弈进入终结局势)
我们首先去计算其他玩家在产生行动序列h 中他们的概率值是多少，乘以在这个策略下，从行动序列h 进入到终止局势z 的概率，最终再乘以玩家i 在终止局势z 的概率。之后对终止局势做一个遍历，把它的乘积做一个累加。
- 玩家i采取行动a 所得到的虚拟遗憾值：
- 行动序列h 所对应的信息集I 遗憾值为：
- 玩家i 在第T 轮次采取行动a 的遗憾值为：
- 同样，对于遗憾值为负数的情况，我们不予考虑，记：
- 在T + 1 轮次，玩家i ii选择行动a 的概率计算如下：
- 玩家i 根据遗憾值大小来选择下一时刻行为，如果遗憾值为负数，则随机挑选一种行为进行博弈。
例子-库恩扑克(Kunh’s pocker)
- 库恩扑克是最简单的限注扑克游戏，由两名玩家进行游戏博弈，牌值只有1，2和3三种情况。
- 每轮每位玩家各持一张手牌，根据各自判断来决定加定额赌注。
- 游戏没有公共牌，摊牌阶段比较未弃牌玩家的底牌大小，底牌牌值最大的玩家即为胜者。
- 游戏规则：
库恩扑克(Kunh’s pocker)：以先手玩家(定义为玩家A AA)为例的博弈树：
从初始节点开始，1、2、3分别表示玩家A AA手中的牌，当玩家拿了1之后，玩家B BB只能拿2或者3。玩家A AA选择过牌还是加注，玩家B BB也可以选择过牌还是加注。依次进行下去，就构建了博弈树。
- 在这个博弈树里面，总共的信息集与12个：{1,1P,1B,1BP,2,2P,2B,2BP,3,3P,3B,3BP}。
- 每个信息集由不同路径可以到达。如信息集1PB可通过如下路径到达：
可见信息集1 P B 1PB1PB所对应的行动序列为{P,B}
- 在该问题中，到达每个信息集的路劲均唯一，因此所有信息集仅对应一个行动序列。
有了上述定义之后，我们可以采取如下算法进行策略选择：
- 初始化遗憾值和累加策略表为0
- 采用随机选择的方法来决定策略
- 利用当前策略与对手进行博弈
- 计算每个玩家采取每次行为后的遗憾值
- 根据博弈结果计算每个行动的累加遗憾值大小来更新策略
- 重复博弈若干次
- 根据重复博弈最终的策略，完成最终的动作选择
计算1PB的遗憾值
- 假设初始情况下，两个玩家都以随机选择的策略进行决策，即在任一节点，都以50%的概率分别选择过牌和加注
- 则最终选择过牌的虚拟价值为：
- 在信息集{ 1 P B } 上采取“过牌”的遗憾值
- 库恩扑克的博弈共有12个信息集，对应上图中的正方形和三角形
- 通过反复迭代计算，可以得到到达各个信息集应采取行动的概率：
- 对于玩家A AA而言，库恩扑克的混合策略纳什均衡的理论解如下(α ∈ [ 0 , 1 / 3 ]
可见，算法得到的解与理论得到的解之间较为接近，验证了算法的有效性。
