An algorithm for the detection of move repetition without the use of hash-keys

Authors

  • Vladan Vučković Faculty of Electronic Engineering Faculty of Philosophy, Niš
  • Đorđe Vidanović Faculty of Electronic Engineering Faculty of Philosophy, Niš

DOI:

https://doi.org/10.2298/YJOR0702257V

Keywords:

theory of games, algorithms in computer chess, repetition detection

Abstract

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., “Null move and deep search: selective-search heuristics for obtuse chess programs”, ICCA Journal, 16 (3) (1993) 137-143.

Fray, P.W., A introduction to Computer Chess. Chess Skill in Man and Machine (Texts and monographs in computer science), Springer-Verlag, New York, N.Y., ISBN 0-387-07957-2, 1977, 55-67.

Kaindl, H., Horacek, H., and Wagner, M., “Selective search versus brute force”, ICCA Journal, 9(3) (1986) 140-145.

Moreland, B., Zobrist keys description could be found at: http://www.brucemo.com/compchess/programming/zobrist.htm, Move repetition discussion at: http://www.brucemo.com/compchess/programming/repetition.htm, 2001.

Zipproth, S., “Suchet, so werdet ihr finden, Eine Reise in die Gedankenwelt eines Schachprogramm”, Computer schach und spiele, 3 (2003) 15-19.

Zobrist, A.L., "A new hashing method with applications for game playing", ICCA Journal, 13(2) (1990) 69-73.

Vučković, V., "Realization of the chess mate solver application", Yugoslav Journal of Operations Research (YUJOR), 14(2) (2004) 273-288.

Vučković, V., “Decision trees and search strategies in chess problem solving applications”, Proceedings of a Workshop on Computational Intelligence Theory and Applications, SCG, Niš, 141-159, 2001.

Downloads

Published

2007-09-01

Issue

Vol. 17 No. 2 (2007)

Section

Research Articles

License

Copyright (c) 2007 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.