Are everybody making this bad?

[Kempelen]

Looking code of a few engines, even top ones like Crafty, it looks to me that all have a draw-score bug:

Let's suppose a branch that in the frontier node, before call quiesce, it is a calm position. When enter quiesce first time, evaluation is called and make a decision (i.e. the score > beta, so return beta).... but, what about if the last move is a 3-repetition or a 50-mov rule draw. It is not examined and it is returned a eval score and not a draw one.

Of course, in the following iteration this could solved, but new nodes will have the same problem.

Does this is a problem? is it important? or am I who is seeing ghots?

Regards,

[Zach Wegner]

It's interesting, it looks like Crafty has that bug. Bob might have reasons for not doing it, it might not be worth the overhead according to massive cluster testing. I know one certain engine that doesn't have the bug though...

Code: Select all

/**
The quiescence search.
**/
case QSEARCH_START:
#ifdef SMP
        smp_block[board.id].q_nodes++;
#else
        zct->q_nodes++;
#endif
        if (sb->ply >= zct->max_depth_reached)
            zct->max_depth_reached = sb->ply;
        if (sb->ply >= MAX_PLY - 1)
            RETURN(evaluate(&sb->eval_block));
        if (board.fifty_count >= 100 && !is_mate())
            RETURN(DRAW);
        if (is_repetition(sb->ply > 1 ? 2 : 3))
            RETURN(DRAW);

        /* mate-distance pruning */
        sb->alpha = MAX(sb->alpha, -MATE + sb->ply);
        sb->beta = MIN(sb->beta, MATE - sb->ply - 1);
        if (sb->alpha >= sb->beta)
            RETURN(sb->alpha);

        /* material draw pruning */
        if (!can_mate(board.side_tm))
        {
            sb->beta = MIN(sb->beta, DRAW);
            if (sb->alpha >= sb->beta)
                RETURN(sb->alpha);
        }
        if (!can_mate(board.side_ntm))
        {
            sb->alpha = MAX(sb->alpha, DRAW);
            if (sb->alpha >= sb->beta)
                RETURN(sb->alpha);
        }

        /* Probe the hash table. */
        if (hash_probe(sb, TRUE))
            RETURN(sb->alpha);
#ifdef EGBB
        /* Probe the bitbases. */
        if &#40;egbb_is_loaded && pop_count&#40;board.occupied_bb&#41; <= 5&#41;
        &#123;
            if &#40;probe_bitbases&#40;&r&#41; && r != _NOTFOUND&#41;
            &#123;
                /* draw, exact score */
                if &#40;r == 0&#41;
                    sb->alpha = sb->beta = 0;
                /* mate */
                else if &#40;r > 0&#41;
                    sb->alpha = MAX&#40;MATE - MAX_PLY - 1, sb->alpha&#41;;
                else if &#40;r < 0&#41;
                    sb->beta = MIN&#40;-&#40;MATE - MAX_PLY - 1&#41;, sb->beta&#41;;
                if &#40;sb->alpha >= sb->beta&#41;
                &#123;
                    hash_store&#40;sb, NO_MOVE, r, HASH_LOWER_BOUND, FALSE&#41;;
                    hash_store&#40;sb, NO_MOVE, r, HASH_LOWER_BOUND, TRUE&#41;;
                    RETURN&#40;r&#41;;
                &#125;
            &#125;
        &#125;
#endif

        sb->check = check_squares&#40;);
        /* If we are in check and depth is sufficient, try all evasions. */
        if &#40;sb->check && sb->depth > 0&#41;
        &#123;
            sb->threat = TRUE;
            sb->select_state = SELECT_HASH_MOVE;
        &#125;
        /* Normal quiescence stand pat score, plus move generation. */
        else
        &#123;
            /* Evaluate for the stand pat. */
            r = sb->best_score = evaluate&#40;&sb->eval_block&#41;;
            if &#40;r > sb->alpha&#41;
            &#123;
                sb->alpha = r;
                if &#40;r >= sb->beta&#41;
                &#123;
                    /* Is this worth it? */
                    hash_store&#40;sb, NO_MOVE, r, HASH_LOWER_BOUND, TRUE&#41;;
                    RETURN&#40;r&#41;;
                &#125;
            &#125;
            sb->select_state = SELECT_GEN_CAPS;
        &#125;

[hgm]

Joker also would recognize the position as a repetition, and therefore might not make the move. Micro-Max would recognize a repetition after making the move if it was a repetition of a position that had occurred in the game.

[Guetti]

Maybe some engines already assign a draw score after the second repetition. This would avoid the bug, wouldn't it?

[bob]

It's interesting, it looks like Crafty has that bug. Bob might have reasons for not doing it, it might not be worth the overhead according to massive cluster testing. I know one certain engine that doesn't have the bug though...

Code: Select all

/**
The quiescence search.
**/
case QSEARCH_START:
#ifdef SMP
        smp_block[board.id].q_nodes++;
#else
        zct->q_nodes++;
#endif
        if (sb->ply >= zct->max_depth_reached)
            zct->max_depth_reached = sb->ply;
        if (sb->ply >= MAX_PLY - 1)
            RETURN(evaluate(&sb->eval_block));
        if (board.fifty_count >= 100 && !is_mate())
            RETURN(DRAW);
        if (is_repetition(sb->ply > 1 ? 2 : 3))
            RETURN(DRAW);

        /* mate-distance pruning */
        sb->alpha = MAX(sb->alpha, -MATE + sb->ply);
        sb->beta = MIN(sb->beta, MATE - sb->ply - 1);
        if (sb->alpha >= sb->beta)
            RETURN(sb->alpha);

        /* material draw pruning */
        if (!can_mate(board.side_tm))
        {
            sb->beta = MIN(sb->beta, DRAW);
            if (sb->alpha >= sb->beta)
                RETURN(sb->alpha);
        }
        if (!can_mate(board.side_ntm))
        {
            sb->alpha = MAX(sb->alpha, DRAW);
            if (sb->alpha >= sb->beta)
                RETURN(sb->alpha);
        }

        /* Probe the hash table. */
        if (hash_probe(sb, TRUE))
            RETURN(sb->alpha);
#ifdef EGBB
        /* Probe the bitbases. */
        if &#40;egbb_is_loaded && pop_count&#40;board.occupied_bb&#41; <= 5&#41;
        &#123;
            if &#40;probe_bitbases&#40;&r&#41; && r != _NOTFOUND&#41;
            &#123;
                /* draw, exact score */
                if &#40;r == 0&#41;
                    sb->alpha = sb->beta = 0;
                /* mate */
                else if &#40;r > 0&#41;
                    sb->alpha = MAX&#40;MATE - MAX_PLY - 1, sb->alpha&#41;;
                else if &#40;r < 0&#41;
                    sb->beta = MIN&#40;-&#40;MATE - MAX_PLY - 1&#41;, sb->beta&#41;;
                if &#40;sb->alpha >= sb->beta&#41;
                &#123;
                    hash_store&#40;sb, NO_MOVE, r, HASH_LOWER_BOUND, FALSE&#41;;
                    hash_store&#40;sb, NO_MOVE, r, HASH_LOWER_BOUND, TRUE&#41;;
                    RETURN&#40;r&#41;;
                &#125;
            &#125;
        &#125;
#endif

        sb->check = check_squares&#40;);
        /* If we are in check and depth is sufficient, try all evasions. */
        if &#40;sb->check && sb->depth > 0&#41;
        &#123;
            sb->threat = TRUE;
            sb->select_state = SELECT_HASH_MOVE;
        &#125;
        /* Normal quiescence stand pat score, plus move generation. */
        else
        &#123;
            /* Evaluate for the stand pat. */
            r = sb->best_score = evaluate&#40;&sb->eval_block&#41;;
            if &#40;r > sb->alpha&#41;
            &#123;
                sb->alpha = r;
                if &#40;r >= sb->beta&#41;
                &#123;
                    /* Is this worth it? */
                    hash_store&#40;sb, NO_MOVE, r, HASH_LOWER_BOUND, TRUE&#41;;
                    RETURN&#40;r&#41;;
                &#125;
            &#125;
            sb->select_state = SELECT_GEN_CAPS;
        &#125;

I am not sure it is a "bug". Once a piece is captured, repetition is not possible, nor is 50-move rule draw. I tried it in the q-search check/check evasion, but it hurt on cluster testing, probably because of the nps drop this produces since it is done in the biggest part of the tree. Ditto for storing and probing hash table. I have it on my list to test again, but several years ago I ran a lot of tests and concluded that the 10% slowdown, which shrunk the tree by 10% was essentially a "wash". Not hashing in qsearch has a big advantage, however, in that there are more nodes out there than in the regular search, so you don't replace nearly as often since less than 50% of total nodes searched get stored. I know of one commercial program (very strong as well) that claims to not even do a q-search at all, just applies SEE to the tips.

[bob]

Maybe some engines already assign a draw score after the second repetition. This would avoid the bug, wouldn't it?

I don't think it matters as you would not see the second repetition in the q-search. I count the 2nd as a draw, of course... To do otherwise invites overlooked repetitions and draws in otherwise won positions.

[hgm]

I know of one commercial program (very strong as well) that claims to not even do a q-search at all, just applies SEE to the tips.

I started out using SEE-based termination in micro-Max as well, (i.e., only considering capturing the last-moving piece in QS), but changing to an all-capture QS produced a 120 Elo strength increase, and thus was well worth the number of characters spent to program it. Even despite the fact that there was no real move ordering, except that the MVV/LVA capture was tried first. (And all other captures in move-gen order.)

Micro-Max does never do any move sorting other than trying the best move of the previous IID iteration (possibly communicated through the hash table) first. But due to IID this still results in a reasonable move ordering: a QS iteration preceeds a d=1 iterations, so all captures are searched before any non-captures.

[bob]

I know of one commercial program (very strong as well) that claims to not even do a q-search at all, just applies SEE to the tips.

I started out using SEE-based termination in micro-Max as well, (i.e., only considering capturing the last-moving piece in QS), but changing to an all-capture QS produced a 120 Elo strength increase, and thus was well worth the number of characters spent to program it. Even despite the fact that there was no real move ordering, except that the MVV/LVA capture was tried first. (And all other captures in move-gen order.)

Micro-Max does never do any move sorting other than trying the best move of the previous IID iteration (possibly communicated through the hash table) first. But due to IID this still results in a reasonable move ordering: a QS iteration preceeds a d=1 iterations, so all captures are searched before any non-captures.

I used the SEE trick myself somewhere around 1975. But when I went to full-width and added q-search, the program played better. Amir once discussed this here and said Junior (a) has no q-search at all and (b) doesn't hash in the last 1 or 2 plies (memory fails me on whether it was 1 or 2 however). I'm not sure if he ever mentioned how he used SEE(), as you could just use it to verify the safety of the moves leading to leaf positions, or you could use it on any apparently hung piece which might be better although I have not tried it.

[Zach Wegner]

I am not sure it is a "bug". Once a piece is captured, repetition is not possible, nor is 50-move rule draw. I tried it in the q-search check/check evasion, but it hurt on cluster testing, probably because of the nps drop this produces since it is done in the biggest part of the tree. Ditto for storing and probing hash table. I have it on my list to test again, but several years ago I ran a lot of tests and concluded that the 10% slowdown, which shrunk the tree by 10% was essentially a "wash". Not hashing in qsearch has a big advantage, however, in that there are more nodes out there than in the regular search, so you don't replace nearly as often since less than 50% of total nodes searched get stored. I know of one commercial program (very strong as well) that claims to not even do a q-search at all, just applies SEE to the tips.

It is true that repetitions and 50-move draws can't happen after captures. But, without testing, I'd imagine that it would help to run the test if you do checks in the qsearch to avoid certain perpetuals.

[bob]

I am not sure it is a "bug". Once a piece is captured, repetition is not possible, nor is 50-move rule draw. I tried it in the q-search check/check evasion, but it hurt on cluster testing, probably because of the nps drop this produces since it is done in the biggest part of the tree. Ditto for storing and probing hash table. I have it on my list to test again, but several years ago I ran a lot of tests and concluded that the 10% slowdown, which shrunk the tree by 10% was essentially a "wash". Not hashing in qsearch has a big advantage, however, in that there are more nodes out there than in the regular search, so you don't replace nearly as often since less than 50% of total nodes searched get stored. I know of one commercial program (very strong as well) that claims to not even do a q-search at all, just applies SEE to the tips.

It is true that repetitions and 50-move draws can't happen after captures. But, without testing, I'd imagine that it would help to run the test if you do checks in the qsearch to avoid certain perpetuals.

I already do this, but only in the qchecks and qevasions modules, not anywhere else. So Crafty will _always_ see the repetition or 50-move draw mentioned at the start of this thread, since the first level of q-search is always the QuiesceChecks() function that checks for reps/etc at the front, and for any check this module produces, QuiseceEvasions() is called and it also checks for repetitions/50-move draws, although I do not hash in those functions...