After struggling for more than a week, I finally succeeded in debugging my SEE algorithm. I am now confident my SEE is without bugs.
I wrote a debug_see() using codes that are already available in my chess program - gen_captures(), is_move_valid(), is_side_incheck(). debug_see() is very simple and almost any implementation works and is without bugs; but it generally cannot be used in a strong program as SEE has to be customized to just pick captures at the exchange squares and not generate all captures as in the gen_captures() used in QS.
I think SEE contributes much to the strength of an engine (possibly 50 - 100 ELO ?). SEE prunes QS captures when SEE loses material - SEE returns gain < 0. I think all strong engines would use SEE to sort quiet moves (delaying, not pruning) to the tail - I can't think of a reason why it should not be done. But one has to 'work' and do the coding! A specially customized SEE is a little complex - this is what I just found in the course of debugging my SEE. But a buggy SEE does nothing but prunes what it should not prune and the gain in ELO may be just zero!
I had my SEE for a few years and never debug it. When I first coded SEE, I could not find an easy way to debug it nor did I think it contributes much to strength - I think I was wrong. So it was used without debugging. What I just discovered is that there are some subtleties in SEE and anyone coding SEE without reference can easily missed them. I found out when SEE and debug_see() returns different scores. I printed out the positions (wrote my fen parser) and examined them in xboard.
1) SEE and debug_see do not return the same values even though both are bug-free! When a side has to pick a capture and there a more then a piece of the same type to choose, then SEE returns different gain/loss depending on which piece is picked; e.g. if there are two P that can capture, one may have a friendly slider following at the rear; the other may have an opponent slider following behind. So how is it to be resolved - I think it is not feasible to code SEE as a search of all possible lines. So what must be done? As another example, if two N can capture, one may release a discovered check of the other side in which case SEE stops.
2) Discovered checks - I think a good SEE need to have it.
3) Promotion of pawns to Queen - I think it need to be taken into consideration. When a P is pushed or captures and promotes to Q, then if the other side captures, it should be a gain of Q - P and not just a P.
A customized bitboard SEE is prone to bugs and it is rare that one who codes SEE the first time have it right at the first try - unless, of course, one is a Richard Vida; or a Robert Houdart ?
Here is my debugged debug_see() codes - it is just simple.
Code: Select all
int debug_see(const move_t move, const int side, const int incheck) {
int x, gain, at = TO(move), targ = BRD_PC(at);
int ply = 0;
if (is_move_valid(move, side, incheck));
else {
return SEE_INVALID;
}
makemove(move, side);
gain = vPiece[targ];
x = -see_search(at, side ^ 1, -gain, ply + 1);
assert(x > -INFI && x < INFI);
unmake(move, side);
if (x < 0) {
return SEE_PRUNE;
}
return 0;
}
static int see_search(const int at, const int side, int gain, int ply) {
move_t *move, list[256];
check_t check_s;
const int targ = BRD_PC(at);
int x, pc, incheck;
assert(gain <= 0);
assert(gain + vPiece[targ] >= 0);
getSideIncheck(&check_s, side);
incheck = check_s.type;
/* If there is a discovered check, SEE stops.*/
if (incheck && (check_s.sq ^ at || incheck == DBL_CHECK)) {
/* Side incheck by discovered check; SEE stops. The only way to
* evade check and to capature at the same time is when there is a king's capture - and it must be valid.
*
* !!! is_move_valid() assumes a king's to-sq is not under attack by P/N/K
*/
if (kMap[at] & bits[side][King] && !IS_SQ_ATTACKED_PNK(at, side ^ 1)) {
/* determine If king's evasion move is free of slider threat */
list[0] = king[side] | (at << 6);
list[1] = 0;
} else {
return gain;
}
} else {
/* gen() must be in order of P/N/B/R/Q/K */
gen(list, side, GEN_QS_NO_EXCLUDE_CAPTURE, -INFI, 0);
}
for (move = list; *move; ++move) {
if (TO(*move) == at && is_move_valid(*move, side, incheck)) {
/* if captures does not equalize material, SEE stops and the side lost. */
gain += vPiece[targ];
assert(gain >= 0);
pc = BRD_PC(FROM(*move));
if (pc == King || (gain - vPiece[pc] > 0)) {/* side wins */
return gain;
}
makemove(*move, side);
x = -see_search(at, side ^ 1, -gain, ply + 1);
assert(x > -INFI && x < INFI);
unmake(*move, side);
return x; /* gain */
}
}
return gain;
}
Rasjid.
