Parsing a Chess FEN

Question

What is an FEN?

Link to the Wikipedia page: Forsyth–Edwards Notation

An FEN is a very simple way of representing a chess position in a single line string. It contains the following data

• Which piece is placed where, and which squares remain empty
• Who is going to play the next move, white or black
• Castling rights
• en-passant
• Halfmove clock ( not required )
• Fullmove number ( not required )

^{Anyone unfamiliar with these terms, you won't need to know what they are}

At the current stage, I don't need to worry about the last two points.

This is what the fen looks like at the very starting position of the chess game

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

Captial letters are white pieces, lowercase letters are black.

How to parse it

Apologies for the lenghty question, but it will be very helpful to the reviewer if he/she understands the FEN completely

The main goal here is to decode this into a character array. The size will be equal to the number of square in a chess board(64).

Assume we are parsing to this array

char board[64];

We can assume this board to be The numbers on the squares are just the indexes. A chess FEN starts the square A8 and ends in the square H8, this is perfect because those are the start and end indexes of our array

So if this is the FEN

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

the first few letters go rnbq.../. So the parsing should go as follows

A / indicates going to the next row. Each time you see a numeric value, for example 8 here.
You skip those number of squares ( which means you leave those squares as empty )So if you see a 5 at index 20. Then 20, 21, 22, 23, 24 are left as empty squares and now we're at the 25th square.

Special attributes

After the parsing of the board is over, the fen has a ' ' or an empty space indicating we're moving to the next attribute

So in our case

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
                                           ^
                                           Here is our first space 
Leaves us with
 w KQkq - 0 1

Each space says that now the fen will describe something else, the rest are split as follows
last two numeric values are not required as mentioned earlier

turn

It will either be w or b,

• w - White will play next
• b - Black will play next

castling

Each color has two types of castling rights, king and queen castle

• k Black's king side castle is possible
• q Black's queen side castle is possible
• K White's king side castle is possible
• Q White's queen side castle is possible

If any type of castle is not possible, then that letter will not be present here

en-passant

• - means no en-passant in this position
• anything other than - will be the en-passant square

examples

 b kK - 

• Black to play
• only king side castles are possible for both colors
• no en-passant

 w KQq e4

• White to play
• White can castle king and queen side, black can castle only queen side
• en-passant is possible on square e4

I hope this explanation helps

My implementation

I'll parse the fen into this class

#include <string>
#include <cctype> 

#define NB_SQ 64     // number of squares
#define NB_CASTLE 2  // number of castle types
#define NB_COLOR 2   // number of colors


enum Castle
{  king_side, queen_side };

enum Color
{ white, black };

class Chess
{
    private:
        Color turn; 
        std::string en_passant;
        char board[NB_SQ];
        bool castle_rights[NB_COLOR][NB_CASTLE];

    public:
        Chess();
        void parse_fen(const std::string&);
};

Chess::Chess()
{
    for (int i = 0; i < NB_SQ; i++) board[i] = '.'; // set all squares to be empty '.'

    for (int i = 0; i < NB_COLOR; i++)
        for (int j = 0; j < NB_CASTLE; j++)
            castle_rights[i][j] = false; // all castle_rights are false by default
}

void Chess::parse_fen (const std::string& fen)
{
    const size_t size = fen.size();
    size_t iter = 0;
    int index = 0;

    // parse the board first
    for (; (iter < size) and (fen[iter] != ' '); iter++)
    {
        if (fen[iter] == '/')
            continue;


        if (isdigit(fen[iter]))
            index += (fen[iter] - '0'); // converts char digit to int. `5` to 5

        else
        {
            board[index] = fen[iter];
            ++index;
        }
    }

    turn = fen[iter + 1] == 'w' ? Color::white : Color::black;


    for (iter += 3; (iter < size )and (fen[iter] != ' '); iter++)
    {

        if (fen[iter] == 'k')
            castle_rights[Color::black][Castle::king_side] = true;

        else if (fen[iter] == 'K')
            castle_rights[Color::white][Castle::king_side] = true;

        else if (fen[iter] == 'q')
            castle_rights[Color::black][Castle::queen_side] = true;

        else if (fen[iter] == 'Q')
            castle_rights[Color::white][Castle::queen_side] = true;
    }


    en_passant = fen.substr(iter + 1, 3);

}

• Speed isn't a concern at all here. Anything that is slower, but better structured and more compact is definitely better since this function is performed at most 2-3 times and takes a few milliseconds anyway.

• Looking to avoid the extra noise in the function.

test

Can test whether this works by printing out the board array

void print_board()
{
    for (int i = 0; i < NB_SQ; i++)
    {
        if (i % 8 == 0) std::cout << '\n';
        std::cout << board[i] << ' ';
    }
}

Output after parsing the default fen

a.parse_fen("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1");

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

Answer 1

• Handle malformed FEN

  The code happily accepts /9/. It doesn't check that the rank spells out exactly 8 files. It doesn't check that the input spells out exactly 8 ranks. In both cases, hello buffer overflow.

  It also doesn't check that the piece letter makes sense (may be good for the fairy chess. but still ...).

• fen.substr(iter + 1, 3); looks strange, as it has no effect. Along the same line, I don't see en passant handling.

• The code assumes that there is exacly one space between board and turn, and between turn and castling rights. I am not sure that FEN standard mandates it. If it does not, allow multiple spaces; if it does, prepare to handle a malformed one.

• More functions please, aka no naked loops

  Every time you feel compelled to annotate a loop with a comment like

    // parse the board first
  

  consider to factor the loop out into a function with the proper name. Something along the lines of

    void Chess::parse_fen (const std::string& fen)
    {
        std::string::iterator it = fen.begin();
        it = parse_board(it);
        it = parse_turn(it);
        it = parse_castle_rights(it);
        ....
    }
  

Answer 2

• Use constant variables, not macros. (Perhaps NB_COLOR and NB_CASTLE could be added to the enums).

• Use enum class instead of a plain enum.

• en_passant could be translated to the relevant index in the board. Perhaps use std::optional, or a named constant (e.g. -1) for the "no en-passant available" case.

• Use std::array instead of a plain array for utility reasons. e.g. in the constructor we could do board.fill('.'). It also makes copying much easier.

• Don't forget to initialize turn in the constructor.

• In addition to vnp's comments about parsing:

  Currently the parser skips over indices in the board (e.g. with /8/). If the board wasn't previously empty, these squares will still contain the pieces from before!! We must explicitly set these squares to be empty.

  It might be better to make parse_fen an alternate form of constructor instead.