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 too slow
Moderators: hgm, Rebel, chrisw
-
- Posts: 155
- Joined: Mon Feb 15, 2010 9:33 am
- Location: New Zealand
Re: SEE is too slow
Those figures look reasonable.
The non check-evasion part of QS should now resemble this (changes from your original pseudocode indicated ////):
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;
}
-
- Posts: 316
- Joined: Wed Apr 12, 2006 10:47 pm
Re: SEE is too slow
Thanks, I actually already had the
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..
I guess I can lose this line now if I'm using the SEE code.
Thanks
Code: Select all
int val = getEval();
if ( val >= beta ) return beta; /////
if ( val > alpha ) alpha = val; /////
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 (val + value(captured)+ 150 < alpha) skipmove;
Thanks
Colin
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: SEE is too slow
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 wrote: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
-
- Posts: 316
- Joined: Wed Apr 12, 2006 10:47 pm
Re: SEE is too slow
Yes, I have...
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
Code: Select all
if ( value(captured) >= value(capturer) || SEE( move ) >= 0) )
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
Colin
-
- Posts: 155
- Joined: Mon Feb 15, 2010 9:33 am
- Location: New Zealand
Re: SEE is too slow
No. K should be the most valuable.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
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: SEE is too slow
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.cms271828 wrote:One other thing, I used this code before to help prevent an explosion in quiescent moves..I guess I can lose this line now if I'm using the SEE code.Code: Select all
if (val + value(captured)+ 150 < alpha) skipmove;
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
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: SEE is too slow
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?cms271828 wrote:Yes, I have...
So negative SEE's are ignored.Code: Select all
if ( value(captured) >= value(capturer) || SEE( move ) >= 0) )
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
Sven
-
- Posts: 1494
- Joined: Thu Mar 30, 2006 2:08 pm
Re: SEE is too slow
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).
-
- Posts: 316
- Joined: Wed Apr 12, 2006 10:47 pm
Re: SEE is too slow
Ok,
In the without case, I just generate all captures, order them by MVVLVA.
Then I skip over them if...
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
In the without case, I just generate all captures, order them by MVVLVA.
Then I skip over them if...
Code: Select all
if (val + value(captured)+ 150 < alpha) skipmove;
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
Colin