qsearch in crafty

[stevemulligan]

I found this FEN in a thread from 2002 titled qsearch explosion:

r4rk1/1p1n1pp1/1bq1bn1p/p1pp4/2P2B2/1NNP2P1/PPQ2PBP/R4RK1 w - - 0 19

On a 4 ply search, my engine searches 223k qsearch nodes, 2369 non-qsearch nodes. Looking at crafty today I saw this:

Code: Select all

//crafty-23.4, quiesce.c
//line 205->209

if (pc_values[Piece(tree->curmv[ply])] >
         pc_values[Captured(tree->curmv[ply])] && TotalPieces(wtm, occupied)
         - p_vals[Captured(tree->curmv[ply])] > 0 &&
         Swap&#40;tree, tree->curmv&#91;ply&#93;, wtm&#41; < 0&#41;
       continue;

Can I add this to my c# engine? What is this technique called? I'm guessing it would give me a total 30k qnodes searched on this position. Huge savings.

What is stored in p_vals[]? Is the Swap() function static exchange evaluation?

[Evert]

Code: Select all

//crafty-23.4, quiesce.c
//line 205->209

if (pc_values[Piece(tree->curmv[ply])] >
         pc_values[Captured(tree->curmv[ply])] && TotalPieces(wtm, occupied)
         - p_vals[Captured(tree->curmv[ply])] > 0 &&
         Swap&#40;tree, tree->curmv&#91;ply&#93;, wtm&#41; < 0&#41;
       continue;

Can I add this to my c# engine? What is this technique called?

Isn't this just a form of futility pruning?
From the looks of it, the branch is pruned when the capturing piece is more valuable than the captured piece, SEE<0 and the side to move is ahead in material (not sure why that's in there).

I'm guessing it would give me a total 30k qnodes searched on this position. Huge savings.

What is stored in p_vals[]? Is the Swap() function static exchange evaluation?

How can you estimate the savings from a piece of code if you don't even know what it does?

[stevemulligan]

How can you estimate the savings from a piece of code if you don't even know what it does?

I used a technique that is dubbed the WAG technique. (Wild Ass Guess)

I turned off this code in Crafty and noticed it's qnodes searched % was about the same as mine. Seeing this I figured taking a guess was worth a try since the it's just a quick calculation. I took my non-qsearch nodes searched and interpolated (linearly) what my qsearch would be if I could get as close to the % qsearch that crafty had.

Since this is a WAG, I doubled this value to get about 30k nodes (to err on the side of caution, in an attempt to account for all the other node saving things Crafty does not specific to this chunk of code). Crafty has extensions too (which I don't) but that could only help my guess be higher than expected. I don't mind guessing too high, because if I save more nodes than expected, then I'm even happier.

Now the fun part is trying to get my qnode count down that low. A savings of 193k evals; I would be dancing around the room!! Experience with the WAG technique tells me not to get very excited yet though.

[Desperado]

... Now the fun part is trying to get my qnode count down that low. A savings of 193k evals; I would be dancing around the room!! ...

Maybe you want to try only the swap (in case it is the SEE implementation)
condition instead of the whole condition presented.

In that case you may fly around in your room .

Good luck anyway with your WAG technique

Michael

[bob]

I found this FEN in a thread from 2002 titled qsearch explosion:

r4rk1/1p1n1pp1/1bq1bn1p/p1pp4/2P2B2/1NNP2P1/PPQ2PBP/R4RK1 w - - 0 19

On a 4 ply search, my engine searches 223k qsearch nodes, 2369 non-qsearch nodes. Looking at crafty today I saw this:

Code: Select all

//crafty-23.4, quiesce.c
//line 205->209

if (pc_values[Piece(tree->curmv[ply])] >
         pc_values[Captured(tree->curmv[ply])] && TotalPieces(wtm, occupied)
         - p_vals[Captured(tree->curmv[ply])] > 0 &&
         Swap&#40;tree, tree->curmv&#91;ply&#93;, wtm&#41; < 0&#41;
       continue;

Can I add this to my c# engine? What is this technique called? I'm guessing it would give me a total 30k qnodes searched on this position. Huge savings.

What is stored in p_vals[]? Is the Swap() function static exchange evaluation?

First, p_vals has the usual piece values 100, 300, 300, 500, 900. That code is a simple optimization. If the piece you are capturing is more valuable than the piece you are capturing with, you win material no matter what. Avoiding a call to Swap() saves time. You can use the difference in the two piece values as an "approximate gain" safely. If the capturing piece is more valuable than the captured piece, I use Swap() to see if it is a good capture or not, and accept the overhead to avoid searching losing captures where they really don't matter.

[bob]

Code: Select all

//crafty-23.4, quiesce.c
//line 205->209

if (pc_values[Piece(tree->curmv[ply])] >
         pc_values[Captured(tree->curmv[ply])] && TotalPieces(wtm, occupied)
         - p_vals[Captured(tree->curmv[ply])] > 0 &&
         Swap&#40;tree, tree->curmv&#91;ply&#93;, wtm&#41; < 0&#41;
       continue;

Can I add this to my c# engine? What is this technique called?

Isn't this just a form of futility pruning?
From the looks of it, the branch is pruned when the capturing piece is more valuable than the captured piece, SEE<0 and the side to move is ahead in material (not sure why that's in there).

Perhaps because it is NOT in there. the only test is to make sure that I am not capturing the last opponent piece. If so, even if I lose material, the capture might allow one of my pawns to run and promote...

I'm guessing it would give me a total 30k qnodes searched on this position. Huge savings.

What is stored in p_vals[]? Is the Swap() function static exchange evaluation?

How can you estimate the savings from a piece of code if you don't even know what it does?

[stevemulligan]

I use Swap() to see if it is a good capture or not

I've been reading your Swap function over the past couple days, trying to understand how it works. I'm stuck on the AttacksBishop (and AttacksRook) functions.

Code: Select all

AttacksBishop(square, occ) *(magic_bishop_indices[square]+((((occ)&magic_bishop_mask[square])*magic_bishop[square])>>magic_bishop_shift[square]))

What are the magic_bishop_indices, magic_bishop_mask, magic_bishop and magic_bishop_shift arrays holding? I know this is generating bishop attacks, but how exactly does this work? I've never seen this before...

[bob]

I use Swap() to see if it is a good capture or not

I've been reading your Swap function over the past couple days, trying to understand how it works. I'm stuck on the AttacksBishop (and AttacksRook) functions.

Code: Select all

AttacksBishop(square, occ) *(magic_bishop_indices[square]+((((occ)&magic_bishop_mask[square])*magic_bishop[square])>>magic_bishop_shift[square]))

What are the magic_bishop_indices, magic_bishop_mask, magic_bishop and magic_bishop_shift arrays holding? I know this is generating bishop attacks, but how exactly does this work? I've never seen this before...

Those two functions simply produce a bitmap of the squares that a bishop on square "square" attacks, given the set of occupied squares "occ" (this is a simple magic multiply move generation for sliding pieces.

[zamar]

What are the magic_bishop_indices, magic_bishop_mask, magic_bishop and magic_bishop_shift arrays holding? I know this is generating bishop attacks, but how exactly does this work? I've never seen this before...

http://chessprogramming.wikispaces.com/Magic+Bitboards

[stevemulligan]

heh, Magic bit boards seem a bit complicated for me at this stage. I'm trying to understand kindergarden bb's and I gotta say, whoever choose that name is making me feel really dumb right now :p

Would a lookup table without any rotations or hashing be too big (under 10Megs?) I know it would give terrible performance compared to MBB's but it would be way faster than what I'm using now to generate attacks.

Code: Select all

 for &#40;int i = 0; i++ i < 64&#41;
   for &#40;j = 0; j < ray_count; j++)
     for &#40;k = 0; k < ray_length; k++)
       if &#40;square_is_occupied&#41;
         break;
       attacks |= rays_square&#91;k&#93;;