Author: Robert Hyatt
Date: 14:19:03 12/22/05
Go up one level in this thread
On December 22, 2005 at 16:17:57, Stuart Cracraft wrote: >On December 22, 2005 at 12:43:40, Robert Hyatt wrote: > >>On December 21, 2005 at 15:48:36, Frederik Tack wrote: >> >>>On December 20, 2005 at 20:30:41, Robert Hyatt wrote: >>> >>>>On December 20, 2005 at 17:11:41, Frederik Tack wrote: >>>> >>>>>I'm looking for the best way to implement a repetition detection in the search >>>>>tree for my engine without loosing performance. >>>>> >>>>>I've found some articles on the internet suggesting to create a repetition table >>>>>using zobristkeys. I have now implemented this and it works fine, but i've lost >>>>>about 10% performance. >>>>> >>>>>I have now come up with a new idea that should have no impact on performance. >>>>>However, i'm not sure if what i'm about to do is completely correct. Here's the >>>>>idea. Before starting the analysis, i store every position i've had on the board >>>>>from the move history in the transposition table with an evaluation of 0 and a >>>>>depth of maxdepth + 1. During the analysis, i use a replacement scheme in the >>>>>transposition table that will not replace the position if the depth in the tree >>>>>is smaller than depth in the table. Since i've stored the historic positions >>>>>with maxdepth + 1, they will never get replaced. This should score every >>>>>position that has been on the board before with a draw score. >>>>> >>>>>The fact is i haven't found any article on the internet discussing this way of >>>>>working, so i fear it may have some drawbacks i'm not aware of. Has any1 tried >>>>>implementing repetition detection this way or has any1 an idea why this wouldn't >>>>>work? >>>> >>>> >>>>There are issues, but several have used this approach. Bruce Moreland (Ferret) >>>>uses a separate table, but hashes it just like normal. Problem is that the old >>>>positions are a tiny part of the problem. The real problem is positions reached >>>>during the current search. >>>> >>>>The solution to this is that each time you reach a new position, you have to >>>>store the position in the table if it is not already there. If it is, increment >>>>a counter so you can tell whether it is a 2nd or 3rd repetition later. >>>> Then as >>>>you unmake that move, you have to decrement the counter and if it goes to zero, >>>>remove the entry. This becomes time-consuming itself. >>> >>>I could try and do the detection just after making the move like you suggest >>>instead of doing the detection at the beginning of my negamax function. That >>>would indeed improve performance. >>>tx for the advice. >>> >>>> And then when you get >>>>ready to parallelize your search, you have to handle the problem of replicating >>>>this stuff since positions from one search can not possibly repeat positions >>>>from another part of the search every time. If you get a hit on a position >>>>stored from another branch of the parallel search, it isn't a draw at all. This >>>>takes some effort to handle, usually replicating the table or else storing a >>>>"thread ID" for each entry. >>>> >>>>The list is just as good, and if you use the 50-move counter to limit how far >>>>back you search the list, the performance loss is not that bad... >> >> >>The main point was that if you store a position in this "repetition hash table" >>when you reach it in the search, you have to remove it from the table when you >>back up the tree and unmake the move that led to this position. Otherwise you >>get lots of false matches. This has some overhead, because now _every_ node >>requires an add and remove operation for this table. The repetition list >>eliminates the "remove operation"... > > >Why bother with this kind of approach? > >Keeping simply the game history list with each item having >the hash representing the position at that time >and scanning backwards to see if the current position being >tested for 3-time-repetition is in that list N times seems >a better solution. > >Am I missing something? Why all the complexity? > >Stuart Several reasons. If you don't do the "2 times is a draw" trick, you will miss a great many repetitions that are simply too deep to see in a normal search, even though you noticed the second repetition easily enough. So that is a problem. Second, the twice in the history once in the search solves a problem that step one above might hit. The second repetition is _not_ a draw, and scoring it as such can turn a win into a draw. For example, suppose you try chasing the king one way only to discover that it can "get back" to the original position. But if you play on, and force him the other way, now you can win. But if you take the second repetition as a draw, you will not search through it to see the win. That's the reason for the complexity. I want to recognize the most repetitions possible, without overlooking something possibly better. There are other more subtle reasons, such as not having a ponder move if the first search move is a two-fold repetition, yet you have to continue playing. This solves that.
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.