Some methods of controlling the tree search in chess programs

✍ Scribed by G.M. Adelson-Velskiy; V.L. Arlazarov; M.V. Donskoy

• Publisher: Elsevier Science
• Year: 1975
• Tongue: English
• Weight: 982 KB
• Volume: 6
• Category: Article
• ISSN: 0004-3702
• DOI: 10.1016/0004-3702(75)90021-1

✦ Synopsis

This paper describes several tree search methods that have been implemented in our chess playing program (KAISSA) and some perspectives on this domain. The most general and most flexible method of program organization is exhaustive search with cutoffs. Therefore our program is based on searching exhaustively to a given depth, and permitting wide usage of cutoffs at any level of the search tree. Besides the program includes analysis of all exchanges up to their end. Experience with earlier programs has ~hown that disregard of exchanges would lead to gross errors.

1. A General Description of the Program

The program receives a position to choose a move from (initial position). Any method of such choice should be formulated in terms of cutoffs in the search tree, As a rule this is easy to do. The main parameter continUing a search is depth (or level) n of a position under consideration in the game tree, or the number of plies (half-moves) which should be executed to obtain this pcsition from the initial (iota given search) position. In the absolute schema, in all positions at depth n ~< N (where N is an integer chosen for a given search) all legal moves are considered (admitted for the search). If n > N, then the forcing schema is employed; namely only captures, checks and replies to checks are considered. Moreover, the computation of a static evaluation function is a forcing move and each side can decide whether it is more advantageous to compute the value of the evaluation function or to continue the forcing variation. The static evaluation function used by our program is of no particular interest and does not essentially differ from those