next singular extension test

[mcostalba]

Or you don't overwrite them because of depth vs draft???

We always overwrite.

I am not sure you have understood what Joona said......

[zamar]

Or you don't overwrite them because of depth vs draft???

Last time I looked Crafty was in "always overwrite" mode when dealing with TT (meaning entry from new iteration _always_ overwrites entry from older iteration). Has this been changed?

[Ralph Stoesser]

I guess this depends on implementation. I don't do the SE search until I have tried everything else. Hash probe, repetition check, even null-move search. However, the TT is an issue in all searches, since it introduces some interesting side effects. I just ignore 'em. Some go to extremes, from not storing mate scores to not storing draw scores. Doesn't solve all the problems so it seems like a waste of time.

I'm not talking about TT Entry of current node, but if you for example do SE search with depth = 5, you spoil all child node entries up to that depth. Sounds pretty bad thing for me. The beauty of the relaxed SE extension is that by excluding the likely main move from SE search we preserve the most valuable child node entries.

Not sure I understand your point regarding SF's relaxed SE correctly. Is the following right?

In the exclusion search you xor the special exclusion key into the search chain. All child node position keys have that exclusion key xor'd in, therefore all non-exclusion child node entries should be preserved from beeing overwritten, not only the most valuable ones. But, as soon as you xor in the exclusion key again, while beeing in an exclusion subtree, the exclusion key get cleared, and now you could again overwrite valuable non-exclusion child nodes.

[zamar]

Not sure I understand your point regarding SF's relaxed SE correctly. Is the following right?

No, what you describe was indeed one possibility of implementing this SE thing, but you didn't note that special exclusion key is used only in SE node, it's not xorred to the actual position key, so it has no effect to children nodes.

This is because in perfectly ordered tree, in cut node, it's only necessary to examine the first move. Relaxed exclusion search examines all the other moves. So with great probability the search trees do not overlap too heavily.

The only exceptions are the PV nodes and it's possible that indeed bad things happens there in SF. Perhaps we could improve by XORring the exclusion key also to the position key, haven't tested it. It's somewhere down in my TODO list (actually more fine tuned approach than single key would be needed for the optimal solution)

[mcostalba]

Perhaps we could improve by XORring the exclusion key also to the position key, haven't tested it. It's somewhere down in my TODO list (actually more fine tuned approach than single key would be needed for the optimal solution)

With a single SE key we could have collisions with normal positions as Ralph explained before: through the double xoring of the grand-childs.

An alternative could be to xor the position with itself (reversed) in case of SE, so to always have different sub-sets of hashes for SE and for normal searches.

Or to use an array of 2^n keys that have the last n bits set to 0 so that the last n bits of the position hash can index the array and are not changed by the xor itself. This is important for the operation to be reversible.

[bob]

Or you don't overwrite them because of depth vs draft???

We always overwrite.

I am not sure you have understood what Joona said......

I've looked at the SF code, and I can only think of one definition for "destroy _child_ nodes". At the ply where I do the sing test, I do not write any hash entry at all. At plies below the sing test ply, I'd think that if there was good stuff there, I'd get quick cutoffs anyway since the depth of the singular test is so reduced.

[bob]

Or you don't overwrite them because of depth vs draft???

Last time I looked Crafty was in "always overwrite" mode when dealing with TT (meaning entry from new iteration _always_ overwrites entry from older iteration). Has this been changed?

Yes and no. I have a version that uses depth-preferred from an earlier singular test. In tests, it made absolutely no difference, however. I even tried another kludge of passing a flag saying "doing singular search" so that nodes below that point in the tree would not overwrite, either. No benefit at all. Even went to the extent of mangling the hash signature below the singular node, but that seemed like a horrible idea, to give up all the potentially useful hash hits that might happen down in the singular search. That idea failed pretty miserably early on so I tried the other things mentioned.

The only trick I use in the current tests is that I do not use Search() to perform the singular test, I have a separate piece of code since I don't need to do anything bug iterate over the moves, don't need to hash probe, check for repetitions, nor do a null-move search. As a result, this code also does not store a hash entry either, at the ply where the singular test is done.

I'm trying to test every reasonable option as I go thru this stuff, since some of these same issues have surfaced in the past. Seemed like a good time to test all hypotheses as I'd like to put this stuff to rest, once and for all....

[bob]

Perhaps we could improve by XORring the exclusion key also to the position key, haven't tested it. It's somewhere down in my TODO list (actually more fine tuned approach than single key would be needed for the optimal solution)

With a single SE key we could have collisions with normal positions as Ralph explained before: through the double xoring of the grand-childs.

An alternative could be to xor the position with itself (reversed) in case of SE, so to always have different sub-sets of hashes for SE and for normal searches.

Or to use an array of 2^n keys that have the last n bits set to 0 so that the last n bits of the position hash can index the array and are not changed by the xor itself. This is important for the operation to be reversible.

I did one test of this idea with an array singular_random[ply] so that when recursive singular tests are done, you mangle, and mangle again the hash signature. Killed efficiency however as once you mangle the real hash key, you lose all move ordering and cutoffs that the hash table normally provides.

[mcostalba]

I did one test of this idea with an array singular_random[ply] so that when recursive singular tests are done, you mangle, and mangle again the hash signature. Killed efficiency however as once you mangle the real hash key, you lose all move ordering and cutoffs that the hash table normally provides.

Indexing by ply as in singular_random[ply] seems wrong to me because you don't preserve the results of the previuos moves during the game.

[Ralph Stoesser]

Not sure I understand your point regarding SF's relaxed SE correctly. Is the following right?

No, what you describe was indeed one possibility of implementing this SE thing, but you didn't note that special exclusion key is used only in SE node, it's not xorred to the actual position key, so it has no effect to children nodes.

This is because in perfectly ordered tree, in cut node, it's only necessary to examine the first move. Relaxed exclusion search examines all the other moves. So with great probability the search trees do not overlap too heavily.

The only exceptions are the PV nodes and it's possible that indeed bad things happens there in SF. Perhaps we could improve by XORring the exclusion key also to the position key, haven't tested it. It's somewhere down in my TODO list (actually more fine tuned approach than single key would be needed for the optimal solution)

Ok, understand now. Thanks for the clarification.