search extensions

[bob]

Hi marco, I'm trying to play with your sentence.

The core idea that if a null search fails low and instead a normal search fails high then there is some 'tension' in the position and it is worth to extend it.

I've just trying to test the idea in the code and these are my first result.

I started count all the time a search end with a fail high if the null move:
1- hasn't been executed
2- has failed low
3- has failed high

those are my result so far for a given set of positions

1- 36%
2- 64%
3- 0%
after some thought it looks the results are ok.


take the case 3, if the nullmove fail high it's very probable you will return without doing the search, so the probability is 0%.

so a fail high can appen only after not having tested the null move at all or after a null move fail-low. it's not a TROUBLESOME position, but a standard position.

this is what I get without adding any new type of search but only counting how many times a fail high appens after the null move fail-low

Don't make the SAME mistake he did. When you enter search with something like alpha=100, beta=101, the null-move search is normally done with the window beta, beta+1, or 101,102 here. The threat extension uses alpha-offset, alpha-offset+1 as the window. I think deep thought (Hsu) ended up using alpha-150, alpha-149 for that threat null-move search. They also used a pawn value of 128 so that 150 needs to be scaled a bit to get a good starting point.

[bob]

I haven't tried these techniques. I do have a variety of extensions, including check, forced check evasions, pawn push, and capture of the last opponent piece.

> There is probably some more interesting things to try to push moves closer
to the front of the move list if they appear to be better

I recently did some experiments with this, for example adding some positional knowledge to the ordering, but surprisingly it performed worse. It does sound intuitively like it ought to work though.

--Jon

It probably needs to be coarse-grained to keep the cost down. All you end up doing (hopefully) is to shift better move to the front so that they are searched deeper.

BTW this series of tests was one of the more interesting I had tried. I generally use a self-test to weed out bad changes quickly, but for some of these tests, self-testing showed improvement, where gauntlet testing shot them down.

I'm sticking with my "extend checks and nothing else" as the check extension was a clear winner in testing, but everything else actually hurt Elo. The old push passed pawns to the 6th or 7th, recapture, etc, not to mention the dynamic extensions such as SE and threat.

[elcabesa]

Don't make the SAME mistake he did. When you enter search with something like alpha=100, beta=101, the null-move search is normally done with the window beta, beta+1, or 101,102 here. The threat extension uses alpha-offset, alpha-offset+1 as the window. I think deep thought (Hsu) ended up using alpha-150, alpha-149 for that threat null-move search. They also used a pawn value of 128 so that 150 needs to be scaled a bit to get a good starting point.

I was just arguing that inside the normal alpha-beta a fail high after a null-move fail low is the NORMAL case and not a troublesome case

[bob]

Don't make the SAME mistake he did. When you enter search with something like alpha=100, beta=101, the null-move search is normally done with the window beta, beta+1, or 101,102 here. The threat extension uses alpha-offset, alpha-offset+1 as the window. I think deep thought (Hsu) ended up using alpha-150, alpha-149 for that threat null-move search. They also used a pawn value of 128 so that 150 needs to be scaled a bit to get a good starting point.

I was just arguing that inside the normal alpha-beta a fail high after a null-move fail low is the NORMAL case and not a troublesome case

Right, IF the null-move search uses the normal window and not a downward offset window. BTW I would not say it is normal. You do a null-move search not knowing whether you are at a CUT or ALL node. If at a CUT node, yes you would expect some move to fail high. If you are at an ALL node, nothing fails high. Whether you have more CUT or ALL nodes depends on the average depth you reach, since CUT and ALL alternate with perfect ordering.

[mcostalba]

Don't make the SAME mistake he did.

Sorry but there is no mistake. I have started with threshold = alpha (test still running and not going bad btw) because is the baseline.

I have already queued up a test with threshold = alpha -100

http://tests.stockfishchess.org/tests/v ... 55a3c87aab

[mcostalba]

Don't make the SAME mistake he did.

Sorry but there is no mistake. I have started with threshold = alpha (test still running and not going bad btw) because is the baseline.

I have already queued up a test with threshold = alpha -100

http://tests.stockfishchess.org/tests/v ... 55a3c87aab

A bit of explanation.

In SF we do null move search only for non-PV nodes and in case of a fail-high we peform a verification search.

I have used the same already exsisting code to:

- Extend null move search also to PV nodes
- In this case we use alpha - <some value> instead of beta as threshold
- In this case we check for a fail-low instead of a fail-high
- In this case if verification search fails-high flag the node to be extended instead of returning

So with reusing the exsisting null search + verification code, the patch tuns out to be very simple.

[pkumar]

When you enter search with something like alpha=100, beta=101, the null-move search is normally done with the window beta, beta+1, or 101,102 here

Are you referring to some other code? The window seems to be 100,101 as per nullmove code in crafty24.1 below:

Code: Select all

      if (depth - tdepth - 1 > 0)
        value =
            -Search(tree, -beta, -beta + 1, Flip(wtm), depth - tdepth - 1,
            ply + 1, 0, NO_NULL);
      else
        value = -Quiesce(tree, -beta, -beta + 1, Flip(wtm), ply + 1, 1);

[elcabesa]

Don't make the SAME mistake he did.

Sorry but there is no mistake. I have started with threshold = alpha (test still running and not going bad btw) because is the baseline.

I have already queued up a test with threshold = alpha -100

http://tests.stockfishchess.org/tests/v ... 55a3c87aab

I'm looking at your patch, let me try to verify if I have understood it.

for PV nodes you do null move verification with a different threshold, if it fail low and verification search fail high -> extend by 1 the first move of the search

[mcostalba]

I'm looking at your patch, let me try to verify if I have understood it.

for PV nodes you do null move verification with a different threshold, if it fail low and verification search fail high -> extend by 1 the first move of the search

Yes, I do this.

[lucasart]

(1) simple singular extensions as found in robbolito/stockfish/who knows what other program. The idea is that (a) a move from the hash table is a candidate singular move. Ignoring a few details, you search every other move (except for the hash move) using an offset window, and if all other moves fail low against that window, this move gets extended. Never thought much of it, and at one point I removed it from Stockfish and my cluster testing (gauntlet NOT self-testing) suggested it was a zero gain/loss idea. I've tested this extensively on Crafty and reached the same conclusion, it doesn't help me at all. When I do self-testing, there were tunings that seemed to gain 5-10 Elo, but when testing against a gauntlet, they were either Elo losing or break-even. I gave up on this.

I also never managed to gain anything by SE in my engine. But in SF the gain is prodigious. More than 20 elo IIRC.

So you are saying that it's only a gain in self-play and just break-even against foreign opponents? I've heard so many claims like that, of patches than behave differently against foreign opponents than in self-play, but never seen any evidence myself.

It would be remarkable if this claim is correct. And would certainly question our whole SF testing methodology!