Optimised Algebraic Notation

[leanchess]

It would be a cool feature of a notation that it could be read in two directions, though.

I've specified something like this https://github.com/Sopel97/chess_pos_db ... s/Eran.cpp (Extended Reverse Algebraic Notation, which is based on Reverse Algebraic Notation but includes castling rights and ep square)and even used it for a chess position database to support going backward . It's fun, but requires too much information for a general purpose notation (I managed to compress it only to 27 bits in a packed binary implementation too, compared to what, like 12 bits for normal move?), so I'm not sure why the original proposal is trying to include it. It is however very useful for identifying transpositions in a database.

I'll allow to repeat myself - what's wrong with uci notation?

Getting a little sidetracked here, I'm not sure what you mean by "compress it only to 27 bits". Wouldn't it neatly fit in 24 bits?

Code: Select all

struct rmove {
    int fromSquare:    6;
    int toSquare:      6;    
    int fromPiece:     3; // MovedKing = 0, MovedRook = 7
    int toPiece:       3; // None = 0, MovedRook = 7
    int flags:         2; // CastleQueen = 1, CastleKing = 2
                          // PromoQueen = 0, PromoKnight = 1
                          // PromoRook = 2, PromoBishop = 3
    int isEnPassant:   1;
    int enPassantFile: 3;
};

[Sopel]

It would be a cool feature of a notation that it could be read in two directions, though.

I've specified something like this https://github.com/Sopel97/chess_pos_db ... s/Eran.cpp (Extended Reverse Algebraic Notation, which is based on Reverse Algebraic Notation but includes castling rights and ep square)and even used it for a chess position database to support going backward . It's fun, but requires too much information for a general purpose notation (I managed to compress it only to 27 bits in a packed binary implementation too, compared to what, like 12 bits for normal move?), so I'm not sure why the original proposal is trying to include it. It is however very useful for identifying transpositions in a database.

I'll allow to repeat myself - what's wrong with uci notation?

Getting a little sidetracked here, I'm not sure what you mean by "compress it only to 27 bits". Wouldn't it neatly fit in 24 bits?

Code: Select all

struct rmove {
    int fromSquare:    6;
    int toSquare:      6;    
    int fromPiece:     3; // MovedKing = 0, MovedRook = 7
    int toPiece:       3; // None = 0, MovedRook = 7
    int flags:         2; // CastleQueen = 1, CastleKing = 2
                          // PromoQueen = 0, PromoKnight = 1
                          // PromoRook = 2, PromoBishop = 3
    int isEnPassant:   1;
    int enPassantFile: 3;
};

you need to preserve castling rights

[leanchess]

you need to preserve castling rights

Those are determined by the corresponding king's and rook's "moved" bits.

[Sopel]

you need to preserve castling rights

Those are determined by the corresponding king's and rook's "moved" bits.

No. A king move (including castling) may reset any of the 16 possible castling rights values to 0. Rook move may reset any of the possible 4 castling rights corresponding to each rook. You cannot retrieve the previous castling rights just from knowing which piece moved.

[leanchess]

Back on the topic, I believe I found a (mostly) backwards-compatible solution.

Since PGN seems to support both 'x' and ':' for capture delimiter, we could agree on the following:

• '-' for no capture
• 'x' for normal capture
• ':' for e.p. capture

As for castling, it appears that we cannot have both reversibility and compatibity.

A "dumb terminal" in C# that should accept a move in the proposed notation (even allowing for some omissions):

Code: Select all

        public void MakeMove(string ran)
        {
            char[] buffer = ran.ToCharArray();
            int i = 0;
            ReadPiece(buffer, ref i);
            var (rankFrom, fileFrom) = ReadSquare(buffer, ref i);
            ReadCapture(buffer, ref i, out var enPassant);
            var (rankTo, fileTo) = ReadSquare(buffer, ref i);
            var piece = board[rankFrom, fileFrom];
            if (i < ran.Length)
                piece = (byte)(GetColor(piece) | ReadPiece(buffer, ref i));
            board[rankTo, fileTo] = piece;
            board[rankFrom, fileFrom] = 0;
            if (enPassant == true)
                board[rankFrom, fileTo] = 0;
        }

        private static (int rank, int file) ReadSquare(char[] buffer, ref int i)
        {
            int file = buffer[i++] - 'a';
            int rank = 8 - (buffer[i++] - '0');
            return (rank, file);
        }

        private static int ReadCapture(char[] buffer, ref int i, out bool? enPassant)
        {
            enPassant = null;
            switch (buffer[i])
            {
                case '-':
                    i++;
                    return 0;
                case 'x':
                    enPassant = false;
                    i++;
                    return ReadPiece(buffer, ref i);
                case ':':
                    enPassant = true;
                    i++;
                    return ReadPiece(buffer, ref i);
                default:
                    return 0;
            }
        }

        private static byte ReadPiece(char[] buffer, ref int i)
        {
            int piece = Array.IndexOf(PieceChars, buffer[i]);
            if (piece < 0)
                return Pawn;
            i++;
            return (byte)piece;
        }

        private static int GetColor(byte piece) => piece & (White | Black);

[leanchess]

you need to preserve castling rights

Those are determined by the corresponding king's and rook's "moved" bits.

No. A king move (including castling) may reset any of the 16 possible castling rights values to 0. Rook move may reset any of the possible 4 castling rights corresponding to each rook. You cannot retrieve the previous castling rights just from knowing which piece moved.

Suppose we keep a dirty bit for every square. Then each one of the castling rights may be determined by NORing the bits in the squares containing the respective rook and king, hence the MovedRook and MovedKing values in From piece and MovedKing value in To piece (as only the rook can be legally captured).

[Sopel]

you need to preserve castling rights

Those are determined by the corresponding king's and rook's "moved" bits.

No. A king move (including castling) may reset any of the 16 possible castling rights values to 0. Rook move may reset any of the possible 4 castling rights corresponding to each rook. You cannot retrieve the previous castling rights just from knowing which piece moved.

Suppose we keep a dirty bit for every square. Then each one of the castling rights may be determined by NORing the bits in the squares containing the respective rook and king, hence the MovedRook and MovedKing values in From piece and MovedKing value in To piece (as only the rook can be legally captured).

No, because the rook/king can move away and back to its original position. You don't know what castling rights were reset by the previous move.

[Sopel]

you need to preserve castling rights

Those are determined by the corresponding king's and rook's "moved" bits.

No. A king move (including castling) may reset any of the 16 possible castling rights values to 0. Rook move may reset any of the possible 4 castling rights corresponding to each rook. You cannot retrieve the previous castling rights just from knowing which piece moved.

Suppose we keep a dirty bit for every square. Then each one of the castling rights may be determined by NORing the bits in the squares containing the respective rook and king, hence the MovedRook and MovedKing values in From piece and MovedKing value in To piece (as only the rook can be legally captured).

Consider
[pgn]1. e4 d5 2. Nf3 e5 3. Be2 d4 4. d3 Be6 5. Rg1 g6 6. Rh1 h5 7. Bd2 Be7 8. c3 dxc3 9. bxc3 c6 10. Qb3 b5 11. Na3 Qd6 12. O-O-O[/pgn]
How do you encode that last castling moves to know that the previous castling rights were Qkq and not KQkq

[pgn]1. h4 g5 2. hxg5 h6 3. gxh6 Rxh6 4. Rh3 Rh8 5. Rxh8[/pgn]
How do you encode the last capture to know that the previous castling rights were Qq

[R. Tomasi]

you need to preserve castling rights

Those are determined by the corresponding king's and rook's "moved" bits.

No. A king move (including castling) may reset any of the 16 possible castling rights values to 0. Rook move may reset any of the possible 4 castling rights corresponding to each rook. You cannot retrieve the previous castling rights just from knowing which piece moved.

Suppose we keep a dirty bit for every square. Then each one of the castling rights may be determined by NORing the bits in the squares containing the respective rook and king, hence the MovedRook and MovedKing values in From piece and MovedKing value in To piece (as only the rook can be legally captured).

Consider
[pgn]1. e4 d5 2. Nf3 e5 3. Be2 d4 4. d3 Be6 5. Rg1 g6 6. Rh1 h5 7. Bd2 Be7 8. c3 dxc3 9. bxc3 c6 10. Qb3 b5 11. Na3 Qd6 12. O-O-O[/pgn]
How do you encode that last castling moves to know that the previous castling rights were Qkq and not KQkq

[pgn]1. h4 g5 2. hxg5 h6 3. gxh6 Rxh6 4. Rh3 Rh8 5. Rxh8[/pgn]
How do you encode the last capture to know that the previous castling rights were Qq

I think an idea may be to simply encode the castling rights into the move. That would be 4bits. The drawback is that moving a piece with KQkq is considered a different move than moving it with Qkq.

[leanchess]

Code: Select all

void make(struct rmove m, int color) {
    int piece = m.fromPiece;
    switch (piece) {
        case MovedRook: piece = Rook;
                        break;
        case MovedKing: piece = King;
                        break; // See what I did here?
        case King:      if (m.flags) {
                            //...
                        }
                        break;
        case Pawn:      //...
                        break;
    }
    board[m.fromSquare] = 0;
    board[m.toSquare] = piece | Moved | color;
    //...
}

void unmake(struct rmove m, int color) {
    int toPiece = m.toPiece != MovedRook
        ? m.toPiece
        : (Rook | Moved);
    board[m.toSquare] = toPiece | (color ^ Color);
    //...
}