A GENERALIZED QUIESCENCE SEARCH ALGORITHM

被引:37
作者
BEAL, DF
机构
[1] Department of Computer Science, Queen Mary College, London University, London, England E1 4NS, Mile End Road
关键词
D O I
10.1016/0004-3702(90)90072-8
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
This paper describes how the concept of a null move may be used to define a generalised quiescence search applicable to any minimax problem. Experimental results in the domain of chess tactics show major gains in cost effectiveness over full-width searches, and it is suggested that null-move quiescence may be almost as widely useful as the alpha-beta mechanism. The essence of the mechanism is that null moves give rise to bounds on position values which are more reliable than evaluations. When opposing bounds touch, they create a single value which is more reliable than ordinary evaluations, and the search is terminated at that point. These terminations are prior to any alpha-beta cutoffs, and can lead to self-terminating searches. © 1990.
引用
收藏
页码:85 / 98
页数:14
相关论文
共 20 条
[1]   SOME METHODS OF CONTROLLING TREE SEARCH IN CHESS PROGRAMS [J].
ADELSONVELSKIY, GM ;
ARLAZAROV, VL ;
DONSKOY, MV .
ARTIFICIAL INTELLIGENCE, 1975, 6 (04) :361-371
[2]  
BEAL DF, 1982, ADV COMPUTER CHESS, V3, P17
[3]  
BEAL DF, 1980, ADV COMPUTER CHESS, V2, P103
[4]  
BEAL DF, 1986, ICCA J, V9, P76
[5]  
BEAL DF, 1984, ICCA J, V7, P10
[6]   B-STAR TREE SEARCH ALGORITHM - BEST-1ST PROOF PROCEDURE [J].
BERLINER, H .
ARTIFICIAL INTELLIGENCE, 1979, 12 (01) :23-40
[7]  
Berliner H., 1974, THESIS CARNEGIE MELL
[8]  
Bernstein A., 1958, P 1958 W JOINT COMP, P157
[9]   MTECHNOLOGY CHESS PROGRAM [J].
GILLOGLY, JJ .
ARTIFICIAL INTELLIGENCE, 1972, 3 (02) :145-163
[10]  
GREENBLATT RD, 1967, FAL P AFIPS JOINT CO, V31, P801