92机器博弈

RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology第六章：机器博弈Chapter06MachineGamePlayingRuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§01关于机器博弈Section01OnMachineGamePlayingRuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§01关于机器博弈1.1博弈的特征：智力竞技博弈是智力竞技。机器博弈，意味着机器参与博弈，参与智力竞技。机器博弈可以是机器与机器之间的博弈，也可以是机器与人类之间的博弈。我们这里的博弈只涉及双方博弈，即双方对垒的智力游戏，常见的是棋类游戏，如：中国象棋，军旗，围棋，以及国际象棋等。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§01关于机器博弈1.2博弈的目标：击败对手博弈的目标是取胜，取胜的棋局如同状态空间法中的目标状态。与八数码游戏一样，游戏者需要对棋局进行操作，以改变棋局，使其向目标棋局转移。然而，八数码游戏只涉及一个主体，不是博弈。博弈涉及多个主体，他们按规则，依次对棋局进行操作，并且，他们的目标是击败对手。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§01关于机器博弈1.3双方博弈实例围棋以围棋为例，竞技的双方分为黑方和白方，由黑方开棋，双方轮流行棋，最终，谁占据的地盘大，谁就成为获胜方。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§02博弈问题的描述Section02RepresentationsofGamePlayingRuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§02博弈问题的描述2.1博弈问题的形式化定义：博弈被定义为一个四元组：其中：G,O,s(o),s(g)(6.1)(1)G={c}：博弈空间(棋局或博弈状态的集合)(2)O={o}：算子空间(操作或规则的集合)(3)c(o)G：当前棋局或博弈状态(最初即开局)(4)c(g)G：胜局或博弈目标集合应用O中的算子(操作或规则)对c(o)进行操作，使其有利于转换为胜局c(g)c(g)的过程称为博弈。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§02博弈问题的描述2.2博弈问题的三要素c(o)和c(g)以及O(1)操作(又称规则或算子)：o:GG或：c(j)=o(c(i))(c(i),c(j)G;oO)(2)当前棋局(最初是开局)：c(o)G(机器当前面对的棋局)(3)k-步博弈树：基于c(o)的k-步博弈规划图RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology博弈空间G：围棋所有可能的棋局的集合§02博弈问题的描述2.3博弈问题描述示例一围棋：围棋博弈空间G中可能的棋局数：|G|361!理论上可能的当前棋局c(o)的数量=|G|361!操作空间O：围棋所有行棋规则的集合k-步博弈树：太复杂太难画(略)RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology假设有7个钱币，两位博弈者依次对其进行划分，使对手遇到不能再进行划分的情形即为获胜者。§02博弈问题的描述2.3博弈问题描述示例二划分钱币：博弈状态编码：(Player,N1,N2,…,Nm)(1)博弈者：Player{Max,Min}(2)Ni{7,6,5,4,3,2,1}：第i堆钱币数(m为钱币堆数)(3)开局：{Max,7}RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§02博弈问题的描述2.3博弈问题描述示例二划分钱币：博弈空间：共有28种可能的博弈状态G={(Max,7),(Max,6,1),(Max,5,2),(Max,4,3),(Max,5,1,1),(Max,4,2,1),(Max,3,2,2),(Max,3,3,1),(Max,4,1,1,1),(Max,3,2,1,1),(Max,2,2,2,1),(Max,3,1,1,1,1),(Max,2,2,1,1,1),(Max,2,1,1,1,1,1),(Min,7)…}算子空间：博弈规则集合O={每次将1堆钱币划分为数量不等的2堆钱币}博弈目标集合(对Max而言)：c(g)={(Min,2,2,2,1),(Min,2,2,1,1,1),(Min,2,1,1,1,1,1)}RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnologyMaxMinMaxMinMaxMin§02博弈问题的描述2.3博弈问题描述示例二划分钱币：博弈树(Max先)：由图可知，Max先行时，Min必定能获胜。红线为Min的行棋策略。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§02博弈问题的描述2.4k-步博弈树通过评估行棋并不是所有的博弈问题都能像钱币游戏那样，几步棋就能解决战斗，并且，能把博弈过程所有的可能都考虑到。实际上，博弈空间可能会很大，如围棋，其博弈空间G理论上可达361!，因此，对于任意棋局，博弈者可能会面临无数的选择，不太可能从当前棋局一直看到终局。因此，博弈者往往采取从当前棋局向前看几步并通过评估行棋的策略。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§02博弈问题的描述2.4k-步博弈树通过评估行棋模拟人的博弈策略，机器(Max)通过k-步博弈树评估当前棋局，“向前看几步”，以确定当前的行棋。3-步博弈树1步2步3步值得注意的是，Max的选择是OR关系，而Min的选择对于Max则是AND关系。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§03极大极小算法Section03Max-MinAlgorithmRuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§03极大极小算法3.1Max-Min博弈Step1.生成k-步博弈树Max代表机器一方/Min代表敌方设Max面对的当前棋局为c(o)，以c(o)为根，生成k-步博弈树：当前棋局c(o)RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§03极大极小算法3.1Max-Min博弈Step2.评估棋局(博弈状态)估价函数为特定的博弈问题定义一个估价函数est(c)，用以评估k-步博弈树叶节点对应的棋局cG，est(c)的值越大，意味着棋局c对Max越有利。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§03极大极小算法3.1Max-Min博弈Step3.回溯评估极大极小运算由叶节点向根节点方向回溯评估，在Max处取最大评估值(或运算)，在Min处取最小评估值(与运算)。行棋决策RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§03极大极小算法3.1Max-Min博弈Step3.回溯评估极大极小运算Max按取最大评估值的方向行棋RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§03极大极小算法3.1Max-Min博弈Step4.递归循环Max行棋后，等待Min行棋;Min行棋后，即产生对于Max而言新的当前棋局c(o);返回Step1.，开始下一轮博弈，即：step1.以c(o)为根，生成k-步博弈树；step2.评估博弈树叶节点对应的博弈状态(棋局)；step3.进行极大极小运算(Max-Min运算)；step4.等待Min行棋，产生新的c(o)，返回step1.RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§03极大极小算法3.2一个示例一字棋设有33棋格，Max与Min轮流行棋，黑先白后，先将3颗棋子连成一线的一方获胜。博弈状态一字棋博弈空间：共有9!种可能的博弈状态一字棋算子空间：博弈规则集合O={&*#!@^###+&%$$$}一字棋博弈目标集合(对Max而言)：c(g)=RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§03极大极小算法3.2一个示例一字棋定义估价函数：est(c)(1)对于非终局的博弈状态c，估价函数为：est(c)=(所有空格都放上黑色棋子之后，3颗黑色棋子连成的直线总数)－(所有空格都放上白色棋子之后，3颗白色棋子连成的直线总数)例如：c=est(c)=3–2=1RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§03极大极小算法3.2一个示例一字棋定义估价函数：est(c)(2)若c是Max的胜局，则：est(c)=+例如：c=(3)若c是Min的胜局，则：est(c)=–例如：c=现在可以进行Max-Min博弈了。需要说明的是，等价的(如具有对称性的)棋局被视为相同棋局。RuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnology§03极大极小算法3.2一个示例一字棋Max-Min博弈：step1.以c(o)=为根，生成2-步博弈树：MaxMinMinMinRuanXiaogangInstituteofArtificialIntelligence&RobotsBeijingUniversityofTechnologyMaxMinMinMinMax-Min博弈：step2.评估博弈树叶节点对应的博弈状态§03极