Multi-layer Extreme Learning Machine Autoencoder With Subspace Structure Preserving
-
摘要: 处理高维复杂数据的聚类问题, 通常需先降维后聚类, 但常用的降维方法未考虑数据的同类聚集性和样本间相关关系, 难以保证降维方法与聚类算法相匹配, 从而导致聚类信息损失. 非线性无监督降维方法极限学习机自编码器(Extreme learning machine, ELM-AE)因其学习速度快、泛化性能好, 近年来被广泛应用于降维及去噪. 为使高维数据投影至低维空间后仍能保持原有子空间结构, 提出基于子空间结构保持的多层极限学习机自编码器降维方法(Multilayer extreme learning machine autoencoder based on subspace structure preserving, ML-SELM-AE). 该方法在保持聚类样本多子空间结构的同时, 利用多层极限学习机自编码器捕获样本集的深层特征. 实验结果表明, 该方法在UCI数据、脑电数据和基因表达谱数据上可以有效提高聚类准确率且取得较高的学习效率.Abstract: To deal with the clustering problem of high-dimensional complex data, it is usually reguired to reduce the dimensionality and then cluster, but the common dimensional reduction method does not consider the clustering characteristic of the data and the correlation between the samples, so it is difficult to ensure that the dimensional reduction method matches the clustering algorithm, which leads to the loss of clustering information. The nonlinear unsupervised dimensionality reduction method extreme learning machine autoencoder (ELM-AE) has been widely used in dimensionality reduction and denoising in recent years because of its fast learning speed and good generalization performance. In order to maintain the original subspace structure when high-dimensional data is projected into a low-dimensional space, the dimensional reduction method ML-SELM-AE is proposed. This method captures the deep features of the sample set by using the multi-layer extreme learning machine autoencoder while maintaining multi-subspace structure of clustered samples by self-representation model. Experimental results show that the method can effectively improve the clustering accuracy and achieve higher learning efficiency on UCI data, EEG data and gene expression data.
-
计算机博弈与人工智能的发展一直相辅相成. 自人工智能(Artificial intelligence, AI)学科诞生伊始, 计算机博弈研究就是AI技术发展创新的沃土, AI领域的先驱图灵和香农都曾研发过计算机博弈程序[1]. 用于测试机器是否具有“智能”的图灵测试, 其实现形式就是通过人和机器之间博弈进行的. 智能博弈一直都是衡量AI技术发展水平的重要评价准则, AI发展历史上的主要里程碑事件都与计算机智能博弈游戏研究相关. 1962年6月机器学习之父阿瑟·塞缪尔的西洋跳棋程序战胜美国著名职业选手尼雷、1997年5月IBM公司的超级电脑“深蓝”战胜国际象棋大师卡斯帕罗夫等,都是AI学科早期发展历史上重要的里程碑事件.
近年来, 计算机的存储与计算能力不断提升, 以及各类数据的爆炸式增长与积累, 以人工神经网络为主要技术工具的深度学习方法[2-3], 因其强大的数据拟合能力与泛化能力, 使其在语音识别[4]、图像识别[5]和自然语言处理[6-7]等领域都取得了突破性进展, 成功推进了AI领域由感知智能到认知智能的跨越. 如今, AI领域正在经历从认知智能迈向决策智能的过程, 以强化学习与深度学习相结合的深度强化学习方法[8-10], 在围棋博弈领域取得了重大突破并成功打败人类顶尖选手[11-15], 为完美信息场景下的博弈决策问题提供了有效的方法指导. 而智能体如何在其所处状态信息不完全已知的情况下做出准确的决策, 是目前AI领域面临的核心问题. 因此, 不完美信息博弈场景下智能决策问题的研究和解决, 是AI取得突破的核心前沿领域和重要驱动力.
游戏是一种虚拟的实验环境, 具有可控损失的优点, 实验成本低且允许实验失败. 博弈游戏本身又存在很多难点, 具有决策空间复杂、实时高动态、信息不完美等特点[16-17], 能够为智能决策问题研究提供一种良好的算法实验环境, 是AI技术绝佳的实验研究平台. 不完美信息博弈游戏是指智能体在游戏中只能够获得自身的游戏状态以及公共游戏信息, 而无法掌握全部的局面信息[18], 例如在德州扑克[19-20]、麻将[21]、斗地主[22]等游戏博弈过程中对手的手牌不可见, 因此获得的局面信息是不完美的, 这也使此类博弈游戏的研究和解决更具挑战性.
现实生活中, 在军事、经济、商业、网络安全等实际场景中的大多问题, 均属于不完美信息博弈问题. 此类问题的研究和解决往往受到实际环境的成本制约, 而将其转化为对博弈游戏抽象模型的求解寻优问题可以大幅降低所需实验成本. 因此, 以不完美信息博弈游戏为载体的研究, 能够为现实问题的解决提供有效的方法论.
本文选择德州扑克游戏作为对不完美信息博弈的主要研究和实验对象, 以演化学习方法[23]和深度神经网络相结合完成对智能体的训练, 通过在线的对手风格建模和种群策略集成的方法使智能体能够适应对手策略变化, 最终实现一种轻量高效并对解决不完美信息博弈问题具有通用性的博弈求解框架.
1. 德州扑克游戏
德州扑克游戏规则明晰、玩法多样且趣味性很强, 是最受欢迎的扑克游戏之一. 德州扑克游戏具有信息不完美、状态和动作空间巨大、对手不确定等特性[24], 是不完美信息博弈游戏的典型代表, 集中反映人工智能领域的许多核心问题, 其研究对于整个人工智能领域的发展有着极其关键的影响, 得到国内外诸多研究团队的极大关注并取得诸多进展.
1.1 游戏规则介绍
德州扑克游戏通常采用52张扑克牌, 参与游戏的玩家人数通常限制在2 ~ 9人. 游戏分为翻牌前、翻牌、转牌和河牌4个阶段, 在翻牌前阶段开始时, 每名玩家将获得2张只有自身能够看到的“底牌”, 之后的3个阶段开始时桌面上会分别发出3张、1张和1张“公共牌”. 在经过各阶段游戏多次的“加注/全压”、“跟注/过牌”、“弃牌”等押注圈操作后, 若牌局仍存在至少两名玩家没有弃牌, 游戏进入“摊牌”阶段, 该阶段各玩家在自己的2张底牌和5张公共牌中挑选5张形成牌组, 按照图1所示的德州扑克游戏牌型大小规则分出胜负, 赢家获得桌面上全部筹码.
本文主要针对两人无限注的德州扑克游戏(Heads-up no-limit Texas Hold＇em, HUNL)进行方法的实验和验证. HUNL是指只有两个玩家参与的德州扑克游戏, 游戏双方按照游戏位置分为大盲位和小盲位. 小盲位在翻牌前阶段首先做动作, 其余阶段均为大盲位首先做动作. 每局游戏结束时双方交换游戏位置并且重置总筹码量, 然后开始下一局游戏.
1.2 相关解决方法介绍
HUNL方面的研究主要经历从博弈树模型搜索优化逼近纳什均衡策略, 到深度神经网络拟合纳什均衡策略, 再到深度强化学习自我博弈优化的发展过程.
Slumbot[25]是博弈树模型搜索优化方法的典型代表, 其核心是利用反事实遗憾最小化(Counterfactual regret minimization, CFR)算法[26]在HUNL中逼近纳什均衡策略. Slumbot主要算法流程为: 首先根据HUNL规则构建出游戏的博弈树原始模型; 然后利用抽象技术[27]将相似游戏状态进行聚类, 从而缩减博弈树规模, 降低算法计算规模; 最后在缩减过的博弈树上进行蒙特卡洛反事实遗憾最小化(Monte Carlo counterfactual regret minimization, MCCFR) 算法[28]迭代, 最终收敛得到近似的纳什均衡策略. 这种方法严重依赖于游戏博弈树模型和人类专家知识进行抽象, 并且CFR算法需要对博弈树上约6.31×10164个状态结点进行不断地采样遍历和迭代优化从而收敛得到纳什均衡策略, 即使经过模型缩减后该方法仍需要耗费大量的计算和存储资源, 例如Slumbot在训练阶段需要耗费大于105个CPU小时的计算资源和TB级别的存储资源来分别迭代优化和离线保存策略. 此外, CFR算法最终收敛得到的是一种静态的离线策略, 所以在对手策略变化时存在无法动态适应和剥削对手等问题.
DeepStack[29]是利用深度神经网络拟合纳什均衡策略方法的典型代表, 其核心主要是利用CFR+算法[30]迭代计算出部分游戏状态对应的纳什均衡策略, 然后使用神经网络对采样到的“状态-策略”样本进行拟合, 并利用神经网络的泛化能力, 估计得到没有采样过状态的策略信息. 此类方法的性能主要依赖于采样到的样本数量和神经网络拟合精度, 比如DeepStack需要在每个阶段游戏中至少采样106种游戏状态, 并在博弈子树上进行至少103轮算法迭代从而得到神经网络训练样本, 这至少需要耗费106个CPU小时和103个GPU小时的计算资源, 因而该方法需要极其巨大算力支持, 导致其运算经济性较差, 并且训练样本的存储也需要耗费大量的存储资源. 此外, 在与对手实际交互过程中, DeepStack每次决策均需要在博弈子树上进行算法迭代以求解均衡策略, 存在决策速度和算法性能的矛盾性问题.
神经虚拟博弈(Neural fictitious play, NFSP)[31]是基于深度强化学习自我博弈优化方法的典型代表, 其核心思想是通过自我博弈对战提升策略性能, 算法训练过程中博弈双方每次固定其中一方策略, 利用强化学习算法通过在线博弈优化另一方策略, 交替进行获得策略提升. 此类基于强化学习的方法需要不断采样大量的交互数据并保存到经验回放池[32-33], 从而给神经网络的训练优化提供样本. NFSP在训练时需要至少采样约3×107组交互样本, 并且强化学习训练存在样本利用率问题. 此方法目前仅适用于小规模博弈问题和简化的德州扑克游戏中, 在大规模和多人博弈问题中存在算法稳定性差和无法快速收敛到纳什均衡解等问题.
上述HUNL的主流求解方法均是为得到近似的纳什均衡策略, 从而在理论上保证自己不输. 但是对于德州扑克这种具有巨大状态和动作空间的不完美信息博弈游戏, 求解近似的纳什均衡策略不仅在计算层面是非常困难的, 而且计算结果与真实纳什均衡之间的差异也很难衡量. 此外, 由于在HUNL中纳什均衡策略的静态特性, 智能体只是根据已知信息使用固定响应作为自身策略, 忽略了对手行为对自身策略的影响, 所以无法根据对手的实际特点发现和利用对手弱点, 进而实现自身收益最大化.
此外, 演化学习在德州扑克游戏中得到过成功应用, ASHE[34]是此类方法的代表. ASHE首先根据人类玩家知识定义具有特定策略规则的对手, 然后通过智能体种群同时与不同对手进行对打和演化训练, 从而不断提升种群对特定对手的适应度. 由于ASHE博弈水平与训练对手的种类及策略水平相关性较强, 因此智能体训练时需要面对博弈类型尽量丰富的对手, 而该方法中对手智能体是根据常见玩法策略经过人工精心设计得到, 使该方法对人类专家知识的依赖较为严重. 并且在博弈过程中, ASHE需要依赖一种规则的决策算法得到其策略, 无法端到端完成该过程.
2. 方法框架
针对第1.2节中各类HUNL主流求解方案所存在的缺点, 本文设计了不完美信息博弈求解框架流程图(见图2). 本框架将演化学习方法和深度神经网络相结合, 通过在线的对手风格建模和种群策略集成使智能体能够适应对手策略的变化.
图 2 不完美信息博弈求解框架整体流程Fig. 2 Overall process of the imperfect information game solving framework本框架整体分为智能体的离线训练和在线博弈2个阶段, 主要包含以下4个步骤:
1) 首先通过智能体与已知风格的对手博弈交互, 完成智能体策略神经网络参数的种群演化训练, 获得能够剥削不同风格对手的克制策略网络;
2) 然后利用不同克制策略网络重新构建智能体, 并分别与其对应克制对手博弈交互, 通过在交互过程中收集对手信息来构建出对手特征库;
3) 在线博弈阶段, 首先对未知对手在线建模, 并与对手特征库进行博弈风格的相似度度量, 得到博弈风格度量矩阵;
4) 然后根据博弈风格度量矩阵对各种克制策略网络的输出进行加权集成, 从而获得集成策略与对手进行博弈交互.
2.1 离线训练阶段
智能体的离线训练阶段主要是为了获得能够剥削已知风格对手的策略网络并构建对手特征库. 本阶段首先设计含有不同博弈风格的对手池和能够在线建模对手的智能体结构, 然后通过智能体与对手池中的不同对手进行博弈交互, 从而利用种群遗传算法对智能体策略网络参数进行演化训练.
1)博弈风格建模与对手池设计
为保证集成策略在面对不同对手时均具有一定适应性, 每种克制策略应尽量均匀分布在整个策略空间中, 因此对手池应为策略网络的种群演化训练提供具有不同典型博弈风格的对手策略.
根据上述要求, 首先对德州扑克游戏人类专业玩家的常见策略和博弈风格进行充分调研和总结, 最终从德州扑克游戏代表性玩法的“策略激进度”和“手牌松紧度” 两个维度出发, 在整个策略空间中定义不同风格的对手策略从而构建对手池. “策略激进度”评价玩家在不同牌局状态时动作的概率分布情况, 激进类玩家即使在游戏局势不足够有利时, 选择加注动作的概率也比较高, 而在相同情况下保守类玩家弃牌的概率较高. “手牌松紧度”评价玩家所玩手牌的牌力范围, 若玩家只在手牌牌力较大时继续游戏, 手牌较小时选择弃牌, 则表示其博弈风格比较“紧”, 如果玩家即使在手牌牌力相对较小时也将游戏进行下去, 则表明其博弈风格比较“松”.
根据上述博弈风格的度量方法得到了如图3所示的对手池策略空间, 并将不同风格的玩家策略归类为“松−弱”、“松−凶”、“紧−弱”和“紧−凶”四类博弈类型. “松−弱”和“松−凶”型玩家具有较“松”的手牌松紧度, 其手牌牌力范围一般大于40 %, “紧−弱”和“紧−凶”型玩家则具有较“紧”的手牌松紧度, 其手牌牌力范围一般小于40 %. “松−弱”和“紧−弱”型玩家具有偏保守的策略激进度, 表现出跟注动作较多和加注动作较少等特点, “松−凶”和“紧−凶”型玩家的策略则偏激进, 表现出加注动作较多和跟注动作较少等特点.
2)智能体结构设计
为获得能在博弈交互过程中建模对手的智能体, 本文设计了图4中右图所示的智能体结构, 该智能体主要由特征提取器和策略网络2个模块组成.
特征提取器主要在博弈交互过程中从游戏的游戏牌局上不断收集与对手的历史交互信息, 然后统计获得对手在不同牌局状态时的特征信息, 并作为对手特征输入智能体策略网络, 从而完成对手建模任务. 德州扑克是一种参与人之间动作具有先后顺序的动态博弈过程, 适合使用博弈树对该类型的博弈进行表示. 而特征提取器就是一种与博弈树类似的树形数据结构, 树中结点代表不同的游戏牌局状态, 结点之间连接的边代表不同的动作, 每个结点上都将维护对手历史博弈交互信息的特征值.
牌局状态主要是由两名玩家交互的动作序列决定的. 特征提取器的构建是根据游戏历史动作序列进行动态“扩充”和“更新”的过程. 例如: 当特征提取器已经存在动作序列“加注300/加注600/跟注”, 如果另外两局游戏的动作序列分别为“加注300/加注600/跟注”和“加注300/加注600/加注900”, 那么对于已有的状态结点“跟注”, 特征提取器将只对该路径结点记录的特征进行更新. 而对于不存在的状态结点“加注900”, 特征提取器将扩充自身结点. 由于德州扑克游戏动作空间巨大, 为了控制树形结构的规模, 对游戏双方均进行了动作抽象, 并按照底池倍数将加注的筹码量映射到以下7个范围内: (0, 0.125)、(0.125, 0.375)、(0.375, 0.75)、(0.75, 1.25)、(1.25, 2.0)、(2.0, 4.0)、(>4.0).
智能体策略网络主要是完成“状态特征−动作策略”的端到端映射过程, 结构如图4所示, 由对手特征网络、游戏特征网络和策略输出网络三个模块组成, 其中对手和游戏特征网络均是由多层长短期记忆网络(Long short-term memory, LSTM)所构成, 图中每个LSTM区块均对应其中一层, 而策略输出网络则是由包含多个隐含层的全连接神经网络组成.
博弈过程中智能体每次做动作时, 首先根据当前的游戏牌局提取出游戏特征, 并根据牌局状态得到在特征提取器中对应结点位置, 从而读取得到结点上维护的对手特征. 然后将游戏特征和对手特征构建为特征向量, 并分别输入对应的特征网络进行特征编码. 最后, 2种特征网络输出的编码信息“拼接”后输入策略输出网络, 策略输出网络输出智能体策略并与对手博弈交互. 详细特征及编码方式见第3.1节特征定义部分.
3)种群遗传算法
在德州扑克这种对抗性的回合制不完美信息博弈游戏中, 由于对手策略未知并且动态变化, 导致深度强化学习算法在这种具有较高随机性环境中的训练难以收敛. 遗传算法通过模拟生物界“优胜劣汰, 适者生存”的进化法则, 在整个解空间内不断搜索具有最高博弈性能的智能体策略并繁衍新的种群, 使得种群适应度得到稳定的提高, 最终以轻量化的算法框架获得良好的收敛效果. 本文基于遗传算法的思想对智能体种群进行演化训练, 训练核心算法流程如图4所示, 主要包括以下3个步骤:
a) 选择. 选择是为了筛选并“淘汰”种群中适应度较低的个体, 适应度较高的个体将存活至下一代种群. 本步骤首先将种群每个智能体分别与所指定的对手进行博弈交互, 然后对每个智能体的适应度进行评估, 最后种群内所有智能体将根据其适应度高低进行排序, 并按照一定的比例(生存率)淘汰部分智能体. 智能体适应度函数为:
$${f} (i) = \frac{1}{m}\sum\limits_{j = 1}^m {\frac{{{e_{ij}}}}{{{n_j}}}} {\rm{, }}{n_j} = \max ({\rm{BB}},{\max_i}({e_{ij}}))$$ (1) 其中,
${{f}} (i)$ 为智能体$i$ 的平均适应度,$m$ 为对手数量,${e_{ij}}$ 为智能体$i$ 针对对手$j$ 的收益,${n_j}$ 为归一化因子, 当智能体的最大收益小于一个大盲注(BB)时, 将${n_j}$ 设置为大盲注以避免归一化错误.b) 交叉. 交叉是为了将种群内的优势基因(策略网络参数)进行“繁殖”得到下一代个体. 为充分保留种群优势基因, 本文将经过选择并生存的智能体进行分层, 其中高于生存智能体平均适应度的部分个体将获得“繁殖权”进行交叉, 其余智能体则直接进入下一代种群中并再次进行评估和选择. 这种分层方法在有效保留优势基因的同时, 能够充分排除游戏随机性因素对智能体性能的影响. 按照适应度对具有“繁殖权”的智能体进行排序, 适应度较高的智能体分别与每个适应度较低的智能体“配对”, “配对”双方进行基因交叉过程, 从而不断得到子代智能体基因, 直到种群恢复至原始规模.
进一步,提取出“配对”智能体的策略网络参数并分别将其拼接成参数向量作为交叉的2种父代基因. 基因交叉过程如图5所示. 对于图中2组父代基因, 将其分割成基因片段并按照其所属位置对双方的每组基因片段都按照智能体的适应度比例
${{f}} (1)$ 和${{f}} (2)$ 进行随机选择, 最终将所选择的基因片段组合成为新的交叉基因.c) 变异. 变异为子代基因增加了一定的随机性, 从而提高对种群整体适应度的探索能力. 变异过程遵循高斯分布, 并且随着种群演化的进行, 突变率和突变强度(即高斯分布的均值和标准差)线性下降. 具体操作步骤是, 首先按照突变率对图5中交叉基因的基因片段进行随机选择, 所选中基因片段将加上服从该突变率和突变强度的高斯噪声从而得到子代基因, 进而最终获得下一代种群.
上述步骤在训练过程中反复进行. 随着不断地种群演化迭代, 种群的整体适应度将不断提升, 最终保存最后一代种群中适应度最高的基因作为智能体策略网络的参数. 算法详细流程如算法1所示.
4)对手特征库构建
为了在线博弈阶段实现对手博弈风格的度量识别, 需要对不同对手的历史交互信息进行收集, 从而构建对手特征库. 对未知对手的博弈风格进行度量时, 对手特征库主要用作比对的“模板”. 为此, 本文使用训练得到的各类克制策略网络重新构建智能体, 并分别与所克制的对手再次进行博弈交互, 最终分别保留其特征提取器构建对手特征库.
2.2 在线博弈阶段
本阶段设计了一种对种群策略加权集成的博弈求解框架. 该框架在对未知对手的博弈风格度量后, 能够根据对手的博弈风格及时调整自身的集成策略, 并且在建模置信度较低时, 智能体也能使用基础策略网络的输出作为安全策略, 从而避免智能体出现重大决策失误. 该框架主要分为以下2个模块:
1)对手博弈风格度量模块
本模块通过对未知风格对手与对手特征库中已知风格对手的博弈风格特征进行相似度度量, 从而估计未知风格对手的博弈类型相似度. 该模块具体结构如图6所示.
算法1. 种群遗传算法
输入. 训练对手集合
$O$ 参数. 演化代数
$G$ , 智能体种群个体数$N$ 1) 随机初始化种群
$N$ 个智能体及策略网络参数;2) for
$g = 1 \to G$ do;3) for
$i = 1 \to N$ do;4) 智能体
$i$ 与对手集合$O$ 中每个对手对打测评得到对应收益;5) 利用式(1)计算智能体
$i$ 平均适应度${{f}} (i);$ 6) end for;
7) 根据智能体适应度
${{f}} (i)$ 按照生存率比例淘汰性能较差个体;8) 按照存活种群平均适应度进行分层, 高于平均值个体将获得繁殖权进行交叉, 其余个体进入第
$g + 1$ 代种群;9) while 第
$g + 1$ 代种群个体数量小于$N$ do;10) 按照适应度大小顺序从具有繁殖权个体中选择交叉父母;
11) 提取交叉双方智能体策略网络参数, 拼接组成父代基因;
12) 按照图5所示方法对父代基因进行交叉得到交叉基因;
13) 对交叉基因片段增加高斯噪声进行变异得到子代基因;
14) 使用子代基因重构智能体并作为第
$g + 1$ 代种群个体;15) end while;
16) end for;
17) 保存种群中适应度最高的个体基因(策略网络参数).
具体地, 智能体与未知风格对手博弈过程中不断收集历史交互信息并构建特征提取器, 从而逐渐提高对手建模可信度. 在当前牌局状态对应的对手博弈风格特征达到置信度要求后, 智能体将收集本游戏阶段内历史轨迹上所有结点的对手博弈风格特征向量序列, 并与对手特征库中不同的已知风格对手的特征向量序列进行“距离”度量, 从而得到未知风格对手与已知风格对手的博弈风格度量矩阵:
$ {{\boldsymbol{D}}}_{8\times k}=\left[{d}_{i}^{p}\right], \;(i=1,2,\cdots ,8;\;p=1,2,\cdots ,k)$ . 其中,$k$ 表示已知风格对手的数量,$i$ 表示智能体分别位于8种不同游戏阶段($i = 1,2,3,4$ 分别表示小盲位的4个游戏押注阶段,$i = 5,6,7,8$ 则表示大盲位的4个游戏阶段),$d_i^p$ 表示未知风格对手在游戏阶段$i$ 与已知风格对手$p$ 之间博弈风格特征向量的相似度. 相似度度量函数为:$$\begin{split} d_i^p =\;& \sum\limits_{j = 1}^m {{\rm{distance}}\left( {{{\boldsymbol{a}}_{ij}},{\boldsymbol{o}}_{ij}^p} \right)} =\\ & \sum\limits_{j = 1}^m {\sqrt {\sum\limits_{l = 1}^n {{{\left( {{f^l}({{\boldsymbol{a}}_{ij}}) - {f^l}({\boldsymbol{o}}_{ij}^p)} \right)}^2}} } } \end{split} $$ (2) 其中,
$m$ 表示当前牌局状态对应游戏历史轨迹上的结点数量(即对手博弈风格特征向量数量),${{\boldsymbol{a}}_{ij}}$ 表示未知风格对手在游戏阶段$i$ 的第$j$ 组博弈风格特征向量,${\boldsymbol{o}}_{ij}^p$ 表示已知风格对手$p$ 的对应博弈风格特征向量,$n$ 表示特征向量维度,${f^l}({{\boldsymbol{a}}_{ij}})$ 表示未知风格对手特征向量${{\boldsymbol{a}}_{ij}}$ 的第$l$ 种特征,${f^l}({\boldsymbol{o}}_{ij}^p)$ 表示已知风格对手$p$ 对应特征向量${\boldsymbol{o}}_{ij}^p$ 的第$l$ 种特征.2)克制策略集成模块
受到集成学习思想的启发, 本节设计了如图7所示的种群策略集成模块, 该模块中各个策略网络的输出是能够剥削不同风格类型对手的策略, 而这些策略只是整个策略空间的一些局部最优解, 因此在面对未知对手时并不具备适用性. 本文设计的策略集成方法可以将不同克制策略网络的输出
${\boldsymbol{\pi }}_i^p$ 通过博弈风格度量矩阵${\boldsymbol{D}}$ 进行加权集成, 从而构建集成策略${{\boldsymbol{\pi }}^{\rm{int} }}$ . 策略加权集成方式:$$\begin{split} {\boldsymbol{\pi }}_i^{\rm{int} } =\;& \sum\limits_{p = 1}^k {{\boldsymbol{\pi }}_i^p} \cdot {\rm{softmax(}}{{\boldsymbol{d}}_i}{\rm{)}}= \\ & \sum\limits_{p = 1}^k {{\boldsymbol{\pi }}_i^p\frac{{{{\rm{e}}^{d_i^p}}}}{{\sum\limits_{q = 1}^k {{{\rm{e}}^{d_i^q}}} }}} = \sum\limits_{q = 1}^k {{{\rm{e}}^{ - d_i^q}}} \sum\limits_{p = 1}^k {{\boldsymbol{\pi }}_i^p \cdot {{\rm{e}}^{d_i^p}}} \end{split} $$ (3) 其中,
${\boldsymbol{\pi }}_i^{\rm{int} }$ 表示游戏阶段$i$ 的集成策略,${\boldsymbol{\pi }}_i^p$ 表示克制策略网络$p$ 在阶段$i$ 的输出策略.在与未知风格对手博弈交互的初始阶段, 由于对手的特征收集累积量较少, 因此对手建模的置信度较差, 此外对于从未经历或者经历次数较少的牌局状态也会出现该问题. 为避免因上述问题而导致决策失误, 本节训练得到一个基础策略网络, 该策略网络是由智能体与对手池中所有已知风格对手对打和种群演化训练得到的, 其输出
${\boldsymbol{\pi }}_i^{base}$ 作为在对手建模置信度较低情况下的安全策略, 从而保证智能体博弈性能的“下限”.最后, 在种群集成策略
${\boldsymbol{\pi }}_i^{\rm{int} }$ 和基础策略${\boldsymbol{\pi }}_i^{base}$ 之间, 智能体将根据建模置信度进行选择, 并作为其最终集成策略${\boldsymbol{\pi }}_i^*$ 与对手交互.3. 实验与结果分析
3.1 实验设置
1)游戏参数设置与性能评价方式
本文所有实验均在2人无限注德州扑克游戏环境中进行. 其中, 玩家每局总筹码量为
$2 \times {10^4}$ , 小盲注和大盲注分为50和100, 每局游戏结束后筹码重置并且双方交换位置. 为评判智能体策略好坏, 游戏双方对打$2 \times {10^4}$ 局游戏并使用德州扑克AI研究领域最为常见的平均每局千分之一个大盲注(Millesimal big blind per hand, mbb/h)作为智能体博弈性能的评价指标.2)特征定义及编码
本文收集了10种特征作为策略网络的输入, 具体的名称、含义及编码方式如下:
a) 访问频率: 游戏历史中访问特征提取器中结点的频率, 代表玩家在不同牌局状态下所有动作的频率分布信息;
b) 弃牌率: 特征提取器中当前结点为根的子树上因对手弃牌使游戏结束的频率;
c) 摊牌率: 特征提取器中当前结点为根的子树上双方玩家均未弃牌而使游戏进入摊牌阶段的频率;
d)期望牌力: 特征提取器中当前结点为根的子树上摊牌时对手的平均牌力;
e) 同花或顺子: 当前公共牌对手同花或顺子的概率;
f) 对牌数量: 当前公共牌中对牌的数量;
g) 游戏轮次: 当前游戏所处轮次;
h) 手牌牌力: 自身当前手牌期望牌力;
i) 对手加注额: 对手加注的总筹码比例;
j) 自身加注额: 自身加注的总筹码比例.
其中, 前4种特征由特征提取器直接获得并组成得到对手特征向量, 特征向量(例如: [0.1432, 0.4833, 0.6528, 0.1189])中每一维度分别对应表示: 访问频率、弃牌率、摊牌率和期望牌力. 而游戏特征则由上述其余6种特征对应组成, 表示当前游戏公共信息和智能体私有信息.
对于对手博弈风格度量模块, 本文需要获取特征提取器中本阶段游戏所对应的历史路径. 对于其中每个结点本文设计了11种对手博弈风格特征
${f^l}({{\boldsymbol{a}}_{ij}}){\rm{ (}}l = 1,2, \cdots ,{\rm{11}})$ 组成对应的特征向量${{\boldsymbol{a}}_{ij}}$ , 除了上述所列举的摊牌率和期望牌力, 还包括当前牌局状态对手选择弃牌、跟牌/过牌、加注动作的概率(即特征提取器在当前牌局状态对应结点下每条边的访问频率), 由于加注动作被抽象为7种, 因此特征提取器每个结点上都将得到一个11维的特征向量${{\boldsymbol{a}}_{ij}}$ .3)对手设置
为给智能体策略网络种群演化训练提供对手, 本文从图4对手池策略空间中采样得到8种具有已知风格的对手智能体
$({O_{\rm{1}}},\;{O_{\rm{2}}},\; \cdots ,\,{O_{\rm{8}}})$ , 每种对手智能体的博弈风格及详细定义如表1所示. 表1中前4个对手$({O_{\rm{1}}},\;{O_{\rm{2}}},\;{O_3},\;{O_4})$ 是4种风格最为明显的智能体, 策略较为简单因而具有较高的利用率, 在种群演化训练过程中比较容易被剥削. 而表1中后4个对手$({O_5},\;{O_6},\;{O_7},\;{O_8})$ 策略相对复杂且利用率适中, 有利于在种群演化训练过程中提高智能体策略的博弈水平.表 1 对手智能体博弈风格及定义Table 1 The opponents＇play styles and definitions名称 类型 手牌松紧度 策略激进度 ${O_{\rm{1}}}$ 松−弱 70 % 极度保守 ${O_2}$ 松−凶 70 % 极度激进 ${O_3}$ 紧−弱 10 % 极度保守 ${O_4}$ 紧−凶 10 % 极度激进 ${O_5}$ 松−弱 50 % 相对保守 ${O_6}$ 松−凶 50 % 相对激进 ${O_7}$ 紧−弱 30 % 相对保守 ${O_8}$ 紧−凶 30 % 相对激进 为验证智能体在对手策略不断变化时的适应能力, 本文设计了一个可以进行策略动态切换的对手智能体
${O_{random}}$ , 该智能体从对手池策略空间中每隔500局游戏随机采样一种对手策略作为自身策略.4)实验参数设置
表2为策略网络结构和遗传算法训练的相关参数, 表2中数据是经过对算法训练的收敛速度和最终平均适应度水平综合考虑后确定的, 各类策略网络均是使用表中所设置参数值进行种群演化训练得到.
表 2 策略网络结构与训练参数Table 2 Policy network structure and the training hyper-parameters参数含义 参数值 对手特征网络LSTM区块数 5 对手特征网络LSTM时间序列步数 5 对手特征网络输出维度 200 游戏特征网络LSTM区块数 5 游戏特征网络LSTM时间序列步数 5 游戏特征网络输出维度 300 策略输出网络输入层神经元数量 500 策略输出网络隐含层数量 2 策略输出网络隐含层神经元数量 300 策略输出网络输出层神经元数量 10 种群演化代数 300 种群个体规模 100 种群生存率 0.25 基因变异率(初始/最终) 0.25/0.05 基因变异强度(初始/最终) 0.5/0.1 单个对手对打训练牌局数量 10000 对手特征库收集游戏对打局数 100000 基础策略网络通过种群智能体与定义的8种对手交互训练得到, 训练过程中对种群的100个智能体进行300代演化训练. 每个智能体与单个对手每次对打
${10^4}$ 种牌局, 并对牌局进行手牌交换后重新对打, 从而排除牌局随机性对性能的影响. 因此, 种群中每一个智能体均与每个对手对打$2 \times {10^4}$ 局游戏后进行适应性评估和选择过程. 最终第300代种群中适应度最高的智能体策略网络保存为基础策略网络.克制策略网络是通过智能体只与一种已知风格对手进行种群演化训练得到的, 训练过程中也对种群的100个智能体进行了300代的种群演化训练, 然后保存第300代中适应度最高的智能体策略网络作为一种克制策略网络. 因此对于对手池中定义的8种不同风格对手, 最终得到8个能够分别克制对应对手的策略网络.
为构建对手特征库, 首先利用每种克制策略网络重新构建智能体, 然后与其克制对手对打
${10^5}$ 局游戏, 最后将特征提取器分别保存并构建对手特征库.表2中策略输出网络隐含层神经元数量和种群生存率2种参数对算法的稳定性和收敛水平具有较大影响, 为确定上述两种参数的合适取值, 本文在基础策略网络训练过程中分别对2种参数进行了网格搜索, 参数对比结果见图8和图9.
图 8 策略输出网络隐含层神经元数量对种群平均适应度的影响Fig. 8 The influence of the hidden neurons in policy output network on population fitness
图 9 种群生存率对种群平均适应度的影响Fig. 9 The influence of population survival rates on population average fitness从图8中数据对比可知, 策略输出网络隐含层神经元数量的取值会对种群会的平均适应度收敛水平造成一定影响. 神经元数目在50到300之间取值过程中, 随着神经数量的增加适应度水平也在不断提升. 当神经元数量达到一定数量后(即300左右及以上), 适应度水平并不会随之一直提升, 而是最终达到一定的水平并趋于稳定. 从图9可明显看出, 种群生存率对平均适应度的影响出现与图8类似的变化趋势. 说明当所选的参数值超过一定“阈值”之后, 系统性能的收敛水平对参数变化并不敏感. 因而, 在保证算法收敛水平的前提下尽量使用较少的参数量, 根据网格搜索的结果最终分别将上述2种参数设置为300和0.25.
3.2 消融实验
1)基础策略网络训练
基础策略网络演化训练时智能体一直与多个对手博弈交互, 由于对手具有不同的博弈风格和水平, 因此训练过程中与不同对手的交互先后顺序可能会对种群的整体适应度产生较大影响. 为最大化种群适应度, 本文设计了一种三阶段的训练策略并与其他三种进行对比实验, 得到如图10所示的种群平均适应度变化曲线, 其中: 训练策略1中智能体种群在300代的演化训练时一直同时与表1中的8种对手交互; 训练策略2中智能体种群在前100代演化训练中一直与前4种对手交互, 后200代则只与后4种对手交互; 训练策略3中智能体种群在前100代演化训练中一直与前4种对手交互, 后200代则与8种对手交互; 训练策略4中智能体种群在前100代训练中一直与前4种对手交互, 中间100代只与后4种对手交互, 最后100代则同时与8种对手交互.
图 10 不同训练策略对种群平均适应度的影响Fig. 10 The influence of different training strategies on population average fitness训练策略1中智能体需要一直同时面对8种不同风格对手进行对打训练, 经过190代左右的种群演化训练, 其平均适应度最终收敛在0.1212左右. 该训练策略在训练过程中与另外两种训练策略相比表现出更大的“震荡”幅度, 而且需要更多的演化代数才能使种群的平均适应度提升并趋于平稳.
训练策略2采用二阶段的分层训练方法, 第1阶段中种群在第30代左右平均适应度得到快速提升并收敛稳定在0.8515左右; 在第2阶段中,由于所面对的对手利用率较低, 因此种群在第101代时的策略无法有效剥削此类对手, 使其平均适应度也迅速降低至−1.5645. 经过第2阶段的训练, 种群在第130代左右平均适应度最终稳定到0.3312左右. 该训练策略 虽然与训练策略1相比能够明显提高种群平均适应度收敛速度, 但最终的平均适应度却明显低于训练策略4. 这表明每次只面对其中4种对手的分层训练策略可能会使种群在第2阶段的训练后陷入局部最优, 从而失去对前四种对手的克制性.
训练策略3也采用两阶段的分层训练方法, 是在策略2的基础上更改第2阶段所面对的对手得到, 即后200代同时面对8种对手. 从曲线对比来看, 策略3最终收敛水平与策略2并无太大差异, 但值得注意的是策略3在第2阶段训练开始时的震荡幅度明显强于策略2, 训练过程中收敛速度和稳定性明显低于策略2. 此外, 策略3与策略4相比最终并不能达到相近适应度水平.
训练策略4采用三阶段的演化训练方案, 在前200代的种群演化训练过程中其与策略2的曲线变化趋势相似, 种群的平均适应度最终稳定在0.6654左右, 与另外两种策略相比最终适应度得到较大提升. 这表明训练策略4的三阶段分层训练方式使种群具有较快的收敛速度并且避免陷入局部最优问题, 最大化地探索了种群的博弈性能.
由图10可以看出, 训练策略4能使种群平均适应度较快地收敛到更高的水平, 因此本文将其作为基础策略网络的种群演化训练策略.
2)在线博弈阶段消融实验
为验证在线博弈阶段种群策略集成框架中不同模块的作用, 本节对其进行消融实验,结果见表3, 其中Slumbot1是世界计算机扑克大赛中2人无限注德州扑克组冠军智能体, 代表纳什均衡策略智能体,并作为本实验对照组, 表3中每组实验数据均表示不同智能体面对某种对手时的评估性能, 例如智能体
${A_{base}}$ 与对手${O_{\rm{1}}}$ 的评估结果是1000 mbb/h, 表示经过$2 \times {10^4}$ 局游戏的对打评测后, 结果表明${A_{base}}$ 博弈性能优于${O_{\rm{1}}}$ .表 3 消融实验结果(mbb/h)Table 3 Ablation study results (mbb/h)智能体\对手 ${O_{\rm{1}}}$ ${O_2}$ ${O_3}$ ${O_4}$ ${O_5}$ ${O_6}$ ${O_7}$ ${O_8}$ ${O_{random}}$ Slumbot 702.53 12761 4942.58 14983 652.73 2623.14 484.29 2449.08 3387.13 ${A_{tar}}$ 999.92 29232 1494.92 27474 1391.04 12746 1371.10 34546 — ${A_{base}}$ 1000.00 22611 1205.05 20380 1109.84 9892.43 793.42 14568 5105.38 ${A_{ave}}$ 999.91 78.46 34.06 −5537.19 927.84 92.36 −631.55 −4461.82 −1068.44 ${A_{\rm{int} }}$ 999.92 29964 1305.04 27314 1316.21 12874 1380.88 18330 2738.98 ${A^*}$ 1000.00 24888 1310.34 27526 1286.08 11253 1020.38 16514 6359.36 ${A_{tar}}$ 为克制策略智能体, 其构建分别使用了不同的克制策略网络, 主要用于分别评估每种克制策略网络对其所克制对手的剥削性能. 因此, 表3中第1行评测数据均是某种对手与对应克制策略智能体的评估结果, 比如第1行中第1组数据代表对手${O_{\rm{1}}}$ 的克制策略博弈性能为999.92 mbb/h. 由测评数据可以看出, 各克制策略均能有效克制对应类型的对手. 由于克制策略只能针对一种对手, 所以此类评测数据可视为本文提出的种群策略集成框架智能体在面对对手池中已知对手时的性能“上界”.${A_{base}}$ 为基础策略智能体, 其构建只使用基础策略网络, 用于单独评估基础策略网络的性能. 测试数据表明${A_{base}}$ 在单独面对已知的不同对手时均具有相对良好的博弈性能, 这验证了基础策略网络所采用的三阶段分层种群演化训练方式, 既能保证种群博弈性能得到快速提升, 又能避免因为不同训练阶段面对不同对手所造成的克制策略“遗忘”问题. 此外,${A_{base}}$ 与动态策略对手${O_{random}}$ 的评测结果为5105.38 mbb/h, 这说明即使对手策略变化时基础策略也具有一定的适应性, 所以基础策略网络的输出可以作为建模置信度较低时的安全策略.${A_{ave}}$ 为克制策略网络静态集成的智能体, 其策略是直接将各个克制策略网络的输出进行“加和”得到的(即博弈风格度量矩阵为均匀分布), 主要用于探究在没有安全策略和对手博弈风格度量矩阵的情况下直接进行策略集成时智能体的性能表现. 从${A_{ave}}$ 、${A_{tar}}$ 及${A_{base}}$ 的实验结果对比可以看出, 这种直接对局部最优解“加和”的集成方法, 失去了克制策略原有的剥削性能, 使智能体即使在面对已知对手时也无法保证其博弈性能. 此外,${A_{ave}}$ 与动态策略对手${O_{random}}$ 的评测结果为−1068.44 mbb/h, 说明在面对对手变化时,${A_{ave}}$ 由于没有对手相似度的度量模块, 导致其不具有对动态策略的适应性.${A_{\rm{int} }}$ 为没有基础策略作为安全策略的动态集成策略智能体(即在${A_{ave}}$ 的基础上加入对手博弈风格度量模块), 用于评价在只使用对手博弈风格度量并进行策略集成时智能体的性能表现. 通过${A_{\rm{int} }}$ 与${A_{ave}}$ 的实验数据对比可以发现, 在使用博弈风格度量矩阵将克制策略进行加权集成后,${A_{\rm{int} }}$ 的博弈性能相比${A_{ave}}$ 得到显著提升, 这说明${A_{\rm{int} }}$ 的集成策略保留了各克制策略的剥削性能. 在面对策略随机变化的对手${O_{random}}$ 时,${A_{\rm{int} }}$ 的测评结果明显低于其在面对8种已知对手时的平均性能, 这说明在对手策略变化时,${A_{\rm{int} }}$ 由于由于没有基础策略作为安全性保障, 因此容易因建模置信度低而造成决策失误.${A^*}$ 为本文提出的种群策略集成框架所对应的智能体. 相比于智能体${A_{\rm{int} }}$ ,${A^*}$ 虽然在面对已知对手时性能表现略低于${A_{\rm{int} }}$ , 但是因其拥有基础策略网络模块作为安全策略, 使得在面对动态策略对手${O_{random}}$ 时${A^*}$ 的性能均明显优于${A_{\rm{int} }}$ 和${A_{base}}$ , 这体现基础策略网络可以有效减缓可能出现的决策失误问题. 此外, 从分别面对${O_{random}}$ 时的评测结果来看,${A^*}$ 的性能为6359.36 mbb/h, 明显高于Slumbot对应的3387.13 mbb/h, 这说明即使在面对对手策略变化时${A^*}$ 相比传统的纳什均衡策略也能够更好地剥削对手, 保证自身能够有良好的博弈性能.3.3 性能对比
1)算法博弈性能
为评估智能体
${A^*}$ 的实际博弈性能, 本节将其与第1.2节所述4种方法、知识AI和${O_{random}}$ 分别对打测评,结果见表4, 其中知识AI是5种基于人类专业玩家策略的规则智能体, 该类智能体具有动态的策略和完备的人类常见打法, 可以模拟人类玩家行为, 表格中知识AI的评测数据均是与五种人类规则AI对打$2 \times {10^4}$ 局游戏后的平均结果.表 4 博弈性能对比结果(mbb/h)Table 4 Performance comparison results (mbb/h)智能体 ${A^*}$ ASHE Slumbot Deepstack NFSP 知识AI ${O_{random}}$ ${A^*}$ — 675.68 −48.49 −896.76 32255 229.64 6359.36 ASHE −675.68 — −153.35 −1552.64 11904 −13.00 3177.68 Slumbot 48.49 153.35 — −103.44 8623.18 52.43 3387.13 DeepStack 896.76 1552.64 103.44 — 4084.27 139.41 1791.27 NFSP −32255 −11904 −8623.18 −4084.27 — −3257.75 −18819 知识AI −229.64 13.00 −52.43 −139.41 3257.75 — −91.92 ${O_{random}}$ −6859.36 −3177.68 −3387.13 −1791.27 18819 91.92 — 从表4可以看出, 智能体
${A^*}$ 、ASHE、NFSP和知识AI分别在面对目前具有最强性能的Slumbot和DeepStack时, 评测统计结果说明这种利用CFR算法求解的近似纳什均衡策略极难被剥削. 智能体${A^*}$ 在面对知识AI时评测统计结果达到229.64 mbb/h, 与ASHE和Slumbot分别对应的-13 mbb/h和52.43 mbb/h相比得到大幅度性能提升, 另外在面对${O_{random}}$ 时智能体${A^*}$ 同样具有最好的性能表现.为评估不同方法智能体在博弈过程中策略的动态变化情况, 本文记录了智能体
${A^*}$ 、ASHE、Slumbot和DeepStack分别与${O_{random}}$ 测评过程中的收益变化情况, 博弈性能变化曲线如图11所示. 数据从第5000局游戏开始,每隔500局游戏统计一次前5000局的平均博弈性能得到的. 可以看出, Slumbot和DeepStack这种典型的纳什均衡策略智能体, 在面对动态策略对手${O_{random}}$ 时由于策略的静态性使其不具备动态适应性. 智能体${A^*}$ 和ASHE能够不断收集交互数据从而建模对手, 使其均具有一定的适应能力, 但由于智能体${A^*}$ 能够通过策略集成策略框架来根据对手实际风格特征针对性地适应对手, 使其相对ASHE具有更加强大的动态适应性.上述实验可以有效说明,本文所提出的博弈求解框架,在博弈交互过程中可以不断建模对手从而获得一定的适应性, 并相比已有方法能够大幅提升面对不断变化的对手策略时的博弈性能. 实验结果也验证纳什均衡策略所存在的严重限制智能体剥削性问题, 使其在对手策略变化时无法最大化自身收益.
2)算法轻量性
为评估本文所提出博弈求解框架的轻量性, 本节对比不同算法分别在训练和测评2个阶段的资源需求, 包括存储资源需求、计算资源需求以及测评的动作响应时间. 详细对比数据如表5所示, 表5数据均来自原始论文以及复现时的实际数据.
表 5 算法轻量性对比Table 5 Light-weight comparison智能体 训练阶段资源需求 测评阶段资源需求 存储资源(GB) 计算资源(h) 存储资源(GB) 计算资源(h) 响应时间(s) ${A^*}$ ~30 ~2×103 CPU <0.5 <0.1 CPU <0.1 ASHE ~30 ~103 CPU ~30 <0.1 CPU <0.1 Slumbot >500 >105 CPU >500 >10 CPU ~1 DeepStack >500 >106 CPU
>103 GPU>10 ~103 CPU
~103 GPU~30 NFSP >50 ~104 CPU
~102 GPU~1 <1 CPU
<1 GPU<1 人类玩家 — — — — ~15 对于训练阶段, 从存储资源需求来看, Slumbot和DeepStack由于需要使用CFR相关算法求解并保存纳什均衡策略, 因此需要500 GB以上的存储资源, NFSP则需要50 GB以上的内存资源将不断采样到的交互数据保存到经验回放池, 而智能体
${A^*}$ 和ASHE仅需要约30 GB的存储资源来离线保存牌力数据. 从算法计算资源需求来看, 智能体${A^*}$ 略高于ASHE的计算资源需求(小于2倍), 仅需一台无GPU的常规计算机使用约2000个CPU小时的计算量, 远低于Slumbot、DeepStack和NFSP这种需要大规模计算机集群进行分布式计算求解的智能体. 在对打测评阶段, 智能体${A^*}$ 对每一局游戏的实际牌力进行在线解算, 在不牺牲响应速度的前提下有效降低对存储资源的需求, 使其对存储和计算资源的需求量均小于其他智能体. 最终, 智能体${A^*}$ 能够以平均小于0.1秒的动作响应时间进行博弈交互, 远低于DeepStack和人类玩家.综上所述, 本文提出的博弈求解框架能够在较少计算和存储资源的情况下保证自身博弈性能和响应速度, 相比其他已知求解方法更具有轻量性优势.
4. 结论
本文提出了一种针对两人无限注德州扑克这种典型大规模不完美信息博弈问题的博弈求解框架, 具有轻量高效并能快速识别和适应对手策略变化等优点. 该框架首先基于演化学习方法对智能体进行种群演化训练得到剥削不同风格对手的克制策略网络, 然后对未知风格对手进行在线建模和风格度量, 最后采用种群策略集成最大化剥削和利用对手.
针对基础策略网络的种群演化训练过程, 本文探讨了4种不同的训练策略对种群平均适应度的影响. 通过对比, 本文的三阶段分层训练方式能有效提升训练速度和种群平均适应度. 在线博弈阶段的消融实验中, 本文验证了不同模块的作用. 实验数据表明,本文提出的种群策略集成框架能有效度量未知对手的博弈风格, 并调整自身集成策略来提升收益. 由评测结果可得, 本博弈求解框架智能体
${A^*}$ 在分别面对动态策略的对手${O_{random}}$ 和人类规则的知识AI时, 其博弈性能明显强于基于纳什均衡策略的智能体. 这说明相比纳什均衡策略, 即使对手策略发生变化${A^*}$ 也能够更好地剥削对手, 保证自身良好的博弈性能. 综上所述, 本文提出的不完美信息博弈求解框架能够有效建模未知对手并度量其所属风格, 利用克制策略的加权集成与对手交互, 有效提高智能体在面对不同对手时的剥削性能.本文提出的博弈求解框架具有一定的通用性, 该框架不仅适用于德州扑克这一特定游戏环境, 还可以为实际生活中的诸多不完美信息博弈问题提供一种可行的解决思路. 未来值得进一步探索的问题包括强化学习在本框架中的应用方式以及本框架在多人德州扑克游戏中的拓展问题等.
-
表 1 数据集描述
Table 1 The data set description
数据集 维数 样本数 类别数 IRIS 4 150 3 Data set IIb 1440 504 2 Data set II 2400 1020 2 DLBCL 5469 77 2 Colon 2 000 62 2 Prostate0 6033 102 2 
下载: 导出CSV
表 2 传统降维方法的聚类准确率(%) (方差, 维数)
Table 2 Comparison of clustering accuracy of traditional methods (%) (variance, dimension)
数据集 k-means 传统算法 PCA LPP NPE IRIS 89.13 (0.32) 89.07 (0.34, 4) 90.27 (0.84, 2) 88.67 (0.00, 2) Data set IIb 86.47 (2.53) 88.21 (0.61, 4) 88.69 (7.33, 4) 89.58 (6.32, 256) Data set II 72.38 (8.94) 79.31 (4.39, 2) 82.26 (0.13, 512) 82.62 (0.71, 256) DLBCL 68.83 (0.00) 68.83 (0.00, 2) 63.55 (1.86, 8) 69.09 (0.82, 32) Colon 54.84 (0.00) 54.84 (0.00, 2) 54.84 (0.00, 2) 56.45 (0.00, 2) Prostate0 56.86 (0.00) 56.83 (0.00, 2) 56.86 (0.00, 2) 56.86 (0.00, 4)
下载: 导出CSV
表 3 ELM降维方法聚类准确率(%) (方差, 维数)(参数)
Table 3 Comparison of clustering accuracy of ELM methods (%) (variance, dimension)(parameters)
数据集 k-means Unsupervised ELM Subspace + unsupervised ELM US-ELM(λ) ELM-AE(c) ML-ELM-AE (c) SNP-ELM(λ,η,δ) SELM-AE(c, λ) ML-SELM-AE(c, λ) IRIS 89.13
(0.32)93.87
(13.78, 2)
(0.1)93.93
(1.19, 2)
(10)95.20
(1.05, 2)
(0.01)98.46
(0.32, 2)
(10, 0.6, −1)98.00
(0.00, 2)
(10, 0.01)98.40
(0.56, 2)
(10, 0.01)Data set IIb 86.47
(2.53)91.59
(4.25, 4)
(0.1)91.98
(0.25, 4)
(0.1)92.46
(0.08, 16)
(1)92.06
(0.13, 16)
(0.001, 0.8, 0.2)95.29
(0.06, 8)
(0.001, 1)96.63
(0.00, 8)
(0.001, 0.1)Data set II 72.38
(8.94)83.18
(0.32, 256)
(10)82.84
(0.00, 2)
(0.001)83.03
(0.00, 2)
(0.1)83.92
(1.65, 2)
(10, 0.2, −0.2)83.14
(0.00, 2)
(0.01, 1)84.22
(0.00, 2)
(0.001, 10)DLBCL 68.83
(0.00)76.62
(0.00, 32)
(0.001)78.05
(0.73, 2)
(0.001)82.46
(0.68, 2)
(0.001)86.34
(1.78, 8)
(0.001, -0.2, 0.6)83.63
(2.51, 2)
(10, 0.1)86.71
(3.48, 2)
(10, 1)Colon 54.84
(0.00)67.06
(4.19, 32)
(0.001)69.35
(0.00, 2)
(0.001)80.32
(1.02, 2)
(0.001)85.95
(3.69, 8)
(0.001, −0.8, 1)83.87
(0.00, 4)
(10, 0.1)85.97
(0.78, 2)
(10, 0.1)Prostate0 56.86
(0.00)64.09
(5.83, 2)
(0.01)75.98
(0.51, 2)
(0.01)79.61
(1.01, 2)
(0.01)82.92
(2.19, 128)
(0.1, 0.2, 0.8)84.31
(0.00, 2)
(10, 1)85.29
(0.00, 2)
(10, 0.01)
下载: 导出CSV
表 4 运行时间对比(s)
Table 4 Comparison of running time (s)
数据集 SNP-ELM SELM-AE ML-SELM-AE IRIS 4.58 0.02 0.02 Data set IIb 4.64×103 0.16 0.33 Data set II 8.24×103 0.65 0.76 DLBCL 7.77 0.04 0.06 Colon 3.44×102 0.03 0.11 Prostate0 1.15×102 0.07 0.13
下载: 导出CSV
表 5 ML-SELM-AE降维前后数据的聚类准确率(%) (方差)
Table 5 Clustering accuracy before and after ML-SELM-AE dimensionality reduction (%) (variance)
数据集 k-means LSR LRR LatLRR 未降维 已降维 未降维 已降维 未降维 已降维 未降维 已降维 IRIS 89.13 (0.32) 98.40 (0.00) 82.40 (0.69) 97.33 (0.00) 90.87 (0.00) 94.00 (0.83) 81.27 (1.03) 97.33 (0.00) Data set IIb 86.47 (2.53) 93.25 (0.00) 83.13 (0.00) 86.59 (0.19) 83.13 (0.00) 86.11 (0.00) 83.13 (0.00) 86.48 (0.25) Data set II 72.38 (8.94) 84.22 (0.00) 83.24 (0.08) 83.29 (0.05) 83.24 (0.00) 83.24 (0.00) 83.24 (0.00) 83.33 (0.00) DLBCL 68.83 (0.00) 86.71 (3.48) 76.62 (0.00) 81.43 (0.63) 76.62 (0.00) 78.57 (0.68) 74.03 (0.00) 78.18 (3.23) Colon 54.84 (0.00) 85.97 (0.78) 67.74 (0.00) 74.19 (0.00) 63.39 (0.00) 69.35 (0.00) 66.13 (1.67) 75.65 (4.06) Prostate0 56.86 (0.00) 85.29 (0.00) 63.82 (1.37) 70.59 (0.00) 57.84 (0.00) 63.73 (0.00) 55.88 (0.00) 74.51 (0.00)
下载: 导出CSV
表 6 三层极限学习机自编码器隐层节点数与聚类准确率(%) (方差)
Table 6 The number of hidden layer nodes and clustering accuracy for three-layer extreme learning machine autoencoder (%) (variance)
数据集 ML-ELM-AE (Multilayer ELM-AE) ML-SELM-AE (Multilayer SELM-AE) 500-100-2 500-100-10 500-100-50 500-100-100 500-100-2 500-100-10 500-100-50 500-100-100 Data set IIb 88.69 (0.00) 91.98 (0.25) 90.89 (0.06) 87.66 (0.20) 95.44 (0.00) 94.92 (0.17) 95.44 (0.00) 94.80 (0.33) Data set II 82.94 (0.00) 82.94 (0.00) 82.94 (0.00) 82.94 (0.00) 83.14 (0.00) 83.04 (0.00) 83.04 (0.00) 83.04 (0.00) DLBCL 74.03 (0.00) 72.99 (3.29) 72.73 (0.00) 69.22 (0.88) 80.52 (0.00) 80.52 (0.00) 78.57 (2.05) 76.62 (0.00) Colon 73.87 (1.67) 59.68 (0.00) 69.52 (7.35) 59.03 (0.83) 78.55 (2.53) 75.97 (7.81) 76.13 (9.46) 70.48 (4.37) Prostate0 66.67 (0.00) 60.78 (0.00) 59.80 (0.00) 62.75 (0.00) 77.16 (0.47) 82.35 (0.00) 78.33 (6.51) 80.39 (0.00) 数据集 2-2-2 10-10-10 50-50-50 100-100-100 2-2-2 10-10-10 50-50-50 100-100-100 Data set IIb 92.46 (0.08) 90.48 (0.00) 90.16 (0.17) 90.40 (0.25) 96.63 (0.00) 95.83 (0.00) 95.44 (0.00) 94.84 (0.00) Data set II 83.04 (0.00) 83.04 (0.00) 83.04 (0.00) 82.94 (0.00) 84.22 (0.00) 83.14 (0.00) 83.04 (0.00) 83.04 (0.00) DLBCL 83.12 (0.00) 77.01 (0.63) 68.83 (0.00) 68.70 (0.41) 86.75 (4.23) 80.52 (0.00) 78.96 (0.82) 76.62 (0.00) Colon 80.64 (0.00) 60.00 (2.50) 70.00 (1.36) 62.90 (0.00) 85.97 (0.78) 68.23 (0.78) 80.65 (0.00) 76.61 (9.48) Prostate0 80.39 (0.00) 57.45 (0.83) 64.41 (0.47) 63.73 (0.00) 85.29 (0.00) 69.61 (0.00) 79.12 (6.67) 84.31 (0.00)
下载: 导出CSV
-
[1] Hinton G E, Salakhutdinov R R. Reducing the dimensionality of data with neural networks. Science, 2006, 313(5786): 504-507. doi: 10.1126/science.1127647 [2] 田娟秀, 刘国才, 谷珊珊, 鞠忠建, 刘劲光, 顾冬冬. 医学图像分析深度学习方法研究与挑战. 自动化学报, 2018, 44(3): 401-424.Tian Juan-Xiu, Liu Guo-Cai, Gu Shan-Shan, Ju Zhong-Jian, Liu Jin-Guang, Gu Dong-Dong. Deep learning in medical image analysis and its challenges. Acta Automatica Sinica, 2018, 44(3): 401-424. [3] Rik D, Ekta W. Partition selection with sparse autoencoders for content based image classification. Neural Computing and Applications, 2019, 31(3): 675-690. doi: 10.1007/s00521-017-3099-0 [4] Shao H D, Jiang H K, Zhao H W. A novel deep autoencoder feature learning method for rotating machinery fault diagnosis. Mechanical Systems and Signal Processing, 2017, 95: 187-204. doi: 10.1016/j.ymssp.2017.03.034 [5] Chiang H T, Hsieh Y Y, Fu S W, Hung K H, Tsao Y, Chien S Y. Noise reduction in ECG signals using fully convolutional denoising autoencoders. IEEE Access, 2019, 7: 60806-60813. doi: 10.1109/ACCESS.2019.2912036 [6] Yildirim O, Tan R S, Acharya U R. An efficient compression of ECG signals using deep convolutional autoencoders. Cognitive Systems Research, 2018, 52: 198-211. doi: 10.1016/j.cogsys.2018.07.004 [7] Liu W F, Ma T Z, Xie Q S, Tao D P, Cheng J. LMAE: a large margin auto-encoders for classification. Signal Processing, 2017, 141: 137-143. doi: 10.1016/j.sigpro.2017.05.030 [8] Ji P, Zhang T, Li H, Salzmann M, Reid L. Deep subspace clustering networks. In: Proceedings of the 31st Conference on Neural Information Processing Systems. Long Beach, USA, 2017. 23−32 [9] Kasun L L C, Yang Y, Huang G B, Zhang ZH Y. Dimension reduction with extreme learning machine. IEEE Transactions on Image Processing, 2016, 25(8): 3906-3918. doi: 10.1109/TIP.2016.2570569 [10] Huang G B, Zhu Q Y, Siew C K. Extreme learning machine: A new learning scheme of feedforward neural networks. In: Proceedings of Internatinaol Joint Conference on Neural Networks. Budapest, Hungary: IEEE, 2004. 985−990 [11] 许夙晖, 慕晓冬, 柴栋, 罗畅. 基于极限学习机参数迁移的域适应算法. 自动化学报, 2018, 44(2): 311-317.Xu Su-Hui, Mu Xiao-Dong, Chai Dong, Luo Chang. Domain adaption algorithm with ELM parameter transfer. Acta Automatica Sinica, 2018, 44(2): 311-317. [12] Huang G, Song S J, Gupta J N D. Semi-supervised and Unsupervised Extreme Learning Machines. IEEE Transactions on Cybernetics, 2014, 44(12): 2405-2417. doi: 10.1109/TCYB.2014.2307349 [13] 陈晓云, 廖梦真. 基于稀疏和近邻保持的极限学习机降维. 自动化学报, 2019, 45(2): 325-333.Chen Xiao-Yun, Liao Meng-Zhen. Dimensionality reduction with extreme learning machine based on sparsity and neighborhood preserving. Acta Automatica Sinica, 2019, 45(2): 325-333. [14] Lu C Y, Min H, Zhao Z Q. Robust and efficient subspace segmentation via least squares regression. In: Proceedings of the 12th European Conference on Computer Vision. Berlin, Germany: Springer, 2012. 347−360 [15] Ji P, Salzmann M, Li H D. Efficient dense subspace clustering. In: Proceedings of Winter Conference on Applications of Computer Vision. Steamboat Springs, CO, USA: IEEE, 2014.461−468 [16] Sun K, Zhang J S, Z C X, Hu J Y. Generalized extreme learning machine autoencoder and a new deep neural network. Neurocomputing, 2017, 230: 374-381. doi: 10.1016/j.neucom.2016.12.027 [17] Ma J, Yuan Y Y. Dimension reduction of image deep feature using PCA. Journal of Visual Communication and Image Representatio, 2019, 63: 1-8. [18] Wang S J, Xie D Y, Chen F, Gao Q X. Dimensionality reduction by LPP-L21. IET Computer Vision, 2018, 12(5): 659-665. doi: 10.1049/iet-cvi.2017.0302 [19] Kong D D, Chen Y J, Li N, Duan C Q, Lu L X, Chen D X. Tool wear estimation in end milling of titanium alloy using NPE and a novel WOA-SVM model. IEEE Transactions on Instrumentation and Measurement, 2020, 69(7): 5219-5232. doi: 10.1109/TIM.2019.2952476 [20] UCI Machine Learning Repository. [Online], available: http://archive.ics.uci.edu, September 8, 2020 [21] NYS Department of Health. [Online], available: http://www.bbci.de/competition/, September 8, 2020 [22] Gene Expression Model Selector. [Online], available: http://www.gems-system.org, September 8, 2020 [23] Kaper M, Ritter H. Generalizing to new subject in brain-computer interfacing. In: Proceedings of the 26th Annual International Conference of the IEEE Engineering in Medicine and Biology Society. San Francisco, USA: IEEE, 2004. 4363−4366 [24] Chen X Y, Jian C R. Gene expression data clustering based on graph regularized subspace segmentation. Neurocomputing, 2014, 143: 44-50. doi: 10.1016/j.neucom.2014.06.023 [25] Liu G C, Lin Z C, Yu Y. Robust subspace segmentation by low-rank representation. In: the 27th International Conference on Machine Learning. Haifa, Israel, 2010. 663−670 [26] Liu G, Yan S. Latent low-rank representation for subspace segmentation and feature extraction. In: Proceedings of International Conference on Computer Vision. Barcelona, Spain: IEEE, 2011. 1615−1622 期刊类型引用(3)
1. 王可，徐明亮，李亚飞，姜晓恒，鲁爱国，李鉴. 一种面向航空母舰甲板运动状态预估的鲁棒学习模型. 自动化学报. 2024(09): 1785-1793 . 
本站查看2. 葛迪，吴彦文，刘三女牙. 低成本自进化的学习者画像模型研究. 计算机工程与应用. 2023(11): 141-150 . 百度学术3. 程蓉，白艳萍，胡红萍，谭秀辉，续婷. 含类信息的极限学习机自动编码器特征学习方法. 电子测量技术. 2022(16): 71-79 . 百度学术其他类型引用(7)
-
AAS-CN-2020-0684数据.zip
-
下载:
计量
- 文章访问数: 1211
- HTML全文浏览量: 502
- PDF下载量: 263
- 被引次数: 10
