fbpx
维基百科

Alpha-beta剪枝

十月 18, 2023

Alpha-beta剪枝是一种搜索算法，用以减少极小化极大算法（Minimax算法）搜索树的节点数。这是一种对抗性搜索算法，主要应用于机器游玩的二人游戏（如井字棋、象棋、围棋）。当算法评估出某策略的后续走法比之前策略的还差时，就会停止计算该策略的后续发展。该算法和极小化极大算法所得结论相同，但剪去了不影响最终决定的分枝[1]。

历史 编辑

Allen Newell和Herbert A. Simon在1958年，使用了John McCarthy所谓的“近似”alpha-beta算法[2]，此算法当时“应已重新改造过多次”[3]。亞瑟·李·塞謬爾（Arthur Samuel）有一个早期版本，同时Richards、Hart、Levine和/或Edwards在美国分别独立发现了alpha-beta[4]。McCarthy在1956年达特默思会议上提出了相似理念，并在1961年建议给他的一群学生，其中包括MIT的Alan Kotok[5]。Alexander Brudno独立发现了alpha-beta算法，并在1963年发布成果[6]。Donald Knuth和Ronald W. Moore在1975年优化了算法[7][8]，Judea Pearl在1982年证明了其最优性[9]。

对原版极小化极大算法的改进 编辑

Alpha-beta的优点是减少搜索树的分枝，将搜索时间用在“更有希望”的子树上，继而提升搜索深度。该算法和极小化极大算法一样，都是分支限界类算法。若节点搜索顺序达到最优化或近似最优化（将最佳选择排在各节点首位），则同样时间内搜索深度可达极小化极大算法的两倍多。

在（平均或恒定）分枝因子为b，搜索深度为d层的情况下，要评估的最大（即招法排序最差时）叶节点数目为O(b*b*...*b) = O(bd)——即和简单极小化极大搜索一样。若招法排序最优（即始终优先搜索最佳招法），则需要评估的最大叶节点数目按层数奇偶性，分别约为O(b*1*b*1*...*b)和O(b*1*b*1*...*1)（或O(bd/2) = O(√bd)）。其中层数为偶数时，搜索因子相当于减少了其平方根，等于能以同深度搜索两次[10]。b*1*b*1*...意义为，对第一名玩家必须搜索全部招法找到最佳招式，但对于它们，只用将第二名玩家的最佳招法截断——alpha-beta确保无需考虑第二名玩家的其他招法。但因节点生成顺序随机，实际需要评估的节点平均约为O(b3d/4)[2]。

一般在alpha-beta中，子树会由先手方优势或后手方优势暂时占据主导。若招式排序错误，这一优势会多次切换，每次让效率下降。随着层数深入，局面数量会呈指数性增长，因此排序早期招式价值很大。尽管改善任意深度的排序，都以能指数性减少总搜索局面，但排序临近根节点深度的全部局面相对经济。在实践中，招法排序常由早期、小型搜索决定，如通过迭代加深。

算法使用两个值alpha和beta，分别代表大分玩家放心的最高分，以及小分玩家放心的最低分。alpha和beta的初始值分别为正负无穷大，即双玩家都以可能的最低分开始游戏。在选择某节点的特定分枝后，可能发生小分玩家放心的最小分小于大分玩家放心的最大分（beta <= alpha）。这种情况下，父节点不应选择这个节点，否则父节点分数会降低，因此该分枝的其他节点没有必要继续探索。

伪代码 编辑

下面为一有限可靠性版本的Alpha-beta剪枝的虛擬代碼[10]： 

 function alphabeta(node, depth, α, β, maximizingPlayer) // node = 节点，depth = 深度，maximizingPlayer = 大分玩家 if depth = 0 or node是终端節點 return 節點的啟發值 if maximizingPlayer v := -∞ for 每个子節點 v := max(v, alphabeta(child, depth - 1, α, β, FALSE)) // child = 子節點 α := max(α, v) if β ≤ α break // β裁剪 return v else v := ∞ for 每个子節點 v := min(v, alphabeta(child, depth - 1, α, β, TRUE)) β := min(β, v) if β ≤ α break // α裁剪 return v 
(* 初始調用 *) alphabeta(origin, depth, -∞, +∞, TRUE) // origin = 初始節點

在這個有限可靠性的alpha-beta中，當v超出調用參數α和β構成的集合時（v < α或v > β），alphabeta函數返回值v。而與此相對，強化的有限可靠性alpha-beta限制函數返回在α與β包括範圍中的值。

参考文献 编辑

  • George T. Heineman, Gary Pollice, and Stanley Selkow. Chapter 7: Path Finding in AI. Algorithms in a Nutshell. Oreilly Media. 2008: 217–223. ISBN 978-0-596-51624-6. 
  • Judea Pearl, Heuristics, Addison-Wesley, 1984
  • John P. Fishburn. Appendix A: Some Optimizations of α-β Search. Analysis of Speedup in Distributed Algorithms (revision of 1981 PhD thesis). UMI Research Press. 1984: 107-111. ISBN 0-8357-1527-2. 
  1. ^ Russell, Stuart J.; Norvig, Peter. 3rd. Upper Saddle River, New Jersey: Pearson Education, Inc. 2010: 167 [2016-02-05]. ISBN 0-13-604259-7. （原始内容存档于2011-02-28）. 
  2. ^ 2.0 2.1 McCarthy, John. Human Level AI Is Harder Than It Seemed in 1955. LaTeX2HTML 27 November 2006 [2006-12-20]. （原始内容存档于2012-04-08）. 
  3. ^ Newell, Allen and Herbert A. Simon. Computer Science as Empirical Inquiry: Symbols and Search (PDF). Communications of the ACM. March 1976, 19 (3) [2006-12-21]. doi:10.1145/360018.360022. （原始内容 (PDF)存档于2007-06-28）. 
  4. ^ Edwards, D.J. and Hart, T.P. The Alpha–beta Heuristic (AIM-030). Massachusetts Institute of Technology. 4 December 1961 to 28 October 1963 [2006-12-21]. （原始内容存档于2012-04-08）. 
  5. ^ Kotok, Alan. MIT Artificial Intelligence Memo 41. 2004-12-03 [2006-07-01]. （原始内容存档于2012-04-08）. 
  6. ^ Marsland, T.A.. (PDF). J. Wiley & Sons: 159–171. May 1987 [2006-12-21]. （原始内容 (PDF)存档于2008-10-30）. 
  7. ^ * Knuth, D. E., and Moore, R. W. An Analysis of Alpha–Beta Pruning (PDF). Artificial Intelligence. 1975, 6 (4): 293–326. doi:10.1016/0004-3702(75)90019-3. [永久失效連結] Reprinted as Chapter 9 in Knuth, Donald E. Selected Papers on Analysis of Algorithms. Stanford, California: Center for the Study of Language and Information - CSLI Lecture Notes, no. 102. 2000 [2016-02-05]. ISBN 1-57586-212-3. OCLC 222512366. （原始内容存档于2010-11-15）. 
  8. ^ Abramson, Bruce. (PDF). ACM Computing Surveys. June 1989, 21 (2): 137 [2008-08-20]. doi:10.1145/66443.66444. （原始内容 (PDF)存档于2008-08-20）. 
  9. ^ Pearl, Judea. The Solution for the Branching Factor of the Alpha–beta Pruning Algorithm and its Optimality. Communications of the ACM. August 1982, 25 (8): 559–564. doi:10.1145/358589.358616. 
  10. ^ 10.0 10.1 Russell, Stuart J.; Norvig, Peter, 2nd, Upper Saddle River, New Jersey: Prentice Hall, 2003 [2016-02-05], ISBN 0-13-790395-2, （原始内容存档于2011-02-28） 

外部链接 编辑

十月 18, 2023
alpha, beta剪枝, 是一种搜索算法, 用以减少极小化极大算法, minimax算法, 搜索树的节点数, 这是一种对抗性搜索算法, 主要应用于机器游玩的二人游戏, 如井字棋, 象棋, 围棋, 当算法评估出某策略的后续走法比之前策略的还差时, 就会停止计算该策略的后续发展, 该算法和极小化极大算法所得结论相同, 但剪去了不影响最终决定的分枝, 目录, 历史, 对原版极小化极大算法的改进, 伪代码, 参考文献, 外部链接历史, 编辑allen, newell和herbert, simon在1958年, 使用了j. Alpha beta剪枝是一种搜索算法 用以减少极小化极大算法 Minimax算法 搜索树的节点数 这是一种对抗性搜索算法 主要应用于机器游玩的二人游戏 如井字棋 象棋 围棋 当算法评估出某策略的后续走法比之前策略的还差时 就会停止计算该策略的后续发展 该算法和极小化极大算法所得结论相同 但剪去了不影响最终决定的分枝 1 目录 1 历史 2 对原版极小化极大算法的改进 3 伪代码 4 参考文献 5 外部链接历史 编辑Allen Newell和Herbert A Simon在1958年 使用了John McCarthy所谓的 近似 alpha beta算法 2 此算法当时 应已重新改造过多次 3 亞瑟 李 塞謬爾 Arthur Samuel 有一个早期版本 同时Richards Hart Levine和 或Edwards在美国分别独立发现了alpha beta 4 McCarthy在1956年达特默思会议上提出了相似理念 并在1961年建议给他的一群学生 其中包括MIT的Alan Kotok 5 Alexander Brudno独立发现了alpha beta算法 并在1963年发布成果 6 Donald Knuth和Ronald W Moore在1975年优化了算法 7 8 Judea Pearl在1982年证明了其最优性 9 对原版极小化极大算法的改进 编辑Alpha beta的优点是减少搜索树的分枝 将搜索时间用在 更有希望 的子树上 继而提升搜索深度 该算法和极小化极大算法一样 都是分支限界类算法 若节点搜索顺序达到最优化或近似最优化 将最佳选择排在各节点首位 则同样时间内搜索深度可达极小化极大算法的两倍多 在 平均或恒定 分枝因子为b 搜索深度为d层的情况下 要评估的最大 即招法排序最差时 叶节点数目为O b b b O bd 即和简单极小化极大搜索一样 若招法排序最优 即始终优先搜索最佳招法 则需要评估的最大叶节点数目按层数奇偶性 分别约为O b 1 b 1 b 和O b 1 b 1 1 或O bd 2 O bd 其中层数为偶数时 搜索因子相当于减少了其平方根 等于能以同深度搜索两次 10 b 1 b 1 意义为 对第一名玩家必须搜索全部招法找到最佳招式 但对于它们 只用将第二名玩家的最佳招法截断 alpha beta确保无需考虑第二名玩家的其他招法 但因节点生成顺序随机 实际需要评估的节点平均约为O b3d 4 2 一般在alpha beta中 子树会由先手方优势或后手方优势暂时占据主导 若招式排序错误 这一优势会多次切换 每次让效率下降 随着层数深入 局面数量会呈指数性增长 因此排序早期招式价值很大 尽管改善任意深度的排序 都以能指数性减少总搜索局面 但排序临近根节点深度的全部局面相对经济 在实践中 招法排序常由早期 小型搜索决定 如通过迭代加深 算法使用两个值alpha和beta 分别代表大分玩家放心的最高分 以及小分玩家放心的最低分 alpha和beta的初始值分别为正负无穷大 即双玩家都以可能的最低分开始游戏 在选择某节点的特定分枝后 可能发生小分玩家放心的最小分小于大分玩家放心的最大分 beta lt alpha 这种情况下 父节点不应选择这个节点 否则父节点分数会降低 因此该分枝的其他节点没有必要继续探索 伪代码 编辑下面为一有限可靠性版本的Alpha beta剪枝的虛擬代碼 10 function alphabeta node depth a b maximizingPlayer node 节点 depth 深度 maximizingPlayer 大分玩家 if depth 0 or node是终端節點 return 節點的啟發值 if maximizingPlayer v for 每个子節點 v max v alphabeta child depth 1 a b FALSE child 子節點 a max a v if b a break b裁剪 return v else v for 每个子節點 v min v alphabeta child depth 1 a b TRUE b min b v if b a break a裁剪 return v 初始調用 alphabeta origin depth TRUE origin 初始節點 在這個有限可靠性的alpha beta中 當v超出調用參數a和b構成的集合時 v lt a或v gt b alphabeta函數返回值v 而與此相對 強化的有限可靠性alpha beta限制函數返回在a與b包括範圍中的值 参考文献 编辑George T Heineman Gary Pollice and Stanley Selkow Chapter 7 Path Finding in AI Algorithms in a Nutshell Oreilly Media 2008 217 223 ISBN 978 0 596 51624 6 Judea Pearl Heuristics Addison Wesley 1984 John P Fishburn Appendix A Some Optimizations of a b Search Analysis of Speedup in Distributed Algorithms revision of 1981 PhD thesis UMI Research Press 1984 107 111 ISBN 0 8357 1527 2 Russell Stuart J Norvig Peter Artificial Intelligence A Modern Approach 3rd Upper Saddle River New Jersey Pearson Education Inc 2010 167 2016 02 05 ISBN 0 13 604259 7 原始内容存档于2011 02 28 2 0 2 1 McCarthy John Human Level AI Is Harder Than It Seemed in 1955 LaTeX2HTML 27 November 2006 2006 12 20 原始内容存档于2012 04 08 请检查 date 中的日期值 帮助 Newell Allen and Herbert A Simon Computer Science as Empirical Inquiry Symbols and Search PDF Communications of the ACM March 1976 19 3 2006 12 21 doi 10 1145 360018 360022 原始内容 PDF 存档于2007 06 28 Edwards D J and Hart T P The Alpha beta Heuristic AIM 030 Massachusetts Institute of Technology 4 December 1961 to 28 October 1963 2006 12 21 原始内容存档于2012 04 08 请检查 date 中的日期值 帮助 Kotok Alan MIT Artificial Intelligence Memo 41 2004 12 03 2006 07 01 原始内容存档于2012 04 08 Marsland T A Computer Chess Methods PDF from Encyclopedia of Artificial Intelligence S Shapiro editor PDF J Wiley amp Sons 159 171 May 1987 2006 12 21 原始内容 PDF 存档于2008 10 30 Knuth D E and Moore R W An Analysis of Alpha Beta Pruning PDF Artificial Intelligence 1975 6 4 293 326 doi 10 1016 0004 3702 75 90019 3 永久失效連結 Reprinted as Chapter 9 in Knuth Donald E Selected Papers on Analysis of Algorithms Stanford California Center for the Study of Language and Information CSLI Lecture Notes no 102 2000 2016 02 05 ISBN 1 57586 212 3 OCLC 222512366 原始内容存档于2010 11 15 Abramson Bruce Control Strategies for Two Player Games PDF ACM Computing Surveys June 1989 21 2 137 2008 08 20 doi 10 1145 66443 66444 原始内容 PDF 存档于2008 08 20 Pearl Judea The Solution for the Branching Factor of the Alpha beta Pruning Algorithm and its Optimality Communications of the ACM August 1982 25 8 559 564 doi 10 1145 358589 358616 10 0 10 1 Russell Stuart J Norvig Peter Artificial Intelligence A Modern Approach 2nd Upper Saddle River New Jersey Prentice Hall 2003 2016 02 05 ISBN 0 13 790395 2 原始内容存档于2011 02 28 外部链接 编辑http www emunix emich edu evett AI AlphaBeta movie sld001 htm 页面存档备份 存于互联网档案馆 http sern ucalgary ca courses CPSC 533 W99 presentations L1 5B McCullough Melnyk 页面存档备份 存于互联网档案馆 http sern ucalgary ca courses CPSC 533 W99 presentations L2 5B Lima Neitz search html 页面存档备份 存于互联网档案馆 https web archive org web 20021223103359 http www maths nott ac uk personal anw G13GAM alphabet html https web archive org web 20041123061044 http chess verhelst org search html http www frayn net beowulf index html 页面存档备份 存于互联网档案馆 http hal inria fr docs 00 12 15 16 PDF RR 6062 pdf 页面存档备份 存于互联网档案馆 Minimax with or without alpha beta pruning algorithm visualization game tree solving Java Applet for balance or off balance trees 页面存档备份 存于互联网档案馆 Demonstration animation of minimax game search algorithm with alpha beta pruning using html5 canvas javascript css 页面存档备份 存于互联网档案馆 Java implementation used in a Checkers Game 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title Alpha beta剪枝 amp oldid 76085163, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。