next singular extension test

[bob]

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.

I agree. But it seemed worth testing as this sends a singular test into a different set of possible hash signatures so that _nothing_ gets overwritten. Of course nothing from outside that specific singular search gets used, either.

[Ralph Stoesser]

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.

Maybe it's enough to xor in the exclusion key for the first level child nodes of an exclusion search.

Code: Select all

excludedMove = ss->excludedMove;
posKey = excludedMove || (ss-1)->excludedMove ? pos.get_exclusion_key() : pos.get_key();

// ss->excludedMove must be initialized to MOVE_NONE in root_search()

Seems to play a little better than default (at 1+0), but not yet enough games.

[bob]

So far, nothing has produced an Elo jump in this second approach, either. I have a couple of versions that are "as good as" but nothing that is "better than" the default 23.4 version. I am once again going to save this version in case I think of more ideas, but after about 50 30,000 game tests, I am currently out of ideas. Time to start looking at the "real SE" approach as defined by Hsu and Campbell...

[Ralph Stoesser]

Code: Select all

excludedMove = ss->excludedMove;
posKey = excludedMove || (ss-1)->excludedMove ? pos.get_exclusion_key() : pos.get_key();

// ss->excludedMove must be initialized to MOVE_NONE in root_search()

Seems to play a little better than default (at 1+0), but not yet enough games.

+213, -185, =602 in favor to throw the first level children into the exclusion search pool.

Match pathway was quiet, no ups and downs. Tested with old Athlon 2,4GHz, 1 thread, TC 1+0. Not sure whether the result would hold if the test would be repeated on much faster hardware though.

[mcostalba]

Code: Select all

excludedMove = ss->excludedMove;
posKey = excludedMove || (ss-1)->excludedMove ? pos.get_exclusion_key() : pos.get_key();

// ss->excludedMove must be initialized to MOVE_NONE in root_search()

Seems to play a little better than default (at 1+0), but not yet enough games.

+213, -185, =602 in favor to throw the first level children into the exclusion search pool.

Match pathway was quiet, no ups and downs. Tested with old Athlon 2,4GHz, 1 thread, TC 1+0. Not sure whether the result would hold if the test would be repeated on much faster hardware though.

Thanks, I will put this in my test queue for a verification.

[Ralph Stoesser]

Code: Select all

excludedMove = ss->excludedMove;
posKey = excludedMove || (ss-1)->excludedMove ? pos.get_exclusion_key() : pos.get_key();

// ss->excludedMove must be initialized to MOVE_NONE in root_search()

Seems to play a little better than default (at 1+0), but not yet enough games.

+213, -185, =602 in favor to throw the first level children into the exclusion search pool.

Match pathway was quiet, no ups and downs. Tested with old Athlon 2,4GHz, 1 thread, TC 1+0. Not sure whether the result would hold if the test would be repeated on much faster hardware though.

Thanks, I will put this in my test queue for a verification.

If there is an Elo gain, then the reason is probably that there are fewer SE extensions in a search line than before. After this change the child nodes of an exclusion node retrieve their ttMove from the pool of exclusion TT entries and that pool is much smaller than the non-exclusion pool. Therefore the chance for those child nodes to retrieve an appropriate TT entry for SE is much smaller.

I think the net effect of this change is something like "no SE-extension on SE-extension child nodes", similar to the null move condition. But then, the appropriate code change should look a little differently...

This SE extension stuff is rather complicated.

Now waiting for the Hsu/Campbell implemetation from Bob.

[mcostalba]

I think the net effect of this change is something like "no SE-extension on SE-extension child nodes", similar to the null move condition. But then, the appropriate code change should look a little differently...

But this should be already taken care of by the non recursive condition here:

Code: Select all

    singularExtensionNode =   depth >= SingularExtensionDepth[PvNode]
                           && tte
                           && tte->move()
                           && !excludedMove // Do not allow recursive singular extension search
                           && is_lower_bound(tte->type())
                           && tte->depth() >= depth - 3 * OnePly;

[Mangar]

Hi,

some engines set the search window on next depth to value-of-last-depth +/- window. Thus in pv alpha = value_of_last_depth - window and beta = value_of_last_depth + window. The expected value the search will return in pv-nodes is then alpha + (beta - alpha) / 2.
If window is small, then alpha will be near the expected value. If the window is large you´ll get no singular extension even if there is only one good move als alpha is far below the expected value.

Maybe you can use value_of_last_depth as test for singularity in pv nodes. This will not depend on window-size and -symetrie and is stable on research. If singular extension will result in a fail low at root the research with larger window may result in not doing singular extension any longer if using alpha. This will make the effect of singular extension rather random at pv nodes. Hash will not solve the problem (at least in spike).

Greetings Volker

[mcostalba]

If window is small, then alpha will be near the expected value. If the window is large you´ll get no singular extension even if there is only one good move als alpha is far below the expected value.

Hi Volker,

thanks, this is a good observation. What do you mean with "value_of_last_depth" ? Do you mean value of last iteration of the iterative deepening loop ?


Another point is that we don't use alpha or beta as reference for the singular extension. We use the value of the TT, doesn't matter how far from alpha it is. The rationale is that SE is a local property, I explain myself better.

The target of SE search is to find if in a given position one move (the TT move) is much better then the remaining ones. In this picture current alpha, beta values don't matter at all. What is important is the _relative_ distance between the score of the best move (and for this we use the TT to get an approximation) and that of the remaining ones.

[Mangar]

Hi Marco,

yes I ment value of last iteration of the iterative deepening loop. It was ment as a reply to bob. Earlier I suggested to use alpha + (beta - alpha)/2 instead to alpha for his current implementaiton of SE.

In your implementation you´ve got the same problem. If SE causes a fail low in pv node your research will not use SE. The fail low is stored in TT as "less_or_equal_value" and thus will not be used for SE in fail-low-research.

Haven´t tried it yet but using "value of last iteration of iterative deepening loop" in pv seems more stable.

Greetings Volker