个人认为:αβ剪枝就是为了减少子节点比较,目的就是为了取最稳妥的,能绝对到手的美元。(其实懂了你就可以知道,这是可以赢的概率)
第一步 “比较” ,理解它本身是一个树结构,这棵树是一层最大值,一层最小值,以此类推。最大值一层就是取子节点最大值。最小值一层就是取子节点最小值。
第二步 “剪枝” ,在第一步的基础上理解,左节点已经确认取值范围后,是否还需要继续判断右节点,如果不需要判断右节点,那么就剪枝。
咱们开始了:
称我方为MAX
,对方为MIN
,图示如下:
比如以此树先理解第一步,每个节点都需要比较大小:
最后这一排数字是什么?它就意味着能得到的美元金额
第一步,圈圈,取最少可以赢多少钱,3美元和17美元,那么最少赢3美元
第二步,圈圈,取最少可以赢多少钱,2美元和12美元,那么最少赢2美元
第三步,方块,取最多可以赢多少钱,3美元和2美元,那么最多可以赢3美元
第四步,方块,取最多赢多少钱,下限已经是3美元了,就不看2美元了,取3美元
依次类推,按这种每个节点都比较大小的算法,最终得到的结果就是:
剪枝:
首先必须牢记一下:β 是上限;α 是下限;
第一步:o代表最少赢3美元,p代表赢17美元,但是H是最小节点,那么就意味着不能贪心,需要取最小值,设置H的上限为3
第二步:那么H是D的子节点,那么D是最大节点,意味着要贪心一点,需要取最大值,但是现在咱们只有3美元,只好先把D下限设置为3。
第三步:首先D的下限已经是3了,所以I的下限也必须为3,(因为I如果确定小于3,那么D节点必然会取3做为最大值)。然后,I的左侧倒推值是2,设置I的上限是2。此时,I的α下限是3,β上限是2,那么R节点不管是多少都不用看了。
换句话说就是,你出I扑克将有几率赢得2美元或者12美元。出H扑克你已经知道能赢3美元,稳妥起见为了规避只赢2美元,那么12美元就不冒险去赌这个概率了。所以,R节点不管是多少,都把他剪掉。