论文部分内容阅读
Korf,R.E:“多棋手的α—β剪枝”(学术研究短文).刊载在《人工智能》杂志1991年48卷的第99页至第111页上。我们考虑将带α——β剪枝的极小极大搜索推广列无合作的、有两名以上棋手的完备博奕。极小极大算法在[2]中推广为 max 算法,施用于 n 元组向量,这种 n 元组表示每一位棋手的估值。假设每位棋手的估值数总和存在一个上界,且对每一个别值存在一个下界,这样,浅层α——β剪枝就能进行,但不能进行深度剪枝。最好情况下,渐近分枝因数减少到(1+(4b-3)~(1/2))/2,而在平均情况下,剪枝不会减少渐近分枝因数,所以α——β剪枝的有效性只存在于两名棋手博奕的特殊情形。此外,我们证明了它是对两名选手的最佳定向算法。
Korf, R. E: “α-β pruning of multi-player” (academic research essay), published in 1991, Vol 48, pp. 99-111. We consider the promotion of a minimal maximal search with α - β pruning to a non - cooperative, complete game with more than two players. The minimax algorithm is generalized to max algorithm in [2] and applied to the n-tuple vector. This n-tuple represents the valuation of each player. Suppose there exists an upper bound for the sum of the estimates of each player and a lower bound for each individual value so that shallow α - β pruning can be done, but no deep pruning can be done. In the best case, the asymptotic branching factor is reduced to (1 + (4b-3) ~ (1/2)) / 2, while in average, the pruning does not reduce the asymptotic branching factor, The effectiveness of -p pruning exists only in the special case of two chess players. In addition, we proved it to be the best directional algorithm for both players.