SEE is too slow

[cms271828]

So I just put see in to my engine (for white captures)..
It takes about 3 times longer to complete a 9 ply search than using MVV/LVA.

I always assumed SEE was faster if done correctly, but I clearly have poor results.
So now I'm stuck with what to do, is it likely I have an error?

Thanks

[Desperado]

Hi Colin,

just some ideas on the fly...

1. do you do SEE() only in QS ?
2. do you do SEE () only for captures at inner nodes or for quiet moves too ?
(especially thinking of nodes close to the horizon)
3. do you delay the SEE() into the move-loop, or is it done when
you sort the movelist ?

Michael

[cms271828]

Hello

1. I can see I'm calling SEE in the QS, I just took this out, and put in MVVLVA, the time taken has gone from 3 times as much to approx twice as much.
So its an improvement on what I had, but still much worse than MVV/LVA

2. I use see at all captures that arent QS.

3. I call SEE directly after each capture generated, so the negative ones go into a different array to the positive( or 0) SEE valued moves.
Then I sort, only the positive SEE, using bubblesort.
Finally when its time in the main alpha-beta loop, I sort the negatively valued SEE moves, just prior to using them. Since if theres a cutoff, it means it was a waste to sort them earlier with the other captures.

Thanks

[micron]

Instead of thinking and saying 'slow', resolve slowness into two measurable factors:
time to depth = node_count / NPS

With SEE in Search() you expect a reduction in NPS; SEE is more work than MVVLVA.

But node_count should drop even more because of the improvement in move ordering, giving a net win for SEE.

By measuring node_count and NPS you should get an idea of what is wrong with your SEE implementation.

[cms271828]

Ok, I've done that, but I still donno whats wrong, (if anything actually is, maybe SEE is supposed to be slow?)

A 10 ply search, after white has played 1.a3 gives..

MVV/LVA version:
total_nodes = 134,574,925
time_taken = 24.078s
nps = 5.589 M

SEE version:
total_nodes = 128,411,817
time_taken = 42.087s
nps = 3.051 M

So thats just a measly 4.5% reduction in nodes (including qs nodes)
But the time taken is almost double.

Ultimately its the time taken to complete 10 ply search that is what we want to reduce.
I don't see how I can make the SEE any quicker to bring down the nps, perhaps there is a bug in the ordering explaining why the total nodes drop is so little, but I don't know what to expect having not done this before

Thanks for any help.

[kbhearn]

Perhaps your evaluation is too light to benefit from the node reduction. If that's singlethreaded NPS your speed seems ridiculously fast and that could account for NPS being almost halved, the extra time to sort by SEE might not yet be worth it for you.

Also after 1. a3 is a bad place to test, since you don't yet have a typical amount of captures to sort in the next 10 ply. Test from a middlegame position instead (you should get better node savings then).

[phjal]

I think you'd be better off using SEE only in QS, ignoring captures with negative SEE in the search. Usually programs spend a lot of time in QS and even small improvments can have a big impact. For move ordering it's not going to make a huge difference, but it should be an improvment for node count, not neccesarily for speed though.

Do you drop out early from SEE if you can't improve, i.e. just return if you're down say a rook and can only capture a knight? This should help speed but then you don't always return correct values (always correct regarding positive/negative values but not the exact score), which affects move ordering. In that case you might want to order by MVV/LVA for positive SEE moves.

[micron]

1. If your SEE() is the complicated, accurate and slow kind that reveals new slider attacks during the exchange, that's overkill for move ordering. Remove the Xray attacks code for better speed. An Xray-enabled SEE is better reserved for pruning decisions in QS, where you need all the accuracy you can get.

2. MVVLVA is actually pretty good order for 'good' captures. You don't lose anything by restricting SEE's role to classifying capture moves [instead of ordering them]:

Code: Select all

  if ( SEE&#40; move ) < 0 ) )
  &#123; PutLateInMoveOrder&#40; move ) &#125; // 'bad'
  else
  &#123; AddToWinningCapturesToBeSortedByMVVLVA&#40; move ) &#125; // 'good'

3. Now an elegant optimization allows many SEE evaluations to be skipped altogether, without affecting the classification:

Code: Select all

  if ( &#40;ValOf&#40; capturedPiece ) < ValOf&#40; capturingPiece )) && &#40;SEE&#40; move ) < 0&#41; )

Robert P.

[cms271828]

Thanks I tried earlier from an early middlegame position, but no change..

Here is a position I just tried
r2q3k/pn2bprp/4pNp1/2p1PbQ1/3p1P2/5NR1/PPP3PP/2B2RK1 b - - 0 1 [forgot how to display it]

Upto 10 ply...

MVVLVA:
1.565 seconds
4.909 M nodes

SEE:
2.808 seconds
4.402 M nodes

So this time, about 10% reduction in nodes, but overall time is still almost double.

[cms271828]

Reply to Peter...

Ok thanks, I think I should look at my QS code first....

for whites QS method/function I have...

Code: Select all

WQS(alpha, beta)
{
    int val = getEval();

    // NOT CHECK, LOOK FOR CAPTURES THAT RAISE SCORE
    if(NOT check)
    {
       moves = getCaptureMoves();

       for(Move move : moves)
       {
           if&#40;val + pieceValues&#91;move.capturedPiece&#93; + 150 < alpha&#41; continue;
        
           MakeMove&#40;);
           val = -BQS&#40;-beta, -alpha&#41;;
           UndoMove&#40;);
 
           if&#40;val >= beta&#41; return beta;
	        if&#40;val > alpha&#41; alpha = val;
        &#125;
    &#125;

    // IN CHECK
    else
    &#123;
         .... Do normal full width search like in non-qs


       if&#40;NO_MOVES&#41; return checkmateScore;
    &#125;

   return alpha;
&#125;

So if ordering the moves using SEE, I can do better than "val+capturedpiece", cause that assumes my piece is not recaptured, perhaps "val+seeValue".
But since when I generate captures, I put them into SEE>=0, and SEE<0 arrays I could just ignore the <0 captures.

About dropping out from see...
I use alpha beta in see, and I essentially just look for 2pawns,2knights,1Bishop,2Rooks,1Queen of both colours.
I have quite a complex system for see using about 19 different cases
depending on which pieces have been found in the sequence.
I also do a basic check for sliders on the + and x bitboards centered on the capture square, which can prevent having to use the fixed shift magics when I try to find the next piece in the sequence.
I've tested quite a few positions, and they all seem to use the minimal amount of iterations needed.