Repetition detection structure.

[Uri Blass]

I already explained how I would handle SMP. So why should I explain it gain. Just read it again? And this time, first look up in one of the many books you can cite what 'split point' means... So that any comments you would feel compelled to make can be to the point, in stead of irrelevant rants.

So in your tree there is on the average only about one move in the table? Well, that still would be a factor 2, as you would have to look at the entry to conclude the miss, and then do a test to conclude that you are done. I conclude that I am done in 99% of the cases immediately, as I hash to an empty table entry.

So it seems that things still as they were from the very beginning: writing hashKey&255 for the initializer of the for-loop in stead of 0 doesn't take me more than half a minute, and the fully-functional hash code I get from this then offers a speeds improvement of about a factor 2...

Oh, and in your scheme, wouldn't you have to keep an administration of where to start or end the linear search, where the last irreversible move was done (or how many ply ago)? If so many of your moves is irreversible, you have to do that a lot... And of course you would have to undo that on UnMake (or copy discard). and that would either involve branches (which can be mispredicted), or dummy operations that you also did on reversible moves.

If I understand your post correctly it seems to me that you do not have fifty move rule variable to tell you the number of moves with no conversion so you cannot detect draw by the 50 move rule(otherwise you have the same problem that you mention that Bob has in his scheme)

Note that I believe that most programmers use the same scheme as Bob.

Uri

[hgm]

If you can do that many useful optimizations in an hour, then gaining 7.5% that way might make sense.

On the other hand, if there's a routine taking 4.6% of the total, maybe its worth more attention than a routine taking only 0.5%?

That depends. If that routine contains 100x more code, all executed on every call, it would be very tough going to get significant reduction of it.

No matter what Bob got from his favorite books, fact is that the way code lines are distributed over the routines that you profile is completely irrelevant. This makes profiles such as presented here by Bob pretty useless. What would be relevant is a breakdown of execution time code line by code line, or code section by code section for approximately equally-sized sections.

And even then, it is just as important how amenable the code is to improvement as how much time it consumes. Hash probes take a significant fraction of the time in my engine (I also probe in QS). But no matter how much I work on the code, I couldn't make it any faster, as it is purely limited by memory access time.

There are some unfortunate classes of software where *everything* takes like 0.5 - 1.0%, and then we have no choice but to try and optimize them all one by one---even if each one takes weeks rather than minutes. ("Uniformly slow code"). That doesn't appear to be the case here though. Optimizing the top 10 things in bob's list is probably a better use of the time.

This is exactly my point. Number 1 in Bob's list, 'Evaluate', is exactly of that type _within_ the routine. It will not be possible to gain much on it, and even if it is possible, it will involve an enormous amount of work. So the list is _very_ misleading.

[hgm]

If I understand your post correctly it seems to me that you do not have fifty move rule variable to tell you the number of moves with no conversion so you cannot detect draw by the 50 move rule(otherwise you have the same problem that you mention that Bob has in his scheme)

This is correct. I found that paying attention to 50-move draws in the evaluation only causes a drop in Elo. (More often than not, the engine avoids the draw by sacrificing a Pawn, after which it loses.) So I only account for it at game level, to claim such draws, and to switch to an evaluation that awards pawn pushing more when the draw gets near and it thinks it is ahead.

[Uri Blass]

If I understand your post correctly it seems to me that you do not have fifty move rule variable to tell you the number of moves with no conversion so you cannot detect draw by the 50 move rule(otherwise you have the same problem that you mention that Bob has in his scheme)

This is correct. I found that paying attention to 50-move draws in the evaluation only causes a drop in Elo. (More often than not, the engine avoids the draw by sacrificing a Pawn, after which it loses.) So I only account for it at game level, to claim such draws, and to switch to an evaluation that awards pawn pushing more when the draw gets near and it thinks it is ahead.

I think that the correct conclusion based on your experience is to improve your evaluation.

There are cases when it is obvious that sacrificing a pawn does not lose when there are chances that it can win and you do not want to miss wins in these cases.

Uri

[hgm]

If it was obvious to the evaluation that a pawn can be sacrificed to improve winning prospects, it wouldn't have taken 50 moves to discover it. So there still would be no reason to pay attention to the 50-move rule.

The only thing that evaluating 50-move draws can achieve is that the engine will start to make sacrifices that it thinks make its position worse, to avoid the draw. The others it will make spontaneously long before the 50-move curtain falls. With a very accurate evaluation making such sacrifices is an even worse idea than with a poor evaluation.

Evaluations (even poor ones) usually evaluate the difference between two related positions more accurately than their absolute evaluation.

[Uri Blass]

If it was obvious to the evaluation that a pawn can be sacrificed to improve winning prospects, it wouldn't have taken 50 moves to discover it. So there still would be no reason to pay attention to the 50-move rule.

The only thing that evaluating 50-move draws can achieve is that the engine will start to make sacrifices that it thinks make its position worse, to avoid the draw. The others it will make spontaneously long before the 50-move curtain falls. With a very accurate evaluation making such sacrifices is an even worse idea than with a poor evaluation.

Evaluations (even poor ones) usually evaluate the difference between two related positions more accurately than their absolute evaluation.

I disagree with your theory
You can decide not to trust sacrifices with small positive evaluation but at least you should trust sacrifices with big positive evaluation.

There are cases when sacrifices that the program does not understand is the only way to win.

Uri

[hgm]

Yes, there are cases when a sacrifice the program doesn't understand is the only way to win. But that does not imply that it is a good idea to try random sacrifices.

In practice, making the program more eager to push Pawns turns out a much better remedy against indecisiveness than making the program more eager to cause captures. That a perfect evaluation would not need either mechanism is a moot point.

[mathmoi]

Yes, it's certainly possible to use a hashtable for doing rep-draw detection. I'm not certain whether it would be faster or slower than just checking until the last non-reversible move, but my suspicion is that it doesn't matter too much, even in the endgame.

Hi Gary,

Thanks for the infos and the code. However since everyone seems to agree that it won't make a difference, i'll use a list for now, since that is simpler.

[mathmoi]

A hash table is doable, but there is an efficiency issue. When you start a node, you have to enter the position, then when you leave the node, you have to remove the position. There are other sticky issues dealing with SMP search, in the repetition hash table has to be a reasonable size to prevent overwriting which would be fatal, and it has to somehow handle an SMP search which makes duplicating it expensive...

repetition list scanning is not a big issue, once you profile an engine to see how little time it actually spends in there, particularly since you don't even probe it in q-search...

Hi M.Hyatt,

Thanks for the input. I did implement a position list, since data you presented elsewhere in the thread seems to indicate there is not much to gain in using a hashtable.

[bob]

I already explained how I would handle SMP. So why should I explain it gain. Just read it again? And this time, first look up in one of the many books you can cite what 'split point' means... So that any comments you would feel compelled to make can be to the point, in stead of irrelevant rants.

Ever consider that perhaps your idea will _not_ work? If you aren't willing to listen, blunder ahead until you see the light...

So in your tree there is on the average only about one move in the table? Well, that still would be a factor 2, as you would have to look at the entry to conclude the miss, and then do a test to conclude that you are done. I conclude that I am done in 99% of the cases immediately, as I hash to an empty table entry.

You hash to a zero entry. I execute a loop one iteration. And your approach is supposedly faster? Please think again. How do you know your entry is zero? Perhaps a comparison? I do a single comparison to determine that the hash signature does not match the table entry. A single comparison is a single comparison. And I don't have to do a store to zero the entry when I exit, I just use a counter that is decremented for other reasons so there is no cost in doing it associated with repetitions.

So it seems that things still as they were from the very beginning: writing hashKey&255 for the initializer of the for-loop in stead of 0 doesn't take me more than half a minute, and the fully-functional hash code I get from this then offers a speeds improvement of about a factor 2...

You are still waving your hands and dismissing the store at the end of a node to clear that entry from the hash table. So you are doing 2x what you claim you are doing, which is now no faster than what I do up front. So exactly how are you faster? Answer: you aren't...

Oh, and in your scheme, wouldn't you have to keep an administration of where to start or end the linear search, where the last irreversible move was done (or how many ply ago)? If so many of your moves is irreversible, you have to do that a lot... And of course you would have to undo that on UnMake (or copy discard). and that would either involve branches (which can be mispredicted), or dummy operations that you also did on reversible moves.

I don't have to do that in my implementation already. Because I have a requirement to keep a 50 move rule counter. And that counter tells me how far backward to look thru the repetition list. So again, no overhead, just reusing existing data... since I have to correctly maintain the 50-move counter anyway...