SEE

[cyberfish]

I tried implementing SEE in my engine and noticed a huge drop in playing strength (~80-40-30 for see-mlv-draws) in 10 second games. The raw nps count seems reasonable and consistent with other people's experience (2Mnps -> 1.4Mnps), which led me to believe my implementation of SEE is flawed. Can someone please have a look?

Code: Select all

Move genSmallestCapture(int dst); //generates capture with smallest attacker on dst. 0 if no capture

...

Score see_values_black[] = { 0, 9, 3, 3, 5, 1, 0, -9, -3, -3, -5, -1 };
Score see_values_white[] = { 0, -9, -3, -3, -5, -1, 0, 9, 3, 3, 5, 1 };

/* PieceType mb[] is the board in mailbox that I kept alongside my bitboards */

Score see(Move mv) { //how good the capture is for the moving side

    int mv_dst = getDst(mv);

    Score *see_values;

    if (moving_side == WHITE) {
        see_values = see_values_white;
    } else {
        see_values = see_values_black;
    }

    Score s = see_values[mb[mv_dst]];

    int stm = 1; //side to move. 1 = opponent, 0 = original moving side

    int moves_to_undo = 1;

    applyMove(mv);

    Move smallest_capture;
    while (true) {

        PieceType victim = mb[mv_dst];

        if (stm == 1) {
            if (s <= 0 || (s + see_values[victim]) >= 0) {
                break;
            }
        } else {
            if (s >= 0 || (s + see_values[victim]) <= 0) {
                break;
            }
        }

        if (!(smallest_capture = genSmallestCapture(mv_dst))) { //no more captures
            break;
        }

        applyMove(smallest_capture);
        ++moves_to_undo;

        s += see_values[victim];

    }

    for (int i = 0; i < moves_to_undo; ++i) {
        undoMove();
    }

    return s;
}

Many thanks!

SEE is only used to order moves. Qsearch searches all captures, even those with < 0 SEE scores. Changing Qsearch to eliminate captures with < 0 SSE scores weakens it even more.

[Harald Johnsen]

You are not supposed to have that nps drop ; your code is not fast enought or you are doing see() too often. Some engine are using see() to score captures only for captures with value(attacker) > value(victim) like Queen x Pawn.

Your code (see or search) is buggy if you can not prune negative see() captures in QSearch.

I don't know if your applyMove() and undoMove() are your standard move code or a special version for see() and i don't know if your genSmallestCapture() generate legal move or not ; perhaps some of those function can not handle correctly illegal position (king in check, etc).

Just to be sure you should construct a few test positions and verify that your see() code returns the correct value.

HJ.

[Sven]

Hi Matthew,

due to this piece of your code:

Code: Select all

        PieceType victim = mb[mv_dst];

which retrieves the next captured piece from your mailbox board, I guess that your applyMove() and undoMove() functions are really making/unmaking the move on the board, is that right? In that case I would think this may be way too much overhead for the small goal of getting the next victim (depends on the amount of other things you do in applyMove(), of course). In addition to that, you also generate the smallest possible capture to the dest square after each applyMove() which "sounds" quite expensive, too.

But since you are always looking onto the same square, the next victim will in general be the enemy piece that did the previous capture - with the exception of promotions which may or may not require a special handling. So the only task before starting the loop (or a recursion, as some other engines do) could be to collect all attackers and defenders of the destination square, and put these into two separate lists.

It is possible that your implementation is expensive but correct; in this case I would at least expect that you get a noticeable reduction of QS nodes when pruning SEE < 0. If this is not the case (which is how I read your posting) then it is very likely that there is some bug. Have you checked all "<"/"<="/">"/">=" operators in your loop termination conditions?

Two more questions to understand your code better:

- How do you handle a king capturing a defended piece?

- Why is your local variable 'stm' left unchanged within the loop? Since you do kind of minimax I would have expected that 'stm' is inverted after each applyMove(), but maybe I missed an important detail.

Sven

[bob]

without looking at your code, the best way to test/debug is to set up a position and pick a target square for SEE analysis. Then just call SEE with that target and print the score, no searching required. I would set up positions where there is just one capture, one capture/recapture, and continue. Make sure you set up positions where you do not want to follow the possible captures to the end, but can stop somewhere in the middle with a good score for side to move. Then change it so that you stop in the middle with a bad score.

If you are handling x-ray attacks (queen behind a rook for example) then you need to set up positions for that as well. If you can't break it, then you will know it isn't a SEE implementation issue, it is a SEE usage issue, which will take you to a different place in your program for debugging.

[Michel]

Where can I read about SEE? I do not even know what SEE stands for, and predictably Google does not help.

[Sven]

Where can I read about SEE? I do not even know what SEE stands for, and predictably Google does not help.

Static Exchange Evaluation, see eg here: http://chessprogramming.wikispaces.com/ ... Evaluation
Sven

[Zach Wegner]

Yes, there are some problems, some of which have been mentioned.

1. stm isn't flipped
2. You don't need to do a full make/unmake
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.

[cyberfish]

Many thanks for the help!

The stm not flipped thing... I am not sure how that happened . It's not the only problem, though. Playing strength is still greatly reduced with that fixed.

I am aware that I don't need to do a full make/unmake, but I am trying to get it right first then optimize it.

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?

You are not supposed to have that nps drop ; your code is not fast enought or you are doing see() too often. Some engine are using see() to score captures only for captures with value(attacker) > value(victim) like Queen x Pawn.

I am already doing that, as per Dr. Hyatt's suggestion to someone else in another thread.

Your code (see or search) is buggy if you can not prune negative see() captures in QSearch.

That I am aware of .

I don't know if your applyMove() and undoMove() are your standard move code or a special version for see() and i don't know if your genSmallestCapture() generate legal move or not ; perhaps some of those function can not handle correctly illegal position (king in check, etc).

applyMove and undoMove are my standard move code. genSmallestCapture actually doesn't check for position legality, and I guess that could be the problem. I will look into that.

which retrieves the next captured piece from your mailbox board, I guess that your applyMove() and undoMove() functions are really making/unmaking the move on the board, is that right? In that case I would think this may be way too much overhead for the small goal of getting the next victim (depends on the amount of other things you do in applyMove(), of course). In addition to that, you also generate the smallest possible capture to the dest square after each applyMove() which "sounds" quite expensive, too.

I agree it's unnecessarily expensive. I am just trying to get it to work correctly first before trying to optimize it.

to collect all attackers and defenders of the destination square, and put these into two separate lists.

That I tried to do, but have trouble with discovered attackers.

- How do you handle a king capturing a defended piece?

my genSmallestCapture() doesn't generate captures by the king. I thought it would be a small inaccuracy due to the king not usually involved in capture sequences.

I will do the test positions analysis, but I think this is my biggest misunderstanding now -

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.

Thanks!

[Zach Wegner]

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). The problem is that it only looks at the immediate material gain, not any recaptures. So if the stm captures a defended rook with a queen, it will blindly accept that the capture had to be made because the rook increased the material balance.

The last loop should look something like this, after s is converted to a stack (warning: quickly written, quite likely buggy):

Code: Select all

    while (moves_to_undo > 0) {
        undoMove();
        s ^= 1;
        int new_value = s[moves_to_undo];
        int old_value = s[moves_to_undo - 1];
        if (s == 1)
           new_value = -new_value;
        else
           old_value = -old_value;

        if (new_value > old_value)
           s[moves_to_undo - 1] = s[moves_to_undo];
        moves_to_undo--;
    }
    return s[0];

So you can sort of see how the absolute-side-to-move issue complicates things. Here's the code from ZCT, which uses the negamax relative-side-to-move concept:

Code: Select all

    while (count > 0)
    {
        if (value[count] > -value[count - 1])
            value[count - 1] = -value[count];
        count--;
    }
    return value[0];

[Harald Johnsen]

my genSmallestCapture() doesn't generate captures by the king. I thought it would be a small inaccuracy due to the king not usually involved in capture sequences.

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.

HJ.