A way to improve PVS

[Sergei Markoff]

Since a long time ago I'm using in SmarThink 1-centipawn aspiration window for the first root move.

result =-Search(-eval[0] - 1, -eval[0] + 1, depth);

The main idea of doing it -- there are a lot of cases where the eval is the same on the consequent iterations (draw, a lot of endgame positions and so on). At practice this technique works with zero effort -- there are no siginificant difference in playing strength between 1/cw version and classic aspiration with 0,2 pawn window.

Anyway, there is a way to provide more fine approximation of the search result. There are a lot of positions where first n PV moves are the same at the consequent iterations. Let we are ready to start next, Xth iteration at the root (with depth = X) and we have PV from the previous iteration. We can get the position after first K moves in PV and do for this position a search with depth X - K with relatively wide window. The result of this search we can use as the approximation of the full search result. So we can now start search with 1/cw.

MakeMovesFromPV(K);
approx = (K & 1) ? -Search(-eval[0] - ASPIRATION_WINDOW, -eval[0] + ASPIRATION_WINDOW, depth - K) : Search(eval[0] - ASPIRATION_WINDOW, eval[0] + ASPIRATION_WINDOW, depth - K);
UnmakeMovesFromPV(K);
result = -Search(-approx - 1, -approx + 1, depth);

This will provide the best cut-off in the cases where the search will keep first K moves in PV.

If you're interested with this tech please send me your further results
It is interestring how much it can help and also how to determine optimal K value.

[bob]

Since a long time ago I'm using in SmarThink 1-centipawn aspiration window for the first root move.

result =-Search(-eval[0] - 1, -eval[0] + 1, depth);

The main idea of doing it -- there are a lot of cases where the eval is the same on the consequent iterations (draw, a lot of endgame positions and so on). At practice this technique works with zero effort -- there are no siginificant difference in playing strength between 1/cw version and classic aspiration with 0,2 pawn window.

This begs the question, "why do it?" The only point for changing anything is to improve the strength. No improvement changes just add code, complexity, and potential bugs or unexpected side-effects...

Anyway, there is a way to provide more fine approximation of the search result. There are a lot of positions where first n PV moves are the same at the consequent iterations. Let we are ready to start next, Xth iteration at the root (with depth = X) and we have PV from the previous iteration. We can get the position after first K moves in PV and do for this position a search with depth X - K with relatively wide window. The result of this search we can use as the approximation of the full search result. So we can now start search with 1/cw.

MakeMovesFromPV(K);
approx = (K & 1) ? -Search(-eval[0] - ASPIRATION_WINDOW, -eval[0] + ASPIRATION_WINDOW, depth - K) : Search(eval[0] - ASPIRATION_WINDOW, eval[0] + ASPIRATION_WINDOW, depth - K);
UnmakeMovesFromPV(K);
result = -Search(-approx - 1, -approx + 1, depth);

This will provide the best cut-off in the cases where the search will keep first K moves in PV.

If you're interested with this tech please send me your further results
It is interestring how much it can help and also how to determine optimal K value.

[Sergei Markoff]

This begs the question, "why do it?" The only point for changing anything is to improve the strength. No improvement changes just add code, complexity, and potential bugs or unexpected side-effects...

I'm simply misevaluated this tech a years ago. Now I made a more careful testing that proved that it can't really help. But in other hand the removal of this code also can't help me. So, I'm planning to experiment with idea described in my post -- may be it will help. The only reason to keep 1cp-width search is that it provides early info about eval change direction which can be useful for deep positional analyse performed by human chess players.

[bob]

This begs the question, "why do it?" The only point for changing anything is to improve the strength. No improvement changes just add code, complexity, and potential bugs or unexpected side-effects...

I'm simply misevaluated this tech a years ago. Now I made a more careful testing that proved that it can't really help. But in other hand the removal of this code also can't help me. So, I'm planning to experiment with idea described in my post -- may be it will help. The only reason to keep 1cp-width search is that it provides early info about eval change direction which can be useful for deep positional analyse performed by human chess players.

I use the 1cp window because it is the fastest search possible, since every node either fails high or fails low.

[Sergei Markoff]

I use the 1cp window because it is the fastest search possible, since every node either fails high or fails low.

We also have a terminology problem. There are "null-window search" and "1cp-width search". I'm using second term for Search (-eval - 1, -eval + 1) (in such a case only nodes with exact "eval" score will not fail high or low).

Some time ago I tried a lot of different modifications of classical PVS/NegaScout (MTD and a lot of non-classical approaches).

For example, we can use zero-window searches with variable step. Let the step is X. Try MTSearch(-eval - X, depth). If it fails beta bound then X += X and re-search. Otherwise X = -(X / 2) and so on.

In other time we can use zero-window search not to reach exact move score (which is not neccessary in the game) but to prove that we have single move which bound is > K. Se we're using shalow search to obtain that the one move has a significant gap in evaluation that the rest of the moves. Then we're starting MTSearch(-K - SOME_VALUE, depth) with each move and if our move is the only move with eval > K + SOME_VALUE -- we're going to the next iteration.

I think that there are a lot of ides that must be checked here. I think it's a good theme for students research.

[Sergei Markoff]

For example, we can use zero-window searches with variable step. Let the step is X. Try MTSearch(-eval - X, depth). If it fails beta bound then X += X and re-search. Otherwise X = -(X / 2) and so on.

Sorry wor wrong pseudo-code. I mean:

step = X;

while (step > 0)
{
eval += step;
new_eval = -MTSearch(-eval, depth);
if (new_eval <= eval && step > 0) step = -(step / 2);
else if (new_eval > eval && step < 0) step = (-step) / 2;
}

[bob]

I use the 1cp window because it is the fastest search possible, since every node either fails high or fails low.

We also have a terminology problem. There are "null-window search" and "1cp-width search". I'm using second term for Search (-eval - 1, -eval + 1) (in such a case only nodes with exact "eval" score will not fail high or low).

Some time ago I tried a lot of different modifications of classical PVS/NegaScout (MTD and a lot of non-classical approaches).

For example, we can use zero-window searches with variable step. Let the step is X. Try MTSearch(-eval - X, depth). If it fails beta bound then X += X and re-search. Otherwise X = -(X / 2) and so on.

In other time we can use zero-window search not to reach exact move score (which is not neccessary in the game) but to prove that we have single move which bound is > K. Se we're using shalow search to obtain that the one move has a significant gap in evaluation that the rest of the moves. Then we're starting MTSearch(-K - SOME_VALUE, depth) with each move and if our move is the only move with eval > K + SOME_VALUE -- we're going to the next iteration.

I think that there are a lot of ides that must be checked here. I think it's a good theme for students research.

The mtd-type search has been tested by many of us. The necessary condition is a very stable tree search and evaluation. If one move can make a big eval swing happen, then mtd has real problems in converging on the score, and it ends up taking longer to complete than a normal PVS-type search. I still have an old MTD version of Crafty around somewhere, but it was never "better" for any variation I tried, In fact, it was never "just as good as" either, it was always worse.