Question about SEE (Static exchange evaluation)

[OliverBr]

Apparently most chess engines use the SEE for cutting down the tree especially in the quiescence search. So did OliThink 4, too.

But I think there is a big problem with SEE. When collecting all those pieces who attack the very square, they are not tested for soft pins. So it could easily be that at the end of SEE the opposite color can capture a big stone but it won't be considered as the SEE already cut down the search.

Is this a known problem? If yes, what are to solutions for it?

PS: I created an example:
k2r1r2/1p6/p1b5/3p4/8/2N2B1P/6P1/3R1Q1K b - - 0 1

A SEE would give here a clear material win for white capturing the pawn on d5, but it's not true, as the bishop is soft pinned.

[bob]

Apparently most chess engines use the SEE for cutting down the tree especially in the quiescence search. So did OliThink 4, too.

But I think there is a big problem with SEE. When collecting all those pieces who attack the very square, they are not tested for soft pins. So it could easily be that at the end of SEE the opposite color can capture a big stone but it won't be considered as the SEE already cut down the search.

Is this a known problem? If yes, what are to solutions for it?

PS: I created an example:
k2r1r2/1p6/p1b5/3p4/8/2N2B1P/6P1/3R1Q1K b - - 0 1

A SEE would give here a clear material win for white capturing the pawn on d5, but it's not true, as the bishop is soft pinned.

Yes there are errors. soft pins. Absolute pins (on the king). Overloaded pieces, overloaded defenders, the list goes on and on. But, fortunately, the trees we search are beyond enormous, so that the errors have little if any effect on the program's performance in a real game...

Correcting the problems would actually hurt play much more because it would slow the SEE down so much the lost search depth would more than offset the increased accuracy, and produce worse results overall...

[hgm]

SEE is not QS, and does not have the pretention to be QS. The soft pins you mention are something you can only expect to see in QS.

Actually the usefulness of SEE is very limited. Joker uses it only to order HxL captures (where the SEE value replaces the victim value as primary sort key), and to prune 'bad' (HxL) captures in QS. And in the bulk of cases it basically do nothing else than find out if the piece was defended. Refraining from Hx(defended L) captures (BLIND) is not significantly less accurate than SEE. It does not consider second attacker and defender, which SEE does, but compared to all other things that SEE ignores (e.g. if these attackers and defenders, in the comparatively rare cases they exist, are (soft) pinned or overloaded or themselfs under attack and tradable) this hardly makes any difference.

[OliverBr]

Yes there are errors. soft pins. Absolute pins (on the king).

Absolute pins... oh, this is an tremendous error, I remember in OliThink 4 I didn't take them out, but I'am planning to do for OliThink 5. But of course I can hardly avoid that piece will be set in in absolute because a other piece disappeared virtually in SEE...

Overloaded pieces, overloaded defenders, the list goes on and on. But, fortunately, the trees we search are beyond enormous, so that the errors have little if any effect on the program's performance in a real game...

In my current implemention of OliThink I want to avoid any pruning/trick/cutting which isn't loss free. So this is like Null Move heuristic a technique which can lead to oversee a good/bad move.

Correcting the problems would actually hurt play much more because it would slow the SEE down so much the lost search depth would more than offset the increased accuracy, and produce worse results overall...

Actually to get rid off absolute pins at start of SEE I think I found a very fast solution which accelerate my move generation. Furthermore the bitboard containing the absolute pins can be reused for normal move generation.

Code: Select all

u64 pinnedPieces(int f, int oc) {
	u64 pin = 0LL;
	u64 b = ((RXRAY1(f) | RXRAY2(f)) & colorb[oc]) & RQU;
	while (b) {
		int t = pullLsb(&b);
		pin |= RCAP(t, oc) & ROCC(f);
	}
	b = ((BXRAY3(f) | BXRAY4(f)) & colorb[oc]) & BQU;
	while (b) {
		int t = pullLsb(&b);
		pin |= BCAP(t, oc) & BOCC(f);
	}
	return pin;
}

f: square of the king
oc: opposite color
R/BQU: Bitboards representing all QueenRooks/QueenBishops
R/BXRAY*: Bitboards of pieces in xray (either color)
R/BCAP: All possible capture moves for Rook/Bishop on square t
R/BOCC:All occupied (first blockers) squares for Rook/Bishop on square t

[OliverBr]

SEE is not QS, and does not have the pretention to be QS. The soft pins you mention are something you can only expect to see in QS.

Actually the usefulness of SEE is very limited. Joker uses it only to order HxL captures (where the SEE value replaces the victim value as primary sort key), and to prune 'bad' (HxL) captures in QS. And in the bulk of cases it basically do nothing else than find out if the piece was defended. Refraining from Hx(defended L) captures (BLIND) is not significantly less accurate than SEE. It does not consider second attacker and defender, which SEE does, but compared to all other things that SEE ignores (e.g. if these attackers and defenders, in the comparatively rare cases they exist, are (soft) pinned or overloaded or themselfs under attack and tradable) this hardly makes any difference.

I wanted to avoid to use SEE because of the problems we are discussing, but then I saw, that my engine produced a lot of more Nodes in QS than e.g. gnuchess5 does.
Actually up to 40% of the total nodes are in QS which is way to much (Gnuchess 5 has never more than 20% and the only cutting in QS I see there is a SEE)

You think SEE can rather help ordering my moves in QS to decreas the number of nodes?

[hgm]

Well, good move ordering in general reduces node count in an alpha-beta tree. Looking at many nodes is not necessarily bad, as the chances that you will discover something will also go up. But you don't want to waste time on nodes that later turn out to be irrelevant (i.e., wuld have been out of window with good move ordering), and you don't want to waste times on nodes with a very low probability of being relevant. Capturing defended pieces with a higher piece has a much smaller probability of being relevant than other moves, so you gain by pruning them.

[Thomas Gaksch]

Hello Oliver,
you can reduce a lot of nodes in QS if you only take capture moves where SEE >= 0.

For example fruit only tries capture moves which are "good" in qs. Here is the code:

static bool capture_is_good(int move, const board_t * board) {

int piece, capture;

ASSERT(move_is_ok(move));
ASSERT(board!=NULL);

ASSERT(move_is_tactical(move,board));

// special cases

if (MOVE_IS_EN_PASSANT(move)) return true;
if (move_is_under_promote(move)) return false; // REMOVE ME?

// captures and queen promotes

capture = board->square[MOVE_TO(move)];

if (capture != Empty) {

// capture

ASSERT(move_is_capture(move,board));

if (MOVE_IS_PROMOTE(move)) return true; // promote-capture

piece = board->square[MOVE_FROM(move)];
if (VALUE_PIECE(capture) >= VALUE_PIECE(piece)) return true;
}

return see_move(move,board) >= 0;
}

it helps really a lot.

Thomas

[Gerd Isenberg]

Actually to get rid off absolute pins at start of SEE I think I found a very fast solution which accelerate my move generation. Furthermore the bitboard containing the absolute pins can be reused for normal move generation.

Code: Select all

u64 pinnedPieces(int f, int oc) {
	u64 pin = 0LL;
	u64 b = ((RXRAY1(f) | RXRAY2(f)) & colorb[oc]) & RQU;
	while (b) {
		int t = pullLsb(&b);
		pin |= RCAP(t, oc) & ROCC(f);
	}
	b = ((BXRAY3(f) | BXRAY4(f)) & colorb[oc]) & BQU;
	while (b) {
		int t = pullLsb(&b);
		pin |= BCAP(t, oc) & BOCC(f);
	}
	return pin;
}

f: square of the king
oc: opposite color
R/BQU: Bitboards representing all QueenRooks/QueenBishops
R/BXRAY*: Bitboards of pieces in xray (either color)
R/BCAP: All possible capture moves for Rook/Bishop on square t
R/BOCC:All occupied (first blockers) squares for Rook/Bishop on square t

Fine idea to lookup the xrays. I like to mention your idea in the wiki.

The other approach is to use rook- and bishop-wise attacks from own king square, to intersect it with own pieces for potential pinned pieces. Those potential pinned pieces are then temporary removed from the occupancy for a second attack-lookup. Xray is then the set-difference (xor) of both attack sets, which is intersected with opponent relevant sliders to get the pinning pieces without any branches.

Code: Select all

rookWise  = rookAttacks(occ, kiSq);
potPinned = rookWise & ownPieces;
xrays     = rookWise ^ rookAttacks(occ ^ potPinned, kiSq);
pinners   = xrays    & oppoRookOrQueen;

pinned    = 0;
while ( pinners )
{
    pinnerSq = bitScanForward(pinners);
    pinned  |= potPinned & obstructed[pinnerSq][kiSq]);
    pinners &= pinners - 1;
}
... same for bishops/queens

Thus, your approach is the faster precondition for

Code: Select all

opponentSlider->ownOrOpponentPiece->ownKing

while the other approach already determines the pinners but no discovered checks by the opponent...

Code: Select all

opponentSlider->ownPiece->ownKing

and may postpone the loop to get pinned pieces, since each pinner implies one pinned piece.
Since absolute pins and opponent discovered checkers are quite rare, I assume your approach the faster one. I guess even more if you somehow reuse the possible discovered checkers of the opponent, you'll might get en passant to trigger some take care flag for eval and elsewhere.

[OliverBr]

Hello Oliver,
you can reduce a lot of nodes in QS if you only take capture moves where SEE >= 0.

I see. This seems to be a common pattern. but I think it is dangerous. I can create situations where SEE is just wrong (due to pinned pieces), and so you leave out good moves in your QS. This yields to different results...

[hgm]

Yes, it is a form of pruning. Only alpha-beta pruning is absolutely safe.

But it is like I said before: by pruning nodes with a below-average probability to be good, you can use the time to search other nodes with above-average probability to be good, which you could otherwise not have searched. And by not searching the latter, on the average you would make more mistakes than by not searching the former. Although there will always be some mistakes you make by not searching a node.

If the aim was to just minimize the number of nodes, it would be very easy. Simply reduce every move in the root by one ply...