SEE

[cms271828]

Hi

I'm thinking about implementing SEE instead of MVVLVA.
Assuming we are generating white captures...
I would loop through all the white pieces, and for each one, obtain a list of 'TO' squares which then get added (if legal).

For SEE, I think it may be quicker to loop through the black pieces, those which have at least 1 white attacker can then be used to create/store the white attacks of that black piece.

Also while that piece is being analyzed to see what its attackers are, we can generate the necessary see value(s) about that black piece (or 'TO' sqaure).

My idea is that some black pieces will be attacked by multiple white pieces so this system avoids looking at the same black pieces twice.

One drawback would be if there was only a white king and say 5 black pieces, then looping through the black pieces would be kind of wasteful.

Any thoughts, I'm not totally sure how SEE works yet either.

[Sven]

Any thoughts, I'm not totally sure how SEE works yet either.

Consider reading this, as a possible starting point.

In practice, you will usually have two functions, one like "see_move()" that returns the SEE value for a given move (and therefore acts like a kind of "root search"), and one like "see_recursive()" that is used within see_move() and works like described in the link above.

There have been some CCC discussions about SEE during the past months, for instance this thread. The CPW entry has been updated since then, as a result of that thread IIRC.

As to your ideas, I am not sure about your key point. Are you thinking about the general algorithm itself, or about an optimization?

Sven

[cms271828]

I was thinking about the algorithm in general.

Bit confused, there appears to be 2 types, the didactic and iterative. I think I understand the didactic after testing out a couple of positions, but I donno about the other one.

I use magic move generation if that is relevant.

[Sven]

I was thinking about the algorithm in general.

Bit confused, there appears to be 2 types, the didactic and iterative. I think I understand the didactic after testing out a couple of positions, but I donno about the other one.

I use magic move generation if that is relevant.

I prefer the third type "Non-didactic", i.e. the real implementation, but still recursive. As soon as you got your recursive algorithm up and running you have the choice to convert it into an equivalent iterative algorithm if optimal performance is an issue for you, or to stick with the recursion. Beginning with a recursive implementation has the advantage of better understanding the concepts before going into the bits deeply. There are other opinions about that, though.

If you like to look at examples, this is "realistic pseudo code" for the essential part of my current (recursive) SEE implementation. The code shown below is independent from the internal board representation, the remaining part has to be filled:

Code: Select all

uint8 attackList[2][15];
uint8 nAttacks[2];


int seeOfCapture(Board const & b, Move const & m, Color side)
{
    buildAttackList(b, m.to(), White);
    buildAttackList(b, m.to(), Black);

    // remove the square of the moving piece from attackList[side]
    int idx = -1;
    for &#40;uint i = 0; idx == -1 && i < nAttacks&#91;side&#93;; i++) &#123;
        if &#40;attackList&#91;side&#93;&#91;i&#93; == m.from&#40;)) &#123;
            idx = i;
        &#125;
    &#125;
    for &#40;uint j = idx; j + 1 < nAttacks&#91;side&#93;; j++) &#123;
        attackList&#91;side&#93;&#91;j&#93; = attackList&#91;side&#93;&#91;j + 1&#93;;
    &#125;
    --nAttacks&#91;side&#93;;

    // do the recursive call
    Piece movingPiece   = b.piece&#40;m.from&#40;));
    Piece capturedPiece = b.piece&#40;m.to&#40;));
    return pieceValue&#91;capturedPiece&#93; - see&#40;b, movingPiece, opp&#40;side&#41;);
&#125;


int see&#40;Board const & b, Piece capturedPiece, Color side&#41;
&#123;
    SqrId sq&#40;popLeastAttacker&#40;b, side&#41;);
    int v = 0;
    if &#40;sq != NoSqrId&#41; &#123;
        v = pieceValue&#91;capturedPiece&#93; - see&#40;b, b.piece&#40;sq&#41;, opp&#40;side&#41;);
    &#125;
    return Max&#40;v, 0&#41;;
&#125;


void buildAttackList&#40;Board const & b, SqrId to, Color side&#41;
&#123;
    nAttacks&#91;side&#93; = 0;
    // put all squares from which 'side' attacks 'to' into attackList&#91;side&#93;
    // based on board repr - up to you &#58;-)
&#125;


SqrId popLeastAttacker&#40;Board const & b, Color side&#41;
&#123;
    // find entry in attackList&#91;side&#93; referencing the least-valued attacker
    // based on board repr - up to you &#58;-)
&#125;

If "seeOfCapture(board, move, side)" returns a value < 0 then the capture can be regarded as a losing capture. In qsearch I skip losing captures while in full search I put them close to the end of the move list. I also restrict use of SEE to those moves where pieceValue[movingPiece] > pieceValue[capturedPiece].

Sven

[hgm]

That is a quite inefficient implementation, as it does not do any kind of alpha-beta pruning, and thus follows the exchange to the very end, even when that is completely futile (e.g. after QxP, PxP, trying to figure out if you can get a second Pawn for your Queen is a waste of time).

An efficient implementation is discussed in the thread you already referred to, at http://www.talkchess.com/forum/viewtopi ... =&start=45 .

[bob]

That is a quite inefficient implementation, as it does not do any kind of alpha-beta pruning, and thus follows the exchange to the very end, even when that is completely futile (e.g. after QxP, PxP, trying to figure out if you can get a second Pawn for your Queen is a waste of time).

An efficient implementation is discussed in the thread you already referred to, at http://www.talkchess.com/forum/viewtopi ... =&start=45 .

I've done it both ways in Crafty. This is a less than 1% issue at very best. And for most cases, it means almost nothing at all.

[Sven]

That is a quite inefficient implementation, as it does not do any kind of alpha-beta pruning, and thus follows the exchange to the very end, even when that is completely futile (e.g. after QxP, PxP, trying to figure out if you can get a second Pawn for your Queen is a waste of time).

An efficient implementation is discussed in the thread you already referred to, at http://www.talkchess.com/forum/viewtopi ... =&start=45 .

Someone who starts implementing SEE for the first time will probably not want to start with something that only you are understanding.

We had discussed that, and Bob had argued that your alpha-beta idea does not improve performance significantly. So I would not call that implementation "inefficient". It is the recursive variant of what most engines are actually doing iteratively. Show me more than one serious engine that uses your alpha-beta approach in SEE, please.

Sven

[bob]

That is a quite inefficient implementation, as it does not do any kind of alpha-beta pruning, and thus follows the exchange to the very end, even when that is completely futile (e.g. after QxP, PxP, trying to figure out if you can get a second Pawn for your Queen is a waste of time).

An efficient implementation is discussed in the thread you already referred to, at http://www.talkchess.com/forum/viewtopi ... =&start=45 .

Someone who starts implementing SEE for the first time will probably not want to start with something that only you are understanding.

We had discussed that, and Bob had argued that your alpha-beta idea does not improve performance significantly. So I would not call that implementation "inefficient". It is the recursive variant of what most engines are actually doing iteratively. Show me more than one serious engine that uses your alpha-beta approach in SEE, please.

Sven

Back up one moment. I have an iterative SEE with the early "exit". And it is barely faster. Once a search is measured in whole seconds (60+ seconds for example) I can't see any difference in search times at all.

I'd _never_ use the recursive approach. That is certainly a questionable solution to a pretty simple problem. It might look a bit neater, but it is also slower.

If you look at the current crafty SEE, you can see the early exit in the place where successive captures are added to the list where when we reach a point where we have played our capture and are _still_ down in material, there is no point in adding more captures to the list. Doing that test every pass thru the loop appears to hurt about as much as it saves when we get out early because of the test. To see the code, look at swap.c, near the bottom of the loop where it flips sides every cycle to find the least valuable attacking piece to use. The test has a "break" on it.

[Sven]

That is a quite inefficient implementation, as it does not do any kind of alpha-beta pruning, and thus follows the exchange to the very end, even when that is completely futile (e.g. after QxP, PxP, trying to figure out if you can get a second Pawn for your Queen is a waste of time).

An efficient implementation is discussed in the thread you already referred to, at http://www.talkchess.com/forum/viewtopi ... =&start=45 .

Someone who starts implementing SEE for the first time will probably not want to start with something that only you are understanding.

We had discussed that, and Bob had argued that your alpha-beta idea does not improve performance significantly. So I would not call that implementation "inefficient". It is the recursive variant of what most engines are actually doing iteratively. Show me more than one serious engine that uses your alpha-beta approach in SEE, please.

Sven

Back up one moment. I have an iterative SEE with the early "exit". And it is barely faster. Once a search is measured in whole seconds (60+ seconds for example) I can't see any difference in search times at all.

I'd _never_ use the recursive approach. That is certainly a questionable solution to a pretty simple problem. It might look a bit neater, but it is also slower.

If you look at the current crafty SEE, you can see the early exit in the place where successive captures are added to the list where when we reach a point where we have played our capture and are _still_ down in material, there is no point in adding more captures to the list. Doing that test every pass thru the loop appears to hurt about as much as it saves when we get out early because of the test. To see the code, look at swap.c, near the bottom of the loop where it flips sides every cycle to find the least valuable attacking piece to use. The test has a "break" on it.

I know your code but I can't see clearly what your argument is. My point was that I did not agree to HGM who said that my approach were inefficient because it did not use his alpha-beta idea. He did not say "recursive therefore inefficient" simply because there is no doubt about that point. We all know that an iterative implementation is faster than the equivalent recursive implementation, and I have always agreed on that. My point was, however, that someone who is new to the SEE topic might initially get a better grasp of the topic by trying the recursive way first. One might think different when it comes to competing with the top 20 engines, which is neither the case for the author of this thread nor for me at the moment. And I also think that the "inefficiency" of the recursive vs. iterative implementation does clearly exist but is not really substantial in terms of ELO. If I need 5 or 10 more ELO points to reach the top 20 then I will probably switch to the more complex iterative way.

It is possible that I misunderstood your post, and that your intent was in fact to agree to my view

EDIT: after rereading, I think you may have replied on my "Show me more than one serious engine that uses your alpha-beta approach in SEE" request. Well, for me your "early exit" is not the same as that alpha-beta approach which appears to be kind of over-designed IMO. Both have the same idea in common, though.

Sven

[bob]

That is a quite inefficient implementation, as it does not do any kind of alpha-beta pruning, and thus follows the exchange to the very end, even when that is completely futile (e.g. after QxP, PxP, trying to figure out if you can get a second Pawn for your Queen is a waste of time).

An efficient implementation is discussed in the thread you already referred to, at http://www.talkchess.com/forum/viewtopi ... =&start=45 .

Someone who starts implementing SEE for the first time will probably not want to start with something that only you are understanding.

We had discussed that, and Bob had argued that your alpha-beta idea does not improve performance significantly. So I would not call that implementation "inefficient". It is the recursive variant of what most engines are actually doing iteratively. Show me more than one serious engine that uses your alpha-beta approach in SEE, please.

Sven

Back up one moment. I have an iterative SEE with the early "exit". And it is barely faster. Once a search is measured in whole seconds (60+ seconds for example) I can't see any difference in search times at all.

I'd _never_ use the recursive approach. That is certainly a questionable solution to a pretty simple problem. It might look a bit neater, but it is also slower.

If you look at the current crafty SEE, you can see the early exit in the place where successive captures are added to the list where when we reach a point where we have played our capture and are _still_ down in material, there is no point in adding more captures to the list. Doing that test every pass thru the loop appears to hurt about as much as it saves when we get out early because of the test. To see the code, look at swap.c, near the bottom of the loop where it flips sides every cycle to find the least valuable attacking piece to use. The test has a "break" on it.

I know your code but I can't see clearly what your argument is. My point was that I did not agree to HGM who said that my approach were inefficient because it did not use his alpha-beta idea. He did not say "recursive therefore inefficient" simply because there is no doubt about that point. We all know that an iterative implementation is faster than the equivalent recursive implementation, and I have always agreed on that. My point was, however, that someone who is new to the SEE topic might initially get a better grasp of the topic by trying the recursive way first. One might think different when it comes to competing with the top 20 engines, which is neither the case for the author of this thread nor for me at the moment. And I also think that the "inefficiency" of the recursive vs. iterative implementation does clearly exist but is not really substantial in terms of ELO. If I need 5 or 10 more ELO points to reach the top 20 then I will probably switch to the more complex iterative way.

It is possible that I misunderstood your post, and that your intent was in fact to agree to my view

EDIT: after rereading, I think you may have replied on my "Show me more than one serious engine that uses your alpha-beta approach in SEE" request. Well, for me your "early exit" is not the same as that alpha-beta approach which appears to be kind of over-designed IMO. Both have the same idea in common, though.

Sven

my comment was with regard to "show me one serious engine that..." Crafty has the early exit (alpha/beta cutoff before enumerating the complete attack list...)