Author: Uri Blass
Date: 04:44:46 10/17/02
Go up one level in this thread
On October 17, 2002 at 07:19:12, Vladimir Medvedev wrote: >I use the following method in my program: > >1. Hashkey (__int64 number) is part of position structure, it is recalculated >after each move. The same for me. > >2. I do not store history of hashkeys in some hash_history[MAX_GAME_LENGTH] >array and check all 0...current_ply entries in this array to detect repetition. I did not think to search all history (I have a fifty varaible that tell me exactly the number of moves that may be relevant that is always less than 49(only positions with the same side to move and the last position is not relevant do the relevant positions are 4 plies before the board position,6 plies before,...98 plies before(100 plies before is irrelevant in case that there is no draw by the 50 move rule). > >Instead, I have two arrays, int SearchRepetitions[REP_SIZE] and int >HistoryRepetitions[REP_SIZE], where REP_SIZE = 100000...500000 (maybe, less >values are possible too). After each MakeMove I increment corresponding elements >in these arrays: > >SearchRepetitions[ pos.Hash % REP_HASH_SIZE ]++; >or >HistoryRepetitions[ pos.Hash % REP_HASH_SIZE ]++; This seems risky to me. I may believe in the search that a line leads to repetition when it does not lead to repetition and I am afraid that it may happen more often at longer time control. > >3. And don't forget to decrement: > >SearchRepetitions[ pos.Hash % REP_HASH_SIZE ]--; >after UnmakeMove(). > >4. Then simply check whether SearchRepetitions != 2 or HistoryRepetitions !=3. > >Of course, this method is theoretically incorrect, and hash collisions can >result in false draw-by-repetition detection. But the probability is very small, >I think - much less than probability of Windows crashing while series of games >:) I can take risks but this risk seems too much for me. I think that everybody who use hash tables to prune the tree or to detect repetition takes risk but the risk is going to be that 2 position get the same 64 bit number. The risk that 2 positions get the same pos.Hash % REP_HASH_SIZE seems too big for me. risk of 1/500000 in wrong repetition detection is not something that I agree to accept. I may use your idea to suspect if there is a repetition but if the answer is yes I need to do another check and compare the 64 bit number to the previous numbers. Your idea is good only to detect in a fast way that there is no repetition but if the array tells me that there is a repetition I need to do another check. If I consider the fact that in 99.9% of the cases there is no repetition that it is a good idea but not in the way that you use it. Uri
This page took 0 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.