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
crazyhouse tips?
Moderators: hgm, Rebel, chrisw
-
- Posts: 4840
- Joined: Sun Aug 10, 2008 3:15 pm
- Location: Philippines
Re: crazyhouse tips?
LMR is not enough use pruning aggressively.zenpawn wrote: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
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 (depth < 4 && dropHistory[pc][to] < 0 && !InterestingDropMove(m) && triedLegalMoves > 3)
prune
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.
-
- Posts: 27866
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: crazyhouse tips?
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...)
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...)
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: crazyhouse tips?
Most drop moves are pointless and can be heavily reduced or pruned outright.zenpawn wrote: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?
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.
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).
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: crazyhouse tips?
Yes, that should help too. I don't do that for drop games specifically though.hgm wrote: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.
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.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.
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!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...)
-
- Posts: 349
- Joined: Sat Aug 06, 2016 8:31 pm
- Location: United States
Re: crazyhouse tips?
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.)
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.)
-
- Posts: 27866
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: crazyhouse tips?
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.zenpawn wrote: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."
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(board[x+=v] == 0) result |= (mask <<= 1)*(attackKey != attacks[x]);
return result & ~mask;
}
void
EvasionDrops (int stm, StackFrame *f, int mask)
{
int i, x = f->checker, v = f->checkDir, s = stm ^ COLOR;
while(board[x+=v] == 0) { // all squares on check ray
int last = maxDrop;
if((mask >>= 1) & 1) continue; // suppress 'futile interpositions'
i = zoneTab[x] & Z_LAST; // Pawn not on first & last rank (OK for zh)
if(perpLoses) { // but it is Shogi!
if(!(zoneTab[x] & stm)) i = 0; // outside zone, so dropping is always allowed
else if(perpLoses < 5) { // Shogi variant with Lance
i *= 2; // no Pawn, then also no Lance!
last += 1 - (zoneTab[x] & (Z_2ND & ~COLOR)) + (perpLoses & 4) >> 3; // on last 2 ranks trim off Knight (not in Wa)
}
if(pawnCount[sqr2file[x]] & maxBulk[stm]) i += !i; // no Pawn in pawn-crowded file
}
for(; i<=last; i++) { // all droppable types
int piece = s + i, from = handSlot[piece];
if((signed char)board[from] < -1) // piece type is in hand
moveStack[moveSP++] = from << 8 | x;
}
}
}
// in Search()
if(f.checker != CK_NONE) {
depth++, maxDepth++, reduction = originalReduction = 0 /*, killers[ply][2] = -1*/; // extend check evasions
if(earlyGen && f.checkDist && maxDepth <= 1) ipMask = SafeIP(&f);
} else if(depth > LMR) ...
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.)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.)
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.