NFGSS中求解最佳对策的一种新混合算法  

New hybrid algorithm for optimal games solving in NFGSS

作　　者：杨瑜 王龙葛[2] Yang Yu;Wang Longge(College of Information Engineering,Zhengzhou Technology and Business University,Zhengzhou 451400,China;Schoolof Software,Henan University,Kaifeng475000,China)

机构地区：[1]郑州工商学院信息工程学院,郑州451400 [2]河南大学软件学院,开封475000

出　　处：《国外电子测量技术》2022年第8期118-124,共7页Foreign Electronic Measurement Technology

基　　金：河南省科技攻关项目(222102210229)资助。

摘　　要：针对采用序贯策略的正则形式博弈进行了研究,提出了一种新的求解最佳对策的混合算法。首先,描述了NFGSS紧凑的网络流表示,提出了这种表示中计算策略的线性规划和所采用的一般效用值计算公式;然后,详细阐述了提出的混合算法思想,通过对限制对策更细粒度的扩展、有效维持和效用值计算的分析;最后给出了最佳对策算法,以实现博弈双方达到期望效用值的策略空间。基于搜索博弈变体的两款游戏的实验结果表明,提出的混合算法相比于采用标准纯策略双Oracle算法和采用紧凑型策略求解完全线性规划算法,不仅在构建最佳博弈限制对策时有更高效的计算时间性能,而且在完整博弈中的策略空间支持大小与迭代算法的相对性能之间有更好的可扩展性。In this paper, we study normal-form games with sequential strategies and propose a new hybrid algorithm to solve the optimal game. Firstly, the compact network flow representation of NFGSS is described, and the linear programming of the computing strategies and the formula for calculating the general utility value used in this representation are proposed. Then, the idea of hybrid algorithm is described in detail. By analyzing the fine-grained expansion, effective maintenance and calculation of utility value of the restricted game, the optimal game algorithm is given in the end to obtain the strategy space of the expected utility value for both sides of the game. Two games variants of search based the experimental results show that the proposed hybrid algorithm, compared with standard pure-strategy double-Oracle algorithm and full linear programming using compact strategies algorithm, not only has more efficient computation time performance in building the optimal game restricted game, but also has better extensibility between strategy support size in the full game strategy space and the relative performance of the iterative algorithm.

关 键 词：正则形式博弈 玩家 序贯策略 纳什均衡 线性规划 期望效用 最佳对策 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]