A Computer Chess Analysis Interchange Format

File formats are like watching paint dry…

Source: Chess-programming wiki on Edwards’s “Spector” program.

Steven Edwards is an American computer scientist and chess programmer. Two decades ago he spearheaded the development and adoption of three standards for communicating chess games and their moves.

Today Ken wishes to present a proposed new format for representing computer analysis of chess games and positions.

This will extend Edwards’s work into the 21st century, since it will leverage the rise of computers as the best players in the world. A new standard for chess: sounds about as exciting as watching paint dry—from Dick—with all apologies to Ken.

But it is really important, it raises a number of interesting issues that concern theorists and computer scientists in general. It is a fundamental process like paint drying: if paint stayed wet where would we be?

File formats are everywhere—see this for a list of a countless number of them. Well a lot of them. At least their environment of information structures and operations is less arcane:

I, Dick, believe that one of the least understood and yet most important endeavors we do in computer science is design good file formats. What makes a good one is clearly a question that requires some deep thought. Ken and I agree that designing them is an art: we can tell when a format is good and often when it is bad. But we what makes a format successful is still, after decades having computer scientists create them, an open problem.

In order to make some progress on thinking about this issue, Ken will now explain the previous chess file formats and also his new one. I think looking at a specific one, as it is being designed, may shed some light on what makes a good one.

So let’s let Ken take over and explain his new chess file format.

Chess Formats

Edwards authored the specification of the Portable Game Notation (PGN) standard for games. He augmented the 19th-century system of David Forsyth for describing positions in postal chess into what is now called Forsyth-Edwards Notation (FEN). Working with John Stanback, he specified Extended Position Description (EPD) files, each of whose lines holds the FEN code of a position and “opcode tags” giving terse information about test moves to find or trap moves to avoid or events when computers play or analyze in that position.

Chess historian and blogger Mark Weeks includes PGN in his post on “The Rise of Internet Chess,” writing:

Before PGN, every chess software vendor had a different way of encoding chess data. PGN … became an immediate success because, as a readable text format, it satisfied the needs of people as well as of computers.

The ChessBase company developed their pathbreaking game-database product in the mid-1980s around a binary code that I already felt to give wondrous compression and performance when I started using it in 1988. The latest 2015 edition of their Big Database has 6,161,343 games, and I can search all of them in half a minute on my old Windows XP box. Of course their format is neither readable nor public, while PGN still does not approach it in time or space complexity.

Edwards prefaced his PGN document with a quotation from the Tower of Babel story in the Bible. Its relevance to standard formats is clear, but did he also mean to reference the motto “We are one people” (Gens una sumus in Latin) of the World Chess Federation?

“If now, while they are one people, all speaking the same language, they have started to do this, nothing will later stop them from doing whatever they propose to do.”

The Tower was stopped before it reached into the clouds. Chess analysis, however, is reaching into the Cloud. ChessBase has again taken the lead in subscription access to computer analysis data that can be uploaded by any user with any chess program “engine.” Since computer analysis is usually—not always—far stronger and more reliable than human analysis, this access is valuable to prepare opening strategies, gain new insights into historical games and thematic positions, and compare different chess programs. My Analysis Interchange Format (AIF) aims to reprise the role of PGN, though again subject to caveats of time and space versus simplicity and readability. At least it extends and improves the ad-hoc format of my previous work. Let’s first say more about PGN.

The PGN Format

Every PGN file is a sequence of PGN games. Each game has a tag section and a moves section. For example, here is the PGN export of the earliest recorded game in Big Database 2015:

[Event "Valencia"]
[Site "Valencia"] 
[Date "1475.??.??"] 
[Round "?"] 
[White "De Castellvi, Francisco"] 
[Black "Vinoles, Narcisco"] 
[Result "1-0"] 
[ECO "B01"] 
[PlyCount "41"] 
[EventDate "1475.??.??"] 
[EventType "game"] 
[EventCountry "ESP"] 
[Source "ChessBase"] 
[SourceDate "2007.11.25"]

1. e4 d5 2. exd5 Qxd5 3. Nc3 Qd8 4. Bc4 Nf6 5. Nf3 Bg4 6. h3 Bxf3 7. Qxf3 e6 8. Qxb7 Nbd7 
9. Nb5 Rc8 10. Nxa7 Nb6 11. Nxc8 Nxc8 12. d4 Nd6 13. Bb5+ Nxb5 14. Qxb5+ Nd7 15. d5 exd5 16. 
Be3 Bd6 17. Rd1 Qf6 18. Rxd5 Qg6 19. Bf4 Bxf4 20. Qxd7+ Kf8 21. Qd8# 1-0 

The first seven tags are required in that order, even if their values are unknown and given with question marks. The value of the Result tag is a required endmarker for the whole item; it is “0-1” for a win by Black, “1/2-1/2” for a draw, and “*” when the game is not yet finished or the result unknown. PGN also requires a blank line between the tags and the moves, and before the next game item in a file. The moves conform to Standard (or “Short”) Algebraic Notation (SAN) with English piece designators including ‘N’ for knight and nothing for pawn.

All tags after the first seven are optional. Some frequently-used optional tags have recommended standard forms. The ECO tag gives the code for the opening in the Encyclopedia of Chess Openings, which did not exist in 1475. Besides EventCountry one can use tags for the 3-letter IOC country codes of the White and Black players. For games since the Elo Rating System was adopted internationally in 1971 there are tags WhiteElo and BlackElo whose value is the player’s current rating, or “-” for unrated or “?” for unknown.

Two strengths of PGN are its simplicity and flexibility. Users may create and use their own tags. Games may have variations with alternative sequences of moves enclosed in parentheses that nest, and annotations enclosed in curly braces which act as range comments at the initial lexing level and do not nest. There is also a rest-of-line comment character, ‘;’ (semicolon), which hence may not appear in real data except between braces. AIF creates a PGN-style structure for computer analysis of individual moves, sequenced within an extension of the PGN structure for games.

AIF Game Structure

An AIF file is a sequence of one or more AIF games or a sequence of AIF move blocks not encapsulated by games. An AIF game consists of a legal PGN game with extra tags followed by a sequence of AIF move blocks. Here is an example of the new game tags:

; AIF v0.5 Kenneth Regan and Tamal Biswas 
[GameID "De Castellvi;Vinoles;Valencia;Valencia ESP;1475.??.??;?;1-0"] 
[EngineID "Komodo-8-32bit"] 
[Platform "Windows XP 32-bit"] 
[Threads "1"] 
[Hash "256"] 
[MultiPV "1"] 
[DepthRange "18-18"] 
[EGT "none"] 
[Mode "forward;r;6-w"] 

The GameID is a “mangle” of the information in the first seven PGN tags plus the site country when available. It follows the common spoken order of giving the player surnames first, then the tournament, place, and year. The EngineID should be reported by the engine itself, while the GUI or script running it can report the platform. The next three tags mimic commands under the Universal Chess Interface (UCI) protocol for communicating with chess programs. Here they say to use just one core thread, a hash table of size 256 megabtyes, and the normal “Single-PV” playing mode which evaluates the optimal move and its principal variation fully. The next tags specify searching to a fixed depth of 18 plies (that is, looking 9 moves ahead for Black and 9 for White) regardless of time taken, not using endgame tables, and moving forward in the game retaining previous hash-table contents starting at White’s 6th move.

These tags are required and can come after the PGN tags, though we allow having GameID come first overall. After other optional tags come the game moves as in PGN.

AIF Move Structure

After the game header come the AIF move blocks for that game. These have their own tags. Here are the position of the game at White’s sixth turn and the AIF move header. Try choosing which move to play as White before looking at the latter.

[GID "De Castellvi;Vinoles;Valencia;Valencia ESP;1475.??.??;?;1-0"]
[EID "Komodo-8-32bit"] 
[Turn "6-w"] 
[MovePlayed "h3"] 
[EngineMove "Ne5"] 
[Eval " +132"] 
[Depth "18"] 
[NodeCount "7461878"] 
[FEN "rn1qkb1r/ppp1pppp/5n2/8/2B3b1/2N2N2/PPPP1PPP/R1BQK2R w KQkq - 6 6"] 
[RepCount "0"] 
[NumLegalMoves "36"] 
[LegalMoves "a3,b3,d3,g3,h3,a4,b4,d4,h4,Nb1,Ne2,Na4,Ne4,Nb5,Nd5,Ng1,Nd4,Nh4,
Ne5,Ng5,Bf1,Be2,Bb3,Bd3,Bb5,Bd5,Ba6,Be6,Bxf7,Rb1,Rf1,Rg1,Qe2,Kf1,Ke2,O-O"] 

The GID repeats the GameID for indexing purposes. We believe EID should repeat EngineID as a label on each move, but are fine with leaving the engine settings to the game header tags.

The game turn is White’s sixth move. De Castellvi pushed his Rook’s pawn, but the computer finds the move 6.Ne5. Although it is a shocking Queen sacrifice, the engine looking 9 moves ahead says White will be ahead 132 centipawns, colloquially more than a pawn ahead. On my old Windows XP machine it took 21 seconds to search 7,461,878 nodes, not all of them distinct positions since the search can transpose and backtrack. Optional tags for Time and NodesPerSecond could express the speed, but those can depend on vagaries of thread scheduling not just on hardware, whereas the total node count and the actual depth of search reached are invariant.

Then come the FEN code for the position and, importantly, the number of times it has occurred earlier in the game. Optionally this can be followed by tags RepLine1 and RepLine2 for one- and two-move sequences that could repeat a previously-occurring position. The rules of chess specify that the third occurrence—that is, the second repetition—of a position can cause the game to be drawn, but engines to avoid search cycling give value 0.00 on the first repetition. Often a player will harmlessly force a repetition to meet the time control before executing a winning strategy. The repeating move will look like a blunder to the engine when it is not—even some major websites showing games in progress have this issue. The problem can also arise in search lookahead when the players don’t actually repeat. Coping with this thorny issue could be a whole other post.

Move Analysis and Principal Variations

The numerical heart is the evaluation grid, which shows how valuable the engine thought certain moves to be at the progressive depth stages of its search. In Single-PV mode this reports only the moves that the engine considered to be best at some point in the search.

----------------------------------------------------------------------------------------------
       1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18
----------------------------------------------------------------------------------------------
Ne5  n.a. n.a. n.a. n.a. n.a. +142 +142 +140 +132 +147 +146 +160 +141 +155 +141 +147 +139 +132
d3   +110 NREC NREC NREC +053 +095 NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC
Bxf7 n.a. n.a. n.a. n.a. +107 +079 NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC
d4   n.a. n.a. n.a. n.a. +054 NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC
h3   +127 +105 +105 +101 +086 NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC
O-O  +103 NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC NREC
==============================================================================================

This says the engine immediately thought about castling or playing 6.d3 but settled on the move 6.h3 which De Castellvi played. At depth 5 it briefly flirts with 6.d4 as well as 6.d3, but then sees it can win a pawn by the temporary bishop sacrifice 6.Bxf7+, to be followed after 6…Kxf7 by 7.Ne5 giving check and next recapturing Black’s bishop on g4.

Well in chess there is a saying, “if you see a good move, wait—look for a better one,” and at depth 6 Komodo finds it: 6.Ne5! If Black takes White’s Queen by 6…Bxd1 there follows 7.Bxf7 checkmate. Komodo likely saw that by depth 3 but thought 6…Be6 would both save Black’s King and keep the pawns equal—I say “likely” because that part of the search was not reported at top level. On deeper thought it judged that after 7.Bxe6 fxe6 8.d4 Black’s pawns are wrecked and his other bishop buried, giving White greater advantage than the 6.Bxf7 pawn grab—and it stayed so firm that henceforth analysis of the previously-considered moves is not recorded (NREC). We use “n.a.” to distinguish absent values at depths before a move is considered.

The last part after the eval grid requires the “Principal Variation” (PV) associated with the preferred move at the highest depth, which in this case was:

18: 6.Ne5 Be6 7.Bxe6 fxe6 8.d4 g6 9.0-0 Bg7 10.Qf3 c6 11.Ne2 Na6 12.Qb3 Qc8 13.Bg5 0-0 
14.Qh3 Nd5 15.c4 Bxe5 16.dxe5 Rf5 17.cxd5 

Komodo actually extended its search for (at least) five plies beyond move 14 in this variation, likely to resolve the captures toward the end, making 23 plies total. Some engines might have reported the depth as “18/23” or more. Had I set MultiPV equal to 5 when using UCI to take the analysis, the engine would have reported full treatment to at least four more moves at each depth. The extra PVs can be listed on successive lines, along with interesting variations from earlier depths for when it “changed its mind” about other moves.

A practical reason to preserve the lower-depth numbers is that they strongly impact an opponent’s likelihood of grasping the subtleties, as demonstrated by my most recent paper with my student, Tamal Biswas. Values overall are truncated to the range [-900 .. +900], with 1,000-n reserved for mate-in-n. Other information and comments can come freely in the PVs section. Perhaps we should close it and the whole move item with an endmarker; currently the next tag beginning with ‘[‘ for the next move or game block serves, or end-of-file.

Issues and Possibilities

The main issues are space and the choice of information to include and exclude. The list of legal moves is a case in point. They could be generated from the FEN by the file reader, but doing so efficiently is a famous problem of chess programming, not nice to impose on a client. Indeed, Tamal solved a speed deficiency of a public Perl module we had been using by interfacing our Perl code with the C++ code of the open-source Stockfish engine. Why include them? They help in cross-checking the correctness of (other) game sources, and counting them is a complexity measure for the position. Engines report values outside of [-900 .. +900] when they judge one side to be ahead more than a queen ahead (colloquially speaking) but don’t see mate yet. Are those values meaningfully different from -900 or +900? Other issues are whether to record node counts and more PVs for intermediate stages in the search.

My own chess research needs fully-considered values for all or most of the legal moves, not just the ones the engine considers best. In 50-PV mode the grids alone become large. Compression may help with the non-numeric entries; besides NREC and “n.a.” there is “PRUN” for k-PV mode. It means that although a move might be among the top k, its inferiority exceeds a “multi-PV cap” value used by the engine to prune it away at lower depths regardless; this cap if used needs a tag. But the move values seem not to be easily compressible. Sophisticated frequency analysis including Benford’s Law could do it, but would impact both human and computer readability.

All this said, the AIF files are many times larger per game than PGN files. My Single-PV file of all 693 games of last November’s 154-player Qatar Masters Open takes almost 100 megabytes. The 50-PV file may be upwards of 1 gigabyte. Can this “Spruce Goose” possibly fly in the Cloud? On the other hand, taken over 6.93 million games, that would scale to only 10 TB for in-depth analysis of pretty much the entire recorded history of chess, which is a pittance in big-data terms.

Beyond this are design issues of which other features could be important to chess players and researchers. Perhaps you can suggest ways both to enhance and economize. There are also technical data-cleansing and format-design considerations. Should I have an endmarker for moves? Should AIF adopt XML markup rather than imitate PGN? Is it already hard to define unique game IDs? As shown above information from the relevant PGN fields can be missing. One could hash the moves of the game instead, but doing so would be less human-readable, would magnify the consequences of an erroneous move in the source, and would fail uniqueness when identical (short) games have been played.

Open Problems

Do you like the new standard? Comments are most welcome.

[first PGN tag was missing]