多棋手的α——β剪枝

Korf,R.E:“多棋手的α—β剪枝”(学术研究短文).刊载在《人工智能》杂志1991年48卷的第99页至第111页上。我们考虑将带α——β剪枝的极小极大搜索推广列无合作的、有两名以上棋手的完备博奕。极小极大算法在[2]中推广为 max 算法,施用于 n 元组向量,这种 n 元组表示每一位棋手的估值。假设每位棋手的估值数总和存在一个上界,且对每一个别值存在一个下界,这样,浅层α——β剪枝就能进行,但不能进行深度剪枝。最好情况下,渐近分枝因数减少到(1+(4b-3)^(1/2))/2,而在平均情况下,剪枝不会减少渐近分枝因数,所以α——β剪枝的有效性只存在于两名棋手博奕的特殊情形。此外,我们证明了它是对两名选手的最佳定向算法。