AI Alpha-Beta剪枝



AI Alpha-Beta剪枝

Alpha-beta剪枝是minimax算法的修改版本。它是minimax算法的一种优化技术。
正如我们在minimax搜索算法中看到的那样,必须检查的游戏状态数量在树的深度上呈指数级。由于我们无法消除指数,因此可以将其减半。因此,存在一种无需检查游戏树的每个节点就可以计算出正确的minimax决策的技术,该技术称为剪枝。这涉及两个阈值参数Alpha和Beta用于将来扩展,因此称为 alpha-beta剪枝。也称为 Alpha-Beta算法
Alpha-beta剪枝可以应用于树的任何深度,有时它不仅可以剪枝树叶,还可以剪枝整个子树。
两个参数可以定义为: Alpha: : 到目前为止,我们在Maximizer路径上的任何位置都找到了最佳(最高价值)选择。 alpha的初始值为-∞ 测试版: 到目前为止,我们在"最小化器"路径上的任何位置都找到了最佳(最低价值)选择。 beta的初始值为 +∞
将Alpha-beta剪枝为标准minimax算法会返回与标准算法相同的动作,但会删除所有不会真正影响最终决策但会使算法变慢的节点。因此,通过剪枝这些节点,可以使算法更快。

注意: 为更好地理解该主题,请研究minimax算法。

Alpha-beta剪枝的条件:

alpha-beta剪枝所需的主要条件是:
α>=β
    

有关alpha-beta剪枝的要点:

Max播放器只会更新alpha的值。
Min播放器只会更新beta的值。
回溯树时,节点值将传递到上层节点,而不是alpha和beta值。
我们只会将alpha,beta值传递给子节点。

Alpha-beta剪枝的伪代码:

function minimax(node, depth, alpha, beta, maximizingPlayer) is
if depth ==0 or node is a terminal node then
return static evaluation of node
if MaximizingPlayer then      // for Maximizer Player
   maxEva=-infinity          
   for each child of node do
   eva= minimax(child, depth-1, alpha, beta, false)
  maxEva= max(maxEva, eva) 
  alpha= max(alpha, maxEva)    
   if beta<=alpha
 break
 return maxEva
  
else                         // for Minimizer player
   minEva= +infinity 
   for each child of node do
   eva= minimax(child, depth-1, alpha, beta, true)
   minEva= min(minEva, eva) 
   beta= min(beta, eva)
    if beta<=alpha
  break        
 return minEva
    

Alpha-Beta剪枝的工作方式:

让我们以两人搜索树为例,了解Alpha-beta剪枝的工作方式
步骤1: 在第一步中,Max玩家将首先从节点A开始移动,其中节点α=-∞和β= +∞,这些alpha和beta值向下传递到节点B,此处α=-∞和β= +∞,并且节点B将相同的值传递给其子D。

AI Alpha-Beta剪枝_https://bianchenghao6.com_【ai 教程】_第1张

步骤2: : 在节点D处,将计算α的值作为其对Max的转向。首先将α的值与2进行比较,然后与3进行比较,max(2,3)= 3将是节点D处的α值,节点值也将是3、
步骤3: 现在算法回溯到节点B,因为这是Min的转弯,因此β的值将发生变化,现在β= +∞将与可用的后续节点值进行比较,即min(∞,3) = 3,因此在节点B处现在α=-∞,β= 3、

AI Alpha-Beta剪枝_https://bianchenghao6.com_【ai 教程】_第2张

下一步,算法遍历节点B的下一个后继节点,即节点E,并且还将传递α=-∞和β= 3的值。
第4步: 在节点E处,Max旋转,并且alpha值将更改。 alpha的当前值将与5进行比较,因此max(-∞,5)= 5,因此在节点Eα= 5和β= 3处,其中α> =β,因此将剪枝E的右后继,并且算法将不会遍历它,并且节点E处的值将为5、

AI Alpha-Beta剪枝_https://bianchenghao6.com_【ai 教程】_第3张

第5步: : 下一步,算法再次将树从节点B移回节点A。在节点A处,alpha的值将被更改,最大可用值为3,因为max(-∞,3)= 3,β= +∞,这两个值现在传递给A的右后继节点,即节点C。
在节点C处,α= 3和β= +∞ ,并将相同的值传递到节点F。
步骤6: : 在节点F处,将再次将α的值与左子级0进行比较,然后max(3,0)= 3,然后与右子元素1比较,max(3,1)= 3仍然保持3,但F的节点值将变为1、

AI Alpha-Beta剪枝_https://bianchenghao6.com_【ai 教程】_第4张

步骤7: : 节点F将节点值1返回到节点C,在Cα= 3和β= +∞的情况下,β的值将被更改,它将进行比较1 min(∞,1)=1、现在在C处,α= 3和β= 1,它又满足条件α> =β,因此将剪枝掉C的下一个孩子,即G,算法不会计算整个子树G。

AI Alpha-Beta剪枝_https://bianchenghao6.com_【ai 教程】_第5张

步骤8: C现在将值1返回给A,这里A的最佳值是max(3,1)=3、下面是最终的游戏树,它显示了计算出的节点和从未计算过的节点。因此,在此示例中,最大化器的最佳值为3、

AI Alpha-Beta剪枝_https://bianchenghao6.com_【ai 教程】_第6张

在Alpha-Beta剪枝中移动顺序:

alpha-beta剪枝的有效性高度依赖于检查每个节点的顺序。移动顺序是alpha-beta剪枝的重要方面。
它可以有两种类型:

最差排序: 在某些情况下,alpha-beta剪枝算法不会剪枝任何树上的叶子,并且与minimax算法完全一样。在这种情况下,由于alpha-beta因素,它还会消耗更多的时间,这种剪枝动作被称为最差排序。在这种情况下,最佳移动发生在树的右侧。这样的订单的时间复杂度为O(b m )。
理想排序: 当在树中进行大量剪枝时,发生理想的alpha-beta剪枝顺序,并且最佳移动发生在树的左侧。我们应用DFS,因此它首先在树的左侧搜索,并且在相同的时间内经过两次最小深度算法。理想排序的复杂度为O(b m/2 )。

找到良好顺序的规则:

以下是一些在alpha-beta剪枝中找到良好顺序的规则:

从最浅的节点获得最佳移动。
对树中的节点进行排序,以便首先检查最佳节点。
使用领域知识,同时找到最佳方法。例如: 对于国际象棋,请尝试顺序: 先捕获,然后威胁,然后向前移动,向后移动。
我们可以保留状态,因为状态可能会重复。