人工智能导论--第二章对抗有哪些信誉好的足球投注网站_171603446.ppt

早就被提出，但是直到有了电子计算机才被广泛应用（有了伪随机数）。蒙特卡洛：摩洛哥的一个著名赌场的名字 * 在给定时间达到之前重复该过程，随时可以得到结果。 * 1，了解不够的节点希望多了解，应优先考虑；2，对当前为止获利高的节点，希望优先。二者要均衡 * 如果一个节点还可以扩展，就扩展，然后模拟。否则从其子节点中按照信心值选择一个节点，循环。（TREEPOLICY的功能） * 第二章 对抗有哪些信誉好的足球投注网站 对抗有哪些信誉好的足球投注网站：博弈 博弈问题 极小极大方法 ?-?剪枝 蒙特卡洛博弈方法 * * 2.1 博弈问题 博弈问题 双人 一人一步 双方信息完备 零和 * 分钱币问题 （7） （6,1） （5,2） （4,3） （5,1,1） （4,2,1） （3,2,2） （3,3,1） （4,1,1,1） （3,2,1,1） （2,2,2,1） （3,1,1,1,1） （2,2,1,1,1） （2,1,1,1,1,1） 对方先走 我方必胜 * 中国象棋 一盘棋平均走50步，总状态数约为10的161次方。 假设1毫微秒走一步，约需10的145次方年。 结论：不可能穷举。 * 0 2.2 极小极大过程 5 -3 3 3 -3 0 2 2 -3 0 -2 3 5 4 1 -3 0 6 8 9 -3 0 -3 3 -3 -3 -2 1 -3 6 -3 0 3 1 6 0 1 1 极大 极小 a b 0 2 * 2.3 ?-?剪枝 极大节点的下界为?。 极小节点的上界为?。 剪枝的条件： 后辈节点的?值≤祖先节点的?值时， ?剪枝 后辈节点的? 值≥祖先节点的?值时， ?剪枝 简记为： 极小≤极大，剪枝 极大≥极小，剪枝 * 4 8 6 -3 1 5 0 3 5 ?-?剪枝（续） -3 3 -3 0 2 2 -3 0 -2 3 0 9 -3 0 0 -3 0 3 3 0 5 4 1 1 -3 1 6 6 1 a b c d e f g h i j k m n 2.4 蒙特卡洛博弈方法 为什么?-?剪枝方法在围棋上失效？ ?-?剪枝方法存在的问题 依赖于局面评估的准确性 局面评估问题 大量专家知识 知识的统一性问题 人工整理 * 围棋落子模型 围棋对弈过程可以看做一个马尔科夫过程： 五元组：{T，S，A(i)，P(·|i,a)，r(i,a)} T：决策时刻 S：状态空间，S={i} A(i)：可行动集合（可落子点） P(·|i,a)：状态i下选择行动a的概率 r(i,a)：状态i下选择行动a后课获得的收益 * 蒙特卡洛方法 二十世纪40年代中期S.M.乌拉姆和J.冯·诺伊曼提出的一种随机模拟方法 多重积分 矩阵求逆 线性方程组求解 积分方程求解 偏微分方程求解 随机性问题模拟 * 蒲丰投针问题 1777年法国科学家蒲丰提出一种计算π的方法： 取一张白纸，在上面画上许多条间距为d的等距平行线，另取一根长度为l（ld）的针，随机地向该纸上投掷针，并记录投掷次数n以及针与直线相交的次数m，据此计算π值。 * * d l x α (x, α)决定了针的位置 针与直线的相交条件：x ≤ (l/2)·sinα 其中：x∈[0, d/2], α∈[0, π] 黄颜色部分与长方形面积之比即为针与直线相交的概率 * d/2 π α 0 * 蒙特卡洛评估 从当前局面的所有可落子点中随机选择一个点落子 重复以上过程 直到胜负可判断为止 经多次模拟后，选择胜率最大的点落子 * 蒙特卡洛规划 解决马尔科夫决策问题的有效方法之一 基本思想与特点： 将可能出现的状态转移过程用状态树表示 从初始状态开始重复抽样，逐步扩展树中的节点 某个状态再次被访问时，可以利用已有的结果，提高了效率 在抽样过程中可以随时得到行为的评价 * 蒙特卡洛规划的步骤 选择 从根节点出发自上而下地选择一个落子点 扩展 向选定的点添加一个或多个子节点 模拟 对扩展出的节点用蒙特卡洛方法进行模拟 回溯 根据模拟结果依次向上更新祖先节点估计值 * 更新过程 设ni为当前要模拟的节点，△为模拟获得的收益 对ni及其祖先的模拟次数加1 ni的收益加△ 更新ni的祖先的收益，同类节点加△，非同类节点减△ （这里节点的类型按照极大极小节点划分） * 蒙特卡洛规划算法流程 * 选择落子点的策略 两方面的因素： 对尚未充分了解的节点的探索 对当前具有较大希望节点的利用 * 多臂老虎机模型 * 多臂老虎机模型 1952年Robbins提出的一个统计决策模型 多臂老虎机 多臂老虎机拥有k个手臂，拉动每个手臂所获得的收益遵循一定的概率且互不相关，如何找到一个策略，使得拉动手臂获得的收益最大化 用于解决蒙特卡洛规划中选择落子点的问题 * 信心上限算法UCB1 function UCB1 for each 手臂j: