Author: Djordje Vidanovic
Date: 09:40:26 08/01/04
Hi, we (Vladan Vuckovic and Djordje Vidanovic) are sorry not to have taken part in the long thread started by Gian Carlo Pascutto that dealt with a paper we wrote some time ago that is now being processed by a journal. We are on holiday, and while Vladan is busy with some extracurricular activities, Djordje is trying to rest his eyes as much as he can and drops in at CCC only once in a couple of days... Anyway, our paper (A New Approach to Draw Detection by Move Repetition in Computer Chess Programming) can be found at the ACM Computing Research Repository as we wished to make it available to people who might help us improve our ideas regarding draw detection. Therefore the opinions of top chess programmers are very important for us. We have already benefitted much from reading the thread that dealt with some aspects of our paper. We would also like to thank primarily Christophe Theron who grasped our ideas very well and already addressed most of the issues and answered most of the questions that appeared in the thread. Some very brief comments are in order. First of all, we'd like to say that the paper presents the theoretical framework of a novel alogrithm written in assembly that is part of the kernel of our chess program. This project is predominantly academic, but the program plays _real chess_ :-) well and will probably be competitive even against some strong chess engines in the near future. The draw detection algorithm has been tried out both in games against human chess masters and against other engines, and it has shown to be very efficient and fast, practically proving the functionality and usefulness of our new procedure. The idea for the draw detection procedure as described in the paper has evolved from the structure of the Axon chess engine, a machine-assembly searcher, doing over 2 million k/ns on an Athlon XP 2200. To optimise the search we have decided to throw out the propagation of positions along the search tree, so that all the operations are performed over one nucleus. The procedures in search actually have access to only the _last_ position, while the previous positions are not accessible as they are _not_ memorised. On the other hand, we should emphasize that we _do not_ use the 64-bit Zobrist hash key, but a different type of hash (best move hash with a 24-bit key) which cannot be used for draw detection as many different positions can generate the same key. Our experiments have shown that using Zobrist hash in the extender is rather inefficient. To speed up the search, the extender must be «cleansed» as much as possible. We did not specifically mention the Zobrist hash key method in our paper, but on page 4 we did talk generally about the comparison speed-up by way of using hash keys (thus covering the Zobrist method as well). It shouldn't be much of a problem to refer to the Zobrist method specifically, of course. An excerpt fromt the paper (bottom of page 4): "In order to speed up the search a positional checksum (16-bit) can be introduced so that the control checksum should be verified before any comparison of positions. In case the sums do not check out correctly there is no need to investigate complete matrices: they simply have to differ. As a checksum a part of the hash key variable can be used, of course if the program has viable hash support." One more thing. In some cases the slow computation of hash key does not pay off in extended search. It is, of course, well known that the optimisation of the extender is crucial for the efficiency of an engine. Thus, at least in our opinion, the only source of information that can serve as a basis for detecting draws (in all cases) are variant strings. The detection procedure _must_ be implemented in the extender as well because if a repetition has been detected the search needn't evaluate the position further and it needn't expand the tree. The procedure that we described runs correctly in _all_ cases. The castling, ep and promotion questions are not relevant as the draw detector applies _only_ to _reversible_ moves. As it has been shown, the move generator sets a flag in the variant list only if non-reversible moves are in question, so that if in the inverse analysis a move that is not reversible has been found, the procedure is terminated. The procedure has two stages: 1. Deletion of the concatenation list (asm: mov cx,24; xor ax,ax; rep stosw NB.: this is VERY fast!) 2. A single-pass processing of the concatenating list that has 24 integers. While it is being processed the machine register AX stores dynamically the number of the vectors that are not 0, while as soon as AX gets the value of 0 a repetition of moves has been detected. The advantage of this method can be seen especially in positions with a small number of pieces and long checking sequences where the bulk of the processing is done in the first few elements of the concatenating list. The generation and processing of 64-bit Zobrist keys takes a bit of time so we think that our draw detector is better suited for Axon than the classical methods employing the Zobrist keys. So we hope that the algorithm described in the paper will find its place in fast chess programs, especially in cases where the access to draw detection is possible only via variant strings (or similar strings) due to absence of positional keys. BTW, Djordje has already replied to some questions regarding the structure of the 6-byte hash as used in Axon in one of the posts in the Winboard Forum, as a reply to Tord Romstad's (Gothmog) and Rahman Paidar's (Ktulu) questions. Regards, Vladan and Djordje
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.