Author: Robert Hyatt
Date: 05:30:18 10/01/98
Go up one level in this thread
On October 01, 1998 at 07:58:57, Roberto Waldteufel wrote: > >On October 01, 1998 at 03:18:58, Bruce Moreland wrote: > >> >>On October 01, 1998 at 00:25:44, James Robertson wrote: >> >>>How do programs detect draws by repetition in a search? I can think of many >>>possible ways, but they all seem really slow. How do most programs quickly >>>detect draws by repetition? >> >>You have a hash key. You have a transposition table. >> >>1) You can set a flag in your transposition table when you enter a node, and >>clear it when you leave the node. If you encounter a flag that's already set, >>it's a rep draw. You have to be careful not to kill your hash entry somehow, >>there is tremendous potential for bugs. >> >>2) You can make a new hash table, a small one, and store the hash key in that >>when you enter a node, and clear it when you leave. >> >>3) You can create a list of hash keys that represent positions that have >>occurred between now and between the capture or pawn move, and iterate. This >>isn't as slow as it sounds, for reasons that I don't understand, but it may get >>really bad in some pathological cases such as when you are near a 50-move draw. >> >>You have to be careful to take into account the en-passant square and the >>castling flags in some circumstances. >> >>Without castling and en-passant, chess would be a lot simpler to program. >> >>You will get bugs no matter what you do. >> >>bruce > >Hi Bruce, > >I use method 2, except I am a bit extravagent in the size, and make my draw >table with the same number of entries as the other tables, so I can access it >faster by not needing to mask any bits off the hash key or maintain a second key >separately. This means that my draw table is very sparse, but it is probed so >many times during the search that I wanted to make it as fast as possible, so >using the same key made some sense to me. I switched to this from method 1 after >encountering all sorts of problems with erased entries and hash collisions etc. > >The only problem I have encountered with method 2 is that draws correctly >identified by the draw hash table will have an adverse affect on the scores of >ancestor nodes in the tree when they are entered into the transposition table >later on, and so a later hit on one of these ancestor nodes may give misleading >information. I don't really see a way to avoid this - it seems at least to be a >rare event. > >Best wishes >Roberto also note that this fails completely when you do a parallel search, because each thread can find positions entered by the other thread, and conclude "draw" when it isn't. And you can't mark positions with a thread ID because this can also be a legitimate draw in other cases... If you don't plan on a parallel search, this works well. If you do... plan on a rewrite... :)
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.