я разрабатываю UCI шахматный движок, и как часть моего движка мне нужно представление позиции, в котором хранится положение каждой фигуры на доске и вся информация об игре, такая как права на рокировку, поле на проходе и т. д. Стандартный способ представления шахматной позиции в удобочитаемый формат — это Обозначение Форсайта-Эдвардса (FEN)который также используется в протоколе UCI и принимает следующий вид:
rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
Первая часть — это расстановка фигур, следующая за стороной для хода, права на рокировку (если есть), квадрат на проходе (если есть), часы на полхода и, наконец, счетчик на полный ход. Вот грамматика FEN в соответствии с Шахматное программирование вики:
<FEN> ::= <Piece Placement>
' ' <Side to move>
' ' <Castling ability>
' ' <En passant target square>
' ' <Halfmove clock>
' ' <Fullmove counter>
<Piece Placement> ::= <rank8>"https://codereview.stackexchange.com/"<rank7>"https://codereview.stackexchange.com/"<rank6>"https://codereview.stackexchange.com/"<rank5>"https://codereview.stackexchange.com/"<rank4>"https://codereview.stackexchange.com/"<rank3>"https://codereview.stackexchange.com/"<rank2>"https://codereview.stackexchange.com/"<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] != "https://codereview.stackexchange.com/")
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/8/PPPPPPPP/RNBQKBNR w KQkq — 0 1». Если входные данные не предоставлены или строка не является допустимой строкой FEN, программа выдаст сообщение об ошибке.
Мне нужны отзывы о правильности кода, представлении платы и внешнем виде кода в целом, учитывая, что код был написан для повышения производительности. Обратите внимание, что синтаксический анализатор FEN не должен быть быстрым, поскольку он запускается только один раз, когда графический интерфейс шахмат отправляет команду для установки позиции движку.
Сердце
1 ответ
Обзор документа
Возможно, код учитывает некоторые из этих проблем.
Что делать, если ладья не взолнованный но его нет
Поскольку «это означает только то, что ни король, ни ладья, соответствующие рокирующей стороне, не двигались на протяжении всей игры», ладью следует считать взолнованный если он взят, даже если из его исходного квадрата. В противном случае можно было бы рокироваться призрачной ладьей, поскольку она никогда не взолнованный.
правило 50 ходов
В FEN отсутствует информация, указывающая, когда в последний раз брали фигуру или продвигали пешку.
3 повторения
В FEN отсутствует информация, необходимая для проверки возможных исходов, повторяющихся 3 раза.
Для этого и предыдущей проблемы с 50 ходами коллекция предыдущих и текущих строк FEN будет достаточно, чтобы записать государство. Одного FEN недостаточно для размещения государства.
Кастинг
Нужно еще 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используйте стандарт UINT64_C(value) от <stdint.h>.
Выделить ссылочному объекту, а не типу
Рассмотрим 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;
}
Документация
Различные static функциям не хватает документации.
Педантичный: is...(negative)
if (isdigit(ch)) это УБ, когда ch < 0 (и нет EOF). Использовать unsigned char ch.
enum размер
Обратите внимание, что Piece board[64]; может быть шире 64 байт, так как enum piece, которому требуется всего 8 бит, может быть шире. Использовать uint8_t board[64] если важен уменьшенный размер.
Скорость против пространства
Не думайте, что меньший объем памяти быстрее — часто бывает наоборот.
В общем, используйте объекты минимальной ширины, когда необходим их массив. В противном случае используйте int, unsigned, double а затем шире по мере необходимости.
Для баланса между скоростью и пространством рассмотрите возможность отказа от рокировки на ходу и используйте struct члены. Тем не менее использовать uint8_t board[64].
short?
Маленькая причина для краткости
// short fullmove_counter
int fullmove_counter
Поддержка нестандартной платы
Хм, с более чем 2 ладьями, 1 королем, я вижу потребность в более чем 2 рокирующих флагах.