Crazyhouse move ordering discussion

[Vinvin20]

I think there are 2 cases here (my current understanding of the phenomenon) :

• when the player has some pieces (> 2) in hand, it's better to test drop first because attack toward the king has good chances to be strong.
• when the player has few pieces (< 3) in hand, it's better to test non-drop first because there's not enough pieces to start an attack.

[ianfab]

@Vinvin20 The patch does not do a partitioning, it only gives a penalty to drops, since it saves a lot of time if most of the bad drops do not have to be searched. Drops with a good history might still be ordered first.

Your idea sounds interesting, but I am not sure whether it will work with such a general rule, since searching drops is expensive. It might have to be limited to drops that are close to the king or attack a square in the king ring or something like that.

I will submit a few tests later. EDIT: http://35.161.250.236:6543/tests/view/59d247b16e23db0578f6dde3 http://35.161.250.236:6543/tests/view/59d249e96e23db0578f6dde6

[ddugovic]

In general when I play crazyhouse, I search for drops which attack the "king ring" or force a promotion (though if I have tempi for that, my opponent isn't attacking).

Calculating which drops would attack the king ring sounds expensive; do we have example games or puzzles where Stockfish is not giving enough priority to drops?

[Vinvin20]

Calculating which drops would attack the king ring sounds expensive

Yes, king ring is a bit expensive. May be "with check" or "near the king" is better.

do we have example games or puzzles where Stockfish is not giving enough priority to drops?

Basically, each game where drops win the game :-) But I don't know the statistics about the ratio "number of drops are good"/"number of non-drops are good". The computing time of dropping moves enter in the equation as well.

[ddugovic]

May be "with check" or "near the king" is better.

It's worth noting that movepick.cpp already gives priority to checks (which I believe includes drops). Based on zero examples, it sounds like the domain over which we're trying to optimize consists of positions where a mating net is constructed with non-checking drops near the opponent's king.

I assume position.cpp already does well penalizing for holes in the king's shelter, and in most positions if the attacker doesn't attempt to exploit the holes, the defender will drop pawns and the evaluation will shift in the defender's favor... which hopefully biases the search (in favor of attacking drops which can help break open a pawn cover). But maybe further bias could be applied somehow (that the shelter / storm functions could consider material in hand or something).

[ianfab]

It's worth noting that movepick.cpp already gives priority to checks (which I believe includes drops).

Does it? In the search (pruning, reductions, extensions) checks are handled differently from other quiet moves, but I am not aware of any difference in move ordering/picking apart from quiet checks in qsearch, but drops are anyway no longer picked there.

Picking a strong attacking move at an early point can help to prune big subtrees, and despite the history heuristics already doing a great job there, there might be room for crazyhouse/drop-specific improvements in move ordering.

[ddugovic]

Ah, now I see how search, qsearch, and MovePicker interact... you're right, check selection is only an aspect of quiescent search. I wonder if my code previous to a16ebb0d211256121ebb1d702b5310e6b39f7b07 was defective & instead should have been:

    if (Type == QUIET_CHECKS)
        moveList = generate_drops<Us, PAWN, true>(pos, moveList, b);
    else
        moveList = generate_drops<Us, PAWN, false>(pos, moveList, b);

since normally we'd expect a drop-check to be a strong attacking move!

While iterative deepening (plus other depth-related techniques) help considerably with pruning, it makes sense that improving move-ordering (if possible) should further improve pruning!

[ianfab]

@ddugovic I only had a brief look at it, but I also think that it was not working as intended. It would be interesting to test the fixed version against the current and/or the old version. Maybe the old code only did not work well because all pawn drops were generated (if I understand correctly), which massively cluttered quiescence search. If this was the case, then the fix might be a big Elo gain.

[ddugovic]

@ianfab Indeed, the STC test hints that there might be a large Elo gain for the reason you suggest!

[ianfab]

@ddugovic It looks like this bug was around for almost a year (since https://github.com/ddugovic/Stockfish/commit/6a9afe7a15afcf3be87b896298dd62cc140fb999). What do you think about moving the generation of pawn drops back to the same place as the generation of other drops? In my opinion this would make such a bug less likely to be introduced or overlooked.

[ddugovic]

That makes sense... I'll test a patch like that although I wonder (aside from the 1st/8th rank bitmask) whether Bitboard b should be initialized the same way for pawn drops & piece drops (for evasions, etc.)... I assume so but might be missing something.

[ianfab]

For reference, the link to the more technical discussion: https://github.com/ddugovic/Stockfish/commit/5e7e1cc94861d065d9a4d546b2419950ca023fb1#commitcomment-24717217

[ddugovic]

Per the technical discussion, there's probably room for further changes somehow.

[ddugovic]

Now the move generator generates non-drops first, and generates drops during qsearch. I think this leaves us with:

Picking a strong attacking move at an early point can help to prune big subtrees, and despite the history heuristics already doing a great job there, there might be room for crazyhouse/drop-specific improvements in move ordering.

Indeed, there might be room for move ordering improvements, and certainly improvement patches would be tested & accepted (irrespective of whether this issue remains open). Fabian attempted Vinvin's suggestion. Should we leave open this issue for discussion?

[ianfab]

If my understanding of the move generation and ordering is correct, changes to the order of generating moves has the following effects:

• sorting might be faster if the list already has a reasonable ordering
• order of moves with the same score depends on which was generated first
• (supposedly) bad moves below the threshold of partial_insertion_sort keep the order of how they were generated

In general these effects should be rather small compared to the effect of changing the scoring/sorting of moves, and the test results also suggest that.

I think that move ordering is an important topic, especially for crazyhouse, so leaving this open for further discussion makes sense.