Why the asserts never triggered?

[Chan Rasjid]

Hello,
[edit : SEE is used here to prune QS captures and to sort to tail quiet moves in full width search. ]

The codes here is a debug version of SEE that uses the QS move generator.

I just can't figure out why the commented asserts within see_search() were never triggered. I expect them to be triggered almost immediately.

Code: Select all

int see_search(const int at, const int side, const int see_side, int gain) {
    move_t *move, list[256], targ = BRD_PC(at);
    check_t check_s;
    int x, pc, incheck;

    assert&#40;gain <= 0&#41;;/* why never triggered ? */
    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;
        /* discovered check; returns */
        if &#40;gain > 0 && side ^ see_side&#41; &#123;
            assert&#40;0&#41;;/* why never triggered ? */
            /* see side lost, but gives check; don't see prune. */
            gain = 0;
        &#125;
        return gain;
    &#125;

    /* If no discovered check and  gain > 0 returns. Others side failed to equalize material. */
    if &#40;gain > 0 || targ == King&#41; &#123;
        assert&#40;0&#41;;/* why never triggered ? */
        return gain;
    &#125;

    /* 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;;

    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. The exception is when a 
             * move gives indirect check.
             * So must call see_search&#40;) to determine if there is a discovered check; even for King's move
             * that may fail to equalize..
             *    */
            gain += vPiece&#91;targ&#93;;
            pc = BRD_PC&#40;FROM&#40;*move&#41;);
            if (&#40;gain >= 0 &&  pc == King&#41; || &#40;gain - vPiece&#91;pc&#93; > 0&#41;) &#123;/* side wins */
                return gain;
            &#125;

            if &#40;gain < 0&#41; &#123;
                if &#40;side == see_side&#41;; /* call see_search to determine if indirect check oppn */
                else &#123;
                    return gain;
                &#125;
            &#125;

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

    return gain;
&#125;

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;;

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

    makemove&#40;move, side&#41;;
    gain = vPiece&#91;targ&#93;;
    x = -see_search&#40;at, side ^ 1, side, -gain&#41;;
    assert&#40;x > -INFI && x < INFI&#41;;
    unmake&#40;move, side&#41;;
    
    if &#40;x < 0 )&#123;
        return SEE_PRUNE;
    &#125;

    return 0;
&#125;

Best Regards,
Chan Rasjid.

[lucasart]

Look, we're not going to do your homework for you... We don't even know the context.

You need to learn to use a debugger.

And to validate that the assert() function works properly, compile and run this trivial program, rather than try to find a needle in a haystack with a complex SEE function

Code: Select all

#include <assert.h>

void main&#40;)
&#123;
    assert&#40;0&#41;;
&#125;

I don't know what compiler you use, and how you use it. But for example with GCC from the command line, if you put "-DNDEBUG" then the assert() are not compiled.

[Chan Rasjid]

Hello,

I discovered a minor bug in the codes of
see_search(); targ is an int, but move_t unsigned int changes nothing.

Code: Select all

static int see_search(const int at, const int side, const int see_side, int gain) {
    move_t *move, list[256];
    const int targ = BRD_PC(at);
    check_t check_s;
    int x, pc, incheck;

    assert&#40;gain <= 0&#41;;/* why never triggered ? */
    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;
        /* discovered check; returns */
        if &#40;gain > 0 && side ^ see_side&#41; &#123;
            assert&#40;0&#41;;/* why never triggered ? */
            /* see side lost, but gives check; don't see prune. */
            gain = 0;
        &#125;
        return gain;
    &#125;

    /* If no discovered check and  gain > 0 returns. Others side failed to equalize material. */
    if &#40;gain > 0 || targ == King&#41; &#123;
        assert&#40;0&#41;;/* why never triggered ? */
        return gain;
    &#125;

    /* 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;;

    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. The exception is when a 
             * move gives indirect check.
             * So must call see_search&#40;) to determine if there is a discovered check; even for King's move
             * that may fail to equalize..
             *    */
            gain += vPiece&#91;targ&#93;;
            pc = BRD_PC&#40;FROM&#40;*move&#41;);
            if (&#40;gain >= 0 &&  pc == King&#41; || &#40;gain - vPiece&#91;pc&#93; > 0&#41;) &#123;/* side wins */
                return gain;
            &#125;

            if &#40;gain < 0&#41; &#123;
                if &#40;side == see_side&#41;; /* call see_search to determine if indirect check oppn */
                else &#123;
                    return gain;
                &#125;
            &#125;

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

    return gain;
&#125;

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;;

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

    makemove&#40;move, side&#41;;
    gain = vPiece&#91;targ&#93;;
    x = -see_search&#40;at, side ^ 1, side, -gain&#41;;
    assert&#40;x > -INFI && x < INFI&#41;;
    unmake&#40;move, side&#41;;
    
    if &#40;x < 0 )&#123;
        return SEE_PRUNE;
    &#125;

    return 0;
&#125;

Best Regards,
Rasjid.

[Chan Rasjid]

Hello,

I have been trying hard to figure what seems obvious and not working.

I could add a assert(0) within see_search()
and it trigers,

Code: Select all

static int see_search(const int at, const int side, const int see_side, int gain) {
    move_t *move, list[256];
    const int targ = BRD_PC(at);
    check_t check_s;
    int x, pc, incheck;

    assert(gain > 0);/* OK; triggers immediate */
    assert&#40;gain <= 0&#41;;/* why never triggered ? */
    assert&#40;gain + vPiece&#91;targ&#93; >= 0&#41;;

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

cowrie: src/see.c:310: see_search: Assertion `gain > 0' failed.
Cowrie Chess Version 1.0, 3rd Feb 2010
score -2
Auto Play Start, num-pc (32) num-move (20)
score -2


game 1 move g2g3
start pc(32)

RUN FAILED (exit value 134, total time: 570ms)

Best Regards,
Rasjid.

[lucasart]

Hello,

I have been trying hard to figure what seems obvious and not working.

I could add a assert(0) within see_search()
and it trigers,

Code: Select all

static int see_search(const int at, const int side, const int see_side, int gain) {
    move_t *move, list[256];
    const int targ = BRD_PC(at);
    check_t check_s;
    int x, pc, incheck;

    assert(gain > 0);/* OK; triggers immediate */
    assert&#40;gain <= 0&#41;;/* why never triggered ? */
    assert&#40;gain + vPiece&#91;targ&#93; >= 0&#41;;

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

cowrie: src/see.c:310: see_search: Assertion `gain > 0' failed.
Cowrie Chess Version 1.0, 3rd Feb 2010
score -2
Auto Play Start, num-pc (32) num-move (20)
score -2


game 1 move g2g3
start pc(32)

RUN FAILED (exit value 134, total time: 570ms)

Best Regards,
Rasjid.

Run your code with a debugger

[MikeGL]

Im just a hobbyist and not a pro.
But it seems the passed parameter 'gain' is always zero or negative.

If this is my case, I will monitor the value of gain by scattering some
printf to see all values of gain. (kludge)

[kinderchocolate]

Can you printf the gain parameter? If it is negative, the assert won't be triggered because the condition is true!

Or give us the source we can take a look.

[Chan Rasjid]

Hello,

It could be a simple case of programmers block when the thinking and reasoning just fails!

I posted my codes as I tried, but could not figure why some bad/wrong asserts did not triger when it seems simple they should. I am most puzzled by what is at the start of see_search() :-

assert(gain <= 0);/* why never triggered

I again briefly go through the codes and see if I could now figure out the puzzle or my own silliness - but I still fail.

I did not clarify why it was so (my apology). Notice the lines just before makemove() and then the call to recursive see_search():

Code: Select all

            if &#40;gain < 0&#41; &#123;
                if &#40;side == see_side&#41;; /* call see_search to determine if indirect check oppn */
                else &#123;
                    return gain;
                &#125;
            &#125;

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

see_search is just simple - it receives the parameter gain and updates it by adding
what it captures. The update gain is passed to see_search() as -gain, i.e. with sign flipped.

It seems clear that when see_search() receives gain, it could be < 0, == 0 or > 0; eg. if a Q starts the capture of a P, then it is likely it would never recover its material even if it has a next capture to follow and gain < 0.

side is flipped and see_side remains unchanged. So it seems simple (codes above) to have gain < 0 and side == see_side easily satisfied in which case -gain (gain > 0) is passed to see_search(). So why assert(gain<= 0) never was trigered after many full debug games?

I don't need to clear the puzzle now as my codes have changed. After some headache, I now finally have debug my SEE with confidence that it is now bug free.

Best Regards.

[Sven]

I think the real reason behind your SEE code causing (or having caused) a lot of headache is its complexity. Have you considered getting rid of using a move generator and a loop over moves to calculate SEE? Note, it is meant as a small and fast routine being called for single capture moves during QS to quickly classify them as "most probably losing capture" or not. If your SEE produces almost an effort of O(qsearch) itself then it means an unacceptably high penalty for your whole QS. The code looks as if you were traversing a tree within your SEE function, although after finding the first relevant move you exit from the loop - but the whole move generation + scanning a lot of moves is still too expensive.

An SEE implementation that is significantly more complex than the CPW example code will most probably cause trouble, sooner or later. One may argue about the details, recursive or iterative, using sophisticated cutoff tricks or not, but the basic principle of SEE is to assume a fixed order of capture moves on the target square, from least-valuable to most-valuable pieces, and to compare doing these captures to not doing them at each level in the chain of capture moves to the target square. I'm not sure whether your algorithm works that way. Especially some conditions regarding discovered check, king moves etc. are not obvious for me.


Regarding your original problem with "assert's", I have taken a brief look into the code you have posted (actually I have done so some days ago but I did not have the time for a longer posting back then). I do not have the final answer but I think I am close to it, so I'll give it a try ... I focus on the first assertion "gain <=0" since I think everything else can be derived from that one.

- At the top level see_search() is called from debug_see() with a gain that is either zero or negative (when calling debug_see() for captures it will be negative since vPiece[targ] is positive).

- Therefore the first assertion "gain <= 0" will not fail within the first call of see_search() (as mentioned, the caller debug_see() already ensures that condition).

- Now "gain <= 0" could only fail if a recursive call of see_search() would occur when the calling instance of see_search() has a negative value for gain so that the recursive call with "(..., -gain)" causes the next recursion level to receive a positive "gain" parameter. But how should "gain" ever become negative at that point of recursive call? All the early exits above the move loop are irrelevant for that since the recursive call is not reached. The "move loop" takes the first matching and valid move to the target square, adds the piece value found on the target square to "gain" descends into recursion and then exits. And now the question remains whether "gain" can still be negative at that point. I'm not perfectly sure why but I think it can't since the piece values considered within the "SEE chain" are in ascending order, and the "gain" value seems to stay inside a tight interval.

- Now returning to the start: if "gain" can't go negative when reaching the recursive call, the next recursion level can't receive a positive gain parameter, so the "gain <= 0" condition always remains true.


After checking again I now also believe that your algorithm is wrong. Instead of returning from recursion if gain < 0, you need to descend into recursion, and after returning from there, compare its result against 0 to decide about doing the capture or not. I do not see that essential part of the algorithm in your code.

I propose to do a full rewrite of SEE, start with a very simple implementation that does not consider checking moves or king moves as a special case, follow the simple algorithm that can be seen in CPW, and get that working before you resort to a more sophisticated solution.

Sven

[Chan Rasjid]

Hello Sven,

The SEE codes I posted here is a debug version that uses the normal gen_capture() for QS and makemove(). I posted my final see_debug(), the corrected version in the other thread. As can be seen, it is very simple to understand and straight forward. It has very few lines.

My customized bitboard SEE has about 400 lines. So my SEE now and the debug version always return the same scores (when they could be compared).

Now I don't want to rake my brain to figure why assert(gain <= 0) passed. I have another major headace which is bugging me a fairly long time. My engine cannot play KRK ending unless hashing is disabled. I don't want to post 'homework' here unless very necessary.

Best Regards,
Rasjid.