ALPHA-BETA SEARCH ENHANCEMENTS WITH A REAL-VALUE GAME-STATE EVALUATION FUNCTION

Article type: Research Article

Authors: Mańdziuk, Jacek¹ | Osman, Daniel¹

Affiliations: Warsaw, Poland

Note: [1] Faculty of Mathematics and Information Science, Warsaw University of Technology, Plac Politechniki 1, 00-661, Warsaw, Poland, email: mandziuk@mini.pw.edu.pl, dosman@prioris.mini.pw.edu.pl

Abstract: The note presents results of applying several Alpha-Beta search enhancements in the game of give-away checkers with a real-value state evaluation function. In particular, the MTD-bi (bisection) algorithm is tested and compared (1) with MTD(f) and (2) with Alpha-Beta search enhanced with transposition tables and the history heuristic. The results show that in the real-value domain the MTD(f) algorithm becomes impractical and loses its superiority over MTD-bi. Several remarks concerning possible implementations of different replacement schemes in transposition tables are presented and discussed.

DOI: 10.3233/ICG-2004-27104

Journal: ICGA Journal, vol. 27, no. 1, pp. 38-43, 2004