SEE

[hgm]

Something I always wondered about: would it be a good idea to treat the Pawns in the King shield as different pieces from other Pawns, and give them value 200 cP is SEE and futility pruning? Perhaps in combination with downgrading them when they move (i.e. treat any move of them, or perhaps only captures, as you would treat a promotion, but with a negative bonus)?

That way a larger part if the King safety would be included in the material eval, allowing you to reduce the futility margins, and not so easily dismissing sacrifices of a minor piece on the King fortress as "bad captures" in QS.

[Sven]

3. There is no backup mechanism. While the cutoff conditions look correct, you need to take into account the fact that the side to move doesn't have to capture. You need a stack of values, indexed by moves_to_undo, and at the end only back up a value if it's greater than or equal to the current value. This is a bit more complicated because you don't use negamax.

Can you please elaborate on that? I thought the moving side only won't make a capture if and only if the score is in its favor?

Yes, the cutoff condition is correct (if stm is already ahead, no need to make any more captures).

Hi Zach,

I am not sure about your last sentence in brackets. Doesn't it depend on how you use SEE, i.e. whether you also use it for move ordering or only for pruning SEE < 0 in QS? In the latter case (pruning only), I can imagine that more cutoffs are possible than in the former case (ordering) since the enemy of the "STM at SEE root" does not need to find the optimal refutation if there exists any.

What I thought up to now was that the only choice for the STM at any point in a capture sequence were *to count* the result of a possible capture or *not to count* it, depending on what's better. So you try a capture move, and if it loses material relative to the current position then you discard it.

Fruit 2.1 (and also Toga which has SEE code identical to Fruit 2.1 IIRC) essentially does it recursively this way (my own comments added):

Code: Select all

   // ... some code to initialize 'value' to the direct material gain of the current capture ...
   // ...
   // 'piece_value' is the material value of the currently capturing piece,
   // or of a queen in case of promotion
   // ...
   value -= see_rec(alists,board,COLOUR_OPP(colour),to,piece_value);
   if (value < 0) value = 0;
   return value;

and I believe that Fabien would have implemented such an additional cutoff if it were possible. (Ok, of course not the strongest argument, I know ...)

So my problem is that I do not understand why more cutoffs should be allowed.

Sven

[cyberfish]

There is often pawns around the king and most engines have some king safety code that rewards pieces targeting the ennemy king position so you have a lot of positions in the search with pieces about to capture those pawns.

You can not prune king captures.

That makes sense. I guess I will just add a special check in genSmallestCapture for king captures (only generate the capture if it doesn't leave the king in check). Since king captures don't happen that often, the performance penalty should be small enough.

[cyberfish]

I have now implemented SEE recursively as that seems to be easier. It is "working" now, in the sense that prunning bad captures from Qsearch no longer makes it weaker.

I have also tried a few test positions, and they seem to work.

Not stronger either, though. It is about equal to the mvv/lva version over 400 games. I guess it is my unoptimized implementation.

According to Dr. Hyatt in another thread, SEE cuts down the tree by ~10%, and I don't think I can ever make SEE only 10% slower than without, so I guess a better option would be to only use SEE to prune out bad captures in Qsearch, and use mvv/lva in alpha-beta to order moves.

[bob]

I have now implemented SEE recursively as that seems to be easier. It is "working" now, in the sense that prunning bad captures from Qsearch no longer makes it weaker.

I have also tried a few test positions, and they seem to work.

Not stronger either, though. It is about equal to the mvv/lva version over 400 games. I guess it is my unoptimized implementation.

According to Dr. Hyatt in another thread, SEE cuts down the tree by ~10%, and I don't think I can ever make SEE only 10% slower than without, so I guess a better option would be to only use SEE to prune out bad captures in Qsearch, and use mvv/lva in alpha-beta to order moves.

Recursive sounds bad. You are adding significant overhead when it is not necessary (the procedure call on X86 is hardly fast). You can easily look at how it is done in Crafty to get the idea, but a simple loop to load up the capturing pieces, followed by a simple minimax backward loop is all that is needed. Faster is always better...

[Sven]

so I guess a better option would be to only use SEE to prune out bad captures in Qsearch, and use mvv/lva in alpha-beta to order moves.

Apply mvv/lva also in Qsearch for ordering of the remaining moves which are not pruned.

Sven

[bob]

so I guess a better option would be to only use SEE to prune out bad captures in Qsearch, and use mvv/lva in alpha-beta to order moves.

Apply mvv/lva also in Qsearch for ordering of the remaining moves which are not pruned.

Sven

Why would you do that? You have _already_ used SEE to decide what to prune, so you already have SEE scores for each move, and those scores are more accurate than MVV/LVA by a wide margin.

SEE is definitely faster, done properly...

[Sven]

so I guess a better option would be to only use SEE to prune out bad captures in Qsearch, and use mvv/lva in alpha-beta to order moves.

Apply mvv/lva also in Qsearch for ordering of the remaining moves which are not pruned.

Sven

Why would you do that? You have _already_ used SEE to decide what to prune, so you already have SEE scores for each move, and those scores are more accurate than MVV/LVA by a wide margin.

SEE is definitely faster, done properly...

You are right if you apply SEE to *all* Qsearch moves. But you can also decide to apply SEE only to captures with 'value(movingPiece) > value(victim)' since usually only these will be subject to pruning. Therefore you could have something like this:

Code: Select all

int scoreMoveInQS(Move const & m, Board const & b, bool & skip)
{
    int score;
    if (materialValue(m.movingPiece) > materialValue(b.piece(m.targetSqr))) {
        score = see(m, b);
        skip = bool(score < 0);
    } else {
        score = mvvLva(m, b);
        skip = false;
    }
    return score;
}

Edit: Maybe this is even too simple, if you always want to try all captures of a minor piece that were not pruned by SEE after all winning or equal captures, instead of comparing SEE scores with MVV/LVA scores as in my code example.

Sven

[bob]

so I guess a better option would be to only use SEE to prune out bad captures in Qsearch, and use mvv/lva in alpha-beta to order moves.

Apply mvv/lva also in Qsearch for ordering of the remaining moves which are not pruned.

Sven

Why would you do that? You have _already_ used SEE to decide what to prune, so you already have SEE scores for each move, and those scores are more accurate than MVV/LVA by a wide margin.

SEE is definitely faster, done properly...

You are right if you apply SEE to *all* Qsearch moves. But you can also decide to apply SEE only to captures with 'value(movingPiece) > value(victim)' since usually only these will be subject to pruning. Therefore you could have something like this:

Code: Select all

int scoreMoveInQS(Move const & m, Board const & b, bool & skip)
{
    int score;
    if (materialValue(m.movingPiece) > materialValue(b.piece(m.targetSqr))) {
        score = see(m, b);
        skip = bool(score < 0);
    } else {
        score = mvvLva(m, b);
        skip = false;
    }
    return score;
}

Edit: Maybe this is even too simple, if you always want to try all captures of a minor piece that were not pruned by SEE after all winning or equal captures, instead of comparing SEE scores with MVV/LVA scores as in my code example.

Sven

Here's the problem. In a q-search, Most use the idea from Crafty...

if val(captured) >= val(capturing) assume gain = val(captured)-val(capturing), which is still a + score. That by itself is more accurate than MVV/LVA type ordering as it will favor PxN over QxR (MVV/LVA would try QxR first).

If val(captured) < val(capturing) then use SEE as you might dismiss QxP if the pawn is defended, while you will happily try QxP if the pawn is not defended. But you already know _both_ before you search any captures... Because with SEE you need to get all the SEE values and then sort the captures best-first...

So mixing in MVV/LVA (which is less accurate by definition) doesn't make much sense to me, even with the so-called "delta pruning" (I just by chance chose the name "delta" in Crafty's code as the "delta" value you need to capture to get score back above alpha)...