《人工智能》第2章问题求解智能体_4.pdfVIP

《人工智能》第2章 问题求解智能体(4) 丁嵘 dingr@ 北航软件开发环境国家重点实验室 大纲  问题求解智能体  无信息的有哪些信誉好的足球投注网站  有信息的有哪些信誉好的足球投注网站  约束可满足问题  博弈中的对抗有哪些信誉好的足球投注网站问题 2 博弈中的对抗有哪些信誉好的足球投注网站问题  博弈中的优化决策(Optimal decisions)  α-β 剪枝(α-β pruning)  不完整的实时决策(Imperfect, real-time decisions) 2014/4/2 3 博弈  多智能体环境下，智能体之间存在合作和竞争关系；  数学领域中的“博弈”：  把任何多智能体环境看成是一种博弈游戏，如果其中每个智能体对其 它智能体的影响是“显著的”，这些影响可以是合作或竟争。  人工智能领域中的“博弈”：  确定性的、有完整信息的，轮流行动的，两个游戏者的零和 游戏。 游戏结束时，效用值总是相等且符号相反。  博弈的抽象本性成为AI研究者感兴趣的对象 博弈 AI 中研究的博弈，即如何根据当前的棋局， 选择对自己最有利的一步棋 ？ 博弈的特点： 双方的智能活动，任何一方都不能单独 控制博弈过程，而是由双方轮流实施其控制 对策的过程。 2014/4/2 6 博弈问题的表示： 用博弈树来表示，它是一种特殊的与或图。 节点代表博弈的格局（即棋局），相当于状态空 间中的状态，反映了博弈的信息。与节点、或节 点隔层交替出现。 2014/4/2 7 为什么与节点、或节点隔层交替出现？ 假设博弈双方为：MAX和MIN 在博弈过程中，规则是双方轮流走步。在博弈 树中，相当于博弈双方轮流扩展其所属节点。 2014/4/2 8 MIN 从MAX方的角度来看： 所有MIN方节点都是与节点 好招 理由： 因为MIN方必定选择最不利于MAX方的方式来 扩展节点，只要MIN方节点的子节点中有一个 对MAX方不利，则该节点就对MAX方不利，故 为 “与节点”。 2014/4/2 9 MAX 从MAX方的角度来看： 所有属于MAX方的节点都是 “或节点” 好招 理由： 因为扩展MAX方节点时，MAX方可选择扩展最 有利于自己的节点，只要可扩展的子节点中有 一个对已有利，则该节点就对已有利。 2014/4/2 10 博弈问题的表示： 在博弈树中，先行一方的初始状态对应树的 根节点，而任何一方