Chess Programming Tutorial...[]

Part 4: Chess Board Implementation : A FEN parser

Now it's time to get some code into our still empty board class.

The chess board is a very complex and powerful class. In my implementation it consists in total of several 1000 lines of code. I will not just paste them here as it's no fun to copy code. It's much more fun to figure things out yourself.

But I will try to get you started. So I will show how the implementation of a FEN parser could look like. This is a very essential piece of functionality that every engine requires. It will also demonstrate the use of the data types and structures we defined in the previous part.

FEN - Forsyth-Edwards Notation

Forsyth–Edwards Notation (FEN) is a standard notation for describing a particular board position of a chess game. The purpose of FEN is to provide all the necessary information to restart a game from a particular position. A FEN record contains six fields. The separator between fields is a space.

The fields are:

1. Piece placement on squares (A8 B8 .. G1 H1) Each piece is identified by a letter taken from the standard English names (white upper-case, black lower-case). Blank squares are noted using digits 1 through 8 (the number of blank squares), and "/" separate ranks.

2. Active color. "w" means white moves next, "b" means black.

3. Castling availability. Either - if no side can castle or a letter (K,Q,k,q) for each side and castle possibility.

4. En passant target square in algebraic notation or "-".

5. Halfmove clock: This is the number of halfmoves since the last pawn advance or capture.

6. Fullmove number: The number of the current full move.

The FEN parser

We implement a public method in our board class called setFEN(string aFEN).

For the moment we assume that this method only gets valid FEN input. You might want to include FEN syntax checking later.

The function first splits the FEN string into its substrings. We use a handy split method for that we programmed in our tools collection. Next it loops through the squares of the board and fill the squares datastructure with the content of the string.

/******************************************************************************** reset the board and set its position to the one specified by FEN ********************************************************************************/ int TBoard::setFEN(string aFEN) { unsigned int i,j,state; ESquare sq; char letter; int aRank,aFile; vector strList; split( strList , aFEN, " " ); // Empty the board quares for (sq=A1;sq<=H8;sq++) bb.squares[sq] = EMPTY; // read the board - translate each loop idx into a square j = 1; i = 0; while ((j<=64) && (i<=strList[0].length())) { letter = strList[0].at(i); i++; aFile = 1+((j-1) % 8); aRank = 8-((j-1) / 8); sq = (ESquare) (((aRank-1)*8) + (aFile - 1)); switch (letter) { case 'p' : bb.squares[sq] = B_PAWN; break; case 'r' : bb.squares[sq] = B_ROOK; break; case 'n' : bb.squares[sq] = B_KNIGHT; break; case 'b' : bb.squares[sq] = B_BISHOP; break; case 'q' : bb.squares[sq] = B_QUEEN; break; case 'k' : bb.squares[sq] = B_KING; break; case 'P' : bb.squares[sq] = W_PAWN; break; case 'R' : bb.squares[sq] = W_ROOK; break; case 'N' : bb.squares[sq] = W_KNIGHT; break; case 'B' : bb.squares[sq] = W_BISHOP; break; case 'Q' : bb.squares[sq] = W_QUEEN; break; case 'K' : bb.squares[sq] = W_KING; break; case '/' : j--; break; case '1' : break; case '2' : j++; break; case '3' : j+=2; break; case '4' : j+=3; break; case '5' : j+=4; break; case '6' : j+=5; break; case '7' : j+=6; break; case '8' : j+=7; break; default: return -1; } j++; }

So here the variable i marks the current position in the FEN string. The variable j walks through the board in the direction the FEN squares occur (A8 .. H1). Next we set the turn which is stored in the 2nd substring

// set the turn; default = White sideToMove = WHITE; if (strList.size()>=2) { if (strList[1] == "w") sideToMove = WHITE; else if (strList[1] == "b") sideToMove = BLACK; else return -1; }

Next the casteling rights. For efficience we store all casteling rights into a single integer where different bits indicate a certain right is there (bit is 1) or right is missing (bit is 0). For bit manipulating we rely on small inline functions that do just set the correct bit to 1.

// set boardstate to initial 0 state = 0; // Initialize all castle possibilities if (strList.size()>=3) { if (strList[2].find('K') != string::npos) state = TBoardState_SET_CASTLE_WHITE_KS(state,WHITE_CASTLE_KINGSIDE); if (strList[2].find('Q') != string::npos) state = TBoardState_SET_CASTLE_WHITE_QS(state,WHITE_CASTLE_QUEENSIDE); if (strList[2].find('k') != string::npos) state = TBoardState_SET_CASTLE_BLACK_KS(state,BLACK_CASTLE_KINGSIDE); if (strList[2].find('q') != string::npos) state = TBoardState_SET_CASTLE_BLACK_QS(state,BLACK_CASTLE_QUEENSIDE); }

The next sub string stands for a possible en passent square. The square is initialized to the square "ER", which just means no valid square (we could initialize also to square 0, which is A1. Because A1 is also not a valid en passent square it is possible to recognize this situation as "No en passent" possibility but keep your code clean and readable. And it is advisable to call an invalid square "Invalid square" and not use a valid square for that, which is just invalid in this situation.

// read en passent and save it into "sq" Default := None (ER) sq = ER; if ((strList.size()>=4) && (strList[3].length()>=2)) { if ((strList[3].at(0)>='a') && (strList[3].at(0)<='h') && ((strList[3].at(1)=='3') || (strList[3].at(1)=='6'))) { aFile = strList[3].at(0) - 96; // ASCII 'a' = 97 aRank = strList[3].at(1) - 48; // ASCII '1' = 49 sq = (ESquare)((aRank-1)*8 + aFile-1); } else return -1; }

Finally we retrieve the turn number

// we start at turn 1 per default currentPly = 1; if (strList.size()>=6) { currentPly = 2 * (StrToInt(strList[5])-1) +1; if (currentPly<0) currentPly = 0; // avoid possible underflow if (sideToMove==BLACK) currentPly++; }

We now create our initial board state record with the en passent square we read and the castle rights we initialized

// initialize the board state history stack boardHistory->initialize(state,sq); // setup the piece related bit boards with this board content initializeBitBoards(); return 0; }

Please notice the final call to initializeBitBoards(). This call synchronizes the piece BitBoards with the contents of "squares" that we just set. It is very importatnt that the square centric representation and the BitBoard representation is always in sync.

/************************************************* initialize the bitboards with the contents of bb.squares **************************************************/ void TBoard::initializeBitBoards() { ESquare sq; memset(&bb.pcs,0,sizeof(bb.pcs)); // initialize the piece bit boards for (sq=A1;sq<=H8;sq++) bb.pcs[bb.squares[sq]] |= BB_SQUARES[sq]; // calculate the utility bitboards bb.pcsOfColor[WHITE] = bb.pcs[W_PAWN] | bb.pcs[W_KNIGHT] | bb.pcs[W_BISHOP] | bb.pcs[W_ROOK] | bb.pcs[W_QUEEN] | bb.pcs[W_KING]; bb.pcsOfColor[BLACK] = bb.pcs[B_PAWN] | bb.pcs[B_KNIGHT] | bb.pcs[B_BISHOP] | bb.pcs[B_ROOK] | bb.pcs[B_QUEEN] | bb.pcs[B_KING]; bb.occupiedSquares = bb.pcsOfColor[WHITE] | bb.pcsOfColor[BLACK]; bb.emptySquares = ~bb.occupiedSquares; }

Great! The parser is done. It is now possible to include a call to setFEN() into the constructor of the board class with the FEN of the initial start position of chess. This will initialize the Board object to the well known initial position.

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