A way to improve PVS

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Sergei Markoff

A way to improve PVS

Post by Sergei Markoff » Mon Sep 07, 2009 4:10 am

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
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: A way to improve PVS

Post by bob » Mon Sep 07, 2009 3:21 pm

Sergei Markoff wrote: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

Re: A way to improve PVS

Post by Sergei Markoff » Mon Sep 07, 2009 9:10 pm

bob wrote: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
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: A way to improve PVS

Post by bob » Tue Sep 08, 2009 12:12 am

Sergei Markoff wrote:
bob wrote: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

Re: A way to improve PVS

Post by Sergei Markoff » Tue Sep 08, 2009 7:18 am

bob wrote: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

Re: A way to improve PVS

Post by Sergei Markoff » Tue Sep 08, 2009 7:24 am

Sergei Markoff wrote: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
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: A way to improve PVS

Post by bob » Tue Sep 08, 2009 8:46 pm

Sergei Markoff wrote:
bob wrote: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.

Post Reply