博弈树搜索算法的分析与设计.pdf-资料库

第卷第期年月计算机学报 , 博弈树搜索算法设计和分析孙伟马绍汉山东大学计算机科学系 , 济南摘要本文提出了博弃树搜索 ’ 算法的两种改进算法 ’ 和 ’ 葬 ’ 搜索博弃树端结点的充分必要条件 , 并由此证明了 , 如果法 , 给出了邵 ’ 和 ’ 算法同时还证明了朋 ’ 葬法优能估计一个合适的上界 , 则于一刀算法论述了刀 ’ 算法搜索深度为奇数的博弃树时 , 在一般情况下也优于朋 ‘ 算法 , 且这两种算法都降低了存储开销 , ’ 算法优于关键词博弃树 , 与或树 , 极小极大值 , ’ 算法 , 。一刀葬法仍侧如哪 , 泞按刀刀吸,匆五左几召 , , 苍份 , 份 ‘ 刀召 ’ 一刀份 , ’ 召 , , , , ’ , 一夕本文年月日收到本课题得到国家自然科学基金及山东省自然科学基金资助孙伟 , 获硕士学位 , 从事并行算法、人工智能方面的研究工作马绍汉 , 教授 , 从事算法分析与设计、并行算法和人工智能等方而的研究工作

计算机学报年箭会二一口 , 年 , 在人工智能博弈树搜索中 , ‘ 不是自左向右搜索 , 而是同时在树中扩展多条路径 , 进行最佳优先搜索一声是一种常用的算法该算法严格的按自左向右顺序搜索一棵博弈树 , 利用从左边得到的信息减少右边搜索的结点个数〔‘ 〕提出了另一种博弈树搜索算法把博弈树看作与或树 , 把博弈树中求极小极大值问题看作与或树中求最优解树值问题在求解过程中要以某种方式遍历与或树的结点 , 这相当于在状态空间中搜索 , 所以该算法称为状态空间搜索法 , 即所谓习泞召 ’ 算法和一刀不同 , 证明了于一刀但长 , 使得它只能搜索较小的树此外 , 当搜索深度为偶数的树时 , 度为奇数的树时 , 和证明了若该估值介于极小极大值和树本文证明了在搜索这种树时 , 召召召二说明了 ’ 和 ‘ 都降低了存储开销 ’ 搜索的端结点个数不会多 ’ 的缺点是存储开销太大 , 所需存储空间随搜索树的深度增加呈指数级增 , 习 ‘ 优于一夕, 但搜索深 ’ 进行了两种改进 , 提出了 ‘ 算法 ’ 算法 , 其中 ’ 是对召习占 ’ 本身修改后得到的 , 要求估计一个合适的初始上界本文 , 适合搜索深度为奇数的 ‘ 一定优于一刀, 并论述了在一般情况下 ’ 也优于 ’ 算法优于一声算法 , 即在搜索一棵博弈树时 , ‘ ’ 有时反而不如一刀本文对之间 , 犷优于刮 , 博弈树及其搜索算法与或树和博弈树与或图是人工智能问题归约法的一种图表示对与或树来说 , 它的每个结点代表一个问题 , 根结点代表初始问题具有儿子的结点称作非端结点 , 每个非端结点或者具有与儿子 , 或者具有或儿子如果任何一个或儿子代表的问题得到解决 , 则具有或儿子的结点代表的问题就得到解决如果所有与儿子代表的问题都得到解决 , 则具有与儿子的结点代表的问题得到解决 , 没有儿子的结点称作端结点 , 每个端结点代表了一个或者可解或者不可解的基本问题与或树搜索通常是寻找一棵在某种条件下最好的解树下面先给出与或树的解树和部分解树的定义定义与或树的解树是满足下述条件的的一棵子树的根结点是 , 的根结点如果的一个非端结点在 , 中 , 若该结点具有或儿子 , 则只有一个或儿子在 , 中若该结点具有与儿子 , 则所有与儿子都在中定义与或树的部分解树刀是满足下述条件的的一棵子树的根结点是即的根结点如果的任何一个除根之外的结点在即中 , 则它如果口的一个具有或儿子的结点在即中 , 则至多只有它的一个或的祖先也在即中儿子在即中由定义可知 , 扩展的部分解树可以得到的解树 , 不同的扩展方法得到不同的解树 , 因此 , 一棵部分解树表示了经过扩展可得到的所有解树的集合对于与或树的解树通常要定义一个收益代价函数了, 并要求出具有最大最小了值

期孙伟等博弈树搜索算法设计和分析的解树 , 这种解树称为最优解树函数有很多定义方法 , 本文只做如下定义定义设。 , 是赋给的端结点刀的收益值 , 则 , ’ 。是 , 的端结点例如对图所示的与或树口 , 方框代表与结点 , 圆圈代表或结点 , 划线部分是它的一棵解树 , 约一图一棵与或树及它的一棵解树和走 , 先走 , 因为的每一种走法 , 博弈树是由两个分别称为的选手对弈产生的一棵搜索树 , 博弈树可以可能有几种不同的走法 , 看作是一种与或树假设走步后得走步后得到的棋局用与结点表示 , 因为对到的棋局用或结点表示 , 然后轮到都要有办法对付 · 另一种解释这种联系的方法是把博弈树的于每个结点了看作问题从出发寻找走 , 则只要任何一个了的儿子能找到一种取胜办法 , 该问题就解决了 , 所以的儿子表示为或结对的每个儿子都找到取胜办法时 , 该问题才点如果此时轮到得到解决 , 所以的儿子表示为与结点这样 , 轮流走步 , 当产生的搜索树到达一定深度时 , 就对处在该深度的结点从一方的观点给出一个估计值 , 这个值通常用静态估计函数来计算例如图所示的与或树实际上就是一棵博弈树 , 其中轮到走步的棋局用方框表示 , 以后称作的一种取胜策略如果此时轮到走 , 则只有当和结点端结点的值就是从最大值 , 而出 , 首先对与或树的所有结点定义一个极小极大值函数则设法减小该值结点轮到一方的观点给出的估计值这样 , 走的棋局用圆圈表示 , 以后称作总是试图取得能够取得的最大值可以由与或树的极小极大值给定义与或树的一个结点兀的极小极大值如下定义如果二具有或儿子 , 则夕二‘ 是的儿子则二二 ‘ 如果二是端结点 , 则这样与或树的极小极大值就是对 , 其中争是的根。夕二‘ ‘ 是的儿子如果二具有与儿子 , 。闭曾证明了 , 若把博弈树看成与或树 , 则博弈树的极小极大值恰好是其最优解树的值 , 即。一硬少是的一棵解树这个结论是召 ‘ 算法的理论基础 · · 一尹算法一刀算法是博弈树搜索常用的算法该算法严格地按自左向右顺序搜索 , 求博弈树的

计算机学报年极小极大值在搜索过程中 , 利用从左边得到的信息删除右边的某些结点 , 从而在总体上减少了搜索结点数对于一棵所有非端结点度数都为。 , 深度为的博弈树 , 一声算法在最好情况下搜索的结点数 , 当为奇数时 , 是 “ ‘ ’‘, 。“ 一 ‘ ’‘ 一当汉为偶数时 , 是。“ 一闭等人给出了〕而用定义求极小极大值则需全部搜索该树的扩个结点年 , 一刀算法搜索博弈树一个结点的充分必要条件对任意一个结点 , 定义 “ 结点了的所有 “ 结点的所有祖先的所有左儿子极小极大值的最大值祖先的所有左儿子极小极大值的最小值定理〕结点被一刀搜索的充分必要条件是一声算法虽然大大减少了搜索结点数 , 提高了搜索效率 , 但由于该算法具有方向性特征 , 算法的效率和结点的排列顺序有很大关系例如对图所示一声算法需全部搜索的三个儿子 , 但若值为的结点是的树 , 的最左儿子 , 则一刀算法只搜索的一个儿子 · · ‘ 算法图对夕不利的情况值得出博弈树的极小极大值 · 朋 ‘ 算法把博弈树看作与或树 , 通过求与或树最优解树的 ‘ 算法实质上是一个最佳优先搜索分枝限界过程 · 它考虑的是由部分解树表示的解树集合的集合 , 并首先对具有最大上界的解树集合分枝 , 即先扩展具有最大上界的部分解树 , 部分解树的上界是该部分解树迄今为止已扩展的所有端结点值的最小值在此过程中 , 删去某些部分解树 , 这些部分解树代表的解树集合中的最大解树值小于当前部分解树代表的解树集合中的最大解树值这个过程一直进行 , 直到一棵部分解树完全扩展成一棵解树为止这棵解树就是最优解树 , 其值就是博弈树的极小极大值二朋 ‘ 的基本思想是设立了一表 , 每个状态可以看成是代表含有结点 “ 的解树集合气其中个保存各。 , 。 , 状态的。的值表示这个集合中解树值的上界表中的状态按其值的递减顺序排列 , 使得具有最大值的状态首先得到扩展算法结束后 , 表中剩下的那个状态的值就是博弈树的极小极大值朋 ‘ 算法的详细描述请参阅〔〕也给出了 ‘ 算法搜索博弈树结点的充分必要条件 , 并由此证明了朋 ’ 算法优于一刀算法设都为设是中的一个结点 , 用议 , 是一棵规则博弈树 , 即全的所有非端结点的度数都为 , 所有端结点的深度表示的极乞镇的表示的第个儿子 , 用小极大值对任意一个结点夕, 定义矛卫老、‘ ￡毛簇一 , 夕哎夕十镇簇乙如果夕如果夕如果夕如果一对任意一个结』点刃夕 , 定义 , 了 · ‘’‘镇‘ , 一 ‘ , 如果如果

期孙伟等博弈树搜索算法设计和分析对任意一个端结点一 , · … , ‘ , , 其祖先 ‘ 夕, 一齐一 ‘ , 这里艺一 , , … , 一再定义此口聋。。了‘ 卜是奇数且无蕊 ‘ 法一夕,‘ ‘ 卜是奇数且镇云簇汉一 ‘ 卜是偶数且一礴则有如下定理定理〕博弈树的一个端结点被习召‘ ’ 搜索的充分必要条件是况 , 群这里是。 ‘ 坛是偶数取得最小值的层数为证明定义设 , 是两个博弈树搜索算法 , 如果对于算法搜索的每一个博弈树的端结 ‘ 算法优于一刀算法 , 首先给出一个定义点 , 算法也要搜索 , 则称算法支配算法推论〕 ’算法支配。一刀算法 ’ 顺序搜索 , 是否删去某推论从理论上说明了习 ’ 算法优于一刀算法的原因由于一刀算法只能自左向右端结点只依赖于从的左边得到的信息 , 即只有在 , 镇 ’ 算法除考虑的左边的信息外 , 同时考虑的右边的群之一成立 , 结点就不必搜索因此 , 对于一刀算 ‘ 算法比一刀算法搜索 ‘ 算法一定不搜索 , 但反之不一定成立 ‘ 这样的情况下才不搜索但镇弋或信息 , 只要法删去的结点较少的端结点 , 从而优于一刀算法 ’ 算法的主要缺点是存储开销太大它需要存储所有待扩展的部分解树用状态 ’ 算法只能搜索较表示 , 存储开销随搜索深度的增加呈指数级增长出于这个原因 , 小的树 · ’ 的两种改进算法 ‘ 算法习 ’ 算法开始时 , 博弈树的根结点相应的状态是 , , , 这里 , 表示所有解树值的上界 , 当然也是最优解树值的上界开始时是然是最保险的 , 执行果我们能估计一个初始上界 , 使得值介于极小极大值和替们把这种带初始上界的习泞召 ’ 算法称作朋 ‘ 算法二 , 用干作初始上界显 ’ 算法一定能求出正确的极小极大值但这也是最悲观的估计 , 如 , 代 , 则执行算法也能求出正确的极小极大值 , 而且搜索更少的结点 · 我之间 , 用 , 十 , , 改 ’ 算法的关键是估计一个合适的上界 , 当值大于且越接近于极小极大值时 , ’ 算法搜索的结点越少如果估计的值偏低 , 树的极小极大值为 ‘ , 执行得到的值是。 , 容易证明下面的结论成立 ‘ 算法求不出正确的极小极大值设博弈 ’ , 若 ’ , 若。镇 ’ 因此 , 如果在能够知道有关博弈树极小极大值的概率信息 , 例如它的概率分布的情况下使用 ‘ 算法 , 可以大大提高搜索效率 ·

刀‘ ‘ 算法年推论证明了朋 ’ 算法支配一声算法 , 这是对搜索深度为偶数的博弈树而言的 , 定端结点被朋 ’ 搜索的充分必要条件但在搜索深度为奇数的博一声不搜索的结点 , 朋 ’ 可能要搜索例如对图所理给出的是一个弈树时 , 示的树 , 习习 ’ 搜索的端结点下用 “ 一 ”划出 , 一刀搜索的端结点下用 “ ”划出 ‘ 算法并不支配一刀算法 , 万餐口一口加芳书关芳关关苦釜苦长釜图习 ‘ 不如 , 刀的例子从此看来 , 结点时 , 就把它所有的 ‘ 算法在搜索深度是奇数的博弈树时有时反而不如一刀算法 , 原因在于朋 ’ 算法遇到儿子结点都放入表中 , 而实际上很多结点以后不会得到扩展 , 即这些结点相应的三元组不会出现在表的顶层 , 最后又被从端结点 , 从而有时搜索的端结点数多于一刀算法这就促使我们考虑在这种情况下如何改进习习习 ‘ 算法 , 使得改进后的算法搜索较少的端结点 , 且能支配一刀算法这是 ’ 算法的出发点表中删去 , 这样召习召 ‘ 算法搜索很多无用的前面所说的博弈树都是以结点为根的博弈树 , 搜索这种树求出的是对来的操作换成对结点的博弈树 , 求对说能取得的最大值现在修改朋 ’ 算法 , 使得能搜索根为来说能取得的最小值把朋 ‘ 算法中所有对结点的操的操作 , 所有的求最小值运算换成是求最大值运算 , 作 , 所有对表中的状态按其值的递减顺序排列改为递增顺序排列经过这种十换成一 , ’ 算法一样 , 算法也是一个最佳优先搜索分枝修改后得到的算法称作算法和限界算法 , 它的基本思想也是通过在所有解树集合中求最优解树来求博弈树的极小极大值但这里的最优解树是指具有最小值的解树 , 而解树的了值定义为其所有端结点值的最大值结点的操作换成是对现在给出算法搜索端结点的充分必要条件 , 从朋算法的形成可以看出 , 算法是对朋 ’ 算法的操作和运算进行取反变换后得到的 , 和朋 ’ 恰好是一对相反的过程因此 , 如果把搜索端点的充分必要条件也进行类似的变换 , 就能得出‘ 端结点的充分必要条件把 ’ 搜索结点定义 , 对的定义改为对小值运算的定理 , 所有的换成所有的中对一的定义所有的求最大值运算结点定义的关系式改为对换成求最这样得到下面换成一 , 一换成

期孙 ‘ 伟等博弈树搜索算法设计和分析定理博弈树的一个端结点被算法搜索的充分必要条件是截 , 镇群 , 其中是竺 ‘ 是偶数取得最大值的层数 · 如同对 ‘ 算法改进得到习 ’ 一样 , 也可以类似地改进算法如果能估计一个合 , 一开始 , 适的下界 , 使得值介于一和极小极大值之间 , 用则算法也能求得正确的值 , 且搜索更少的结点设博弈树的极小极大值为尸 , 执行算法得到的值为 , 容易证明下式成立 · , 代替 , , ’, 一一若一簇镇 ’ 若 ’ 算法是用来搜索根为虽然结点的树 , 此时肥算法表示为函数过程刀搜索树的根结点 , 第二个参数表示初始下界设用小极大值 , , … , , , 结点的博弈树 , 它也可以作为子过程搜索根为表示待的儿子个数为 ,‘ , 分别结点为根的博弈树的极 , 其中第一个参数根结点一表示 , 下面的算法 ‘ 求出以习户犷‘ , , 一刀名艺气泞 · ‘, 以为根的博弈树的极小极大值 ‘ 等于它的各个以小极大值的最大值设这个最大值在它的第议成‘镇个儿子取得根的儿子调用朋过程搜索各子树在云的左边、调用第 ‘个儿子调用朋时能得到正确的极小极大值 ’ 然后用子 , 由于以这些儿子为根的子树的极小极大值都小于 ’ , 所以调用儿子为根的子树的极 ’ 算法自左向右对时得到的值都小于 ’ , 因此对 ’ 继续搜索云右边的儿后得到的值都为 ’ , 这就证明了 ‘ 算法的正确性 · · ‘ 和邵 ’ 的性能分析本节首先给出邵 ’ 算法搜索博弈树的一个端结点的充分必要条件 , 然后相应端结点的充分必要条件 , 并由此出发把 ‘ 和 ’ 同占‘召 , 算给出甜 ’ 算法搜索一个法和一刀算法进行了比较设此 , 熊和一定理设 ‘ ’ 的初始上界为 , 一个当仍同时 , 当式定义 , 则有下述定理端结点被 ‘ 搜索的充分必要条件是时 , 艺 , 刀盆 , 其中 , 是。 ‘ ‘是偶数取得最小值的层数证明充分性是显然的一 , 满足和此的端结点在朋 ’ 算法执行到某一时刻 , 必然以三元组 , , 的形式出现在表的顶层下面证明必要性设一端结点被 ’ 搜索 , 则一定会在某时刻出现在三元组是 , , 其中一王 , 歼 , 因此只需证明表顶层 , 相应的假设

计算机学报年弋定义 , 在出现时将有值 , 按戍的定义 , 必存在的祖先 ‘ , 使得簇。表中存在的左边兄弟夕, 使得了力 , 因此及其后代在 , 这样结点相应的三元组 , ‘ , 再按。 ‘ 的表中 , 不会出现在表的顶层 , 即不被朋 ’ 搜索 , 这与假设矛盾所以成 , 即况 ‘ 式的证明和定理的证明非常类似 , 这里略去二推论如果 ‘ 钱证明若一个 , 则朋 ’ 算法支配召习习 ‘ 算法端结点不被 ‘ 搜索 , 根据定理 , 或者况不成立 , 或者 , 群不成立 , 或者两式均不成立由于 ’ 算法的初始上界一 , 定理的式中的条件也不成立 , 所以朋 ’ 算法也不搜索 , 按定义 , , 此时 ’ 算法支配 ’ 算法推论指出 , 如果估计的值是介于极小极大值和端结点被朋 ’ 算法搜索 , 它也一定被之间的一个值 , 则若一个 ’ 算法搜索 , 但反之不成立这说明 ’ 算表占用的存储空间相应减少 , 法优于朋 ‘ 算法此外 , 由于 ’ 搜索更少的结点 , 从而降低了存储开销现在我们从定理峨出发 , 得出 ‘ 算法相应的结论把一式进行如定理要求的各项取反变换 , 由定理可得如下定理定理设是朋 ’ 算法开始搜索所在的以端点被夕 ‘ 搜索的充分必要条件是结点为根的博弈树时的下界 , 则当时 , 呈当时 , , 盆 , 其中 ‘ 是袱 ‘ 是偶数取得最大值的层数证明由定理进行变换后得到条件应是 ‘ 当乙时 , 刀‘ 摊尝 , 刀‘ 镇‘ ’ 这里的心 , 月才‘ 镇时 , 心和 ‘ 都是对以 , 当理根结点的儿子为根的子树定义的根据的定义 , 一王 , , 相应地有弋 , 将这式子代入 ‘和 ‘ , 即得到定理的两个条件一对 ’ 一心 , 戒推论证明如果博弈树的一个 ’ 算法支配一刀算法满足乙何情况下 , 因此艺当乙时 , 满足此都成立注意到这里的 , 这里的况就是那里的 , 所以端结点被 ’ 算法搜索 , 根据定理 , 当艺 , 一时 , 镇艾在任就是定理中对一刀算法定义的成立根据定理 , 也被。一刀算法搜索 · 按定义 , 前面说过 , ‘ 算法支配一刀算法 · ‘ 算法搜索深度为奇数的博弈树时 , 有时 ’比一刀算法搜索更多的端结点而根据推论 , 。。 · 算法在此情况下一定优于。一 , 算法 , 它搜索的端结点不会多于。一 , 算法这说明从总体上看 ‘ 比朋 ‘ 更适合搜索这种类型的树 ‘ 算法是按自左向右的顺序搜索以儿子为根的子树 , 这有些类似于一刀算法在搜索各子树时 , 朋 ’ 和习尽习 ‘ 一样采用的是最佳优先搜索策略这样 , 朋 ‘ 兼有一刀算法和习习习 ’ 算法的特征 ‘ 算法搜索一棵子树 ‘ 镇云镇 , 时 , 利用 ‘ 左 , 簇夕的极小极大值的最大值作为初始下界 , 这就减少了搜索 ‘ 的结点边的子树 , 数通常来说 , 具有较大的极小极大值的子树越靠左越好 , 因为右边子树得到的值越大 , 根结点的

资料库

博弈树搜索算法的分析与设计.pdf

相关推荐

开发技术

热门标签

最新资料