---博弈树与极大极小算法.pdf

博博弈树与极大极小算法 弈 主要内容 目  博弈的基本概念  博弈树与极大极小算法 井字棋 基本概念  什么是博弈论？ 又称对策论 （Game Theory）,既是现代数学的一个新分支，也是 运筹学的一个重要学科。 研究两人或多人之间竞争合作关系的一门科学，它使用严谨的数 学模型来解决现实生活中的各种冲突问题。 计算机中的博弈论考虑游戏中的个体的预测行为和实际行为，并 研究它们的优化策略，并通过算法实现。 基本概念 一个完整的博弈应当包括五个方面的内容：  第一，博弈的参加者  第二，博弈信息  第三，可选的行为或策略的集合  第四，博弈的次序  第五，博弈方的收益 基本概念  博弈的两种分类：  静态博弈与动态博弈 静态博弈是指在博弈中，两个参与人同时选择或两人不同时选择，但 后行动者并不知道先行动者采取什么样的具体行动。 动态博弈是指在博弈中，两个参与人有行动的先后顺序，且后行动者 能够观察到先行动者所选择的行动。  完全信息博弈与不完全信息博弈 完全信息博弈指参与者对所有参与者的策略空间及策略组合下的支付 有 “完全的了解”，否则是不完全信息博弈。  完全信息静态博弈、完全信息动态博弈、不 完全信息静态博弈、不完全信息动态博弈 博弈树 由于动态博弈参与者的行动有先后次序，因此可以 依次将参与者的行动展开成一个树状图形。 博弈树的值：指的是博弈树中一个子结点的值,该值 对于博弈双方都是最优的.博弈树的子树 （subtree ） 在该子树有哪些信誉好的足球投注网站完成之后也会返回一个博弈值,虽然该 值对于该子树来说最优的,但是对整个博弈树来说并 不是全局最优的. 一个简单的问题 Grundy博弈 有一堆数目为n的钱币，由两 位选手轮流进行分堆。 要求：每个选手每次只把其 中某一堆分成数目不等的两小堆。 例如选手甲把n分成两堆后， 轮到乙就可以挑其中一堆来分， 如此进行下去，直到有一位选手 先无法把钱币分成不相等的两堆 时就得认输。 状态空间图Max and Min (7,Min) (6,1,Max) (5,2,Max) (4,3,Max) (5,1,1,Min) (4,2,1,Min) (3,2,2,Min) (3,3,1,Min) (4,1,1,1,Max) (3,2,1,1,Max) (2,2,2,1,Max) B (3,1,1,1,1,Min) (2,2,1,1,1,Min) A (2,1,1,1,1,1,Max) C Max与节点 Min或结点  对Min走后的每一个Max节点,必须证明Max对Min可能的 每一个棋局对弈后能获胜，即Max必须应付Min的所有的 招法，这是一个 “与” 的含义，因此，含有Max的节点可 看成 “与节点”。  对Max走后的每一个Min节点,只须证明Max有一步走赢就 可以，即Max只要考虑走一步棋使Min无法招架就成，因 此含有Min的节点可看成 “或” 节点。  这样对弈过程的有哪些信誉好的足球投注网站图就呈现出 “与或图”的形式。  敌对双方交替动作的有哪些信誉好的足球投注网站叫做对抗性有哪些信誉好的足球投注网站。 与或图 (7) (6,1) (5,2) (4,3) (5,1,1) (4,2,1) (3,2,2)