用FEN解析器表示国际象棋位置

Question

我正在开发一个UCI国际象棋引擎，作为我的引擎的一部分，我需要一个位置表示来存储棋盘上每个棋子的位置以及所有有关游戏的信息，如抛出的权利、过道方块等。以人类可读的格式表示国际象棋位置的标准方法是福赛斯-爱德华兹表示法，它也用于UCI协议，并采取以下形式：

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

第一部分是片的放置，后面的一边移动，丢弃的权利(如果有的话)，在过道广场(如果有的话)，半移动的时钟，最后是全移动计数器。以下是根据国际象棋编程维基的分语法：

<FEN> ::=  <Piece Placement>
       ' ' <Side to move>
       ' ' <Castling ability>
       ' ' <En passant target square>
       ' ' <Halfmove clock>
       ' ' <Fullmove counter>

<Piece Placement> ::= <rank8>'/'<rank7>'/'<rank6>'/'<rank5>'/'<rank4>'/'<rank3>'/'<rank2>'/'<rank1>
<ranki>       ::= [<digit17>]<piece> {[<digit17>]<piece>} [<digit17>] | '8'
<piece>       ::= <white Piece> | <black Piece>
<digit17>     ::= '1' | '2' | '3' | '4' | '5' | '6' | '7'
<white Piece> ::= 'P' | 'N' | 'B' | 'R' | 'Q' | 'K'
<black Piece> ::= 'p' | 'n' | 'b' | 'r' | 'q' | 'k'

<Side to move> ::= {'w' | 'b'}

<Castling ability> ::= '-' | ['K'] ['Q'] ['k'] ['q'] (1..4)

<En passant target square> ::= '-' | <epsquare>
<epsquare>   ::= <fileLetter> <eprank>
<fileLetter> ::= 'a' | 'b' | 'c' | 'd' | 'e' | 'f' | 'g' | 'h'
<eprank>     ::= '3' | '6'

<Halfmove Clock> ::= <digit> {<digit>}
<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

<Fullmove counter> ::= <digit19> {<digit>}
<digit19> ::= '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
<digit>   ::= '0' | <digit19>

此外，由于这是国际象棋引擎的一部分，为了提高缓存性能，位置表示必须很小，而且移动块、获取抛出权限等操作必须是快速的，因为位置是在一个递归函数中修改的，该函数搜索最佳的下一步操作。

下面是pos.c的代码：

#include <ctype.h>
#include <errno.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <check.h>

#include "pos.h"

/*
 * The piece placement is stored in two formats, in piece-centric bitboard
 * arrays and in a square-centric array.
 * 
 * In the piece-centric format there are two arrays, one indexed by the color
 * and one indexed by the piece type, both storing bitboards where the set bits
 * represent a piece of that color or type at a square, where the square is
 * counted from the least significant bit to the most significant bit, from 0
 * to 63. The bitboards store pieces using a Little-Endian Rank-File mapping
 * (LERF), which means each byte, from the least significant byte to the most
 * significant byte represent a rank, and each bit of these bytes represent a
 * square on that rank. Which means that A1 is square 0, H1 is square 7, A2 is
 * square 8, H2 is square 15 and so on.
 * 
 * The square-centric format is just a flat array indexed by the square number
 * in a LERF mapping and each element of the array is a piece, or PIECE_NONE if
 * the square is empty.
 * 
 * The castling rights are stored in a nibble, the 2 least significant bits are
 * for white and the next 2 bits for black, the least significant and most
 * significant bits of each are for the queen and king sides respectively. A
 * set bit means that the king has the right to castle. Notice that having
 * right to castle does not mean that castling really is possible
 * (castling ability), it only means that neither the king nor the rook
 * corresponding to the castling side have moved throughout the game. In order
 * for castling to be possible, the following conditions must be met:
 * - The side must have castling rights;
 * - There are no pieces between the king and rook;
 * - The king will not be in check after castling.
 * 
 * The en passant square is not stored, but instead only its file. This is to
 * save space, since it is possible to recover the square by using the color of
 * the side to move. Because there are only 8 files the file is stored in just
 * the 3 least significant bits of a nibble and the most significant bit of the
 * nibble is set when there is an en passant square and unset otherwise. Since
 * both the castling rights and en passant file are stored in a nibble, I
 * stored both together in one byte.
 * 
 * Because changes to some of the position data can't be undone, like the
 * castling ability (if the rook moves back and forth there's no way to know
 * that it happened later on), all this irreversibe state is stored in a stack
 * where the top is the current state and to undo a move one only has to pop
 * the last irreversible state off the stack and undo the changes to the
 * reversibe data.
 */

struct irreversible_state {
    u8 castling_rights_and_enpassant;
    u8 halfmove_clock;
    u8 captured_piece;
    struct irreversible_state *previous;
};

struct position {
    struct irreversible_state *irreversible;
    u8 side_to_move;
    short fullmove_counter;
    u64 color_bb[2];
    u64 type_bb[6];
    Piece board[64];
};

static size_t parse_fen(Position *pos, const char *fen);
static size_t parse_fullmove_counter(Position *pos, const char *str);
static size_t parse_halfmove_clock(Position *pos, const char *str);
static size_t parse_enpassant(Position *pos, const char *str);
static size_t parse_castling(Position *pos, const char *str);
static size_t parse_side(Position *pos, const char *str);
static size_t parse_pieces(Position *pos, const char *str);
static int is_one_of(const char *str, char ch);
static char *trim(char *str);
static int get_index_of_first_bit(u64 n);
static int count_bits(u64 n);

int
main(int argc, char **argv)
{
    if (argc > 1) {
        if (!strlen(argv[1])) {
            fprintf(stderr, "FEN not provided.\n");
            return EXIT_FAILURE;
        }
        Position *pos = pos_create(trim(argv[1]));
        if (!pos) {
            fprintf(stderr, "Invalid FEN.\n");
            return EXIT_FAILURE;
        }
        pos_print(pos);
        pos_destroy(pos);
    } else {
        fprintf(stderr, "FEN not provided.\n");
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

void pos_print(const Position *pos)
{
    const char piece_table[] = {
        [PIECE_TYPE_PAWN ] = 'p', [PIECE_TYPE_KNIGHT] = 'n',
        [PIECE_TYPE_ROOK ] = 'r', [PIECE_TYPE_BISHOP] = 'b',
        [PIECE_TYPE_QUEEN] = 'q', [PIECE_TYPE_KING  ] = 'k',
    };

    Rank rank = RANK_8;
    File file = FILE_A;
    for (rank = RANK_8, file = FILE_A; file <= FILE_H || rank > RANK_1;) {
        if (file > FILE_H) {
            --rank;
            file = FILE_A;
            putchar('\n');
        }

        Square sq = pos_file_rank_to_square(file, rank);
        Piece piece = pos_get_piece_at(pos, sq);
        char ch = '\0';
        if (piece == PIECE_NONE) {
            ch = '0';
        } else {
            PieceType piece_type = pos_get_piece_type(piece);
            Color color = pos_get_piece_color(piece);
            ch = piece_table[piece_type];
            if (color == COLOR_WHITE)
                ch = toupper(ch);
        }
        printf("%c ", ch);
        ++file;
    }
    printf("\n\n");

    Color color = pos_get_side_to_move(pos);
    if (color == COLOR_WHITE)
        printf("Turn: white\n");
    else
        printf("Turn: black\n");

    printf("En passant: ");
    if (pos_enpassant_possible(pos)) {
        Square sq = pos_get_enpassant(pos);
        file = pos_get_file_of_square(sq);
        rank = pos_get_rank_of_square(sq);
        printf("%c%d\n", file + 'A', rank + 1);
    } else {
        printf("-\n");
    }

    printf("Castling rights: ");
    if (pos_has_castling_right(pos, COLOR_WHITE, CASTLING_SIDE_KING))
        putchar('K');
    if (pos_has_castling_right(pos, COLOR_WHITE, CASTLING_SIDE_QUEEN))
        putchar('Q');
    if (pos_has_castling_right(pos, COLOR_BLACK, CASTLING_SIDE_KING))
        putchar('k');
    if (pos_has_castling_right(pos, COLOR_BLACK, CASTLING_SIDE_QUEEN))
        putchar('q');
    printf("\n");

    printf("Halfmove clock: %d\n", pos_get_halfmove_clock(pos));
    printf("Fullmove counter: %d\n", pos_get_fullmove_counter(pos));
}

void pos_decrement_fullmove_counter(Position *pos)
{
    --pos->fullmove_counter;
}

void pos_increment_fullmove_counter(Position *pos)
{
    ++pos->fullmove_counter;
}

void pos_remove_castling(Position *pos, Color c, CastlingSide side)
{
    pos->irreversible->castling_rights_and_enpassant &= ~(1 << side <<
                                                          2 * c);
}

void pos_add_castling(Position *pos, Color c, CastlingSide side)
{
    pos->irreversible->castling_rights_and_enpassant |= 1 << side <<
                                                        2 * c;
}

void pos_flip_side_to_move(Position *pos)
{
    if (pos->side_to_move == COLOR_WHITE)
        pos->side_to_move = COLOR_BLACK;
    else
        pos->side_to_move = COLOR_WHITE;
}

void pos_set_captured_piece(Position *pos, Piece piece)
{
    pos->irreversible->captured_piece = piece;
}

/*
 * Remove a piece from a square.
 */
void pos_remove_piece(Position *pos, Square sq)
{
    const Piece piece = pos_get_piece_at(pos, sq);
    const u64 bb = U64(0x1) << sq;
    pos->color_bb[pos_get_piece_color(piece)] &= ~bb;
    pos->type_bb[pos_get_piece_type(piece)]  &= ~bb;
    pos->board[sq] = PIECE_NONE;
}

/*
 * Place a piece at a square, if another piece is at this square, it will be
 * removed first.
 * 
 * There's an important detail about this function. The bitboards are stored in
 * a piece centric format, so we can't just overwrite the old piece with the
 * new one if the pieces are of different types, the bitboard of the piece
 * being replaced would still store the piece as if it's still on the board,
 * because only the new piece's board would be modified. Because of that, the
 * old piece must be removed first with the pos_remove_piece function by the
 * caller. The reason why this is not done here is to avoid slowing down code
 * that places a piece in an empty square.
 */
void pos_place_piece(Position *pos, Square sq, Piece piece)
{
    const u64 bb = U64(0x1) << sq;
    if (pos->board[sq] != PIECE_NONE)
        pos_remove_piece(pos, sq);
    pos->color_bb[pos_get_piece_color(piece)] |= bb;
    pos->type_bb[pos_get_piece_type(piece)]  |= bb;
    pos->board[sq] = piece;
}

void pos_reset_halfmove_clock(Position *pos)
{
    pos->irreversible->halfmove_clock = 0;
}

void pos_increment_halfmove_clock(Position *pos)
{
    ++pos->irreversible->halfmove_clock;
}

void pos_unset_enpassant(Position *pos)
{
    pos->irreversible->castling_rights_and_enpassant &= 0xf;
}

/*
 * Set the possibility of en passant and store the file.
 */
void pos_set_enpassant(Position *pos, File file)
{
    pos->irreversible->castling_rights_and_enpassant &= 0x8f;
    pos->irreversible->castling_rights_and_enpassant |= 0x80;
    pos->irreversible->castling_rights_and_enpassant |= (file & 0x7) << 4;
}

Piece pos_get_captured_piece(const Position *pos)
{
    return pos->irreversible->captured_piece;
}

int pos_has_castling_right(const Position *pos, Color c, CastlingSide side)
{
    return (pos->irreversible->castling_rights_and_enpassant &
            0x1 << side << 2 * c) != 0;
}

int pos_get_fullmove_counter(const Position *pos)
{
    return pos->fullmove_counter;
}

int pos_get_halfmove_clock(const Position *pos)
{
    return pos->irreversible->halfmove_clock;
}

int pos_enpassant_possible(const Position *pos)
{
    return pos->irreversible->castling_rights_and_enpassant & 0x80;
}

Square pos_get_enpassant(const Position *pos)
{
    const File f = (pos->irreversible->castling_rights_and_enpassant
                    & 0x70) >> 4;
    const Rank r = pos->side_to_move == COLOR_WHITE ? RANK_6 : RANK_3;
    return pos_file_rank_to_square(f, r);
}

Color pos_get_side_to_move(const Position *pos)
{
    return pos->side_to_move;
}

Square pos_get_king_square(const Position *pos, Color c)
{
    const Piece piece = pos_make_piece(PIECE_TYPE_KING, c);
    const u64 bb = pos_get_piece_bitboard(pos, piece);
    return get_index_of_first_bit(bb);
}

Piece pos_get_piece_at(const Position *pos, Square sq)
{
    return pos->board[sq];
}

int pos_get_number_of_pieces(const Position *pos, Piece piece)
{
    const u64 bb = pos_get_piece_bitboard(pos, piece);

    return count_bits(bb);
}

u64 pos_get_piece_bitboard(const Position *pos, Piece piece)
{
    const PieceType type = pos_get_piece_type(piece);
    const Color color = pos_get_piece_color(piece);
    const u64 bb = pos->type_bb[type] & pos->color_bb[color];
    return bb;
}

u64 pos_get_color_bitboard(const Position *pos, Color c)
{
    return pos->color_bb[c];
}

void pos_backtrack_irreversible_state(Position *pos)
{
    struct irreversible_state *const current = pos->irreversible;
    pos->irreversible = pos->irreversible->previous;
    free(current);
}

/*
 * This function must be called before externally calling any function that
 * modifies the irreversible state of the position.
 *
 * It creates a new copy of the old irreversible state and pushes
 * it onto the stack, making it the current one. The reversible state is
 * preserved since changes can be undone.
 */
void pos_start_new_irreversible_state(Position *pos)
{
    struct irreversible_state *current = pos->irreversible;
    struct irreversible_state *new = malloc(sizeof(*new));
    if (!new) {
        fprintf(stderr, "Could not allocate memory.\n");
        exit(1);
    }
    memcpy(new, current, sizeof(struct irreversible_state));
    new->previous = current;
    pos->irreversible = new;
}

/*
 * Create a new position using FEN. It returns NULL if the FEN is invalid. It is
 * assumed that the string it not empty and that there are no leading or trailing
 * white spaces. Keep in mind that whether the position is actually valid
 * according to the rules of chess is not checked, so even if the FEN string is a
 * valid FEN string according to the grammar, the position might be illegal. For
 * example, the number of pawns in the board is not checked, so it is possible to
 * set up a position using a FEN string that describes a board with 9 pawns. This
 * is intentional, as the user might want to set up a non-standard board.
 */
Position *pos_create(const char *fen)
{
    Position *pos = malloc(sizeof(Position));
    if (!pos) {
        fprintf(stderr, "Could not allocate memory.\n");
        exit(1);
    }
    pos->irreversible = malloc(sizeof(struct irreversible_state));
    if (!pos->irreversible) {
        fprintf(stderr, "Could not allocate memory.\n");
        exit(1);
    }

    pos->fullmove_counter = 0;
    pos->irreversible->previous = NULL;
    pos->irreversible->captured_piece = PIECE_NONE;
    pos_reset_halfmove_clock(pos);
    pos_unset_enpassant(pos);
    pos_remove_castling(pos, COLOR_WHITE, CASTLING_SIDE_KING);
    pos_remove_castling(pos, COLOR_WHITE, CASTLING_SIDE_QUEEN);
    pos_remove_castling(pos, COLOR_BLACK, CASTLING_SIDE_KING);
    pos_remove_castling(pos, COLOR_BLACK, CASTLING_SIDE_QUEEN);
    for (Square sq = A1; sq <= H8; ++sq)
        pos->board[sq] = PIECE_NONE;
    for (size_t i = 0; i < 6; ++i)
        pos->type_bb[i] = 0;
    for (size_t i = 0; i < 2; ++i)
        pos->color_bb[i] = 0;

    size_t rc = parse_fen(pos, fen);
    if (rc != strlen(fen)) {
        pos_destroy(pos);
        return NULL;
    }
    return pos;
}

void pos_destroy(Position *pos)
{
    struct irreversible_state *prev = NULL;

    for (struct irreversible_state *p = pos->irreversible; p; p = prev) {
        prev = p->previous;
        free(p);
    }
    free(pos);
}

Square pos_file_rank_to_square(File f, Rank r)
{
    return 8 * r + f;
}

File pos_get_file_of_square(Square sq)
{
    return sq % 8;
}

Rank pos_get_rank_of_square(Square sq)
{
    return sq / 8;
}

Color pos_get_piece_color(Piece piece)
{
    return piece & 0x1;
}

PieceType pos_get_piece_type(Piece piece)
{
    return piece >> 1;
}

Piece pos_make_piece(PieceType pt, Color c)
{
    return pt << 1 | c;
}

/*
 * Modifies a position by parsing a FEN string and returns the number of
 * characters read, if it's less than the length then an error ocurred. Each of
 * the parse_* functions return the number of characters that were read, and if
 * the sequence of characters is invalid they return 0.
 */
static size_t parse_fen(Position *pos, const char *fen)
{
    size_t (*const steps[])(Position *, const char *) = {
        parse_pieces,
        parse_side,
        parse_castling,
        parse_enpassant,
        parse_halfmove_clock,
        parse_fullmove_counter,
    };
    const size_t num_steps = sizeof(steps) / sizeof(steps[0]);

    size_t rc = 0, ret = 0;
    for (size_t i = 0; i < num_steps; ++i) {
        ret = steps[i](pos, fen);
        if (!ret)
            return 0;
        fen += ret;
        rc += ret;
        if (i < num_steps - 1) {
            if (fen[0] != ' ')
                return 0;
            else
                ++rc;
        }
        ++fen;
    }

    return rc;
}

/*
 * Both the parse_fullmove_counter and parse_halfmove_clock functions parse the
 * number up to the first invalid character (a character that is not part of a
 * number). So the functions will not fail because of the space character after
 * the number in the FEN string.
 */
static size_t parse_fullmove_counter(Position *pos, const char *str)
{
    char *endptr = NULL;
    errno = 0;
    unsigned long counter = strtoul(str, &endptr, 10);
    if (errno == ERANGE)
        return 0;
    else if (endptr == str)
        return 0;
    else if (counter > SHRT_MAX)
        return 0;
    pos->fullmove_counter = (short)counter;
    return endptr - str;
}

static size_t parse_halfmove_clock(Position *pos, const char *str)
{
    char *endptr = NULL;
    errno = 0;
    unsigned long clock = strtoul(str, &endptr, 10);
    if (errno == ERANGE)
        return 0;
    else if (endptr == str)
        return 0;
    else if (clock > SHRT_MAX)
        return 0;
    pos->irreversible->halfmove_clock = (u8)clock;
    return endptr - str;
}

static size_t parse_enpassant(Position *pos, const char *str)
{
    if (str[0] == '-')
        return 1;
    if (!str[0] || !str[1])
        return 0;
    else if (str[0] < 'a' || str[0] > 'h' ||
         (str[1] != '3' && str[1] != '6'))
        return 0;
    File file = str[0] - 'a';
    pos_set_enpassant(pos, file);
    return 2;
}

static size_t parse_castling(Position *pos, const char *str)
{
    if (str[0] == '-')
        return 1;
    int Kcnt = 0, Qcnt = 0, kcnt = 0, qcnt = 0;
    size_t rc = 0;
    for (; str[rc] && str[rc] != ' '; ++rc) {
        switch (str[rc]) {
        case 'K':
            pos_add_castling(pos, COLOR_WHITE,  CASTLING_SIDE_KING);
            ++Kcnt;
            break;
        case 'Q':
            pos_add_castling(pos, COLOR_WHITE, CASTLING_SIDE_QUEEN);
            ++Qcnt;
            break;
        case 'k':
            pos_add_castling(pos, COLOR_BLACK, CASTLING_SIDE_KING);
            ++kcnt;
            break;
        case 'q':
            pos_add_castling(pos, COLOR_BLACK,  CASTLING_SIDE_QUEEN);
            ++qcnt;
            break;
        default:
            return 0;
        }
        if (Kcnt > 1 || Qcnt > 1 || kcnt > 1 || qcnt > 1)
            return 0;
    }
    return rc;
}

static size_t parse_side(Position *pos, const char *str)
{
    switch (str[0]) {
    case 'w':
        pos->side_to_move = COLOR_WHITE;
        break;
    case 'b':
        pos->side_to_move = COLOR_BLACK;
        break;
    default:
        return 0;
    }
    return 1;
}

static size_t parse_pieces(Position *pos, const char *str)
{
    const Piece table[] = {
        ['P'] = PIECE_WHITE_PAWN,   ['p'] = PIECE_BLACK_PAWN,
        ['N'] = PIECE_WHITE_KNIGHT, ['n'] = PIECE_BLACK_KNIGHT,
        ['R'] = PIECE_WHITE_ROOK,   ['r'] = PIECE_BLACK_ROOK,
        ['B'] = PIECE_WHITE_BISHOP, ['b'] = PIECE_BLACK_BISHOP,
        ['Q'] = PIECE_WHITE_QUEEN,  ['q'] = PIECE_BLACK_QUEEN,
        ['K'] = PIECE_WHITE_KING,   ['k'] = PIECE_BLACK_KING,
    };

    size_t rc = 0;
    File file = FILE_A;
    Rank rank = RANK_8;
    for (size_t i = 0; file <= FILE_H || rank > RANK_1; ++i) {
        if (!str[i])
            return 0;
        char ch = str[i];
        ++rc;

        if (file > FILE_H) {
            if (str[i] && str[i] != '/')
                return 0;
            --rank;
            file = FILE_A;
            continue;
        }

        if (isdigit(ch)) {
            int digit = ch - '0';
            if (digit > 8 || digit < 1 || !digit || file + digit > 8)
                return 0;
            file += digit;
        } else if (is_one_of("PNRBQKpnrbqk", ch)) {
            Piece piece = table[(size_t)ch];
            Square sq = pos_file_rank_to_square(file, rank);
            pos_place_piece(pos, sq, piece);
            ++file;
        } else {
            return 0;
        }
    }

    return rc;
}

/*
 * Check if ch is one of the characters in str, where str is a string containing
 * all characters to be checked and not separated by space.
 * For example:
 * is_one_of("ar4h", 'r')
 * returns 1, but
 * is_one_of("r57g", '9')
 * returns 0.
 */
static int is_one_of(const char *str, char ch)
{
    if (!ch || !strchr(str, ch))
        return 0;
    return 1;
}

static char *trim(char *str)
{
    char *end;

    while (isspace(*str))
        ++str;
    if (!*str)
        return str;
    end = str + strlen(str) - 1;
    while (end > str && isspace(*end))
        --end;
    end[1] = '\0';
    return str;
}

static int
get_index_of_first_bit(u64 n)
{
#if defined(__clang__) || defined(__GNUC__)
    return __builtin_ffsll(n) - 1;
#else
    static const int index[64] = {
        0,  47,  1, 56, 48, 27,  2, 60,
        57, 49, 41, 37, 28, 16,  3, 61,
        54, 58, 35, 52, 50, 42, 21, 44,
        38, 32, 29, 23, 17, 11,  4, 62,
        46, 55, 26, 59, 40, 36, 15, 53,
        34, 51, 20, 43, 31, 22, 10, 45,
        25, 39, 14, 33, 19, 30,  9, 24,
        13, 18,  8, 12,  7,  6,  5, 63,
    };
    static const u64 debruijn = U64(0x03f79d71b4cb0a89);

    return index[((n ^ (n - 1)) * debruijn) >> 58];
#endif
}

static int
count_bits(u64 n)
{
#if defined(__clang__) || defined(__GNUC__)
    return __builtin_popcountll(n);
#else
    static const u64 m1  = 0x5555555555555555;
    static const u64 m2  = 0x3333333333333333;
    static const u64 m4  = 0x0f0f0f0f0f0f0f0f;
    static const u64 m8  = 0x00ff00ff00ff00ff;
    static const u64 m16 = 0x0000ffff0000ffff;
    static const u64 m32 = 0x00000000ffffffff;
    static const u64 h01 = 0x0101010101010101;

    x -= (x >> 1) & m1;
    x = (x & m2) + ((x >> 2) & m2);
    x = (x + (x >> 4)) & m4;
    return (x * h01) >> 56;
#endif
}

这是pos.h的代码：

#ifndef POSITION_H
#define POSITION_H

#define U64(n) n##ull

typedef uint64_t u64;
typedef uint8_t u8;

typedef enum direction {
    NORTH,
    NORTHEAST,
    EAST,
    SOUTHEAST,
    SOUTH,
    SOUTHWEST,
    WEST,
    NORTHWEST,
} Direction;

typedef enum file {
    FILE_A, FILE_B, FILE_C, FILE_D,
    FILE_E, FILE_F, FILE_G, FILE_H,
} File;

typedef enum rank {
    RANK_1, RANK_2, RANK_3, RANK_4,
    RANK_5, RANK_6, RANK_7, RANK_8,
} Rank;

typedef enum square {
    A1, B1, C1, D1, E1, F1, G1, H1,
    A2, B2, C2, D2, E2, F2, G2, H2,
    A3, B3, C3, D3, E3, F3, G3, H3,
    A4, B4, C4, D4, E4, F4, G4, H4,
    A5, B5, C5, D5, E5, F5, G5, H5,
    A6, B6, C6, D6, E6, F6, G6, H6,
    A7, B7, C7, D7, E7, F7, G7, H7,
    A8, B8, C8, D8, E8, F8, G8, H8,
} Square;

/*
 * It's safe to get the opposite color with the ! operator on the color.
 */
typedef enum color {
    COLOR_WHITE,
    COLOR_BLACK,
} Color;

typedef enum piece_type {
    PIECE_TYPE_PAWN,
    PIECE_TYPE_KNIGHT,
    PIECE_TYPE_ROOK,
    PIECE_TYPE_BISHOP,
    PIECE_TYPE_QUEEN,
    PIECE_TYPE_KING,
} PieceType;

typedef enum piece {
    PIECE_WHITE_PAWN   = COLOR_WHITE | PIECE_TYPE_PAWN   << 1,
    PIECE_WHITE_KNIGHT = COLOR_WHITE | PIECE_TYPE_KNIGHT << 1,
    PIECE_WHITE_ROOK   = COLOR_WHITE | PIECE_TYPE_ROOK   << 1,
    PIECE_WHITE_BISHOP = COLOR_WHITE | PIECE_TYPE_BISHOP << 1,
    PIECE_WHITE_QUEEN  = COLOR_WHITE | PIECE_TYPE_QUEEN  << 1,
    PIECE_WHITE_KING   = COLOR_WHITE | PIECE_TYPE_KING   << 1,

    PIECE_BLACK_PAWN   = COLOR_BLACK | PIECE_TYPE_PAWN   << 1,
    PIECE_BLACK_KNIGHT = COLOR_BLACK | PIECE_TYPE_KNIGHT << 1,
    PIECE_BLACK_ROOK   = COLOR_BLACK | PIECE_TYPE_ROOK   << 1,
    PIECE_BLACK_BISHOP = COLOR_BLACK | PIECE_TYPE_BISHOP << 1,
    PIECE_BLACK_QUEEN  = COLOR_BLACK | PIECE_TYPE_QUEEN  << 1,
    PIECE_BLACK_KING   = COLOR_BLACK | PIECE_TYPE_KING   << 1,

    PIECE_NONE = 0xff /* Only used for the array board. */
} Piece;

typedef enum castling_side {
    CASTLING_SIDE_QUEEN,
    CASTLING_SIDE_KING,
} CastlingSide;

struct position;
typedef struct position Position;

void pos_print(const Position *pos);
void pos_decrement_fullmove_counter(Position *pos);
void pos_increment_fullmove_counter(Position *pos);
void pos_remove_castling(Position *pos, Color c, CastlingSide side);
void pos_add_castling(Position *pos, Color c, CastlingSide side);
void pos_flip_side_to_move(Position *pos);
void pos_set_captured_piece(Position *pos, Piece piece);
void pos_remove_piece(Position *pos, Square sq);
void pos_place_piece(Position *pos, Square sq, Piece piece);
void pos_reset_halfmove_clock(Position *pos);
void pos_increment_halfmove_clock(Position *pos);
void pos_unset_enpassant(Position *pos);
void pos_set_enpassant(Position *pos, File file);
Piece pos_get_captured_piece(const Position *pos);
int pos_has_castling_right(const Position *pos, Color c, CastlingSide side);
int pos_get_fullmove_counter(const Position *pos);
int pos_get_halfmove_clock(const Position *pos);
int pos_enpassant_possible(const Position *pos);
Square pos_get_enpassant(const Position *pos);
Color pos_get_side_to_move(const Position *pos);
Square pos_get_king_square(const Position *pos, Color c);
Piece pos_get_piece_at(const Position *pos, Square sq);
int pos_get_number_of_pieces(const Position *pos, Piece piece);
u64 pos_get_piece_bitboard(const Position *pos, Piece piece);
u64 pos_get_color_bitboard(const Position *pos, Color c);
void pos_backtrack_irreversible_state(Position *pos);
void pos_start_new_irreversible_state(Position *pos);
Position *pos_create(const char *fen);
void pos_destroy(Position *pos);
Square pos_file_rank_to_square(File f, Rank r);
File pos_get_file_of_square(Square sq);
Rank pos_get_rank_of_square(Square sq);
Color pos_get_piece_color(Piece piece);
PieceType pos_get_piece_type(Piece piece);
Piece pos_make_piece(PieceType pt, Color c);

#endif

我补充说，main函数只是为了有一个输出，它不是最终程序的一部分，而get_index_of_first_bit和count_bits函数以及u8和u64的类型定义应该是另一个文件的一部分，我将它们添加到pos.c中只是为了避免向问题中添加另一个文件。

如果您在一个终端上运行这个程序，以一个FEN字符串作为第一个参数，那么输出应该如下所示：

r n b q k b n r
p p p p p p p p
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
P P P P P P P P
R N B Q K B N R

Turn: white
En passant: -
Castling rights: KQkq
Halfmove clock: 0
Fullmove counter: 1

这是输入字符串“RNBQKBNR/PPPPPPPP/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -01”的输出。如果没有提供输入，或者字符串不是有效的分字符串，程序就会抱怨。

我希望对代码的正确性、板表示和代码的外观进行一些反馈，同时记住代码是为了性能而编写的。请注意，FEN解析器不需要运行得很快，因为它只在象棋GUI发送命令设置位置到引擎时才运行一次。

Answer 1

医生回顾

代码可能会考虑其中的一些问题。

，如果rook没有移动，但是不在那里，

怎么办？

与“它只意味着国王或相应的推车既没有移动整个游戏”，一辆车应该考虑移动，如果它是采取，即使从它原来的正方形。否则一个人可以用鬼车城堡，因为它从来不动。

50移动规则

分缺乏信息，表明最后一次采取或典当前进的时间。

3重复

FEN缺乏必要的信息来检查可能的结果重复3次。

对于这一点和过眼云烟的50移动关注，一个以前和现在的分线的集合将足以记录国家。一个分钱不足以容纳这个州。

Castling

还需要2项：

国王在试图城堡的时候没有受到控制。

国王不会越过支票的。

僵局和其他

如果一方缺乏合法的行动怎么办？

如果FEN状态由于位置原因无效怎么办？(抛下的旗子没问题，没有车，没有典当，白色可以移动，但没有一块。)

需要多少错误检查？

代码评审

充分利用const

很好地使用pop前缀

还能有更多。pop.h创建许多可能与其他代码冲突的命名项，如NORTH、FILE_A、A1、Square、Color等。考虑更普遍地使用pop前缀。

充分利用sizeof

使用标准名称

u8, u64可能有助于快速编写代码，但缺乏uint8_t, uint64_t的清晰性。用标准。

避免假设unsigned long long和uint64_t是相同的

unsigned long long现在很常见，因为uint64_t被指定为至少64位。与其使用unsigned long long常量#define U64(n) n##ull，不如使用<stdint.h>中的标准UINT64_C(value)。

分配给引用对象，而不是

类型。

考虑下面的2条。你觉得哪一个更容易编码，检查和维护？哪一个要求编码器正确同步类型和对象？

pos->irreversible = malloc(sizeof(struct irreversible_state));
// vs.
pos->irreversible = malloc(sizeof pos->irreversible[0]);

幻数

为什么是6号？

for (size_t i = 0; i < 6; ++i)
  pos->type_bb[i] = 0;

相反：

size_t n = sizeof type_bb / sizeof type_bb[0];
for (size_t i = 0; i < n; ++i)
  pos->type_bb[i] = 0;

或者简单的

memset(pos->type_bb, sizeof pos->type_bb, 0);

风格:为什么是十六进制？

0x的惊人使用。

// return piece & 0x1;
return piece & 1;

风格：()

即使在使用了多年的C语言之后，像pt << 1 | c这样的代码也会使我暂停并检查这些优先级规则。考虑(pt << 1) | c的代码，否则依赖较不常见的优先级规则。

风格：{}

即使对于1行块，也可以考虑{}。

    //if (!ret)
    //    return 0;
    if (!ret) {
        return 0;
    }

Documentation

各种static函数缺乏文档。

Pedantic：is...(negative)

if (isdigit(ch))是UB时ch < 0 (而不是EOF)。使用unsigned char ch。

enum size

请注意，Piece board[64];可能大于64字节，因为只需要8位的enum piece可能更宽.如果缩小大小很重要，请使用uint8_t board[64]。

速度与空间

不要认为较小的内存占用速度更快

通常，在需要最小宽度对象数组时使用它们。否则，请使用int、unsigned、double，然后根据需要扩展。

要实现速度和空间的平衡，可以考虑放弃抛出的比特，通过并使用struct成员。但是要使用uint8_t board[64]。

short?

很短的理由

 // short fullmove_counter
 int fullmove_counter

非标准板支持

嗯，有两个以上的车钩，一个国王，我认为需要两个以上的扔旗。