qsearch testing

[bob]

I have been experimenting with qsearch options for a while now and thought I would relay my results. note that they may or may not apply to other programs, as there are lots of variables to consider.

I first discovered that adding one layer of checks to the qsearch had a +very+ small effect on Crafty's results in cluster testing. So small it took on the order of 100K games to get a hint that it might barely be better.

Before giving up, I decided to try null-move R=3, rather than the adaptive R=2~3 I have been using for many years. The adaptive idea came from John Stanback on R.G.C.C around 1995 or so and was one way of addressing catastrophic null-move failures where you could be faced with a mate in 1, but by playing a null-move you collapsed the remainder of the search depth to zero and dropped into the q-search which would not spot the mate. But with the layer of checks added on the first ply of q-checks, this particular problem went away. And as a result, R=3 was 4-5 Elo better than R=2~3. So we now had about 5 Elo "in our pocket" and I released this version.

I should add that this code was fairly efficient. I first try SEE >= 0 captures first, before dealing with checks, since a capture is good enough to refute most leaf nodes already. If the SEE >= 0 captures don't do anything, I then explicitly generate non-capturing moves that deliver check and try those. At this level in the tree first ply where depth == 0, any move that checks the opponent produces a full-width "check evasions" search at the next ply where I use the GenerateCheckEvasions() code in crafty that is basically a legal-move generator so that I can discover if the check was actually a checkmate. It did not have a significant increase on total tree size, and with the +5 Elo gain, I considered it marginally worthwhile.

I have been experimenting with this same approach except extending it another layer or two or three. I first found that another layer of checks would speed up tactical solutions quite a bit, but the overall Elo dropped by over 20. The default qchecks=1 was the best, qchecks=2 (two in a row) was worse by about 10, qchecks=3 was worse by about 20 and I didn't bother testing 3.

The only requirement when qchecks was > 1 was that the checks had to be in a sequence so there was no option to stand pat which would make forcing a mate impossible. With qchecks=2, if the first qsearch move was not a check, then two plies deeper checks would not be tried. So this was a bust.

I then tried various ways of restricting when the extra checks were tried. For example, requiring that the last normal-search move had to be a check. Or the last 2 normal-search moves had to be checks. Or the last normal search check had to be a non-capturing check... All had no effect in eliminating that 10-20 elo loss. So the code was dumped and I am back to doing one level of checks.

Another note is that the 10-20 elo was on _very_ fast games. I started a test with 1+1 games instead, but the loss stretched out to -35 for one extra layer of q-search checks, where the gain for just one layer was very slightly higher. I did not try more than 2 layers in the longer tests since 2 convinced me it wasn't working.

As always, YMMV. These tests produced about 2,000,000 games at about 32,000 games per hour.

[bob]

BTW I forgot to add that this has been one of several cases where what appears to be a good idea turns into a waste of time. I doubt it will be the last. But there are more ideas waiting to be tested.

[Steve Maughan]

Bob,

Interesting.

Another idea worth trying may be to restrict checks in the qsearch to nodes where the null move calls the qsearch. So if after the null move reduction the depth <= 0 do a qsearch with checks. However, if the qsearch is reached normally (i.e. after a normal move and depth <= 0) then do a qsearch without checks.

The logic here is that checks are effective for preventing some horizon problems with null move threats. However the vast majority of qsearches are reached simply because depth <= 0 and the checks are of less interest for these nodes.

I'd be interested in seeing any results.

Cheers,

Steve

[gladius]

Thanks for the interesting information! It's quite interesting how these improvements can easily fall off a cliff into ELO loss, but it's super hard to even gain a few ELO.

[bob]

Thanks for the interesting information! It's quite interesting how these improvements can easily fall off a cliff into ELO loss, but it's super hard to even gain a few ELO.

In recent testing, even tiny changes have cost me 20 Elo. It is much harder to find a tiny change that adds 20 however.

[bob]

Bob,

Interesting.

Another idea worth trying may be to restrict checks in the qsearch to nodes where the null move calls the qsearch. So if after the null move reduction the depth <= 0 do a qsearch with checks. However, if the qsearch is reached normally (i.e. after a normal move and depth <= 0) then do a qsearch without checks.

The logic here is that checks are effective for preventing some horizon problems with null move threats. However the vast majority of qsearches are reached simply because depth <= 0 and the checks are of less interest for these nodes.

I'd be interested in seeing any results.

Cheers,

Steve

I actually tried two variations of that.

1. always do one "layer" of checks, but if the last normal-search move was a null-move, add on the "extra layers". still hurt overall rating.

2. only try qchecks after nulls, but not after normal moves. This was still a gain over no q-hecks, but not as big a gain as with qchecks everywhere.

There are a couple of places where this might be attributed to other things, however. For example, in normal q-search I do not check for repetitions, which means the last move in the regular search might be a repetition or 50-move draw and I would not see it. Now, with the qchecks I check for repetitions in the first layer always, and if I follow a check to the next level, I check for draws there as well. So it is possible that part of the "qcheck" improvement came from the extra level of repetition checks. I have not tested that however, and don't really plan to unless I start fiddling around with qchecks again for some reason.