SEE implemented the wrong way?

[flok]

Hi,

I've been trying to implement SEE in QS. After 20k games played it looks like the non-see is 13 elo better, not good.
I don't see what I'm doing wrong here. Maybe any of you?

Code: Select all

To reduce the number of variables that need to be pushed on the stack, I've put the ones that stay the same in a structure that is passed as a parameter.

Scene *s is an object that keeps the board structure, the chess piece info, etc

MoveList *mls[2] are the lists of moves for white and for black

mlIndex[2] is, for white and for black, the position in their movelists. That way I don't need to remove the ones I processed from the list.

bool first is magic so that the first move processed is the one in the movelist we're working on in quiesceSearch(). That way the 2nd and so on are again from the beginning of the list.

targetx/y are the field we're working on

typedef struct
{
        Scene *s;
        MoveList *mls[2];
        size_t mlIndex[2];
        bool first;
        int targetx, targety;
} see_pars_t;

int see(see_pars_t *const sp, const PlayerColor c)
{
// get a pointer to the board-structure (8x8)
        Board *b = sp -> s -> getBoard();

        Move m;
        for(;;) {
// get a move from the movelist of the current color (c)
                m = sp -> mls[c] -> at(sp -> mlIndex[c]);

                sp -> mlIndex[c]++;

                if (sp -> first) {
                        sp -> mlIndex[c] = 0;
                        sp -> first = false;
                }

// if it is not a capture move (or end of list reached) then stop going through the
// movelist. the lists are sorted, captures (and promotions) first
                if (m.isCatchMove == false || sp -> mlIndex[c] >= sp -> mls[c] -> size())
                        return 0;
// if the piece the current move "points to" has already been moved, then we cannot
// use this move
                if (b -> getAt(m.fx, m.fy) == NULL)
                        continue;

// this move targets the move? then use it
                const ChessPiece *victim = b -> findVictim(m);
                if (victim && victim -> getX() == sp -> targetx && victim -> getY() == sp -> targety)
                        break;
        }

// find the evaluation-value of the piece that's on the target-field
        int eval = b -> getAt(sp -> targetx, sp -> targety) -> getEvalVal();

        sp -> s -> doMove(m);
// subtract the value of a call to see() for the opponent color
        eval -= see(sp, opponentColor(c));
        sp -> s -> undoMove();

        return eval;
}

int quiesceSearch()
{
   for(Move *m : moves) {
      bool icm = m -> isCatchMove;
      if (ivm) {
                        sp.first = true;
                        sp.mlIndex[c] = idx;
                        sp.mlIndex[opponentColor(c)] = 0;

                        sp.targetx = m -> tx;
                        sp.targety = m -> ty;

                        int seeVal = see(&sp, c);

                        icm = m -> promoteTo != NONE ? seeVal >= 0 : seeVal > 0;
       }

       if (icm) {
           // do move (doMove() ; quiesceSearch() ; undoMove() and so on)
      }
}

[Henk]

Maybe adding alpha, beta and a maximal depth to SEE helps.

[brtzsnr]

Your algorithm looks correct. However, SEE must be very fast in order to provide any benefit in QS. A simple QS is faster than doing several DoMove/UndoMove for every move tested is slow.

The SWAP algorithm is close to what I use. A mock implementation can be found at: https://chessprogramming.wikispaces.com ... +Algorithm

For testing and performance measuring purposes I implemented both algorithms. The SWAP algorithm is 12x faster than the slow version which is very close to what you have:

Code: Select all

BenchmarkSEESlow-16               100000             16046 ns/op
BenchmarkSEEFast-16              1000000              1372 ns/op

[Evert]

One of the key points is that you don't actually have to make moves on the board, which is needlessly slow. You just need to have a function that gives you a list of pieces that attack a particular square and loop over that until the list for either side is clear. You can speed up SEE by an order of magntude or more this way.

Of course it doesn't need to be an actual list. I use either a bitboard, or a bitmask representing an entry in a piece list.

[hgm]

You have to be careful not to miss the X-ray attacks, however. In Joker's SEE I use an auxiliary board to mark pieces that are used, or were found to be the single blocker of an aligned slider. So that when it is the blocker's turn to be used, it rewinds the attackers list to the X-ray attacker.

My eventual conclusion, however, was that a full-blown SEE does not really pay off. Long exchanges do not occur often, and the side effects of the captures to the given square (by using soft-pinned or overloaded pieces) accumulate, so that deep SEEs almost never give the correct result. So my later engines do not use SEE but BLIND: only attempt to capture a Lesser piece If it is Not Defended. Capture of protected lower-valued pieces are treated as bad captures.

[Daniel Anulliero]

In Isa , I don't have SEE yet , only MVV/LVA
I don't understand how implement SEE without costly making / unmaking moves , to check if a capture is legal or illegal :
An exemple with a position (imaginary) :
[d]3r2k1/1b3ppp/pp3p2/3n4/P3P3/1PN2P2/r2R1KPP/3R4 w - - 0 5

Here the engine want to know the value of SEE for the capture at d5

Pxd5(+300) Bxd5(+100)
Nxd5(+300) Rxd5(+300)
see = 300 - 100 + 300 - 300 = +200
Here Rd2xd5 is illegal because the black rook at a2

Nxd5(+300) Rxd5(+300)
Pxd5(+500) Bxd5(+100)
see = 300 - 300 + 500 - 100 = +400

Ok so , how to check Rd2xd5 is illegal without making / unmaking loves ?
SEE must have a routine to control this kind of illegal moves right?

[flok]

Will give blind a try!
A first test showed a dramatic result: depth 9 in 2.6s instead of 3.4s.

[hgm]

Here the engine want to know the value of SEE for the capture at d5

Pxd5(+300) Bxd5(+100)
Nxd5(+300) Rxd5(+300)
see = 300 - 100 + 300 - 300 = +200
Here Rd2xd5 is illegal because the black rook at a2

Nxd5(+300) Rxd5(+300)
Pxd5(+500) Bxd5(+100)
see = 300 - 300 + 500 - 100 = +400

Ok so , how to check Rd2xd5 is illegal without making / unmaking loves ?
SEE must have a routine to control this kind of illegal moves right?

Actually it is much worse than that, and a good illustration for how useless deep SEE in general is: at any time white can play Rxa2 and black can play Rxd2+, completely upsetting the SEE calculation. Even for calculating what Pxd5 would do as alternative for Rxa2, the exchange listed above has zero reality value. After Pxd5 Bxd5 white would continue with Rxa2, solving the pin and grabbing a Rook. Black would be forced to play Rxd2 first to save Ra2, but this would involve the other Rook in the battle for d5 by the white recapture Rxd2.

[zd3nik]

In Isa , I don't have SEE yet , only MVV/LVA
I don't understand how implement SEE without costly making / unmaking moves , to check if a capture is legal or illegal :
An exemple with a position (imaginary) :
[d]3r2k1/1b3ppp/pp3p2/3n4/P3P3/1PN2P2/r2R1KPP/3R4 w - - 0 5

Here the engine want to know the value of SEE for the capture at d5

Pxd5(+300) Bxd5(+100)
Nxd5(+300) Rxd5(+300)
see = 300 - 100 + 300 - 300 = +200
Here Rd2xd5 is illegal because the black rook at a2

Nxd5(+300) Rxd5(+300)
Pxd5(+500) Bxd5(+100)
see = 300 - 300 + 500 - 100 = +400

Ok so , how to check Rd2xd5 is illegal without making / unmaking loves ?
SEE must have a routine to control this kind of illegal moves right?

I think this a perfect example of when *not* to use SEE. IMO you only need to do SEE on exchanges that potentially lose material.

A PAWNxMINOR capture can't lose material and therefore doesn't need SEE and should never be pruned in qsearch unless your deficit is greater than a minor piece.

A MNIORxMINOR capture can't lose material and therefore doesn't need SEE and should never be pruned in qsearch unless your deficit is greater than a minor piece.

And in this case RxN is illegal (as move 1 in the exchange) so SEE on that move should never be considered anyway. How it effects the other 2 exchange variations is also irrelevant in this scenario for the reasons given in the 2 points above. If there are subtleties in the position that make the 2 points above untrue, SEE isn't going to compensate for it unless you have a REALLY amazing SEE routine.

An approach I used in some of my engines is: if the piece being captured is defended and is worth less than the piece doing the capture do SEE or simply score the move as (CaptureValue - CapturingPieceValue). That seems to work well for move ordering and for deciding which moves to prune in deep quiescence (e.g. qsearch were depth < 0). SEE is just as prone to overlook subtleties (such as mate threats) as this simple logic. If you want to make sure you don't overlook the subtleties you have to do the search. Pruning is *always* a gamble.

In my most recent engine I have a very smart and reasonably fast SEE (it uses bitboards and it accounts for x-ray attackers). I have not noticed that it has provided any better results than what I just described above. It's no worse either, so I'm still using it with the hope that it will be worth the extra complexity in some rare scenarios, but that's just hope.

There is no one-size-fits-all approach. But I definitely suggest trying the simplest approach first. You then have a benchmark to compare against if you think you need to try the more complicated stuff later.

[hgm]

SEE is also pretty meaningless when there are threats against the stm. In the face of a PxR threat, you can theorize whether RxB should be tried before or after PxN, based on whether the B is protected or not, and the value of this protector. But that is all moot, because even P x unprotected N would be met with the pre-existing PxR.

A QS strategy I experimented with, and which was reasonably succesful, was 'auto-fail': if you can play a move with an 'obvious gain' more than what the opponent captured on the ply before, you return beta without search. 'Obvious gain' is defined as the difference between victim value and attacker value for protected pieces, or victim value for unprotected pieces.

This rule prunes most SEE-wise bad captures, but also SEE-wise good captures that are stupid because of a counter threat. The idea is that when your material balance deteriorates in two successive plies, you just made it more difficult to reach alpha then when you would have refrained from playing them.