传统的战略式博弈求解方法——虚拟博弈(Fictitious Play)讲解及其代码

传统的战略式博弈求解方法——虚拟博弈(Fictitious Play)讲解及其代码

传统的战略式博弈求解纳什均衡方法——虚拟博弈(Fictitious Play)讲解及其代码

虚拟博弈是博弈论中一种传统的方法，其历史真的非常久远，于1951年被Brown, George W 提出。

其核心思想非常简单，就是利用博弈论中常用的反应函数思想。使每个智能体拥有两个策略集。一个是最优策略集，一个是历史平均策略集。在每一轮博弈的开始，每个均智能体根据对手的历史平均策略集，找到一个最优的针对策略。然后根据历史平均策略和本轮最优策略更新自己的历史平均策略。

拿石头剪刀布举例子：首先第一轮随机出拳，如果P1石头，P2剪刀。在第二轮时，P1根据P2的历史数据（P2只出了剪刀）得出自己应该出石头，则P1还是出石头，P2根据P1历史数据（P1只出了石头）得出自己应该出布。所以第二轮P1石头，P2布；玩家更新自己的历史策略集P1还是只出了石头，P2有50%的情况出了剪刀，50%的情况出布，以此类推。。。随着迭代的继续，策略会慢慢收敛到纳什均衡。

但是，虚拟博弈并不能解决所有问题。虚拟博弈只能解决零和博弈，或者是包含纯策略纳什均衡解的常和博弈。在常和博弈中如果存在多个纳什均衡，则虚拟博弈收敛的结果会由收益矩阵和初始策略有关，并不能保证收敛到“最优均衡”。此外，虚拟博弈依赖于问题是战略式描述，如果要求扩展式的问题，则一直等到2015年FSP (Fictitious Self-Play) 虚拟自我博弈出现才能处理，我们之后再说。

附虚拟博弈代码：

# -*- encoding:utf-8 -*-import numpy as npclass Player(object):def __init__(self, policy_len, utility, num):""":param policy_len: 策略个数:param utility:  收益矩阵:param num: 玩家0写0 玩家1写1"""self.utility = utilityself.policy_len = policy_lenself.policy = np.random.random(self.policy_len)self.history = np.zeros(self.policy_len)self.num = numdef change_policy(self, op_pro):"""根据传入的对手历史策略，选择自己的最优策略，并改变自己的策略:param op_pro: 对手策略"""earn = op_pro * self.utilitymoney_sum = np.sum(earn, axis=1 - self.num)best_choice = np.argmax(money_sum)self.history[best_choice] += 1self.policy = self.history / np.sum(self.history)def get_policy(self):""":return: 返回自己本轮策略"""if self.num == 0:shape(self.policy, (self.policy_len, 1))else:return self.policydef exploitability(self, op_pro):"""测试对手策略的可利用度（实质就是epsilon-纳什均衡的epsilon）:param op_pro: 对手策略"""earn = op_pro * self.utilitymoney_sum = np.sum(earn, axis=1 - self.num)best_choice = np.argmax(money_sum)print('p' + str(1 - self.num) + ' exploitability:', money_sum[best_choice])class Nash(object):def __init__(self, p0, p1):self.p0 = p0self.p1 = p1def get_nash_equilibrium(self, loop_time):"""求解纳什均衡:param loop_time: 迭代次数"""for i in range(loop_time):self.p0.change_policy(_policy())self.p1.change_policy(_policy())def show_result(self):"""显示结果"""print('p0', _policy())print('p1', _policy())def show_exploitability(self):"""显示可利用度""&#ploitability(_policy())p1.exploitability(_policy())if __name__ == '__main__':"""# 以下例子求解如下纳什均衡（囚徒困境）#     P0╲P1    坦白    抵赖#      坦白   -4，-4   0，-5#      抵赖   -5， 0  -1，-1u0 = np.array([[-4, 0],[-5, -1]])u1 = np.array([[-4, -5],[0, -1]])p0 = Player(2, u0, 0)p1 = Player(2, u1, 1)"""# 以下例子求解如下纳什均衡（石头剪刀布）#     P0╲P1    石头    剪刀    布#      石头    0, 0   1,-1  -1, 1#      剪刀   -1, 1   0, 0   1,-1#       布     1,-1  -1, 1   0, 0u0 = np.array([[0, 1, -1],[-1, 0, 1],[1, -1, 0]])u1 = np.array([[0, -1, 1],[1, 0, -1],[-1, 1, 0]])p0 = Player(3, u0, 0)p1 = Player(3, u1, 1)nash = Nash(p0, _nash_equilibrium(1000)nash.show_result()nash.show_exploitability()