SEE

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

SEE

Post by Chan Rasjid » Mon Feb 25, 2013 3:59 pm

Hello,

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&#40;const move_t move, const int side, const int incheck&#41; &#123;
    int x, gain, at = TO&#40;move&#41;, targ = BRD_PC&#40;at&#41;;
    int ply = 0;

    if &#40;is_move_valid&#40;move, side, incheck&#41;);
    else &#123;
        return SEE_INVALID;
    &#125;

    makemove&#40;move, side&#41;;
    gain = vPiece&#91;targ&#93;;
    x = -see_search&#40;at, side ^ 1, -gain, ply + 1&#41;;
    assert&#40;x > -INFI && x < INFI&#41;;
    unmake&#40;move, side&#41;;

    if &#40;x < 0&#41; &#123;
        return SEE_PRUNE;
    &#125;

    return 0;
&#125;

static int see_search&#40;const int at, const int side, int gain, int ply&#41; &#123;
    move_t *move, list&#91;256&#93;;
    check_t check_s;
    const int targ = BRD_PC&#40;at&#41;;
    int x, pc, incheck;

    assert&#40;gain <= 0&#41;;
    assert&#40;gain + vPiece&#91;targ&#93; >= 0&#41;;

    getSideIncheck&#40;&check_s, side&#41;;
    incheck = check_s.type;

    /* If there is a discovered check, SEE stops.*/
    if &#40;incheck && &#40;check_s.sq ^ at || incheck == DBL_CHECK&#41;) &#123;
        /* 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&#40;) assumes a king's to-sq is not under attack by P/N/K 
         */
        if &#40;kMap&#91;at&#93; & bits&#91;side&#93;&#91;King&#93; && !IS_SQ_ATTACKED_PNK&#40;at, side ^ 1&#41;) &#123;
            /* determine If king's evasion move is free of slider threat */
            list&#91;0&#93; = king&#91;side&#93; | &#40;at << 6&#41;;
            list&#91;1&#93; = 0;
        &#125; else &#123;
            return gain;
        &#125;
    &#125; else &#123;
        /* gen&#40;) must be in order of P/N/B/R/Q/K */
        gen&#40;list, side, GEN_QS_NO_EXCLUDE_CAPTURE, -INFI, 0&#41;;
    &#125;

    for &#40;move = list; *move; ++move&#41; &#123;
        if &#40;TO&#40;*move&#41; == at && is_move_valid&#40;*move, side, incheck&#41;) &#123;
            /* if captures does not equalize material, SEE stops and the side lost. */
            gain += vPiece&#91;targ&#93;;
            assert&#40;gain >= 0&#41;;
            pc = BRD_PC&#40;FROM&#40;*move&#41;);
            if &#40;pc == King || &#40;gain - vPiece&#91;pc&#93; > 0&#41;) &#123;/* side wins */
                return gain;
            &#125;

            makemove&#40;*move, side&#41;;
            x = -see_search&#40;at, side ^ 1, -gain, ply + 1&#41;;
            assert&#40;x > -INFI && x < INFI&#41;;
            unmake&#40;*move, side&#41;;
            return x; /* gain */
        &#125;
    &#125;

    return gain;
&#125;
Best Regards,
Rasjid.
Don't believe when you're told "There's no free lunch!" There is Linux.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: SEE

Post by ZirconiumX » Mon Feb 25, 2013 4:17 pm

Chan Rasjid wrote:Hello,

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.

<snip>

Best Regards,
Rasjid.
1) Assume the opponent captures with his least valuable piece.
2) Lucas Braesch does this - I suggest you examine DiscoCheck for how to do this.
3) See above.

Note that for a pure speed engine - 2 and 3 may be a regression because it slows down the engine.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: SEE

Post by hgm » Mon Feb 25, 2013 4:59 pm

I would be very surprised if SEE would even gain you 10 Elo.

I would not worry too much about the 'foe-backed captures'. See is inherently unreliable (it does not take into account things like soft-pinning or overloading of the capturers). When you have foe-backed capturers, it would totally suck in most cases anyway. Because the assumption that the exchange will be limited to a single square is completely flawed in such cases. The blocked enemy slider will also attack the capturer, and usually the capturer will attack it back. If one of the two will be more valuable than the other, it usually pays to capture that in stead of on the target square. Imagine two Rooks attacking a Pawn from different direction, but one of those has a Queen of the opponent behind it. Which of the two should I use to capture the Pawn? (Answer: none. Capture the Queen in stead!) Now suppose the Pawn was attacked by two Queens, with an enemy Rook behind one of them. Should I capture with the other first, so that tha Queen keeps 'blocking' the Rook? (Bye bye Queen, despite it being a SEE-wise 'good capture'!).

In general, how would you know if the piece blocking the enemy slider is (sufficiently) protected? Not using it to capture first might make the opponent retaliate against that piece, rather than against the target square (which is likely a less valuable target, as you decided to use it first).

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: SEE

Post by Chan Rasjid » Mon Feb 25, 2013 5:37 pm

Hello,
hgm wrote:I would be very surprised if SEE would even gain you 10 Elo.

I would not worry too much about the 'foe-backed captures'. See is inherently unreliable (it does not take into account things like soft-pinning or overloading of the capturers). When you have foe-backed capturers, it would totally suck in most cases anyway. Because the assumption that the exchange will be limited to a single square is completely flawed in such cases. The blocked enemy slider will also attack the capturer, and usually the capturer will attack it back. If one of the two will be more valuable than the other, it usually pays to capture that in stead of on the target square. Imagine two Rooks attacking a Pawn from different direction, but one of those has a Queen of the opponent behind it. Which of the two should I use to capture the Pawn? (Answer: none. Capture the Queen in stead!) Now suppose the Pawn was attacked by two Queens, with an enemy Rook behind one of them. Should I capture with the other first, so that tha Queen keeps 'blocking' the Rook? (Bye bye Queen, despite it being a SEE-wise 'good capture'!).

In general, how would you know if the piece blocking the enemy slider is (sufficiently) protected? Not using it to capture first might make the opponent retaliate against that piece, rather than against the target square (which is likely a less valuable target, as you decided to use it first).
What you say is logic - I agree your analysis is flawless pertaining precisely to the situations you mentioned.

Many things do not get solved just through logical reasoning alone. Just like the game of chess from the start position, there are too many factors to consider and the game is not solved. The only way to find out is, of course, testing. I believe your ELO of 10 is surely wrong - it should have been a -30 ELO! it prunes what it should not and sort backwards what causes an xray check!

My instinct somehow says it is very valuable. It is not without reason that all top programs have it. Don Dailey also mentioned exactly the use of SEE as in my post. Sorting is only about likelihood of it been correct - most of the time. QS SEE pruning is about pruning the big capturing the small and SEE cannot add much wrong by pruning when gain < 0.

The proof of eating is the pudding. The following game shows Cowrie winning against Stockfish. For the matter, Cowrie was using a SEE that was half-baked (not fully debugged, but worth 600 ELO) and with futility pruning, LMR and nullmove disabled (not confident they were working yet).
[Event "Computer Chess Game"]
[Site "mycomputer"]
[Date "2013.02.23"]
[Round "-"]
[White "Stockfish 2.2.2 JA"]
[Black "Cowrie Ver 1.0"]
[Result "1/2-1/2"]
[TimeControl "60/30"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 Bc5 4. O-O Nf6 5. Nxe5 O-O 6. Bxc6 dxc6 7. d3
Re8 8. Nf3 Bg4 9. Nc3 a5 10. h3 Bh5 11. Be3 Bd6 12. a3 h6 13. g4 Nxg4 14.
hxg4 Bxg4 15. d4 Qf6 16. Kg2 Qg6 17. Rg1 Rxe4 18. Nxe4 Qxe4 19. Rh1 h5 20.
c4 Re8 21. c5 Re6 22. Kf1 Bxf3 23. Rh4 Bg2+ 24. Kg1 Qxh4 25. Kxg2 Bxc5 26.
Rc1 Bb6 27. b4 Re4 28. Qf3 Rg4+ 29. Kf1 axb4 30. axb4 Bxd4 31. Rc4 g6 32.
Ke2 Qe7 33. Kd3 Bxe3 34. Rxg4 hxg4 35. Qxe3 Qxb4 36. Ke2 Kf8 37. Qg3 Qe7+
38. Kf1 f5 39. Qc3 Qd6 40. Qh8+ Kf7 41. Qh7+ Kf6 42. Qh8+ Kg5 43. Qa1 g3
44. fxg3 Qxg3 45. Qa8 Qf3+ 46. Ke1 Qe3+ 47. Kd1 Qd3+ 48. Ke1 Qc3+ 49. Kd1
Qb3+ 50. Ke1 Qb4+ 51. Ke2 Qc4+ 52. Kd2 Qd4+ 53. Kc1 Qc3+ 54. Kd1 Qd3+ 55.
Ke1 Qe4+ 56. Kd1 Qd4+ 57. Kc1 Qg1+ 58. Kd2 Qg2+ 59. Kc1 Qf1+ 60. Kc2 Qc4+
61. Kd2 Qf4+ 62. Kc2 Qe4+ 63. Kd1 Qf3+ 64. Ke1 Qc3+ 65. Kd1
{Draw by repetition} 1/2-1/2


Best Regards,
Rasjid.
Don't believe when you're told "There's no free lunch!" There is Linux.

User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: SEE

Post by hgm » Mon Feb 25, 2013 6:08 pm

In my experience it is only important to recognize the case 'unprotected piece', and SEE is needlessly expensive to do that. For equal and Low x High captures you are not interested in any case, as these go always by MVV/LVA. You would want to try gobbling up a hanging piece first even if it is with High x Low, however. Anything more complex is better postponed, or cancelled if it is obviously bad (i.e. you could never get ahead, even when the recapturer would be unprotected, e.g. after QxB which is protected by R, as B+R < R). Lettig QS figure out how complex exchanges work is much more reliable than letting SEE do it, and not that much more expensive. So I always use BLIND, rather than SEE (Better, or Lower If Not Defended).

User avatar
lucasart
Posts: 2991
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: SEE

Post by lucasart » Mon Feb 25, 2013 11:12 pm

ZirconiumX wrote:
Chan Rasjid wrote: 2) Discovered checks - I think a good SEE need to have it.
2) Lucas Braesch does this - I suggest you examine DiscoCheck for how to
As far as I know, my SEE doesn't handle discovered checks. What it does do, is en-passant capture and promotion (including promoting recaptures). It is based on Glaurung's SEE (improved to handle en-passant and promotion). Note that Glaurung uses the iterative approach, rather than recursive.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

bob
Posts: 20357
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: SEE

Post by bob » Tue Feb 26, 2013 2:36 am

hgm wrote:I would be very surprised if SEE would even gain you 10 Elo.

I would not worry too much about the 'foe-backed captures'. See is inherently unreliable (it does not take into account things like soft-pinning or overloading of the capturers). When you have foe-backed capturers, it would totally suck in most cases anyway. Because the assumption that the exchange will be limited to a single square is completely flawed in such cases. The blocked enemy slider will also attack the capturer, and usually the capturer will attack it back. If one of the two will be more valuable than the other, it usually pays to capture that in stead of on the target square. Imagine two Rooks attacking a Pawn from different direction, but one of those has a Queen of the opponent behind it. Which of the two should I use to capture the Pawn? (Answer: none. Capture the Queen in stead!) Now suppose the Pawn was attacked by two Queens, with an enemy Rook behind one of them. Should I capture with the other first, so that tha Queen keeps 'blocking' the Rook? (Bye bye Queen, despite it being a SEE-wise 'good capture'!).

In general, how would you know if the piece blocking the enemy slider is (sufficiently) protected? Not using it to capture first might make the opponent retaliate against that piece, rather than against the target square (which is likely a less valuable target, as you decided to use it first).
It actually gains quite a bit. From the following things:

(1) you can eliminate a BUNCH of futile captures in the q-search, greatly reducing the size of the qsearch tree. Speed gain of 2x is certainly doable.

(2) you can use SEE to detect "spite checks" that are pointless, and refuse to extend them, saving search space. Ditto for other moves you might want to look at on the surface because they look interesting, but with SEE you see they are unsafe.

I could turn the stuff off in my q-search...

Here are a couple of quick runs. with only the q-search (so-called "delta" pruning" disabled (the part that uses swap)).


log.001: time=10.65 mat=0 n=55650241 fh=93%, cf=92 nps=5.2M
log.002: time=5.21 mat=0 n=24825524 fh=94%, cf=47 nps=4.8M

(first is SEE disabled, second is on).

log.001: time=52.66 mat=0 n=268289225 fh=93%, cf=100 nps=5.1M
log.002: time=15.73 mat=0 n=72612868 fh=93%, cf=9 nps=4.6M

So at least a factor of 2x, which is 50-70, and I did not remove the extension selection tests or any other uses of Swap(), just q-search...

I do agree with your "don't waste time on the enhancements, since SEE is nothing more than a rough approximation." But since the q-search is a rough approximation as well (most of the time the best move is not a capture, yet that is all it considers).

bob
Posts: 20357
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: SEE

Post by bob » Tue Feb 26, 2013 2:39 am

Chan Rasjid wrote:Hello,
hgm wrote:I would be very surprised if SEE would even gain you 10 Elo.

I would not worry too much about the 'foe-backed captures'. See is inherently unreliable (it does not take into account things like soft-pinning or overloading of the capturers). When you have foe-backed capturers, it would totally suck in most cases anyway. Because the assumption that the exchange will be limited to a single square is completely flawed in such cases. The blocked enemy slider will also attack the capturer, and usually the capturer will attack it back. If one of the two will be more valuable than the other, it usually pays to capture that in stead of on the target square. Imagine two Rooks attacking a Pawn from different direction, but one of those has a Queen of the opponent behind it. Which of the two should I use to capture the Pawn? (Answer: none. Capture the Queen in stead!) Now suppose the Pawn was attacked by two Queens, with an enemy Rook behind one of them. Should I capture with the other first, so that tha Queen keeps 'blocking' the Rook? (Bye bye Queen, despite it being a SEE-wise 'good capture'!).

In general, how would you know if the piece blocking the enemy slider is (sufficiently) protected? Not using it to capture first might make the opponent retaliate against that piece, rather than against the target square (which is likely a less valuable target, as you decided to use it first).
What you say is logic - I agree your analysis is flawless pertaining precisely to the situations you mentioned.

Many things do not get solved just through logical reasoning alone. Just like the game of chess from the start position, there are too many factors to consider and the game is not solved. The only way to find out is, of course, testing. I believe your ELO of 10 is surely wrong - it should have been a -30 ELO! it prunes what it should not and sort backwards what causes an xray check!

My instinct somehow says it is very valuable. It is not without reason that all top programs have it. Don Dailey also mentioned exactly the use of SEE as in my post. Sorting is only about likelihood of it been correct - most of the time. QS SEE pruning is about pruning the big capturing the small and SEE cannot add much wrong by pruning when gain < 0.

The proof of eating is the pudding. The following game shows Cowrie winning against Stockfish. For the matter, Cowrie was using a SEE that was half-baked (not fully debugged, but worth 600 ELO) and with futility pruning, LMR and nullmove disabled (not confident they were working yet).
[Event "Computer Chess Game"]
[Site "mycomputer"]
[Date "2013.02.23"]
[Round "-"]
[White "Stockfish 2.2.2 JA"]
[Black "Cowrie Ver 1.0"]
[Result "1/2-1/2"]
[TimeControl "60/30"]

1. e4 e5 2. Nf3 Nc6 3. Bb5 Bc5 4. O-O Nf6 5. Nxe5 O-O 6. Bxc6 dxc6 7. d3
Re8 8. Nf3 Bg4 9. Nc3 a5 10. h3 Bh5 11. Be3 Bd6 12. a3 h6 13. g4 Nxg4 14.
hxg4 Bxg4 15. d4 Qf6 16. Kg2 Qg6 17. Rg1 Rxe4 18. Nxe4 Qxe4 19. Rh1 h5 20.
c4 Re8 21. c5 Re6 22. Kf1 Bxf3 23. Rh4 Bg2+ 24. Kg1 Qxh4 25. Kxg2 Bxc5 26.
Rc1 Bb6 27. b4 Re4 28. Qf3 Rg4+ 29. Kf1 axb4 30. axb4 Bxd4 31. Rc4 g6 32.
Ke2 Qe7 33. Kd3 Bxe3 34. Rxg4 hxg4 35. Qxe3 Qxb4 36. Ke2 Kf8 37. Qg3 Qe7+
38. Kf1 f5 39. Qc3 Qd6 40. Qh8+ Kf7 41. Qh7+ Kf6 42. Qh8+ Kg5 43. Qa1 g3
44. fxg3 Qxg3 45. Qa8 Qf3+ 46. Ke1 Qe3+ 47. Kd1 Qd3+ 48. Ke1 Qc3+ 49. Kd1
Qb3+ 50. Ke1 Qb4+ 51. Ke2 Qc4+ 52. Kd2 Qd4+ 53. Kc1 Qc3+ 54. Kd1 Qd3+ 55.
Ke1 Qe4+ 56. Kd1 Qd4+ 57. Kc1 Qg1+ 58. Kd2 Qg2+ 59. Kc1 Qf1+ 60. Kc2 Qc4+
61. Kd2 Qf4+ 62. Kc2 Qe4+ 63. Kd1 Qf3+ 64. Ke1 Qc3+ 65. Kd1
{Draw by repetition} 1/2-1/2


Best Regards,
Rasjid.

Dangerous ground. One game?

Chan Rasjid
Posts: 567
Joined: Thu Mar 09, 2006 3:47 pm
Location: Singapore

Re: SEE

Post by Chan Rasjid » Tue Feb 26, 2013 3:58 am

Hello,

I don't get it why anyone need to run SEE through an en-passant move. Or did I miss out bigtime on some things.

SEE is only about isolating bad captures that may lose material and be pruned or sorted back - it does not matter if a move is clearly winning or equalizes. En-passant can never be a loser and be a candidate for prunning. It should always be make() early if there is one. So what am I missing here?

As for the one game win against Stockfish, this is the first time it happens a few days back after I added some to evaluation. But I am less surprised that it happens, even if just a rare one time event. I am confident my engine, search and evaluation, now is very thoroughly debug and almost bugfree.

Best Regards,
Rasjid.
Don't believe when you're told "There's no free lunch!" There is Linux.

User avatar
hgm
Posts: 22587
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: SEE

Post by hgm » Tue Feb 26, 2013 6:32 am

bob wrote:So at least a factor of 2x, which is 50-70, and I did not remove the extension selection tests or any other uses of Swap(), just q-search...
Time-to-depth speedup for a pruning is not a decisive measure, right? You also lose accuracy, which might cost you Elo. Some of the SEE-wise bad captures you prune actually win material (because a protector was overloaded or soft-pinned, or a capture delivered a discoverd threat), and your search will now miss that.

Besides, SEE is not really necessary for this pruning. With BLIND I make similar prunings too.

Post Reply