Author: Stan Arts
Date: 10:36:43 01/14/04
Go up one level in this thread
The results are indeed strange for the tactical position.
In the startingposition indeed with aspirationsearch the difference between
PVS on or off seems smaller. (The reason for me asking the question was that
in Neurosis pvs seems to make little/no difference over a normal form of
alpha-beta, but always trying to search with a tight as possible alpha-beta
window from the root. So I found your numbers for improvement huge and
wondered how that could be.)
Took me a little bit to understand your code, I'm not so good in C..(writing
neurosis in pascal)
You write, after falling outside the search-window it researches the entire
iteration with full window, that is ok to do in a fail-low, where you find
the current move is losing (but not by how much) and then seeing if another
move will bring the score back. But not when the score is going up (in favour
of the engine) then you want to step back the move-counter at the root and
research that move right after you find it's score is higher then the
window. So in the middle of the iteration. Incase of Neurosis I also
research per move incase of dropping scores, to get the accurate score and
adjust time-use for the iteration etc. But it depends on the position if that
pays off or not, and if there is a move to bring back the score to the
current level or not.
Second improvement is to use the score outside the window as a new upper or
lower bound instead of -inf , +inf that does away a lot of the gain. So
incase you did a search with -0.30 to +0.30 and the move/iteration returns
+0.30 and it's the upper bound of search, then research with +0.30 to +inf.
And that will be a big speed up compared to -inf to +inf, because of the
extra beta-cutoffs you get for that move or initial move of the iteration,
you otherwise wouldn't get with the big window. (And if your alpha-beta
search can return valuesoutside the alpha-beta window, you can adjust even
further.)
Problem with that is you could get search instability if you are searching
"up" and it returns the lower bound that time, or the other way around.. But
that'll be (very)rare (mostly/usually a consequence of nullmove) and if it
happens in Neurosis I hold that lower bound as the "real" score and dont do
a new search and move on to the next moves/iteration.
Then you can open up the window in steps and I do that in Neurosis but it's
not always a gain even if the score is below and within the limit towards
infinity, but it's worth trying how much that gives, because again you have
an extra limit to eliminate some captures in q-search.
I think just using the new upper / lower bound to research will save a lot,
and make up most of the difference you had in the tactical position.
In anyway you still have some gain with PVS even in the openingposition and
that's good.. And will make me try again in my program. :)
Greetings and thank you,
Stan
On January 14, 2004 at 11:53:38, Michel Langeveld wrote:
>This is how I implemented PVS now:
>
>/* think() calls search() iteratively. Search statistics
> are printed depending on the value of output */
>void think()
>{
> int i, x, middle;
> int window = 30;
> int low_window, high_window;
>
> /* try the opening book first */
> pv[0][0].u = book_move();
> if (pv[0][0].u != -1)
> return;
>
> /* some code that lets us longjmp back here and return
> from think() when our time is up */
> stop_search = FALSE;
> setjmp(env);
> if (stop_search) {
>
> /* make sure to take back the line we were searching */
> while (ply) {
> //nullmove?
> if (hist_dat[hply-1].m.u == 0)
> takebacknullmove();
> else
> takeback();
> }
> return;
> }
>
> start_time = get_ms();
> stop_time = start_time + max_time;
>
> ply = 0;
> nodes = 0;
> memset(pv, 0, sizeof(pv));
> memset(history, 0, sizeof(history));
>
> middle = eval();
>
> if (output == 1)
> printf("ply time nodes score pv\n");
> for (i = 1; i <= max_depth; ++i) {
> follow_pv = TRUE;
>
> low_window = middle - window;
> high_window = middle + window;
>
>research:
> printf("searching [%d,%d]\n", low_window, high_window);
> x = search(low_window, high_window, i, TRUE);
> do_output(i, x, TRUE);
>
> //are we mate?
> if (x > 9000 || x < -9000) break;
>
> //research?
> if (x <= low_window || x >= high_window) {
> low_window = -10000;
> high_window = 10000;
> printf("research\n");
> goto research;
> }
>
> middle = x;
>
> movecount = 0;
> }
>}
>
>The strange thing I tested 2 positions:
>- starting position
>- tactical position
>
>In the first aspiration windows is a tiny bith faster in the other pos it is big
>way slower. Is the asp window implemented as you expected I do I have to make
>it smarter?
>
>starting position 8 ply:
>
>-asp -pvs
> 8* 1762 2987720 -9 b1c3 d7d5 i1h3 i8h6 h3f4 d5d4 c3e4 c8f5
>
>-asp +pvs:
> 8* 1028 1689903 -9 b1c3 d7d5 i1h3 i8h6 h3f4 d5d4 c3e4 c8f5
>
>+asp -pvs
> 8* 1054 1702334 -9 b1c3 d7d5 i1h3 i8h6 h3f4 d5d4 c3e4 c8f5
>
>+asp +pvs:
> 8* 996 1631105 -9 b1c3 d7d5 i1h3 i8h6 h3f4 d5d4 c3e4 c8f5
>
>think you are right for this one 5.5% improvement.
>
>tactical position 8 ply:
>
>-asp -pvs:
> 7 1234 2303662 -9990 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 g2i2 i5j5 e8h5
> 7* 1234 2303662 -9990 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 g2i2 i5j5 e8h5
>
>-asp +pvs:
> 7* 160 328189 -9990 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 g2i2 i5j5 e8h5
>
>+asp +pvs (asp makes it slower):
> 7* 329 675245 -9990 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 g2i2 i5j5 e8h5
>
>+asp -pvs (asp makes it slower):
> 7* 1459 2862993 -9990 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 g2i2 i5j5 e8h5
>
>The problem with adding asp on the tactical position is that it had to do the
>research the entire ply full with again, as follows:
>
>ply time nodes score pv
>searching [412,472]
> 1 0 77 427 i3j3 f8d8
> 1* 0 77 427 i3j3 f8d8
>searching [397,457]
> 2 0 993 442 i3j3 f8d8 j1g1
> 2* 0 993 442 i3j3 f8d8 j1g1
>searching [412,472]
> 3 1 3499 412 i3j3 g2h2 j3i3 h2g2
> 3* 1 3499 412 i3j3 g2h2 j3i3 h2g2
>research
>searching [-10000,10000]
> 3 3 5285 0 i3j3 g2h2 j3i3 h2g2
> 3* 3 5285 0 i3j3 g2h2 j3i3 h2g2
>searching [-30,30]
> 4 4 8100 0 i3j3 g2h2 j3i3 h2g2
> 4* 4 8100 0 i3j3 g2h2 j3i3 h2g2
>searching [-30,30]
> 5 6 14075 0 i3j3 g2h2 j3i3 h2g2
> 5* 6 14075 0 i3j3 g2h2 j3i3 h2g2
>searching [-30,30]
> 6 39 77459 -30 i3j3 h5h4 d1j7 i8j7 j1j2 c8e8
> 6* 39 77459 -30 i3j3 h5h4 d1j7 i8j7 j1j2 c8e8
>research
>searching [-10000,10000]
> 6 87 175274 -461 i3j3 h5h4 d1j7 i8j7 j3i4 g2h2 i4h4 f8d8 d3b2 h2f2
> 6* 87 175274 -461 i3j3 h5h4 d1j7 i8j7 j3i4 g2h2 i4h4 f8d8 d3b2 h2f2
>searching [-491,-431]
> 7 150 308074 -491 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 g2i2 i5j5 e8h5
> 7* 150 308074 -491 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 g2i2 i5j5 e8h5
>research
>searching [-10000,10000]
> 7 329 675245 -9990 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 g2i2 i5j5 e8h5
> 7* 329 675245 -9990 i3j3 h5h4 d1j7 i8j7 j3i4 c8e8 i4i5 g2i2 i5j5 e8h5
>Time: 3297 ms
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.