Author: Roberto Waldteufel
Date: 08:00:47 10/02/98
Go up one level in this thread
On October 01, 1998 at 08:30:18, Robert Hyatt wrote: >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... :) Yes, I never thought about that because I do not have access to multi-processor hardware, but it would be completely useless for parallelism. It seems to work quite well for the serial search, and let's face it, we serial searchers need to squeaze every bit of speed we can out of our single processors if we are ever going to hope to compete with you parallel guys! It's interesting to hear that the list-of-hash-signatures approach is so cheap, even in something as list-hostile as good old Fine #70. Maybe my draw hash table space would be better used for something else.....:-) Roberto
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.