人工智能导论（微课视频版）课件 第9章9.1-9.2-智能博弈

第九章智能博弈9.智能博弈2026年8月19日9.1博弈论基础9.2博弈问题的复杂度9.3智能博弈策略求解技术9.4智能博弈应用及经典案例9.1博弈论基础2026年8月19日博弈论，又称为对策论（GameTheory）、赛局理论等。博弈论考虑对局中的个体预测行为和实际行为，研究博弈行为中最优的对抗策略及其稳定局势，协助人们在一定规则范围内寻求最合理的行为方式/策略。古人在围棋对弈中所体现的智慧就是一种典型的博弈策略。《司马法》、《孙子兵法》和《孙膑兵法》等军事著作，在我国古代军事战争实践中，都起过极其重要的作用。9.1博弈论基础2026年8月19日博弈论，又称为对策论（GameTheory）、赛局理论等。博弈论考虑对局中的个体预测行为和实际行为，研究博弈行为中最优的对抗策略及其稳定局势，协助人们在一定规则范围内寻求最合理的行为方式。到了现代，1928年，冯·诺依曼证明了博弈论的基本原理，从而宣告了博弈论的正式诞生。1944年，冯·诺依曼与摩根斯坦共著的《博弈论与经济行为》将二人博弈推广到多人博弈结构并系统地应用于经济领域，奠定了学科的基础和理论体系。冯·诺依曼也被后人称为“博弈论之父”。JohnvonNeumann(1903-1957),OskarMorgenstern(1902-1977),TheoryofGamesandEconomicBehavior,PrincetonUniversityPress,19449.1博弈论基础2026年8月19日博弈基本要素：局中人、策略、得失、次序和均衡。局中人（players）：有决策权的参与者，也叫做参与人或玩家。在一场博弈中，根据参与人数的不同，可分为单人、二人和多人博弈。在单人博弈中，小型益智游戏如华容道、俄罗斯方块等；在二人博弈中，如五子棋、围棋等棋类问题；在多人博弈中，常见场景如桥牌、多人跳棋等。策略（strategies）：参与者可以采取的行动方案。可选全部策略组合为策略空间如若参与者只能选择某个特定策略，则称为纯策略；如博弈参与者在给定信息下以一定的概率值来选择策略，则称为混合策略。如果所有参与方的策略数量都是有限的，称为有限博弈；如果有一方的策略是无限多的，称为无限博弈。9.1博弈论基础2026年8月19日得失：指博弈结束时的对局结果。每个参与者在一局博弈结束后的得失，不仅与该自身策略有关，而且与全部参与人所选定的策略组合有关。一个特定的策略组合中参与人所获得的利益，通常称为支付或效用（payoff）函数。次序：即博弈各方决策的先后顺序。静态博弈：各参与方同时决策，或者做出选择之前不允许知道或者无法知道其他方的选择。动态博弈：参与人采取的行动有先后顺序。均衡：均衡即平衡，为稳定的博弈局势。在博弈均衡下，各方参与人都不轻易改变自己策略，从而达到一种平衡稳定的状态。博弈基本要素：局中人、策略、得失、次序和均衡。9.1博弈论基础2026年8月19日纳什均衡(Nashequilibrium)，又称非合作博弈均衡，只考虑个人利益的稳定的博弈局势。是指满足下列的所有玩家策略的集合：式中，为玩家的值函数，即给定玩家策略下玩家的期望回报；为玩家在策略空间中选择的任一策略纳什均衡指的是博弈参与人做出的这样一种策略组合，在该策略组合上，任何参与人单独改变策略都不会提高自身收益。即如果在一个策略组合上，当所有其他人都不改变策略时，没有人会改变自己的策略，则该策略组合就是一个纳什均衡。

9.1博弈论基础2026年8月19日“囚徒困境”（prisoner‘sdilemma）博弈模型由数学家塔克给出。假设有两个小偷A和B联合犯罪而被警察抓住。由于警方没有足够的证据定罪，将两人分别置于不同的两个房间内进行单独审讯，对每一个嫌疑人，警方给出的政策是：AB坦白抵赖坦白8,80,10抵赖10,01,1如果两个嫌疑人都坦白，两人各被判刑8年；如果一个嫌疑人坦白，而另一个抵赖，则抵赖者再加刑2年，坦白者立即释放；如果两人都抵赖，则警方将两人各判入狱1年。9.1博弈论基础2026年8月19日“囚徒困境”案例由于两人分别置于不同的房间，都会从利己的角度出发进行选择。对A而言，尽管他不知道B作何选择，但无论B选择什么，A选择“坦白”策略总是刑期最短的（若B选择抵赖，则A选择坦白时可以获释；若B选择坦白，A选择坦白刑期更短）。相对应，B也会选择“坦白”，结果是两人都被判刑8年。两人同时抵赖整体收益最大，但利己角度使两人会选择同时坦白，即纳什均衡。A

B坦白抵赖坦白8,80,10抵赖10,01,19.1博弈论基础2026年8月19日智能博弈相关比赛博弈比赛名称赛事介绍全国大学生计算机博弈大赛计算机博弈大赛是以娱乐载体(如五子棋、六子棋、点格棋、中国象棋、围棋、连珠棋等)为研究载体的比赛全国兵棋推演大赛专项赛在推演平台上，用智能体控制飞机、舰船等单元，获得兵棋博弈的胜利ICGA（国际计算机博弈锦标赛）包含国际象棋项目和计算机奥林匹克运动会等赛事，具体项目包括各种棋类游戏和麻将等NeurIPS国际上最权威神经网络会议之一，举办了很多神经网络比赛，包括挖矿、地牢逃生、机械臂移动等复杂的比赛项目，参赛的队伍实力都很强劲，比较困难，知乎链接中有比赛汇总RLChina智能体挑战赛依托中科院自动化所“及第”多智能体开源开放平台，通过竞赛对抗对智能体进行实战训练，有效地提升人工智能的算法和人工智能处理复杂问题的能力。挑战赛项目包括智能税收，奥林匹克竞赛等。“庙算杯”人机混合对抗赛以高水平人类为对手，助力博弈决策智能技术研究。由人人对抗选拔赛、智能体选拔赛及人机混合编组对抗赛三阶段赛事组成9.智能博弈2026年8月19日9.1博弈论基础9.2博弈问题的复杂度9.3智能博弈策略求解技术9.4智能博弈应用及经典案例9.2博弈问题的复杂度

2026年8月19日博弈问题的状态复杂度和博弈树复杂度：衡量博弈问题复杂程度的两个重要标准以井字棋为例，井字棋（三子连珠棋tic-tac-toe），是一种在3

3格子上进行的连珠游戏，和五子棋类似，由于棋盘一般不画边框，格线排成井字故得名。双方的棋子由记号“

”和“×”表示，三个同一记号形成一条直线，即是胜者。共有９个位置可落子，能够形成的局面较少，复杂度的估算相对容易9.2博弈问题的复杂度

2026年8月19日博弈问题的状态复杂度和博弈树复杂度状态复杂度：是指各方从博弈的初始状态开始，所能达到的、所有不同的合法博弈状态的个数。此数量很难准确得出，通常情况下，以棋类问题为例，通过对棋盘上所有状态，即包括不合法和不可能出现的博弈状态进行统计，得到一个上限值来估算。博弈树复杂度：是指从博弈的初始状态所产生的、能完整解决该博弈问题的最小完整博弈树中叶子节点的个数，其中，整个决策树包含树中所有深度的节点。在棋类博弈中，复杂度与各种棋类博弈的博弈规则、棋盘大小等有关。对于不同棋类博弈问题，它们的复杂度相差很大。9.2博弈问题的复杂度

2026年8月19日状态复杂度及博弈树复杂度的估算方法

9.2博弈问题的复杂度

2026年8月19日状态复杂度及博弈树复杂度的估算方