SEE is too slow

[cms271828]

Thanks that helps...

I more or less get it now after analysing a couple of trees.
In the QS, I ordered by MVVLVA, then applied see when value(capturer) > value(captured)
But its still about 20% slower compared to just using MVVLVA.

I did a count in qs for a 14 ply deep search of:
2r5/qnrbb3/k3n3/1ppp4/1PPP4/BN1KNB2/1QR5/2R5 b - - 0 1
Counts are shown below:

value(capturer) < value(captured) = 19,782,451
value(capturer) = value(captured) = 13,527,435
value(capturer) > value(captured) = 42,215,374

So I'm calling SEE about 60% of the time on the moves in QS which seems a lot

any thought(s)?

Thanks

[micron]

Those figures look reasonable.

The non check-evasion part of QS should now resemble this (changes from your original pseudocode indicated ////):

Code: Select all

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

       if ( val >= beta ) return beta; /////
       if ( val > alpha ) alpha = val; /////

       moves = getCaptureMoves(); 
       for(Move move : moves) 
        { 
           if ( value(captured) >= value(capturer) || SEE( move ) >= 0) ) /////
           {
             MakeMove(); 
             val = -QS(-beta, -alpha); 
             UndoMove(); 
             if(val >= beta) return beta; 
             if(val > alpha) alpha = val; 
            }
        } 
       return alpha; 
} 

[cms271828]

Thanks, I actually already had the

Code: Select all

int val = getEval();

if ( val >= beta ) return beta; /////
if ( val > alpha ) alpha = val; ///// 

I must have accidently skipped over those lines while I was copy and pasting my code in here.

The code you wrote is effectively what I have now which is a little slow.
Perhaps it is cause of my thin eval function or maybe I can make SEE a little faster, but I'm not sure how, I made it as efficient as I possibly could.

One other thing, I used this code before to help prevent an explosion in quiescent moves..

Code: Select all

if &#40;val + value&#40;captured&#41;+ 150 < alpha&#41; skipmove;

I guess I can lose this line now if I'm using the SEE code.

Thanks

[bob]

Thanks that helps...

I more or less get it now after analysing a couple of trees.
In the QS, I ordered by MVVLVA, then applied see when value(capturer) > value(captured)
But its still about 20% slower compared to just using MVVLVA.

I did a count in qs for a 14 ply deep search of:
2r5/qnrbb3/k3n3/1ppp4/1PPP4/BN1KNB2/1QR5/2R5 b - - 0 1
Counts are shown below:

value(capturer) < value(captured) = 19,782,451
value(capturer) = value(captured) = 13,527,435
value(capturer) > value(captured) = 42,215,374

So I'm calling SEE about 60% of the time on the moves in QS which seems a lot

any thought(s)?

Thanks

SEE is not free. As I said, you have to "gain something." Are you completely skipping q-search captures where SEE < 0? That will cut out 1/2 of your total search nodes which should be far more effort saved than the cost of the SEE to cull them...

[cms271828]

Yes, I have...

Code: Select all

if ( value(captured) >= value(capturer) || SEE( move ) >= 0) )

So negative SEE's are ignored.
But the total nodes searched is actually 2% more using SEE, than without (With the position 1kr5/qnrbb3/4n3/1ppp4/1PPP4/BN2NB2/1QR5/1KR5 b - - 0 1 at 13 ply search), I'm not sure whats going on, or how to proceed.

Perhaps my MVVLVA is wrong, I value moves by 16*victim - attacker
where the values are K=0, P=1,N=3,B=4,R=5,Q=6
This seems ok though

[micron]

Perhaps my MVVLVA is wrong, I value moves by 16*victim - attacker
where the values are K=0, P=1,N=3,B=4,R=5,Q=6
This seems ok though

No. K should be the most valuable.

[Sven]

One other thing, I used this code before to help prevent an explosion in quiescent moves..

Code: Select all

if &#40;val + value&#40;captured&#41;+ 150 < alpha&#41; skipmove;

I guess I can lose this line now if I'm using the SEE code.

You can keep that in, it helps to also skip *winning* captures that are not winning enough material to reach alpha. This is not related to SEE in the way you are using it.

For instance, being a rook down (a rook below alpha, to be more correct) you don't need to do q-search for moves winning a pawn since it is extremely unlikely (or maybe impossible) for any positional gain of pawn-winning moves to compensate for the (rook-pawn) difference.

Sven

[Sven]

Yes, I have...

Code: Select all

if ( value(captured) >= value(capturer) || SEE( move ) >= 0) )

So negative SEE's are ignored.
But the total nodes searched is actually 2% more using SEE, than without (With the position 1kr5/qnrbb3/4n3/1ppp4/1PPP4/BN2NB2/1QR5/1KR5 b - - 0 1 at 13 ply search), I'm not sure whats going on, or how to proceed.

Perhaps my MVVLVA is wrong, I value moves by 16*victim - attacker
where the values are K=0, P=1,N=3,B=4,R=5,Q=6
This seems ok though

As already noted by Robert, the K value should be greater than the Q value. But this would not explain getting 2% more nodes when using SEE. A higher node count with a fixed-depth search seems to indicate that you are even skipping more nodes without SEE, so what exactly are you doing in the "without" case?

Sven

[mjlef]

Perhaps your SEE is not very efficient yet. You do not need to do SEE if the moving piece value is <= the captured piece. And while playing out the captures you can often cut it off early. For example, QxB, and if the B was protected by even a single pawn, you can stop and know the QxB capture is losing (assuming the pawn is not pinned).

[cms271828]

Ok,

In the without case, I just generate all captures, order them by MVVLVA.

Then I skip over them if...

Code: Select all

if &#40;val + value&#40;captured&#41;+ 150 < alpha&#41; skipmove;

I did have K as 7, but I just changed it to 0, since I assumed king capturing pieces would be better than any other piece as the king can't be recaptured. Although I only work with legal moves, so might be minutely faster to make K=7, then check the legality of the king move before playing it, but thats a minor issue at the moment.

Perhaps the best thing I can do is setup a very simple board with a small capture sequence which goes quiet after a few ply, then analyse all the moves and mvvlva and see values by hand to make sure it corresponds