人机博弈是人工智能的重要分支,人们在这一领域探索的过程中产生了大量的研究成果,而极小化极大算法(minimax)是其中最基础的算法,它由Shannon在1950年正式提出。Alpha-beta剪枝的本质就是一种基于极小化极大算法的改进方法。
在人机博弈中,双方回合制地进行走棋,己方考虑当自己在所有可行的走法中作出某一特定选择后,对方可能会采取的走法,从而选择最有利于自己的走法。这种对弈过程就构成了一颗博弈树,双方在博弈树中不断搜索,选择对自己最为有利的子节点走棋。在搜索的过程中,将取极大值的一方称为max,取极小值的一方称为min。max总是会选择价值最大的子节点走棋,而min则相反。这就是极小化极大算法的核心思想。
极小化极大算法最大的缺点就是会造成数据冗余,而这种冗余有两种情况:①极大值冗余;②极小值冗余。相对应地,alpha剪枝用来解决极大值冗余问题,beta剪枝则用来解决极小值冗余问题,这就构成了完整的Alpha-beta剪枝算法。接下来对极大极小值冗余和具体剪枝过程作简要介绍。
极大值冗余如图1所示,这是一颗博弈树的某一部分,节点下的数据为该节点的值,节点B的值为20,节点D的值为15,这里,C为取极小值的min节点,因此节点C的值将小于等于15;而节点A为取最大值max的节点,因此A只可能取到B的值,也是就说不再需要搜索C的其他子节点E和F的值就可以得出节点A的值。这样将节点D的后继兄弟节点减去称为Alpha剪枝。
图 1 极大值冗余的Alpha剪枝
极小值冗余如图2所示,这也是一颗博弈树的某一部分,节点B的值为10,节点D的值为19,这里,C节点为取最大值max节点。因此,C的值将大于等于19;节点A为取极小值的min节点,因此A的值只能取B的值10,也就是说不再需要求节点C的子节点E和F的值就可以得出节点A的值。这样将节点D的后继兄弟节点减去称为Beta剪枝。
图2 极小值冗余的Beta剪枝
[描述来源:Shannon, C. E. (1950). XXII. Programming a computer for playing chess. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 41(314), 256-275.
URL:http://www.tandfonline.com/doi/pdf/10.1080/14786445008521796
描述来源:Knuth, D. E., & Moore, R. W. (1975). An analysis of alpha-beta pruning. Artificial intelligence, 6(4), 293-326.
URL:http://www.sciencedirect.com/science/article/pii/0004370275900193
描述来源:Su, Y. J. F. (2009). IMPROVEMENT ON ALPHA-BETA SEARCH ALGORITHM IN CHINESE CHESS [J]. Journal of Beijing Normal University (Natural Science), 2, 013.
URL:http://en.cnki.com.cn/Article_en/CJFDTotal-BSDZ200902013.htm]