Stockfish: Move for crazyhouse and giveaway no longer fits in 16 bits (as expected by struct TTEntry)

[sf-x]

subj. See definition of struct TTentry. Do drops really need extension of Move to 18 bits?

[ddugovic]

Our motivation was to provide a clean Move implementation.

I now see uint16_t move16 in struct TTentry. I overlooked this when asked this question about the size of a Move.

I'll defer to @ianfab since I don't think I can safely (without great performance penalty or greatly increasing memory requirements) change struct TTentry (used for standard chess).

[ianfab]

Good point, I also overlooked this.

I think it is difficult to encode drops and king promotions with 16 bits. It would be possible to encode the promotion piece type using the bits where the origin square is supposed to be, but we would still need one bit each for the flags for piece drop and the king promotion. However, we only have four bits for the move type and the promotion piece type, where these have to fit in.

When the move type is not PROMOTION, the promotion piece type bits are not used (=0). So we essentially have enough room for 9 flags (3 move types x 3 promotion piece types), if I calculated correctly. I do not like this hacky way of encoding moves, but if there is no other way to fix TTentry, we should probably consider it.

[ddugovic]

It seems that any sort of hack must incur a performance penalty for standard chess. Perhaps that penalty can be minimized by using an uncommon move type for drops, such as PROMOTION (encoding from and to with the same value).

[isaacl]

Building on @ddugovic's comment, how about:

All drops have origin=destination.

• pawn drop encoded as NORMAL MoveType.
• piece drop encoded as PROMOTION MoveType with piece type specified using the promotion piece bits.

Care has to be taken to avoid conflicting with MOVE_NULL and MOVE_NONE:

/// Special cases are MOVE_NONE and MOVE_NULL. We can sneak these in because in
/// any normal move destination square is always different from origin square
/// while MOVE_NONE and MOVE_NULL have the same origin and destination square.

MOVE_NONE and MOVE_NULL could be renumbered to something in the enpassant or castling range which is impossible in normal circumstances. As far as I can tell, the value of these constants doesn't matter as long as it's unique.

[ianfab]

A problem with setting the origin and destination square to the same value is that it might yield the same value as MOVE_NULL or MOVE_NONE, so either the move type or the promotion piece must be guaranteed to be unequal to 0 (NORMAL and KNIGHT, respectively).

Edit: I have just seen your edit. I think this could work. Any suggestions on how to encode king promotions in antichess? Maybe we could use the move type CASTLING and set the promotion piece type !=KNIGHT.

[isaacl]

I'm working on a patch with my idea just for show, not tested.

One other idea is to combine ENPASSANT and CASTLING into a 'special' enum, as the origin/destition doesn't overlap. And then we have a fresh extra for DROPs.

Not sure about king promotion for antichess.

[isaacl]

So this is possible but pretty hairy. Maybe we should look at my other idea:

combine ENPASSANT and CASTLING. Then we have an extra spot for DROP type.

[ddugovic]

A problem with setting the origin and destination square to the same value is that it might yield the same value as MOVE_NULL or MOVE_NONE, so either the move type or the promotion piece must be guaranteed to be unequal to 0 (NORMAL and KNIGHT, respectively).

Certainly this is concerning; presently piece types are enumerated:

enum PieceType {
  NO_PIECE_TYPE, PAWN, KNIGHT, BISHOP, ROOK, QUEEN, KING,
  ALL_PIECES = 0,
  PIECE_TYPE_NB = 8
};

so a value of (pt << 12) should be unequal to zero unless I'm missing something. I guess we could coerce MOVE_NONE = 0 if we're worried about a collision?

enum Move : int {
  MOVE_NONE,
  MOVE_NULL = 65
};

[ianfab]

Promotion piece types are subtracted by KNIGHT to fit into 2 bits, so a knight underpromotion has a zero there.

[ddugovic]

Thanks, I entirely forgot about that. Sorry for my confusion. Hmm...

[ddugovic]

I think @isaacl has a point; combining two move types such as ENPASSANT and CASTLING together somehow could free up an entire MoveType for drops, which could be a good thing.

(Alternatively, we'd encode piece drops using PROMOTION and pawn drops some other way, but this seriously drifts from a clean implementation and might perform even worse.)

[ianfab]

If only the piece type of the dropped piece is encoded, will the color of the dropped piece be determined from the information about the side to move?

[ddugovic]

I suppose so as I'm unsure how else it could be determined.

[ianfab]

I was just wondering because I wasn't sure whether the position object is accessible everywhere where we have to determine the color of the dropped piece. Since all piece drops are written in uppercase, this seems to be the case.

[ddugovic]

I think such determination is only done when executing (or undoing) a move; I'm not aware of anything in the move selector which considers a move irrespective of the position.

[isaacl]

Can someone explain the ramifications of the current state (18bit)? Does it make stockfish slower overall, or only when built in certain contexts?

I'm willing to work on a patch for this, if it's impactful.

[ianfab]

To be precise drops use 22 bits. As far as I can tell this does not cause a slowdown, but the differentiation of cases with if-statements probably does (slightly). However, this would not change (or even get worse) if drops would be encoded with only 16 bits. In my opinion, the only reason to change the encoding is the issue with TTentry.

[ddugovic]

Possible evidence of this bug causing a TT misread/miswrite - maybe undo_move() or do_move() changed the position?
http://en.lichess.org/GDuMBfB5#26

Not reproducible from a clean start as 13... Nh4?? is the worst antichess move I have witnessed in my decades playing the game. I'm not complaining, it's excellent to have antichess support, I'm just very confused about how to reproduce this!

setoption name UCI_Variant value giveaway
info string variant giveaway startpos rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
position fen r6r/p1p1p2p/6n1/2P3p1/8/4P3/PP1K1P1P/RNB3N1 b - - 3 13
go movetime 800 depth 23

[sf-x]

Can someone explain the ramifications of the current state (18bit)? Does it make stockfish slower overall, or only when built in certain contexts?

I'm too lazy to check, but it seems to me that the move will be mis-stored in TT; drops will turn into an ordinary move from a1 (0) to the drop square (possibly even a legal move!), king promotions will turn into knight promotions.

[ddugovic]

@sf-x Yeah, I'm very concerned about these possible implications of a misread / miswrite.

[Vinvin20]

Damned ! about +80 Elo for this fix !!!!!

[ddugovic]

Given recent test results I can't help but wonder if recently my machine provided bad test results.
EDIT: Oh wait, the regression test is for standard chess, whereas the Elo gain is for crazyhouse!

[ianfab]

I also ran a local STC test for giveaway:

LLR: 2.96 (-2.94,2.94) [-10.00,5.00]
Total: 4202 W: 1103 L: 1080 D: 2019

I will open a PR as soon as the regression test for standard chess is finished.