一种不完美信息扩展式博弈中计算最佳反应策略的方法

摘要

本发明公开了一种不完美信息扩展式博弈中计算最佳反应策略的方法，包括如下步骤：（1）初始化策略、所有信息集的虚拟价值和虚拟遗憾值；（2）根据当前策略，与对手进行一次博弈，并记录博弈结果；（3）对于在本次博弈中每一个被访问的信息集，根据博弈结果计算出该信息集的虚拟价值；（4）根据步骤（3）所得到的各个信息集的虚拟价值，计算出每个信息集上每一个动作的虚拟遗憾值；（5）在每一个被访问的信息集上执行遗憾值匹配过程，更新该信息集上的策略；（6）返回步骤（2），直至不再有博弈进行。本发明避免了对手策略动态变化所带来的误差，同时也提高了计算效率。

说明书

技术领域

本发明涉及一种不完美信息扩展式博弈中计算最佳反应策略的方法。

背景技术

博弈论被广泛应用于经济、政治、安全、游戏等领域中，具有重大的研究和应用价值。一类重要的博弈类型是不完美信息扩展式博弈（imperfect information extensive-form game），它在日常生活中也很常见，例如：扑克、麻将等。博弈论研究的核心问题是计算出有效的博弈策略，使局中人（player）在博弈中获得理想的博弈收益（utility）。这其中包含：(1) 纳什均衡（Nash equilibrium）策略的计算；(2) 最佳反应（best response）策略的计算。

纳什均衡是博弈论中的最基本的概念之一，在博弈中使用纳什均衡策略能够保证局中人不被对方利用（exploit）。但它是基于对手绝对理性的假设，而绝大多数对手都是非理性或有限理性的。针对特定对手，采用最佳反应策略往往能使局中人获得更高的收益。

目前，在计算最佳反应策略这一问题的研究工作中，绝大多数方法都采用了对手建模（opponent modeling），即：首先通过统计观察，得出对手的策略模型，然后在该策略模型的基础上通过优化方法得到最佳反应策略。然而，这些方法没有考虑到对手的策略是有可能动态变化的。在对手的策略不断变化的情形下，对手建模的方法无法建立准确的对手策略模型，因此无法在博弈中获得较高的博弈收益。另外，对手建模方法所耗费的计算量也比较大，在大规模博弈（即：状态空间很大）中无法有效应用。

发明内容

发明目的：针对上述现有技术存在的问题和不足，本发明的目的是提供一种不完美信息扩展式博弈中计算最佳反应策略的方法，针对不完美信息扩展式博弈中，对手策略动态变化的情形，提出从遗憾最小化（regret minimization）的角度来计算最佳反应策略，避免对手建模，同时也提高计算速率。

技术方案：为实现上述发明目的，本发明采用的技术方案为一种不完美信息扩展式博弈中计算最佳反应策略的方法，包括如下步骤：

（1）初始化局中人                                                的策略、所有信息集的虚拟价值和虚拟遗憾值，其中为有限局中人集合；

（2）根据当前策略，与对手进行一次博弈，并记录博弈结果；

（3）对于在本次博弈中每一个被访问的信息集，根据目前为止所得到的所有博弈结果计算出该信息集的虚拟价值；

（4）根据步骤（3）所得到的虚拟价值，计算出每个信息集上每一个动作的虚拟遗憾值，其中表示在信息集上可以执行的动作的集合；

（5）在每一个被访问的信息集上执行遗憾值匹配过程，更新该信息集上的策略；

（6）返回步骤（2），直至不再有博弈进行。

进一步的，所述步骤（3）中，采用基于统计采样的方法，从目前所得到的博弈结果中计算出每个终止信息集的虚拟价值；而非终止信息集的虚拟价值通过其后继信息集的虚拟价值计算出来。

进一步的，所述步骤（4）中，将信息集的虚拟价值与信息集的虚拟价值相减，得到动作的虚拟遗憾值，其中表示在信息集执行动作后所到达的信息集。

进一步的，所述步骤（5）中，采用遗憾值匹配的方式，计算信息集上动作的执行概率：如果动作的虚拟遗憾值越大，表明不执行动作所造成的遗憾也就越大，相应地就应该更多地提高动作的执行概率。

有益效果：本发明与现有方法相比，其显著优点是避免了对对手策略模型的建立，能够对对手策略的动态变化做出快速反应，相对于对手建模方法，本发明能够获得更高的胜率（win rate）和博弈收益（utility），运行速度也大大提高。

附图说明

图1为本发明的总体架构图；

图2为本发明的流程图。

具体实施方式

下面结合附图和具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发明的各种等价形式的修改均落于本申请所附权利要求所限定的范围。

本发明通过采样的方法，在每一次博弈后根据博弈的结果计算出每个信息集的虚拟价值以及该信息集上每个动作的虚拟遗憾值，然后采用遗憾值匹配的方法更新每个信息集上的策略。基本步骤为：（1）初始化策略、所有信息集的虚拟价值和虚拟遗憾值；（2）根据当前策略，与对手进行一次博弈，并记录博弈结果；（3）对于在本次博弈中每一个被访问的信息集，根据博弈结果计算出该信息集的虚拟价值；（4）根据步骤（3）所得到的各个信息集的虚拟价值，计算出每个信息集上每一个动作的虚拟遗憾值；（5）在每一个被访问的信息集上执行遗憾值匹配过程，更新该信息集上的策略；（6）返回步骤（2），直至不再有博弈进行。

不完美信息扩展式博弈的形式化定义如下：

定义1. 不完美信息扩展式博弈是一个六元组

 对于局中人，其策略可以表示为。对于每一个信息集，是在动作集概率分布函数。局中人的策略空间用表示。一个策略组包含所有局中人策略，用表示。一般地，对于局中人，我们用表示中除了之外的策略。

给定其他所有局中人的策略组，局中人的最佳反应策略可以定义如下：

定义 2. 最佳反应（best response）：对于局中人，其对于所有其他局中人的策略组的最佳反应策略满足：

在这里，表示局中人在其他局中人使用策略组，而自己使用时所得到的效用值；令，其效用值计算公式为，也即将所有可能的博弈结果做一个加权和，权重表示在所有局中人按照策略组采取动作的情况下，到达终止动作序列的概率。

虚拟遗憾最小化（counterfactual regret minimization）的方法最早由文献“Zinkevich M, Johanson M, Bowling M, et al. Regret minimization in games with incomplete information. Advances in Neural Information Processing Systems, 2008, 20: 1729–1736”所提出。与本发明的目的不同，该文献用虚拟遗憾最小化方法来计算扩展式博弈中的近似纳什均衡策略。其最核心的内容是信息集的虚拟价值（counterfactual value）的定义：

定义 3. 对于局中人和信息集，关于策略组的虚拟价值计算如下

信息集的虚拟价值的代表着它在所有局中人采用策略组的情况下，对局中人的价值大小。在该公式中，表示从信息集出发，所能到达的终止动作序列的集合；表示在终止序列为的情况下，信息集所代表的实际动作序列；代表在其他局中人使用策略组的情况下，到达的概率；代表所有局中人按照策略组选择动作，从能到达的概率。该计算公式中出现的表明在的计算中需要使用其他局中人的策略组。而本发明为了避免对对手策略模型的学习，无法获知对手的策略组。本发明从自己的问题角度出发，根据大数定律，提出了新的计算虚拟价值的方法。

如图1所示，本发明的总体步骤包括：进行博弈、根据博弈结果计算信息集的虚拟价值、根据虚拟价值计算每个信息集上动作的虚拟遗憾值以及根据虚拟遗憾值进行遗憾值匹配更新当前策略。本发明的流程图如图2所示，下面详细进行说明：

步骤1：初始化，对于局中人的所有信息集，其虚拟价值；对于所有上所有可执行的动作，其中表示在信息集上可以执行的动作的集合，其虚拟遗憾值，其执行概率；

步骤2：使用当前策略同对手进行博弈，并记录博弈结果。

步骤3：根据目前为止所记录的博弈结果，计算当前博弈中被访问的信息集的虚拟价值，方法如下。

给定当前策略组，对于局中人的任意终止信息集，定义其虚拟价值（counterfactual value）如下：

在这里，为当前博弈进行的总次数，为访问信息集的次数，代表第次访问该信息集时所获得的效用值，表示在策略组的情况下到达信息集的概率。而对于任意非终止信息集，其虚拟价值可通过其后继信息集的虚拟价值计算出来：

这里的表示在策略组的情况下，从非终止信息集转移到其后继信息集的概率；集合表示在非终止信息集之后做出某个动作之后，所到达的所有可能的后继信息集的集合，也即。

步骤4：对于任意信息集，根据其虚拟价值计算该信息集上每一个动作的虚拟遗憾值，方法如下：

其中表示在信息集执行动作后所到达的信息集。

步骤5：对于每一个信息集，基于每个动作的虚拟后悔值，采用遗憾值匹配（regret matching）的方式来更新当前的策略：

这里的代表信息集上所有动作遗憾值的加和，其中是为了区别，而动作是当前我们需要更新值的动作，更新的这个值需要用到整个动作集里面的所有动作的虚拟遗憾值，就代表中的任意动作。采用遗憾值匹配的方法的含意是：如果在信息集上不执行的某个动作所产生的遗憾较大，那么我的策略就会偏向于更多地执行动作。

步骤6：若博弈继续，则返回步骤2；否则，结束。