Someone turned that chessboard sideways!

Representations of Chess: FEN, PGN, and Bitboards

the_real_greco

Updated: Jun 6, 2019, 3:51 PM | 7

How can a computer understand a chess position? It isn't looking a physical board; even if it could, an image of a board would be basically useless for computation. If you want to write a chess engine, that is the first problem you need to solve: how to represent chess positions in a format your program can understand. This might seem trivial, but these representations need to be quickly generated and manipulated if you want to be looking at millions of positions per second.

In this post I'll look at two machine-readable formats you might be familiar with- PGN and FEN. Then I'll describe how modern engines handle positions using bitboards.

Forsyth-Edwards Notation (FEN), as you might guess from its name, is the work of two people. David Forsyth invented it in 1883; much later, Steven Edwards standardized it for computation. FEN is used to describe exactly one static position on the chessboard. Even if you don't know its name, you've likely seen something that looks something like this:

r3k2r/pp1n2pp/2p2q2/b2p1n2/BP1Pp3/P1N2P2/2PB2PP/R2Q1RK1 w kq b3 0 13

Valid FEN strings have strict formatting requirements so that they can be easily parsed by a program. They always have six fields, separated by spaces. The first field contains the positions of the pieces on the board. Reading the board top to bottom left to right, we use lowercase for black's pieces, uppercase for white's pieces, numbers for consecutive empty squares, and "/" when we hit the edge of a rank. Look at the board, and try to make sense of this string:

r3k2r/pp1n2pp/2p2q2/b2p1n2/BP1Pp3/P1N2P2/2PB2PP/R2Q1RK1

After describing the pieces' locations, you add whose turn it is (Lowercase, b or w)

r3k2r/pp1n2pp/2p2q2/b2p1n2/BP1Pp3/P1N2P2/2PB2PP/R2Q1RK1 w

Next you add which castling is still active. (Uppercase K and/or Q for white; Losercase k and/or q for black; - if none is active)

r3k2r/pp1n2pp/2p2q2/b2p1n2/BP1Pp3/P1N2P2/2PB2PP/R2Q1RK1 w kq

Fourth, the en passant square. (Algebraic notation, or - if there is no en passant square).

r3k2r/pp1n2pp/2p2q2/b2p1n2/BP1Pp3/P1N2P2/2PB2PP/R2Q1RK1 w kq b3

Next is the 50-move rule counter, incremented at every ply since an irreversible move was played. Ranges 0-99.

r3k2r/pp1n2pp/2p2q2/b2p1n2/BP1Pp3/P1N2P2/2PB2PP/R2Q1RK1 w kq b3 0

The last field is the fullmove counter, which is just the number of full moves that have been played. This is useful in combining FEN and PGN.

r3k2r/pp1n2pp/2p2q2/b2p1n2/BP1Pp3/P1N2P2/2PB2PP/R2Q1RK1 w kq b3 0 13

FEN is nice if you want to save a position from a physical board- you don't need to know the entire game but can write it down very quickly. Any chess reader can also accept and generate FEN. A small weakness of FEN is that it doesn't contain information about 3-fold repetitions, but that would greatly increase the necessary length of the string. The larger drawback is that they are extremely abstracted from the game- which is easier, playing a game using FEN or with the diagram above? Even figuring out the legal moves from FEN is difficult, let alone deciding which one to play.

What if you want to describe an entire game, rather than just a position? That's what Portable Game Notation (PGN) is for. PGN is a fairly recent invention- 1993, by the same Steven Edwards- but is based on algebraic game notation and is intuitively the most simple. There is a listing of game information in brackets, each piece separated by a line break:

[Event "Moscow"]
[Site "Moscow URS"]
[Date "1935.02.15"]
[Round "1"]
[White "Mikhail Botvinnik"]
[Black "Rudolf Spielmann"]
[Result "1-0"] 
[ECO "B13"]
[PlyCount "23"]

1.c4 c6 2.e4 d5 3.exd5 cxd5 4.d4 Nf6 5.Nc3 Nc6 6.Bg5 Qb6
7.cxd5 Qxb2 8.Rc1 Nb4 9.Na4 Qxa2 10.Bc4 Bg4 11.Nf3 Bxf3
12.gxf3 1-0

The first seven fields- Event through Result- are required to be included, even if they are unknown (in which case a "?" is used). A large number of extra tags can be optionally added- "Annotator", "Mode", etc.. Everything about a chess game can be stored in PGN. (Even if your opponent cheats; just use the tag [Termination "Rules Infraction"].) You can even start a game from a custom position by adding a [FEN] tag!

If you want to share complete games that can be opened on the computer, you should use PGN. But this obviously doesn't work for the internal calculation of chess engines. For one thing, PGN contains unnecessary information- you don't need to know who's playing to make optimal moves. Second, while you can generate a position from a PGN, it takes (relatively speaking) a lot of computation to do so. While it's not a trouble to load a game by PGN once, you don't want to be doing it millions of times.

Bitboards are how engines internally represent positions, and are likely to be much less familiar than FEN and PGN.

There are twelve different chess pieces: P, N, B, R, K, Q, p, n, b, r, k, q. The uppercase are white pieces; the lowercase are black pieces. So we make twelve different chessboard-sized bitboards, each containing just one type of piece. Locations marked with '1' contain that piece; locations marked with '0' do not contain that piece. This is the 'P' bitboard in a French-advance:

Having all 12 bitboards lets you know the location of every piece on the board (a "plane" among engine-folk). You might hear these 12 bitboards described as being stacked on top of one another, as this is a handy way to visualize their relationship. Extra information, such as castling rights, needs to be stored elsewhere.

One reason bitboards are useful is that they can be used with bitwise logical operators. These are functions like AND, OR, NOT, etc., which are all extremely fast to execute on a CPU- significantly faster than simple addition. Furthermore, 64-bit processors (the 'x64' you might have seen before) can complete 64-bit logical operations in one CPU cycle. This has obvious advantages for a 64-square chessboard, for which each bitboard is exactly 64-bits long. The "P" bitboard above would be stored in memory as:

0000000000000000000000000000100000010000000000001110011100000000

(Cool, right? Obviously these strings make much more sense when graphed onto an 8x8 grid.)

Let's say you're writing an engine's evaluation function, and you want to have a simple "it's good to have the king in the center" heuristic active during the endgame. Once you reach the endgame, you can just use one bitwise operation for the white king and another bitwise operation for the black king, comparing each to a center-of-the-board bitboard:

(K)

(k)

There is exactly one square that contains a '1' in both the K bitboard and the center-of-the-board bitboard. That square is labelled '1' in the product bitboard, and every other square is labelled '0'. (That the K bitboard is identical to the output is just a coincidence). Since the output is not zero everywhere, this position will receive a small evaluation bonus for having a centralized white king.

There are no squares that contain a '1' in both the k bitboard and the center-of-the-board bitboard. Therefore, every square in the output bitboard is labelled '0'. Since the output is zero everywhere, black's position will not receive an evaluation bonus for having a centralized king.

There's a lot more to be said on this topic, especially with bitboards. But hopefully this gives you a taste of how computers deal with positions. If you want to know more, let me know in the comments!

Thanks for reading!

Representations of Chess: FEN, PGN, and Bitboards

the_real_greco’s Blog