crazyhouse tips?

[zenpawn]

I have crazyhouse fully implemented, but the search tree explosion (even with greater LMR for quiet drops) is making it painfully slow. What do some of the other crazyhouse engines like CrazyWa do to handle this? Are some drops just not searched at all?

Thanks,
-Erin

[Ferdy]

I have crazyhouse fully implemented, but the search tree explosion (even with greater LMR for quiet drops) is making it painfully slow. What do some of the other crazyhouse engines like CrazyWa do to handle this? Are some drops just not searched at all?

Thanks,
-Erin

LMR is not enough use pruning aggressively.

Try to have a drop move history for example, if such move failed low penalize it.

For example.

Code: Select all

InitDropHistoryToZero()

[...]

if (searchValue(m) > beta)
    IncreaseDropHistory(m)
else
    DecreaseDropHistory(m)

[...]

if &#40;depth < 4 && dropHistory&#91;pc&#93;&#91;to&#93; < 0 && !InterestingDropMove&#40;m&#41; && triedLegalMoves > 3&#41;
   prune

You can also try to prune drop moves with bad SEE.

Good move ordering is one of the features that improve crazyhouse play. You may spend some time on it.
Once you have the moves in order properly you can then apply pruning based on late moves.

Still if you can search drop moves by stage it would be better, i.e
0. Check drop moves
1. Check-threat drop moves
2. Capture-threat drop moves
and others.

[hgm]

CrazyWa limits the depth of QS to 10 (or 8, I forgot) ply, to clip 'endless' sequences of checking captures, where the capturer is in an all-node and burning all his material, but the opponent cannot profit from his huge leadd by standing pat because he is in check. In addition, it searches general drops only after all other moves, and only generates them when all other moves failed low. (Check drops are selectively generated earlier, ad hash move and killers can be drops.) That doesn't help lowering the branching factor, but it increases the nps.

It reduces non-captures (except hash and killers and check drops) by 1, and non-checking drops by 2. There is no hard pruning. In QS is searches only captures and check evasions. For the latter it does prune 'futile interpositions', i.e. drops on an unprotected square, where the checker would simply renew the check by capturing the dropped piece with the original checker.

It does have a very robust search, however, doing IID in every node, and switching back to lower depth (through self-deepening of the cut-moves) when a previous cut-move doesn't last all the way to the final depth. So it never wastes much time on deep searches of moves that are obviously no good, but happened to come early in the static move ordering. This might help to reduce the effective branching factor.

My intention is to publish the CrazyWa source, but I consider the current source too messy for that (writing it was a hasty job, and it is still spattered with debug print statements), and wanted to clean it up a bit first. I got about half way with that, but the project stalled because now I am in a great hurry to finish the Tenjiku-Shogi engine. (Its clock is already running in the tourney I entered it in...)

[Evert]

I have crazyhouse fully implemented, but the search tree explosion (even with greater LMR for quiet drops) is making it painfully slow. What do some of the other crazyhouse engines like CrazyWa do to handle this? Are some drops just not searched at all?

Most drop moves are pointless and can be heavily reduced or pruned outright.
In SjaakII, I have the following:

• No drops in QS (except as check evasion)
• Separate history table for drop moves
• Severe reduction of unsafe (SEE<0) drops, even stronger than of other late moves.
• Sort drops on the enemy half of the board ahead of those on your own side.
• Pruning of unsafe drop moves in the last two plies of regular search.
• Futility pruning of drop moves that don't give check in frontier nodes.

This is not enough to prevent search explosion in all cases, but it does help. There are many more clever things you can do with pruning and move ordering (the criteria I use for deciding whether drops are pointless or not can be far more specific, allowing for more agressive pruning).

Some other things: you may want to check for repetitions on the board (same board position, different hand material). This may mean that you're leaking material to the opponent, which can never be good (just fail low in that case). Make sure you count hand material in the evaluation function, and give a nice PST bonus to hand material (so the program doesn't try to drop stuff on the board as quickly as possible).

[Evert]

CrazyWa limits the depth of QS to 10 (or 8, I forgot) ply, to clip 'endless' sequences of checking captures, where the capturer is in an all-node and burning all his material, but the opponent cannot profit from his huge leadd by standing pat because he is in check.

Yes, that should help too. I don't do that for drop games specifically though.

In addition, it searches general drops only after all other moves, and only generates them when all other moves failed low. (Check drops are selectively generated earlier, ad hash move and killers can be drops.) That doesn't help lowering the branching factor, but it increases the nps.

Staged move generation is also a very useful thing. SjaakII can actually use a staged move generation as well, but I currently only use it for the special mate search.

My intention is to publish the CrazyWa source, but I consider the current source too messy for that (writing it was a hasty job, and it is still spattered with debug print statements), and wanted to clean it up a bit first. I got about half way with that, but the project stalled because now I am in a great hurry to finish the Tenjiku-Shogi engine. (Its clock is already running in the tourney I entered it in...)

Ah, and here I was refreshing the page to see whether there was an update to your progress with it! Good luck with the tournament, knock'em dead!

[zenpawn]

Thanks, everyone. I'm doing some of these things, such as move ordering, greater LMR if the drop is deemed "quiet", only allowing evasion drops in QS, and bonus eval for pieces in hand.

Based on your suggestions, outright pruning is on the docket and potentially depth limits on QS. Unfortunately, I don't have SEE, just MVV-LVA, so I don't know whether a drop is unprotected to prune it as a "futile interposition."

Also, I only have standard iterative deepening, not IID. Tried it once for standard chess without success. Maybe it's worth another shot? (Sounds like H.G.'s is even fancier than that; you lost me a bit re: the tricks you're doing there.)

[hgm]

Unfortunately, I don't have SEE, just MVV-LVA, so I don't know whether a drop is unprotected to prune it as a "futile interposition."

CrazyWa does not use SEE either. What I do is during move generation mark all squares to which you have potential capture moves (so also diagonal Pawn moves to empty squares) on an auxiliary board. That hardly takes any time. Then, when in (distant) check, I collect that information for all squares along the check ray as a bit mask. The routine that generates evasion drops then tests this mask, to suppress any drops on squares that were not attacked by pieces on the board.

Code: Select all

static int attackKey;
int attacks[];

// in board-move generator
  int c = ++attackKey;
    // loop over piece moves
    int d = c - (range == 11); // spoil for Pawn straight-ahead moves
      // in loop over to-squares, before testing occupant
      attacks[to] = d;


int
SafeIP (StackFrame *f)
{   // figure out which squares are protected on the check ray
    int result = 0, v = f->checkDir, x = f->checker, mask = 1;
    while&#40;board&#91;x+=v&#93; == 0&#41; result |= &#40;mask <<= 1&#41;*&#40;attackKey != attacks&#91;x&#93;);
    return result & ~mask;
&#125;

void
EvasionDrops &#40;int stm, StackFrame *f, int mask&#41;
&#123;
    int i, x = f->checker, v = f->checkDir, s = stm ^ COLOR;
    while&#40;board&#91;x+=v&#93; == 0&#41; &#123; // all squares on check ray
        int last = maxDrop;
        if&#40;&#40;mask >>= 1&#41; & 1&#41; continue; // suppress 'futile interpositions'
        i = zoneTab&#91;x&#93; & Z_LAST; // Pawn not on first & last rank &#40;OK for zh&#41;
        if&#40;perpLoses&#41; &#123; // but it is Shogi!
            if&#40;!&#40;zoneTab&#91;x&#93; & stm&#41;) i = 0; // outside zone, so dropping is always allowed
            else if&#40;perpLoses < 5&#41; &#123;       // Shogi variant with Lance
                i *= 2;                    // no Pawn, then also no Lance!
                last += 1 - &#40;zoneTab&#91;x&#93; & &#40;Z_2ND & ~COLOR&#41;) + &#40;perpLoses & 4&#41; >> 3; // on last 2 ranks trim off Knight &#40;not in Wa&#41;
            &#125;
            if&#40;pawnCount&#91;sqr2file&#91;x&#93;&#93; & maxBulk&#91;stm&#93;) i += !i; // no Pawn in pawn-crowded file
        &#125;
        for&#40;; i<=last; i++) &#123; // all droppable types
            int piece = s + i, from = handSlot&#91;piece&#93;;
            if&#40;&#40;signed char&#41;board&#91;from&#93; < -1&#41; // piece type is in hand
                moveStack&#91;moveSP++&#93; = from << 8 | x;
        &#125;
    &#125;
&#125;

// in Search&#40;)
    if&#40;f.checker != CK_NONE&#41; &#123;
        depth++, maxDepth++, reduction = originalReduction = 0 /*, killers&#91;ply&#93;&#91;2&#93; = -1*/; // extend check evasions
        if&#40;earlyGen && f.checkDist && maxDepth <= 1&#41; ipMask = SafeIP&#40;&f&#41;;
    &#125; else if&#40;depth > LMR&#41; ...

I see I only suppress the futile interpositions at low depth. Occasionally they are useful, to lure the checker to another square, where he loses an attack on some other hanging piece that was worth more. Then he would capture that anyway, rather than the interposed piece. But what I wanted to prevent is that it would overlook an unavoidable mate by making futile interpositions on the check ray to push the mate over the horizon. (Which might not cause a fail low if the interposed material is cheap.) If the futile interpositions are forbidden, and there are no other evasions, it would consider itself checkmated already.

Also, I only have standard iterative deepening, not IID. Tried it once for standard chess without success. Maybe it's worth another shot? (Sounds like H.G.'s is even fancier than that; you lost me a bit re: the tricks you're doing there.)

My philosophy was that QS scores in drop games are usually crappy, because the material during a capture search accumulates in the hand, and at some point drops become more dangerous than captures, but are not searched. You then see the fallacy on a deeper search, where the drops come within the horizon. These misevaluations are rare in Chess, but in drop games they happen all the time. And they often need a complete restructuring of the search tree, pushing the search to areas that were never visited before because everything you preferred so far turns sour. (E.g. you counted on a Rook being sufficiently protected, and now it turns out you cannot afford to recapture it, because it can be dropped with mate as soon as the opponent gets it in the hand. Such a thing usually happens in all leaves of a sub-tree at once, so that you have to change move in a node at the root of a large sub-tree.)

So I wanted a search that would perform well in situations where it the cut-move that worked well so far suddenly fails low at high depth. Trying to find an alternative by blindly trying the other moves (that have never been searched at ay depth so far) is extremely inefficient, because the first 10 moves you pick could be obvious blunders, but you would still commit yourself to searching them to the high depth you are at. It is then much better to quickly discard the obvious blunders with low-depth searches, until you get to a move that at least looks promising at low depth, and try your luck with that.