An algorithm for the detection of move repetition without the use of hash-keys
DOI:
https://doi.org/10.2298/YJOR0702257VKeywords:
theory of games, algorithms in computer chess, repetition detectionAbstract
This paper addresses the theoretical and practical aspects of an important problem in computer chess programming - the problem of draw detection in cases of position repetition. The standard approach used in the majority of computer chess programs is hash-oriented. This method is sufficient in most cases, as the Zobrist keys are already present due to the systemic positional hashing, so that they need not be computed anew for the purpose of draw detection. The new type of the algorithm that we have developed solves the problem of draw detection in cases when Zobrist keys are not used in the program, i.e. in cases when the memory is not hashed.References
Donninger, C. (1993) Null move and deep search: Selective-search heuristics for obtuse chess programs. ICCA Journal, 16, (3), 137-143
Fray, P.W. (1978) Chess skill in man and machine, texts and monographs in computer science. Berlin, itd: Springer Verlag
Kaindl, H., Horacek, H., Wagner, M. (1986) Selective search versus brute force. ICCA Journal, 9, (3), 140-145
Moreland, B. (2001) Zobrist keys. http://www.brucemo.com/compchess/programming/zobrist.htm, Move repetition discussion at: http://www.brucemo. com/compchess/programming/repetition.htm
Vučković, V.V. (2004) Realization of the chess mate solver application. Yugoslav Journal of Operations Research, vol. 14, br. 2, str. 273-288
Vučković, V.V. (2001) Decision trees and search strategies in chess problem solving applications. u: Computational Intelligence: Theory and Applications, Proceedings of the Workshop, University of Niš, 141-159
Zipproth, S. (2003) Suchet so werdet ihr finden Eine Reise in die Gedankenwelt eines Schachprogramm. Computer schach und spiele, 3, 15-19
Zobrist, A.L. (1990) A new hashing method with applications for game playing. ICCA Journal, 13(2) 69-73
Downloads
Published
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.