双人国际象棋小游戏(全球象棋双人赛成都圆满落幕 赵鑫鑫时凤兰喜获冠军)
双人国际象棋小游戏文章列表:
- 1、全球象棋双人赛成都圆满落幕 赵鑫鑫时凤兰喜获冠军
- 2、AI玩多人德扑击败顶级玩家！150美元，实力可掏空在线扑克公司
- 3、亲子游戏推荐：那些可以和孩子一起成长的游戏
- 4、AlphaGo原来是这样运行的，一文详解多智能体强化学习
- 5、什么？象棋和围棋都存在不败策略？
全球象棋双人赛成都圆满落幕 赵鑫鑫时凤兰喜获冠军
封面新闻记者 陈甘露
经过两天四轮的激烈争夺，11月20日晚，2022年第五届“一带一路”成都全球象棋双人赛在成都望江宾馆落下帷幕。
在国内混双组的较量中，赵鑫鑫/时凤兰组合经过一盘慢棋和两盘快棋加赛后，艰难击败洪智/党国蕾，喜获冠军和15万元奖金，洪智/党国蕾亚军，获得10万元奖金。这也是赵鑫鑫与不同组合连续第三次夺得全球双人赛冠军。在国际双人组比赛决赛中，中国澳门李梓毅/东马豪威组合击败中国沈思凡/马来西亚佐佐木雄希夺得冠军。
本届比赛由世界象棋联合会、成都市人民政府主办，中国象棋协会、成都市体育局、锦江区人民政府承办，成都棋院、锦江区文体旅局、腾讯棋牌天天象棋、成都市棋类运动协会协办。
在首日比赛中，国内混双组首轮郑惟桐/张国凤击败孟辰/郎祺琪，郝继超/王琳娜击败谢靖/梁妍婷，另外两台，蒋川/陈幸琳弈和赵鑫鑫/时凤兰，洪智/党国蕾与汪洋/赵冠芳也战和。晚上的第二轮，赵鑫鑫/时凤兰执黑击败孟辰/郎祺琪，另外三台全部弈和。
下午的第三轮比赛中，赵鑫鑫/时凤兰弈和郑惟桐/张国凤，以1胜2和稳稳地获得A组第一名。洪智/党国蕾则击败谢靖/梁妍婷，获得B组第一名，两对组合会师的决赛。
经过抽签，洪智/党国蕾执红，赵鑫鑫/时凤兰执黑。在慢棋比赛中，洪智组合错失开局的领先，被赵鑫鑫组合逐渐反先，最终慢棋弈和。之后进入紧张的10 10快棋加赛，赵鑫鑫目前在快棋等级分榜上位列第一，首局双方弈和，又进入第二局加赛，赵鑫鑫与时凤兰攻势猛烈，最终执黑胜出。
蒋全胜、李艾东、党斐、孙若谷等名师、帅哥、美女棋手的组合在直播间为棋友讲棋，也深受好评和追捧。
本届双人赛赛场氛围浓厚，各种高端直播设备琳琅满目，充分体现了象棋与互联网和AI的深度融合，同时为进一步优化赛场公开透明的竞赛环境，赛事组委会还特意在比赛场地安排专业机构对干扰竞赛的信号进行监测，取得良好效果。
赛后，成都棋院院长危建华表示，“一带一路”成都全球象棋双人赛是落实市委、市政府高质量发展世界赛事名城建设的重要组成部分，也是棋城高质量发展的重要一环。
同时，危建华表示，成都棋院坚持落实市委、市政府和市体育局有关疫情防控的各项措施，坚持办赛谋城、兴业惠民的发展理念，一边抓赛事举办，一边统筹好疫情防控，确保我们“一带一路”成都全球象棋双人赛能够在全年的第四季度收官季圆满完成。这是对成都经济社会发展和体育赛事全面复苏的一个积极响应。
本届全球象棋双人赛，创新采用线上线下相结合、海外棋手和国内棋手搭配相结合的形式。赛事直播这一块做到了和互联网AI的深度融合，并且赛场的竞赛环境进一步优化，透明公开。
【如果您有新闻线索，欢迎向我们报料，一经采纳有费用酬谢。报料微信关注：ihxdsb，报料QQ：3386405712】
AI玩多人德扑击败顶级玩家！150美元，实力可掏空在线扑克公司
人工智能终于开始掌握人性中一些独特的能力，并且比它的老师玩得还好。
要想在扑克中获胜，就需要利用这样一项能力：狡猾。为了获胜，玩家必须分析对手如何出牌，然后欺骗他们交出手中的筹码。当然，这种狡诈对人来说很自然。现在，人工智能程序首次表现出能够用类似的技能来欺骗人类的职业扑克选手。
近日，Facebook 与卡内基梅隆大学合作开发的一款新型人工智能系统 Pluribus，在世界上最流行、最广泛的扑克游戏：六人无限注德州扑克 (Texas Hold'em poker) 中击败了顶级人类职业玩家。Pluribus 在“5 个 AI 1 个人类玩家”和“1 个 AI 5 个人类玩家”两种模式下都击败了职业玩家。这是人工智能机器人第一次在超过两名玩家 (或两支队伍) 的大型基准游戏中击败顶级专业人士.
此前，人工智能技术已经能够在只有一个对手的情况下打败人类扑克高手。但像 Pluribus 这样，在多人同桌的情况下击败人类精英玩家，才是关键的里程碑。
Pluribus 是通过基于 Libratus 的几项创新，以及 Tuomas Sandholm 在卡内基梅隆大学研究实验室开发的其他算法和代码实现这一成果的。Libratus 是 2017 年在双人无限注德州扑克中击败人类职业选手的 AI。特别是，Pluribus 采用了新的在线搜索算法，它可以通过之前的几个步骤就能有效地评估其下注选项，而不用搜索到游戏结束。Pluribus 还使用了新的更快的自玩算法来玩包含隐藏信息的游戏。
图丨Tuomas Sandholm （来源：Carnegie Mellon）
更让让人想不到的是，这些进步可以使用很少的处理能力和内存——相当于不到 150 美元的云计算资源——就培训出 Pluribus。这个效率与最近其他人工智能里程碑项目形成了鲜明对比，它们需要相当于数百万美元的计算资源来进行培训。
这些在扑克游戏中的创新具有十分重要的意义，因为两个人的零和互动 (一名玩家赢，一名玩家输) 在休闲游戏中很常见，但在现实生活中却非常罕见。现实世界中，对有害内容采取行动，应对网络安全挑战，以及管理在线拍卖或导航流量，通常会涉及多个参与者还有多重隐藏信息。多玩家交互对过去的人工智能技术提出了严峻的理论和实践挑战。然而，现在的结果表明，人工智能算法可以在双人零和游戏之外达到超凡的表现。
图丨Seth Davies，职业扑克选手 (来源：Facebook)
它有掏空在线扑克公司的实力
研究人员通过与一群优秀的人类专业人士比赛来评估 Pluribus。职业选手包括 2000 年世界扑克大赛主赛事冠军 Chris "Jesus" Ferguson，2012 年世界扑克大赛主赛事冠军 Greg Merson 等。参赛的每一个选手之前都在扑克牌桌上赢得了超过 100 万美元，其中有些人甚至赢得了超过 1000 万美元的奖金。
对战有两种形式：五个职业玩家和一个人工智能，一个职业玩家和五个人工智能副本。在每一种形式下，牌桌上都有六名玩家，每一手开始都有 10000 个筹码。小盲注是 50 个筹码，大盲注是 100 个筹码。
虽然扑克是一种技巧游戏，但也有很大的运气成分。对于顶级专业人士来说，仅仅因为运气不好，就输掉 1 万手筹码是很常见的。为了减少运气的作用，研究人员使用了 AIVAT 方差减少算法来评估结果。例如，如果机器人的某一手真的很强，AIVAT 将从它的奖金中减去一个基线值来抵消运气成分。
在 5 个职业玩家 1 个 AI 的实验中，10000 手游戏玩了 12 天。每天从专业人员中挑选五名志愿者参与。官方将根据选手的表现分给他们奖金 5 万美元，以激励他们发挥出最佳水平。在使用 AIVAT 后，Pluribus 的胜率估计为每 100 手 5 个大盲注 (5 bb/100)，这是以精英人类作为对手的压倒性胜利 (盈利，p 值为 0.021)。如果每个筹码都值 1 美元，Pluribus 平均每手赢得 5 美元的奖金，并且每小时可以赚到 1000 美元。这一结果超过了职业玩家在与职业和业余玩家的混合比赛中获胜的预期。
在 5 个 AI 1 个职业玩家的模式下，由三名志愿者参与，每个人类玩家和 5 个 Pluribus 副本玩 5000 手。Pluribus 并没有根据对手的情况调整策略，因此 AI 之间不存在故意勾结问题。总的来说，人类损失了 2.3 bb/100（每 100 手 2.3 个大盲注）。
Pluribus 的算法实在太成功了。“这对扑克社区来说可能是非常危险的，”参与开发算法的 Facebook 研究员 Noam Brown 说。他今年被评为《麻省理工科技评论》的 35 岁以下科技创新者之一。
“你通常可以找出对手的弱点，但没有找到（它的）弱点，”游戏中的扑克职业选手 Jason Les 说，“这个 AI 非常强大，你找不到任何可以利用或占便宜的机会。”
研究人员担心 Pluribus 可能被用来掏空在线德州扑克公司的金库，因此决定不发布其代码。目前，Facebook 也没有计划去应用为六人扑克开发的技术。
六人德州扑克的两大挑战
几十年来，扑克游戏一直是人工智能领域一个困难而又重要的挑战难题。
这是因为扑克游戏中包含隐藏信息，你不知道对手的牌，想要获胜需要会虚张声势以及一些其他策略，而且，这些策略又不同于象棋、围棋和其他游戏。这也是人工智能技术在其他游戏中取得突破，却不能突破扑克的原因，扑克游戏对人工智能技术有天生的抵抗力。
具体来说，六人德州扑克一直面临着两大挑战。
第一大挑战，德州扑克不只是两玩家的零和游戏。
之前 AI 突破的所有基准游戏仅限于那些只有两名或两队玩家的零和游戏，例如跳棋、象棋、围棋、双人扑克、星际争霸 2 和 Dota 2。在这些情况下，人工智能取得了成功，因为它采用了一种称为纳什均衡（Nash equilibrium）的策略。在两名或两队玩家的零和游戏中，精确的纳什均衡能做到无论对手做什么都不可能输(例如，剪刀-石头-布的纳什均衡策略是随机选取概率相等的石头、布或剪刀)。
虽然纳什均衡在任何游戏中都是存在的，但在三个或三个以上对战玩家的游戏中，通常不可能有效地计算出纳什均衡。此外，在一场多人参与的游戏中，即使采用精确的纳什均衡策略，也有可能失败。其中一个例子是 Lemonade Stand 游戏，每个玩家同时在一个圆环上取一个点，并要尽可能地远离其他玩家。纳什均衡是让所有玩家在环上的距离相等，但实现这一点的方法有无穷多种。如果每个玩家独立地计算其中一个均衡，那么最终不太可能使所有参与者在环上的距离相等。
图丨Lemonade Stand 游戏（来源：Facebook）
在多于两个玩家的零和游戏中，纳什均衡存在的缺陷，引发研究人员的思考：在这样的游戏中，正确的目标应该是什么？以六人德州扑克为例，研究人员认为，目标不应该是一个特定的博弈论解决方案，而是创造一个通过长期经验战胜人类对手甚至专业人士的人工智能。
在多于两玩家的零和游戏中，研究人员用来构造 Pluribus 的算法不能保证收敛到纳什均衡。尽管如此，Pluribus 的策略始终能在六人扑克游戏中击败精英人类扑克专家。
第二大挑战，信息隐藏在更复杂的环境中。
没有任何其他游戏能像扑克那样体现隐藏信息的挑战，每个玩家都有其他玩家所缺乏的信息。一个成功的扑克 AI 必须对这些隐藏的信息进行推理，并谨慎地平衡其策略，保持自身的不可预测，同时仍然选择好下一步行动。例如，虚张声势有时可能是有效的，但总是虚张声势就会被对手预测到手牌，并可能导致损失很多钱。因此，有必要谨慎地平衡一个人虚张声势的概率和他下注的概率。换句话说，在不完全信息博弈游戏中，一个行为的价值取决于选择它的概率和选择其他行为的概率。
相反，在完全信息游戏中，玩家不需要担心如何平衡每一步的概率。例如在国际象棋中，好棋就是好的，无论它被选中的概率是多少。
之前的扑克游戏机器人 Libratus，通过将基于 Counterfactual Regret Minimization(CFR) 理论完善的自玩算法与精心构建的不完全信息游戏搜索过程相结合，来处理像双人德州扑克游戏中的隐藏信息。然而，在德州扑克中添加额外的玩家会成倍地增加游戏的复杂性。这些以前的技术不能扩展到六人德州扑克。如今，Pluribus 使用的新技术可以更好地应对这一挑战。
Pluribus 的培训成本不到 150 美元
Pluribus 策略的核心是通过自我游戏来计算的，在这种策略中，人工智能对抗自己的副本，不使用任何人类游戏数据作为输入。人工智能通过随机游戏从零开始，并逐渐改进。它会记录游戏进行了哪些操作，以及这些操作上的概率分布，然后在与早期版本的策略对战中获得更好的输出结果。在 Pluribus 中使用的自我游戏版本是迭代 Monte Carlo CFR (MCCFR) 算法的改进版本。
在算法的每次迭代中，MCCFR 指定一个玩家作为“遍历者”，其当前策略在迭代中更新。在迭代开始时，MCCFR 基于所有玩家的当前策略 (最初完全是随机的) 模拟一手扑克牌。一旦模拟完成，算法会检查遍历器做出的每个决策，并研究如果选择其他可用的操作，它会做得更好还是更差。接下来，人工智能会评估每一个假设的决策的价值，这些决策是按照可用操作做出的，以此类推。
在 8 天时间内，研究人员在 64 核服务器上培训了 Pluribus 的蓝图策略，所需内存不到 512 GB，而且没有使用 GPU。按照典型的云计算的成本估计，培训成本不到 150 美元。这与最近的其他人工智能项目突破形成了鲜明对比，这些突破通常需要花费数百万美元进行训练。
在玩德州扑克时，Pluribus 运行在两个 CPU 上。相比之下，2016 年，AlphaGo 在与顶级围棋专业人士李世乭的比赛中，使用了 1,920 个 CPU 和 280 个 GPU 进行实时搜索。而且，Pluribus 使用不到 128 GB 的内存。Pluribus 搜索每手游戏所花费的时间在 1 秒到 33 秒之间变化，具体取决于实际情况。平均而言，Pluribus 的速度是典型人类职业选手的两倍：在六人德州扑克中与自己的副本进行比赛时，时间为每手 20 秒。
图丨Pluribus 和专业玩家的游戏界面（来源：Facebook）
从扑克游戏到现实不完全信息博弈的挑战
此前，人工智能在完全信息的两玩家零和游戏中取得了一系列引人瞩目的成功。但现实世界中的大多数战略互动都涉及隐藏的信息，而不是两方的零和博弈。Pluribus 的成功表明，在大规模、复杂的多玩家博弈中，尽管缺乏强有力的性能以及理论保证，但精心构造的自玩搜索算法仍然可以成功。
Pluribus 的不同寻常之处还在于，它的训练和运行成本远低于近期其他用于基准游戏的人工智能系统。此前，该领域的一些专家担心，未来的人工智能研究将由拥有数百万美元计算资源的大型团队主导。Pluribus 是一个强有力的证据，现在有理由相信，只需少量资源的新方法可以推动前沿人工智能研究。
图丨由 Tuomas Sandholm 和 Noam Brown 开发的计算机程序在2017年的比赛中击败了四名职业扑克玩家（来源：互联网）
尽管 Pluribus 是为玩扑克而开发的，但其所使用的技术并不针对扑克，也不需要开发任何专业领域知识。这项研究让我们对如何构建通用的人工智能有了更好的基础理解。另外，Pluribus 在牌桌上击败多个对手的技术可能有助于 AI 社区在多种领域开发有效的策略。
亲子游戏推荐：那些可以和孩子一起成长的游戏
小时候总是做着长大的梦，长大却又做着童年的梦，大朋友们，是否还记得小时候在红白机、街机厅、GBA上收获的游戏快乐，是不是也很怀念被父母撵着跑着斗智斗勇的无忧时光，业已长大的大朋友们遇到了曾经父母的同样烦恼，那为何不把游戏当作桥梁，与其死守严防，不如寓教于乐，一起游戏，共同成长。
益智类游戏：割绳子、保卫萝卜、鳄鱼小顽皮爱洗澡
作为曾经大朋友手机里也有一席之地的益智游戏，通关并不困难，但想要满分通关，就需要大小朋友开动脑筋，一起思考，共同试错，十分适合大小朋友共同玩耍。
鳄鱼小顽皮爱洗澡，帮助一只讲卫生的小鳄鱼好好洗一把干净澡
割绳子，滑动手指割断绳子，让糖果掉入小家伙的嘴里
保卫萝卜，经典可爱的塔防游戏，保卫萝卜免受怪物的啃食
合作类游戏：胡闹厨房、只只大冒险、双人成行
此类游戏更适合陪伴一些龄稍大的孩子游玩，这些游戏可以教会我们，理解与包容，合作与进步，在嬉笑打闹中培养感情，感受亲子合作带来的温暖。
胡闹厨房，扮演两位厨师，尝试以最有效率的方式，完成最高品质的料理
双人成行，在爱之书世界冒险，游戏虽然以修复夫妻关系为主题，却不失爱与合作
只只大冒险，双人冒险解谜类游戏，凭借自己的双脚进行一场冒险
竞技类游戏：NBA2K、FIFA、棋类游戏
竞技类游戏的本质不是在家宅游戏，而是希望通过此类游戏，培养孩子兴趣，往后可以出门来场真人篮球，踢场真人足球，下场真人围棋，找到志同道合的伙伴，让游戏回归生活。
NBA2K，篮球模拟游戏
FIFA，足球模拟游戏
棋类游戏，围棋、象棋、军旗、跳棋、斗兽棋，开启一局头脑的对弈
创造类游戏：我的世界、动物园之星
凭借可玩性、创造性、趣味性等元素，此类游戏收获了大量粉丝喜爱，在这些游戏中，没有限制，没有边界，有的是底层严谨逻辑带来的无限可能，合成物品你需要懂得化学，建设铺路你需要懂得规划，变被动学习为主动学习，寓教于乐。
动物园之星，动物园经营模拟游戏，为动物打造合适的栖息地
我的世界，生存创造类沙盒游戏，自由建造属于自己的世界
其实玩什么游戏并不重要，教育的本质在于陪伴，大朋友们在工作之余，不要忘记陪伴孩子，堵不如疏，重要的是通过游戏，引导小朋友有最基础的人生观、世界观、价值观，玩游戏只是为了放松身心，而不是麻痹自我。愿大朋友们和小朋友们一起茁壮成长，愿我们都能遇见最美的童年。
AlphaGo原来是这样运行的，一文详解多智能体强化学习
机器之心分析师网络
作者：杨旭韵
编辑：Joni
在这篇综述性文章中，作者详尽地介绍了多智能强化学习的理论基础，并阐述了解决各类多智能问题的经典算法。此外，作者还以 AlphaGo、AlphaStar为例，概述了多智能体强化学习的实际应用。
近年来，随着强化学习（reinforcement learning）在多个应用领域取得了令人瞩目的成果，并且考虑到在现实场景中通常会同时存在多个决策个体（智能体），部分研究者逐渐将眼光从单智能体领域延伸到多智能体。
本文将首先简要地介绍多智能体强化学习（multi-agent reinforcement learning, MARL）的相关理论基础，包括问题的定义、问题的建模，以及涉及到的核心思想和概念等。然后，根据具体应用中智能体之间的关系，将多智能体问题分为完全合作式、完全竞争式、混合关系式三种类型，并简要阐述解决各类多智能体问题的经典算法。最后，本文列举深度强化学习在多智能体研究工作中提出的一些方法（multi-agent deep reinforcement learning）。
1. 强化学习和多智能体强化学习
我们知道，强化学习的核心思想是“试错”（trial-and-error）：智能体通过与环境的交互，根据获得的反馈信息迭代地优化。在 RL 领域，待解决的问题通常被描述为马尔科夫决策过程。
图 1：强化学习的框架（同时也表示了马尔科夫决策过程）。图源：[1]
当同时存在多个智能体与环境交互时，整个系统就变成一个多智能体系统（multi-agent system）。每个智能体仍然是遵循着强化学习的目标，也就是是最大化能够获得的累积回报，而此时环境全局状态的改变就和所有智能体的联合动作（joint action）相关了。因此在智能体策略学习的过程中，需要考虑联合动作的影响。
1.1 多智能体问题的建模——博弈论基础
马尔科夫决策过程拓展到多智能体系统，被定义为马尔科夫博弈（又称为随机博弈，Markov/stochastic game）。当我们对博弈论有一定了解后，能够借助博弈论来对多智能体强化学习问题进行建模，并更清晰地找到求解问题的方法。
图 2：马尔科夫博弈过程。图源：[2]
在马尔科夫博弈中，所有智能体根据当前的环境状态（或者是观测值）来同时选择并执行各自的动作，该各自动作带来的联合动作影响了环境状态的转移和更新，并决定了智能体获得的奖励反馈。它可以通过元组 < S,A1,...,An,T,R1,...,Rn > 来表示，其中 S 表示状态集合，Ai 和 Ri 分别表示智能体 i 的动作集合和奖励集合，T 表示环境状态转移概率，表示损失因子。此时，某个智能体 i 获得的累积奖励的期望可以表示为：
对于马尔科夫博弈，纳什均衡（Nash equilibrium）是一个很重要的概念，它是在多个智能体中达成的一个不动点，对于其中任意一个智能体来说，无法通过采取其他的策略来获得更高的累积回报，在数学形式上可以表达为：
在该式中，π^表示智能体 i 的纳什均衡策略。
值得注意的是，纳什均衡不一定是全局最优，但它是在概率上最容易产生的结果，是在学习时较容易收敛到的状态，特别是如果当前智能体无法知道其他智能体将会采取怎样的策略。这里举个简单的例子来帮助理解，即博弈论中经典的囚徒困境。根据两个人不同的交代情况，判刑的时间是不一样的：
在这个表格中，当 A 和 B 都选择撒谎时，能够达到全局最优的回报。但是每个个体都不知道另外的个体会做出怎样的行为，对于 A 或者是来 B 说，如果改成选择坦白，则能够获得更优的回报。实际上，对于 A 或者 B 来说，此时不管另外的个体选择了哪种行为，坦白是它能够获得最优回报的选择。所以，最终会收敛到 A 和 B 都选择坦白，即囚徒困境中的纳什均衡策略。
均衡求解方法是多智能体强化学习的基本方法，它对于多智能体学习的问题，结合了强化学习的经典方法（如 Q-learning）和博弈论中的均衡概念，通过 RL 的方法来求解该均衡目标，从而完成多智能体的相关任务。这种思路在后面介绍具体的学习方法中会有所体现。
相比于单智能体系统，强化学习应用在多智能体系统中会遇到哪些问题和挑战？
环境的不稳定性：智能体在做决策的同时，其他智能体也在采取动作；环境状态的变化与所有智能体的联合动作相关；
智能体获取信息的局限性：不一定能够获得全局的信息，智能体仅能获取局部的观测信息，但无法得知其他智能体的观测信息、动作和奖励等信息；
个体的目标一致性：各智能体的目标可能是最优的全局回报；也可能是各自局部回报的最优；
可拓展性：在大规模的多智能体系统中，就会涉及到高维度的状态空间和动作空间，对于模型表达能力和真实场景中的硬件算力有一定的要求。
1.2 多智能体问题的求解——多智能体强化学习算法介绍
对于多智能体强化学习问题，一种直接的解决思路：将单智能体强化学习方法直接套用在多智能体系统中，即每个智能体把其他智能体都当做环境中的因素，仍然按照单智能体学习的方式、通过与环境的交互来更新策略；这是 independent Q-learning 方法的思想。这种学习方式固然简单也很容易实现，但忽略了其他智能体也具备决策的能力、所有个体的动作共同影响环境的状态，使得它很难稳定地学习并达到良好的效果。
在一般情况下，智能体之间可能存在的是竞争关系（非合作关系）、半竞争半合作关系（混合式）或者是完全合作关系，在这些关系模式下，个体需要考虑其他智能体决策行为的影响也是不一样的。参考综述[3]，接下来的部分将根据智能体之间的关系，按照完全竞争式、半竞争半合作、完全合作式来阐述多智能体问题的建模以及求解方法。
1.2.1 智能体之间是完全竞争关系
minimax Q-learning 算法用于两个智能体之间是完全竞争关系的零和随机博弈。首先是最优值函数的定义：对于智能体 i，它需要考虑在其他智能体（i-）采取的动作（a-）令自己（i）回报最差（min）的情况下，能够获得的最大（max）期望回报。该回报可以表示为：
在式子中，V 和 Q 省略了智能体 i 的下标，是因为在零和博弈中设定了 Q1=-Q2，所以上式对于另一个智能体来说是对称等价的。这个值函数表明，当前智能体在考虑了对手策略的情况下使用贪心选择。这种方式使得智能体容易收敛到纳什均衡策略。
在学习过程中，基于强化学习中的 Q-learning 方法，minimax Q-learning 利用上述 minimax 思想定义的值函数、通过迭代更新 Q 值；动作的选择，则是通过线性规划来求解当前阶段状态 s 对应的纳什均衡策略。
图 3：minimax-Q learning 算法流程。图源[4]
minimax Q 方法是竞争式博弈中很经典的一种思想，基于该种思想衍生出很多其他方法，包括 Friend-or-Foe Q-learning、correlated Q-learning，以及接下来将要提到的 Nash Q-learning。
1.2.2 智能体之间是半合作半竞争（混合）关系
双人零和博弈的更一般形式为多人一般和博弈（general-sum game），此时 minimax Q-learning 方法可扩展为 Nash Q-learning 方法。当每个智能体采用普通的 Q 学习方法，并且都采取贪心的方式、即最大化各自的 Q 值时，这样的方法容易收敛到纳什均衡策略。Nash Q-learning 方法可用于处理以纳什均衡为解的多智能体学习问题。它的目标是通过寻找每一个状态的纳什均衡点，从而在学习过程中基于纳什均衡策略来更新 Q 值。
具体地，对于一个智能体 i 来说，它的 Nash Q 值定义为：
此时，假设了所有智能体从下一时刻开始都采取纳什均衡策略，纳什策略可以通过二次规划（仅考虑离散的动作空间，π是各动作的概率分布）来求解。
在 Q 值的迭代更新过程中，使用 Nash Q 值来更新：
可以看到，对于单个智能体 i，在使用 Nash Q 值进行更新时，它除了需要知道全局状态 s 和其他智能体的动作 a 以外，还需要知道其他所有智能体在下一状态对应的纳什均衡策略π。进一步地，当前智能体就需要知道其他智能体的 Q(s')值，这通常是根据观察到的其他智能体的奖励和动作来猜想和计算。所以，Nash Q-learning 方法对智能体能够获取的其他智能体的信息（包括动作、奖励等）具有较强的假设，在复杂的真实问题中一般不满足这样严格的条件，方法的适用范围受限。
图 4：nash-Q learning 算法流程。图源：[5]
1.2.3 智能体之间是完全合作关系
前面提到的智能体之间的两种关系，都涉及到了个体和个体的相互竞争，所以对于个体来说，在策略学习过程中考虑对方（更一般地，其他智能体）的决策行为，才能够做出更好地应对动作，这是比较容易理解的。那么，如果智能体之间完全是合作关系，个体的决策也要考虑其他智能体的决策情况吗？实际上，“合作”意味着多个智能体要共同完成一个目标任务，即这个目标的达成与各个体行为组合得到的联合行为相关；如果个体“一意孤行”，那么它很难配合其他队友来共同获得好的回报。所以，智能体的策略学习仍然需要考虑联合动作效应，要考虑其他具有决策能力的智能体的影响。
怎样实现在智能体策略学习过程中考虑其他协作智能体的影响呢？这个问题我们可以分类讨论，分类的依据是具体问题对于智能体协作的条件要求，即智能体通过协作获得最优回报时，是否需要协调机制:
不需要协作机制
对于一个问题（或者是任务），当所有智能体的联合最优动作是唯一的时候，完成该任务是不需要协作机制的。这个很容易理解，假设对于环境中的所有智能体 存在不只一个最优联合动作，即有 和，那么 A 和 B 之间就需要协商机制，决定是同时取π，还是同时取 h；因为如果其中一个取π、另一个取 h，得到的联合动作就不一定是最优的了。Team Q-learning 是一种适用于不需要协作机制的问题的学习方法，它提出对于单个智能体 i，可以通过下面这个式子来求出它的最优动作 hi：
Distributed Q-learning 也是一种适用于不需要协作机制的问题的学习方法，不同于 Team Q-learning 在选取个体最优动作的时候需要知道其他智能体的动作，在该方法中智能体维护的是只依据自身动作所对应的 Q 值，从而得到个体最优动作。
隐式的协作机制
在智能体之间需要相互协商、从而达成最优的联合动作的问题中，个体之间的相互建模，能够为智能体的决策提供潜在的协调机制。在联合动作学习（joint action learner，JAL）[6]方法中，智能体 i 会基于观察到的其他智能体 j 的历史动作、对其他智能体 j 的策略进行建模。在频率最大 Q 值（frequency maximum Q-value, FMQ）[7]方法中，在个体 Q 值的定义中引入了个体动作所在的联合动作取得最优回报的频率，从而在学习过程中引导智能体选择能够取得最优回报的联合动作中的自身动作，那么所有智能体的最优动作组合被选择的概率也会更高。
JAL 和 FMQ 方法的基本思路都是基于均衡求解法，但这类方法通常只能处理小规模（即智能体的数量较少）的多智能体问题：在现实问题中，会涉及到大量智能体之间的交互和相互影响，而一般的均衡求解法受限于计算效率和计算复杂度、很难处理复杂的情况。在大规模多智能体学习问题中，考虑群体联合动作的效应，包括当前智能体受到的影响以及在群体中发挥的作用，对于智能体的策略学习是有较大帮助的。
基于平均场理论的多智能体强化学习（Mean Field MARL, MFMARL）方法是 UCL 学者在 2018 年 ICML 会议上提出的一种针对大规模群体问题的方法，它将传统强化学习方法（Q-learning）和平均场理论（mean field theory）相结合。平均场理论适用于对复杂的大规模系统建模，它使用了一种简化的建模思想：对于其中的某个个体，所有其他个体产生的联合作用可以用一个 “平均量” 来定义和衡量。此时，对于其中一个个体来说，所有其他个体的影响相当于一个单体对于它的影响，这样的建模方式能够有效处理维度空间和计算量庞大的问题。
MFMARL 方法基于平均场理论的建模思想，将所有智能体看作一个“平均场”，个体与其他智能体之间的关系可以描述为个体和平均场之间的相互影响，从而简化了后续的分析过程。
图 5：基于平均场理论的多智能体建模方式，单个智能体只考虑与相邻的其他智能体（蓝色球体区域）的相互作用。图源：[8]
首先，为了处理集中式全局值函数的学习效果会受到智能体数量（联合动作的维度）的影响，对值函数进行分解。对于单个智能体 j，它的值函数 Qj(s,a)包含了与所有 Nj 个相邻智能体 k 之间的相互作用：
然后，将平均场理论的思想结合到上式中。考虑离散的动作空间，单个智能体的动作采用 one-hot 编码的方式，即 aj=[h(aj_1), ... h(aj_d)]，其中 h(aj_i)=1 if aj=aj_i ?: 0；其他相邻智能体的动作可以表示为平均动作 bar和一个波动δ的形式：
利用泰勒二阶展开，得到
该式子即是将当前智能体 j 与其他相邻智能体 k 的相互作用，简化为当前智能体 j 和虚拟智能体 bar的相互作用，是平均场思想在数学形式上的体现。此时，在学习过程中，迭代更新的对象为平均场下的 Q(s,aj,bar)值（即 MF-Q），有：
在更新中使用 v 而不是使用 max Q 的原因在于：对 Q 取 max，需要相邻智能体策略 bar的合作，而对于智能体 j 来说是无法直接干涉其他智能体的决策情况；另一方面，贪心的选择依旧会导致学习过程受到环境不稳定性的影响。
对应地，智能体 j 的策略也会基于 Q 值迭代更新，使用玻尔兹曼分布有：
原文证明了通过这样的迭代更新方式，bar最终能够收敛到唯一平衡点的证明，并推出智能体 j 的策略πj 能够收敛到纳什均衡策略。
显式的协作机制
关于显式的协作机制，我们将通过多智能体深度强化学习在多机器人领域的应用中会简单介绍（主要是人机之间的交互，考虑现存的一些约束条件 / 先验规则等）。
2. 多智能体深度强化学习
随着深度学习的发展，利用神经网络的强大表达能力来搭建逼近模型（value approximation）和策略模型（常见于 policy-based 的 DRL 方法）。深度强化学习的方法可以分为基于值函数（value-based）和基于策略（policy-based）两种，在考虑多智能体问题时，主要的方式是在值函数的定义或者是策略的定义中引入多智能体的相关因素，并设计相应的网络结构作为值函数模型和策略模型，最终训练得到的模型能够适应（直接或者是潜在地学习到智能体相互之间的复杂关系），在具体任务上获得不错的效果。
2.1 policy-based 的方法
在完全合作的 setting 下，多智能体整体通常需要最大化全局的期望回报。前面提到一种完全集中式的方式：通过一个中心模块来完成全局信息的获取和决策计算，能够直接地将适用于单智能体的 RL 方法拓展到多智能体系统中。但通常在现实情况中，中心化的控制器（centralized controller）并不一定可行，或者说不一定是比较理想的决策方式。而如果采用完全分布式的方式，每个智能体独自学习自己的值函数网络以及策略网络、不考虑其他智能体对自己的影响，无法很好处理环境的不稳定问题。利用强化学习中 actor-critic 框架的特点，能够在这两种极端方式中找到协调的办法。
1. 多智能体 DDPG 方法（Multi-Agent Deep Deterministic Policy Gradient, MADDPG）
这种方法是在深度确定策略梯度（Deep Deterministic Policy Gradient，DDPG）方法的基础上、对其中涉及到的 actor-critic 框架进行改进，使用集中式训练、分布式执行的机制（centralized training and decentralized execution），为解决多智能体问题提供了一种比较通用的思路。
MADDPG 为每个智能体都建立了一个中心化的 critic，它能够获取全局信息（包括全局状态和所有智能体的动作）并给出对应的值函数 Qi(x,a1,...,an)，这在一定程度上能够缓解多智能体系统环境不稳定的问题。另一方面，每个智能体的 actor 则只需要根据局部的观测信息作出决策，这能够实现对多智能体的分布式控制。
在基于 actor-critic 框架的学习过程中，critic 和 actor 的更新方式和 DDPG 类似。对于 critic，它的优化目标为：
对于 actor，考虑确定性策略μi(ai|oi)，策略更新时的梯度计算可以表示为：
图 6：中心化的 Q 值学习（绿色）和分布式的策略执行（褐色）。Q 值获取所有智能体的观测信息 o 和动作 a，策略π根据个体的观测信息来输出个体动作。图源：[9]
在 MADDPG 中，个体维护的中心化 Q 值需要知道全局的状态信息和所有智能体的动作信息，此时假设了智能体能够通过通信或者是某种方式得知其他智能体的观测值和策略，这种假设前提过于严格。MADDPG 进一步提出了可以通过维护策略逼近函数 hat{miu}来估计其他智能体的策略，通过对其他智能体的行为建模使得维护中心化的 Q 值、考虑联合动作效应对单个个体来说是可行的。智能体 i 在逼近第 j 个智能体的策略函数时，其优化目标是令策略函数能够近似经验样本中智能体 j 的行为，同时考虑该策略的熵，可表示为：
除了考虑联合动作以外，MADDPG 在处理环境不稳定问题方面还使用了策略集成（policies ensemble）的技巧。由于环境中的每个智能体的策略都在迭代更新，因此很容易出现单个智能体的策略对其他智能体的策略过拟合，即当其他智能体的策略发生改变时，当前得到的最优策略不一定能很好的适应其他智能体的策略。为了缓和过拟合问题，MADDPG 提出了策略集成的思想，即对于单个智能体 i，它的策略μi 是由多个子策略μi^k 构成的集合。在一个 episode 中，只使用一种从集合中采样得到的子策略进行决策和完成交互。在学习过程中最大化的目标是所有子策略的期望回报，即
每个子策略的更新梯度为：
总的来说，MADDPG 的核心是在 DDPG 算法的基础上，对每个智能体使用全局的 Q 值来更新局部的策略，该方法在完全合作、完全竞争和混合关系的问题中都能取得较好效果。算法流程如下所示：
图 7：MADDPG 算法流程。图源：[9]
2. 反事实多智能体策略梯度法方法（Counterfactual Multi-Agent Policy Gradients, COMA）
在合作式的多智能体学习问题中，每个智能体共享奖励（即在同一个时刻获得相同的奖励），此时会存在一个 “置信分配” 问题（credit assignment）：如何去评估每个智能体对这个共享奖励的贡献？
COMA 方法在置信分配中利用了一种反事实基线：将智能体当前的动作和默认的动作进行比较，如果当前动作能够获得的回报高于默认动作，则说明当前动作提供了好的贡献，反之则说明当前动作提供了坏的贡献；默认动作的回报，则通过当前策略的平均效果来提供（即为反事实基线）。在对某个智能体和基线进行比较的时，需要固定其他智能体的动作。当前策略的平均效果和优势函数的定义如下：
COMA 方法结合了集中式训练、分布式执行的思想：分布式的个体策略以局部观测值为输入、输出个体的动作；中心化的 critic 使用特殊的网络结构来输出优势函数值。
具体地，critic 网络的输入包括了全局状态信息 s、个体的局部观测信息 o、个体的编号 a 以及其他智能体的动作，首先输出当前智能体不同动作所对应的联合 Q 值。然后， 再经过 COMA 模块，使用输入其中的智能体当前策略和动作，计算反事实基线以及输出最终的优势函数。
图 8：(a) COMA 方法中的 actor-critic 框架图，(b) actor 的网络结构，(c) critic 的网络结构（包含了核心的 COMA 模块来提供优势函数值）。图源：[10]
2.2 value-based 的方法
在前面提到的 policy-based 方法中，中心化的值函数是直接使用全局信息进行建模，没有考虑个体的特点。在多智能体系统是由大规模的多个个体构成时，这样的值函数是难以学习或者是训练到收敛的，很难推导出理想的策略。并且仅依靠局部观测值，无法判断当前奖励是由于自身的行为还是环境中其他队友的行为而获得的。
值分解网络（value decomposition networks, VDN）由 DeepMind 团队在 2018 年提出，该方法的核心是将全局的 Q(s,a)值分解为各个局部 Qi(si,ai)的加权和，每个智能体拥有各自的局部值函数。
这样的分解方式，在联合动作 Q 值的结构组成方面考虑了个体行为的特性，使得该 Q 值更易于学习。另一方面，它也能够适配集中式的训练方式，在一定程度上能够克服多智能体系统中环境不稳定的问题。在训练过程中，通过联合动作 Q 值来指导策略的优化，同时个体从全局 Q 值中提取局部的 Qi 值来完成各自的决策（如贪心策略 ai=argmax Qi），实现多智能体系统的分布式控制。
图 9：左图是完全分布式的局部 Q 值网络结构，右图是 VDN 的联合动作 Q 值网络结构。考虑两个智能体，它们的联合动作 Q 值由个体的 Q1 和 Q2 求和得到，在学习时针对这个联合 Q 值进行迭代更新，而在执行时个体根据各自的 Qi 值得到自身的动作 ai。图源：[11]
VDN 对于智能体之间的关系有较强的假设，但是，这样的假设并不一定适合所有合作式多智能体问题。在 2018 年的 ICML 会议上，有研究者提出了改进的方法 QMIX。
QMIX 在 VDN 的基础上实现了两点改进：1）在训练过程中加入全局信息进行辅助；2）采用混合网络对单智能体的局部值函数进行合并（而不是简单的线性相加）。
在 QMIX 方法中，首先假设了全局 Q 值和局部 Q 值之间满足这样的关系：最大化全局 Q_tot 值对应的动作，是最大化各个局部 Q_a 值对应动作的组合，即
在这样的约束条件下，既能够使用集中式的学习方法来处理环境不稳定性问题以及考虑多智能体的联合动作效应（全局 Q 值的学习），又能够从中提取出个体策略实现分布式的控制（基于局部 Q 值的行为选择）。进一步地，该约束条件可转化为全局 Q 值和局部 Q 值之间的单调性约束关系：
令全局 Q 值和局部 Q 值之间满足该约束关系的函数表达式有多种，VDN 方法的加权求和就是其中一种，但简单的线性求和并没有充分考虑到不同个体的特性，对全体行为和局部行为之间的关系的描述有一定的局限性。QMIX 采用了一个混合网络模块（mixing network）作为整合 Qa 生成 Q_tot 的函数表达式，它能够满足上述的单调性约束。
图 10：QMIX 网络结构。图源：[12]
在 QMIX 方法设计的网络结构中，每个智能体都拥有一个 DRQN 网络（绿色块），该网络以个体的观测值作为输入，使用循环神经网络来保留和利用历史信息，输出个体的局部 Qi 值。
所有个体的局部 Qi 值输入混合网络模块（蓝色块），在该模块中，各层的权值是利用一个超网络（hypernetwork）以及绝对值计算产生的：绝对值计算保证了权值是非负的、使得局部 Q 值的整合满足单调性约束；利用全局状态 s 经过超网络来产生权值，能够更加充分和灵活地利用全局信息来估计联合动作的 Q 值，在一定程度上有助于全局 Q 值的学习和收敛。
结合 DQN 的思想，以 Q_tot 作为迭代更新的目标，在每次迭代中根据 Q_tot 来选择各个智能体的动作，有：
最终学习收敛到最优的 Q_tot 并推出对应的策略，即为 QMIX 方法的整个学习流程。
3. 多智能体强化学习的应用
3.1. 游戏应用
分步对抗游戏
这类游戏包括了围棋、国际象棋、扑克牌等，MARL 在这几种游戏中都有相关的研究进展并取得了不错的成果。其中，著名的 AlphaGo 通过在和人类对战的围棋比赛中取得的惊人成绩而进入人们的视野。围棋是一种双玩家零和随机博弈，在每个时刻，玩家都能够获取整个棋局。它一种涉及超大状态空间的回合制游戏，很难直接使用传统的 RL 方法或者是搜索方法。AlphaGo 结合了深度学习和强化学习的方法：
针对巨大状态空间的问题，使用网络结构 CNN 来提取和表示状态信息；
在训练的第一个阶段，使用人类玩家的数据进行有监督训练，得到预训练的网络；
在训练的第二个阶段，通过强化学习方法和自我博弈进一步更新网络；
在实际参与游戏时，结合价值网络（value network）和策略网络（policy network），使用 蒙特卡洛树搜索（MCTS）方法得到真正执行的动作。
图 11：AlphaGo 在 2016 年击败人类玩家。图源：https://rlss.inria.fr/files/2019/07/RLSS_Multiagent.pdf
实时战略游戏
MARL 的另一种重要的游戏应用领域，是实时战略游戏，包括星际争霸，DOTA，王者荣耀，吃鸡等。该类游戏相比于前面提到的国际象棋、围棋等回合制类型的游戏，游戏 AI 训练的难度更大，不仅因为游戏时长过长、对于未来预期回报的估计涉及到的步数更多，还包括了多方同时参与游戏时造成的复杂空间维度增大，在一些游戏设定中可能无法获取完整的信息以及全局的形势（比如在星际争霸中，不知道迷雾区域是否有敌方的军队），在考虑队内合作的同时也要考虑对外的竞争。
OpenAI Five 是 OpenAI 团队针对 Dota 2 研发的一个游戏 AI [13]，智能体的策略的学习没有使用人类玩家的数据、是从零开始的（learn from scratch）。考虑游戏中队内英雄的协作，基于每个英雄的分布式控制方式（即每个英雄都有各自的决策网络模型），在训练过程中，通过一个超参数 “team spirit” 对每个英雄加权、控制团队合作，并且使用基于团队整体行为的奖励机制来引导队内合作。考虑和其他团队的对抗，在训练过程中使用自我对抗的方式（也称为虚拟自我博弈，fictitious self-play， FSP）来提升策略应对复杂环境或者是复杂对抗形势的能力。这种自我对抗的训练方式，早在 2017 年 OpenAI 就基于 Dota2 进行了相关的研究和分析，并发现智能体能够自主地学习掌握到一些复杂的技能；应用在群体对抗中，能够提升团队策略整体对抗的能力。
AlphaStar 是 OpenAI 团队另一个针对星际争霸 2（Starcraft II）研发的游戏 AI，其中在处理多智能体博弈问题的时候，再次利用了 self-play 的思想并进一步改进，提出了一种联盟利用探索的学习方式（league exploiter discovery）。使用多类个体来建立一个联盟（league），这些个体包括主智能体（main agents）、主利用者（main exploiters）、联盟利用者（league exploiters）和历史玩家（past players）四类。这几类智能体的策略会被保存（相当于构建了一个策略池），在该联盟内各类智能体按照一定的匹配规则与策略池中的其他类智能体的策略进行对抗，能够利用之前学会的有效信息并且不断增强策略的能力，解决普通的自我博弈方法所带有的 “循环学习” 问题（“Chasing its tail”）。
图 12：联盟利用者探索（league exploiter discovery）的学习框架。图源：[14]
3.2. 多机器人避碰
在现实生活中，多机器人的应用场景主要是通过多个机器人的协作来提升系统的性能和效率，此时多智能体强化学习的关注重点主要在于机器人（智能体）之间的合作。
在移动机器人方面，自主避障导航是底层应用的关键技术，近几年通过强化学习的方法来学习单机器人导航策略这方面的工作成果比较多；而当环境中存在多个移动机器人同时向各自目标点移动的时候，需要进一步考虑机器人之间的相互避碰问题，这也是 MARL 在多机器人导航（multi-robot navigation）领域的主要研究问题。Jia Pan 教授团队 [13] 在控制多机器人避碰导航问题上使用了集中式学习和分布式执行的机制，在学习过程中机器人之间共享奖励、策略网络和值函数网络，通过共享的经验样本来引导相互之间达成隐式的协作机制。
图 13：多机器人向各自目标点移动过程中的相互避碰。仓库物件分发是该问题的常见场景，多个物流机器人在向各自指定的目标点移动过程当中，需要避免和仓库中的其他物流机器人发生碰撞。图源：[15]
另外，不仅有机器人和机器人之间的避碰问题，有一些工作还考虑到了机器人和人之间的避碰问题，如 SA-CADRL（socially aware collision avoidance deep reinforcement learning） 。根据该导航任务的具体设定（即机器人处在人流密集的场景中），在策略训练是引入一些人类社会的规则（socially rule），相当于要让机器人的策略学习到前面 1.2.3 部分提到显式的协调机制，达成机器人与人的行为之间的协作。
图 14：左图展示了相互避碰时的两种对称规则，上面为左手规则，下面为右手规则。右图是在 SA-CADRL 方法中模型引入这样的对称性信息，第一层中的红色段表示当前智能体的观测值，蓝色块表示它考虑的附近三个智能体的观测值，权重矩阵的对称性是考虑了智能体之间遵循一定规则的对称行为。图源：[16]
4. 总结
多智能体强化学习（MARL）是结合了强化学习和多智能体学习这两个领域的重要研究方向，关注的是多个智能体的序贯决策问题。本篇文章主要基于智能体之间的关系类型，包括完全合作式、完全竞争式和混合关系式，对多智能体强化学习的理论和算法展开介绍，并在应用方面列举了一些相关的研究工作。在未来，对 MARL 方面的研究（包括理论层面和应用层面）仍然需要解决较多的问题，包括理论体系的补充和完善、方法的可复现性、模型参数的训练和计算量、模型的安全性和鲁棒性等 [15]。
参考文献：
[1] Sutton R S, Barto A G. Reinforcement learning: An introduction[M]. MIT press, 2018.
[2] Zhang K , Yang Z , Baar T . Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms[J]. 2019.
[3] L. Busoniu, R. Babuska, and B. De Schutter, “A comprehensive survey of multi-agent reinforcement learning,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, vol. 38, no. 2, pp. 156–172, Mar. 2008.
[4] Littman M L. Markov games as a framework for multi-agent reinforcement learning[C]. international conference on machine learning, 1994: 157-163.
[5] Hu J, Wellman M P. Nash Q-learning for general-sum stochastic games[J]. Journal of machine learning research, 2003, 4(Nov): 1039-1069.
[6] Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. In Proceedings of the Fifteenth National Conference on Artificial Intelligence, pp. 746–752, 1998.
[7] S. Kapetanakis and D. Kudenko. Reinforcement learning of coordination in cooperative multi-agent systems. American Association for Artificial Intelligence, pp. 326-331, 2002.
[8] Yang Y, Luo R, Li M, et al. Mean Field Multi-Agent Reinforcement Learning[C]. international conference on machine learning, 2018: 5567-5576
[9] Lowe R, Wu Y, Tamar A, et al. Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments[C]. neural information processing systems, 2017: 6379-6390.
[10] Foerster J, Farquhar G, Afouras T, et al. Counterfactual Multi-Agent Policy Gradients[J]. arXiv: Artificial Intelligence, 2017.
[11] Sunehag P, Lever G, Gruslys A, et al. Value-Decomposition Networks For Cooperative Multi-Agent Learning.[J]. arXiv: Artificial Intelligence, 2017.
[12] Rashid T, Samvelyan M, De Witt C S, et al. QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning[J]. arXiv: Learning, 2018.
[13] OpenAI Five, OpenAI, https://blog.openai.com/openai-five/, 2018.
[14] Vinyals, O., Babuschkin, I., Czarnecki, W.M. et al. Grandmaster level in StarCraft II using multi-agent reinforcement learning. Nature 575, 350–354 (2019).
[15] P. Long, T. Fan, X. Liao, W. Liu, H. Zhang and J. Pan, "Towards Optimally Decentralized Multi-Robot Collision Avoidance via Deep Reinforcement Learning," 2018 IEEE International Conference on Robotics and Automation (ICRA), Brisbane, QLD, 2018, pp. 6252-6259, doi: 10.1109/ICRA.2018.8461113.
[16] Y. F. Chen, M. Everett, M. Liu and J. P. How, "Socially aware motion planning with deep reinforcement learning," 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Vancouver, BC, 2017, pp. 1343-1350, doi: 10.1109/IROS.2017.8202312.
[17] Hernandez-Leal P , Kartal B , Taylor M E . A survey and critique of multiagent deep reinforcement learning[J]. Autonomous Agents & Multi Agent Systems, 2019(2).
什么？象棋和围棋都存在不败策略？
象棋和围棋都是中华文明的瑰宝，更是训练和测试思维能力的方式之一，那些在这两种棋类上取得成就的人们，其智商普遍得到公众认可。但是，我们是否想过，在这两种棋类上是否存在必胜或者平局的策略？答案是存在的，这是策梅洛关于双人完全信息博弈的一个定理的结论。本文将详细介绍这个定理的证明，并将其用于诸如五子棋的分析中。如无特殊说明，后文所提及的游戏都是双人游戏。
什么是最优策略
为了让大家对最优策略有一个直观的理解，这里举一个小游戏作为例子。这个小游戏叫Chop，在游戏的最开始有一个m×n的网格(下图是一个4×6网格示例)，游戏由两位玩家轮流操作，每位玩家每轮可以沿着一整根竖网格线或者一整根横网格线将网格割掉一块，割到只剩下一个小方格的玩家为胜者。注意，不能沿着剩余网格的边界线做切割，例如不能沿着下图的AB线切割，但是沿着CD线或者EF线切割都是可以的。每次切割完之后网格会被分成两块，由操作切割的玩家决定留下哪一块。
对于这类双人游戏，一般会有最先进行操作的玩家，我们将其称为先手，另一位被称为后手。如果一开始的时候m和n其中一个数为1，比如n=1，先手玩家可以直接切割掉(m-1)个格子即可获得胜利，这个策略就是先手玩家的最优策略。如果对于一般的m和n，先手或者后手怎样才能保证获胜呢？读者可以稍作思考，再接着往下看。
其实很简单，如果m和n不相等，那么先手的最优策略会导致必胜的结果：这时候先手玩家只要割掉其中一块使得剩下的网格是个长和宽相等的网格即可。这样，无论后手切割哪条线，都是在长和宽相等的基础上进行切割，最后必然得到一个长宽不相等的网格，也就不可能是单独一个网格。先手玩家只要每一步实行这个策略，无论后手玩家怎么操作，先手玩家都会获胜。这时候读者肯定明白了，当m=n的时候，无论先手玩家怎么操作，后手玩家都可以借助前述一样的策略获胜。
完全信息博弈和策梅洛定理
现在回到一般游戏的讨论上。策梅洛定理适用于被称为完全信息博弈的一类游戏。所谓完全信息博弈，指的是游戏的所有信息都是公开的，游戏双方都能清楚了解到目前游戏所处的状态信息，并且游戏的每一步都不涉及概率因素。这个条件把扑克、飞行棋、暗棋和翻棋玩法下的军棋都排除掉了。然后，我们还需要这个游戏能在有限步内结束，并且，游戏的结局要么是平局要么有一方是胜者。很明显，围棋是属于完全信息博弈的。至于象棋，有可能会进入循环状态从而整个游戏没完没了。为了避免这一点，我们可以加入一些新规则使得象棋不会出现循环，比如，设定一个很大的数N，只要连续N步双方都没有被吃掉棋子就判为和棋，或者不允许超过N次进入同一种棋子状态，否则判为和棋。加入这些规则或者类似的规则之后，象棋就满足要求了。
下面给出策梅洛定理的严格表述：在双人完全信息博弈下，只有三种情况：要么先手具有必胜策略，要么后手具有必胜策略，要么双方的最优策略会导致平局。比如前面所说的Chop游戏，当m≠n时，先手玩家具有必胜策略；如果m=n，后手玩家具有必胜策略。Chop游戏没有平局。策梅洛定理是一个结论很强的定理，下面我们会发现，它的证明非常简单，不需要用到很高深的知识。
策梅洛定理的证明
为了证明策梅洛定理，我们需要引入一个小小的概念：游戏树。在游戏的每一步，玩家有很多种走法，每一个走法都会产生新的分支，把两位玩家的所有可能走法考虑进来，就会得到一个树状结构。这个树状结构穷尽了游戏过程的所有可能性。下图是Chop游戏在1×4情况下的游戏树。在本文，我们用(1,0)表示先手获胜，(0,1)表示后手获胜，(0,0)表示平局。
在游戏树上，节点会标注上游戏状态，比如上图中的方格。有时候为了信息完全，还会标注上在此节点轮到哪位玩家操作了。因为我们把游戏循环往复的可能性排除了，游戏状态转移图不会出现圈图，所以必然是树图。(对于象棋，如果用A表示棋子状态，加上了前文所述的其中一个规则后，整个游戏状态将由(A, i)表示，其中i表示已经连续i步双方都没有被吃掉棋子或者已经i次进入棋子状态A了。在这样的表示下，当i不等于j时，(A, i)和(A, j)哪怕棋子状态都是A，但是依然代表不同的游戏状态。于是，象棋的游戏转移也不会出现圈图。)
接下来，我们假设每一位玩家都是理智的，当玩家处于游戏树的某个节点时，她/他必然会选择对其最有利的走法。假如现在游戏状态来到了倒数第二步，再走一步游戏将结束了，那么我们就会看到游戏树的末端，大概是如下图这样的，其中省略号表示未画出的末端节点
在上图的游戏树中，如果在A处轮到先手玩家操作了，那么她/他必然会选择走向B。走向C和D对先手玩家来说都不是最优走法。于是，A虽然不是末端节点，但是它依然可以带有胜负信息(1,0)，这个胜负信息表示先手方在A处只要按最优策略走就会获胜。当然，上图只是一个例子，有可能末端节点都不是(1,0)状态的，这时候对先手玩家来说最优策略就是走到平局状态(如果有平局末端的话)，这样A节点将会带有(0,0)的胜负信息。如果是最坏情况，节点A下的所有末端节点都对应(0,1)的胜负，那么在A处无论先手玩家怎么走都必输，于是节点A带有的胜负信息是(0,1)。假如我们给胜负引入大小关系：(1,0)>(0,0)>(0,1)，那么前述得到A的胜负信息的分析可以总结为：轮到先手方操作，A节点的胜负=A的下一级节点的胜负最大值。另一方面，如果在A处轮到后手玩家操作了，我们也可以通过类似的分析得到A处的胜负信息，只不过最大值要换成最小值：轮到后手方操作，A节点的胜负=A的下一级节点的胜负最小值。
得到了A处的胜负信息之后，我们就可以忽略A下面的所有节点了，这时候A就成了一个末端节点，它带有相应的胜负信息，这个胜负信息表示从该节点出发，两位玩家都使用最优策略后会导致的胜负结局。这个操作可以继续进行下去，不断得到上一级节点的胜负信息，然后忽略掉旧的末端节点。如此往复，因为树是有限高的，最终我们会得到游戏一开始那个节点(术语叫根节点)的胜负信息。如果根节点的胜负信息是(1,0)，那么意味着先手玩家只要按最优策略走下去就会必胜；如果根节点的胜负信息是(0,1)，那么意味着后手玩家具有必胜策略；如果根节点的胜负信息是(0,0)，那么意味着双方的最优策略会导致平局。至此，策梅洛定理证明完毕。
从下往上的胜负信息推导
如何确定谁才具有必胜策略：策略窃取
想必读者已经跃跃欲试了，如果知道了象棋或者围棋的最优策略，岂不是在棋坛上横着走？可惜的是，虽然策梅洛定理的证明是构造性的，但是构造过程需要我们先得到整个游戏树，而像围棋这类棋，游戏的路径(指从根节点到末端节点的一条路径)比宇宙的原子数目还要多，要想通过整个游戏树来得到最优策略是不可能的了。如此说来，策梅洛定理仅仅给必胜或者平局策略提供了存在性。不过，借助策梅洛定理所提供的存在性，我们可以利用被称为策略窃取的方法证明在某些游戏上后手不存在必胜策略，换言之，先手有不败策略。
本文将以著名的五子棋为例介绍策略窃取是怎么一回事。很明显，五子棋满足策梅洛定理的条件，于是有且仅有三种可能性：先手具有必胜策略、后手具有必胜策略、双方的最优策略会导致平局。接下来我们使用反证法。假如后手具有必胜策略，我们把这个策略称为S。这时候无论先手玩家怎么走，后手玩家只要使用策略S，先手玩家必输。
策略窃取的要点就是把对方的策略“窃取”过来。先手玩家先在棋盘上随便放一个棋子，位置记为P1，然后假装这个棋子不存在。这时候轮到后手玩家放子了，由于假装P1上的棋子不存在，后手玩家成了“先手”，而先手玩家成了“后手”，于是先手玩家可以使用必胜策略S。根据这个策略的必胜性质，无论对方怎么走，“后手”玩家(也就是先手玩家)都将获胜。不过，事情似乎没那么简单。我们只是假装P1上的棋子不存在而已，实际上这个棋子是存在的。P1位置上的棋子会怎么影响到策略S的使用呢？假如走到了某一步，策略S要求“后手”玩家将棋子放在P1位置，这时候P1已经存在“后手”玩家的棋子了，但是游戏要求玩家每一步都不能不下棋子，此时“后手”玩家可以在这一步把棋子下在其他的任意位置，记为P2。这样的话P1和P2都占据了“后手”玩家的棋子，这就等价于游戏一开始“后手”玩家将棋子下在了P2，并且在目前这一轮“后手”玩家根据策略S的要求把棋子下在了P1位置。如果接下来策略要求棋子下在P2，那么“后手”玩家可以任意把棋子下在P3位置……如此类推，先手玩家可以完美使用策略S，于是会必胜。这和反证法的假设相矛盾。于是，五子棋只能存在两种情况：先手具有必胜策略、双方的最优策略会导致平局。或者更简洁地表述为，先手具有不败策略。
回顾前述关于五子棋的讨论，这个“五”字完全没有体现出来，我们完全可以把相关结论推广到四子棋、六子棋等等。特别地，井字棋本质上是一种三子棋，由于它的游戏树很简单，我们甚至可以通过穷举法证明在井字棋上确实是先手玩家具有不败策略。
在哪都能玩的井字棋
转载内容仅代表作者观点
不代表中科院物理所立场
来源：中科院理论物理研究所
原标题：DoctorCurious 26: 什么？象棋和围棋都存在不败策略？
编辑：藏痴