Alpha-beta剪枝

✍ dations ◷ 2025-07-20 11:40:22 #Alpha-beta剪枝

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

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

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

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

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

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

下面为一有限可靠性版本的Alpha-beta剪枝的伪代码:

01 function alphabeta(node, depth, α, β, maximizingPlayer) 02      if depth = 0 or node是终端节点03          return 节点的启发值04      if maximizingPlayer05          v := -∞06          for 每个子节点07              v := max(v, alphabeta(child, depth - 1, α, β, FALSE)) 08              α := max(α, v)09              if β ≤ α10                  break 11          return v12      else13          v := ∞14          for 每个子节点15              v := min(v, alphabeta(child, depth - 1, α, β, TRUE))16              β := min(β, v)17              if β ≤ α18                  break 19          return v
alphabeta(origin, depth, -∞, +∞, TRUE) 

在这个有限可靠性的alpha-beta中,当v超出调用参数α和β构成的集合时(v < α或v > β),alphabeta函数返回值v。而与此相对,强化的有限可靠性alpha-beta限制函数返回在α与β包括范围中的值。

相关

  • 脑膜炎奈瑟菌脑膜炎双球菌(学名Neisseria meningitidis),又名脑膜炎奈瑟菌或脑脊髓膜炎双球菌,简称为脑膜炎球菌,是一种革兰氏阴性菌,因其所导致的脑膜炎而闻名,亦会造成脑膜炎球菌血症(一种致
  • DNA重组重组DNA是一种人工合成的脱氧核糖核酸。它是把一般不同时出现的DNA序列组合到一起而产生的。从遗传工程的观点来看重组DNA是把相关的DNA添加到已有生物的基因组中,比如细菌的
  • 末日论末世论或末日论(英语:Eschatology)是研究历史终结及其相关方面的哲学或者神学理论,神学上的末世论一般关心人类社会的终结以及如何终结等问题,而哲学上的末世论则可能着眼于人类
  • 宝血基督的血,基督宗教教内又称之为宝血,是基督教神学术语,指基督耶稣被钉十字架死时流出的血。基督的血使《新约》的救赎得以完成,使上帝与人的新约生效;也指圣餐中所使用的酒。新约
  • 芳香胺芳香胺(英语:Aromatic amine)是指具有一个芳香性取代基的胺——即-NH2、-NH-或含氮基团连接到一个芳香环上,芳香烃的结构中通常含有一个或多个苯环。苯胺是这类化合物最简单的实
  • 十三月历十三月历的提出可追溯至1849年,Auguste Comte创立。当时的主要考虑是,现行公历每个月的天数有长有短,而且与实际的月球运行周期不吻合,另外月份跟星期之间的关系十分混乱。而相
  • 乔治·亨丁顿乔治·亨丁顿(英语:George Huntington,1850年4月9日-1916年3月3日),为美国医学家,发现亨丁顿舞蹈症。
  • 台华轮台华轮是台湾本岛与澎湖之间的交通船,固定航线是高雄港和马公港,营运者是台湾航业。除了固定航班以外,但近年来台华轮也行驶高雄再经由马公通往厦门和小三通以及其他包船的航行
  • 网域游戏网域游戏,全称网域计算机网络有限公司,于1997年4月在深圳成立,主要从事网络游戏的开发和运营,主要注重MMORPG的开发。公司位于深圳市南山区高新科技园中区。2011年改名为光速工
  • 米哈伊尔·巴克莱·德托利米哈伊尔·博格达诺维奇·巴克莱·德托利亲王(Mikhail Bogdanovich Barklay-de-Tolli,西里尔字母: Михаи́л Богда́нович Баркла́й-де-То́лл