PDN standard

[Wieger Wesselink]

I'm working on an EBNF definition for draughts games in PDN notation. The goal is to standardize the usage of PDN. There are many conflicts in the way programs deal with PDN, and such an EBNF might help to clarify what is valid PDN and what not. To give a small example: is it allowed to have spaces in a move like '1 - 7'? Some programs accept this, others don't.

I'd like to get feedback from other draughts programmers, so that we can come to one unified definition. I'm particularly interested to hear if you agree with the given definition, and if you are willing to use it in your own software.

The most sensible definition for PDN that I have found on the web is a draft standard for PDN 2.0 from Murray Cash: http://www.nemesis.info/pdn2.txt. I found one major problem with this definition. This problem is inherited from PDN 1.0. The game terminator is equal to the game result and must be one of the strings "1-0", "0-1", "1/2-1/2" or "*". Not only is it redundant to repeat the result at the end of a game, it also introduces conflicts. For example a straightforward way to parse moves is using the pattern

NUMBER (DELIMITER NUMBER)+

meaning a number followed by one or more times a delimiter followed by a number. This covers normal moves (32-28) and captures (25x14x3). Unfortunately, the terminator strings 1-0 and 0-1 are also accepted by this pattern. Note that in chess this is not a problem, since they use a different move notation. Another problem is that the '*' terminator conflicts with the strength field. This means that the string '32-28* 19-23' can be interpreted as one game of two moves (with * indicating a forced move) or two games of one move (with * indicating a game terminator). To get rid of this problem I see no other option than to entirely remove the game terminator. Instead I added the restriction that the header must contain at least one tag. This is enough to serve as a separator between games.

My first attempt at making an EBNF definition for PDN is the following one:

Code: Select all

separator space:  '\s+'     
token delimiter   '[:x-]'   
token strength    '[*?!]'   
token number:     '\d+'       
token identifier: '[a-zA-Z]\w*'
token comment:    '{\w*}'     

PDNFile          -> (Game)*
Game             -> GameHeader GameBody
GameHeader       -> (Tag)+
Tag              -> '\[' identifier '"' identifier '"' '\]'
GameBody         -> (AnnotatedMove)*
AnnotatedMove    -> (MoveNumber)? Move (strength)? (Annotation)?
MoveNumber       -> number '\.'
Variation        -> '\(' GameBody '\)'
Annotation       -> VariationComment | CommentVariation
VariationComment -> Variation (comment)?
CommentVariation -> comment (Variation)?
Move             -> number (delimiter number)+                                                                                                                                     

There is no checking included for correctness of the tags, the moves and move numbers etc. I think it does not belong to this EBNF definition. For those who are interested I can supply a small python script to parse games according to this EBNF, using the Toy Parser Generator. Just send me a PM for that.

Something that also needs to be discussed is extensions to this standard. How should clock times be added to a game? This is useful for games played on an electronic board and for games between computers. How should time controls and times used by the players be recorded? Finally it would be nice to have a possibility to do a setup of a new position at arbitrary points. This helps to store analyses of games, and it also makes it possible to store games with illegal moves.

[Wieger Wesselink]

Feike Boomstra wondered if this definition allows for doing a "FEN-only" setup. It does, a single [FEN "..."] tag is allowed. But multiple FEN tags will belong to the same game. If this is undesirable, a game separator should be introduced, but different from the current values. Since FEN-setup is quite unreadable, I'd vote for supporting a Setup tag like this as well:

Code: Select all

[Setup "
        x   x   x   x   x  
      .   x   x   x   x  
        x   x   x   x   x  
      x   x   .   x   x  
        .   .   x   .   .  
      x   o   o   .   .  
        .   o   o   o   o  
      o   o   o   o   o  
        o   o   o   o   o  
      o   o   o   o   .  
 W
"]

Spaces in the quoted string should be ignored. The only thing missing in this encoding is the number of rows and columns, but that could easily be encoded somewhere else, such as the GameType tag.

[Ed Gilbert]

Hi Wieger,

I'd like to get feedback from other draughts programmers, so that we can come to one unified definition. I'm particularly interested to hear if you agree with the given definition, and if you are willing to use it in your own software.

I am glad to see some one take an interest in cleaning up the pdn standard. I gave some inputs to Murray when he was drafting his document, but he seems to have stopped working on checkers programming.

I agree with most of your changes or clarifications to what is existing:
- result codes at the end of the moves list are redundant and should be eliminated.
- a valid game should not require any particular header tags, and a header tag after a list of moves serves as a terminator for the previous game.

To give a small example: is it allowed to have spaces in a move like '1 - 7'? Some programs accept this, others don't.

On this point I prefer the syntax shown in your grammar (no spaces allowed). I have never seen a colon used as a move separator though.

To get rid of this problem I see no other option than to entirely remove the game terminator. Instead I added the restriction that the header must contain at least one tag.

I think the standard should allow a degenerate case of a single game without any header tags, as long as it has at least one move. This is the most common use case for my parser -- copying some list of moves from an email or web page and pasting into a draughts program.

Because there is so much existing pdn that does not obey all the new rules, a practical parser will have to accept some of the constructs that are not allowed. Result codes like 1-0 at the end of the moves can be treated like comments. Actually a forgiving parser can treat almost anything that is not recognized as one of the elements of pdn as a comment.

How should clock times be added to a game? This is useful for games played on an electronic board and for games between computers. How should time controls and times used by the players be recorded?

I think that these will be tags in the header, and as you said, specifying particular tag names is outside the scope of the standard. Maybe the standard can 'recommend' a few tag names in the interest of promoting uniformity.

Since FEN-setup is quite unreadable, I'd vote for supporting a Setup tag like this as well:

Code: Select all

[Setup " 
        x   x   x   x   x  
      .   x   x   x   x  
        x   x   x   x   x  
      x   x   .   x   x  
        .   .   x   .   .  
      x   o   o   .   .  
        .   o   o   o   o  
      o   o   o   o   o  
        o   o   o   o   o  
      o   o   o   o   .  
W 
"] 

This I personally do not care for. I like the existing fen string notation. It does not give a pictoral representation like above, but it is compact, unambiguous, and is already widely used. The standard should probably spell out the correct syntax for a valid fen string.

-- Ed

[Rein Halbersma]

I like the existing fen string notation. It does not give a pictoral representation like above, but it is compact, unambiguous, and is already widely used. The standard should probably spell out the correct syntax for a valid fen string.

-- Ed

One extension for the FEN notation that I would like very much is the possibility to let consecutive squares to be joined in a list with a seperator such as the character '-'. E.g. the initial position could be written as "W:W31-50:B1-20", the Woldouby position as ""W:W25,27,28,30,32-35,37,38:B12-14,16,18,19,21,23,24,26"

A second thing: does the currect PDN standard allow for the short notation (used by problem composers) that leaves out redundant information from moves. E.g. 32-28 becomes 328, 35-30 becomes 35 etc. It would be handy to incorporate this as well. Chess PGN does allow for it.

[FeikeBoomstra]

I guess I still know how to edit with emacs, but today I prefer a WYSIWYG editor. The same for PDN, you could create the pdn with a simple text editor, but today the very most pdn's are created with a program.

So who bothers how many characters you have to type for a FEN tag?

[ildjarn]

I guess I still know how to edit with emacs, but today I prefer a WYSIWYG editor. The same for PDN, you could create the pdn with a simple text editor, but today the very most pdn's are created with a program.

So who bothers how many characters you have to type for a FEN tag?

Isn't the inverse also true? Almost all PDN is read by computers, so who cares that the FEN string is hard to read for humans?

[Ed Gilbert]

A complete standard should probably distinguish between what a compliant parser will accept for reading and what it will write. A draughts program with a pdn parser should read forgivingly and write exactly, and a description of pdn should reflect that. For example, during reading I think the parser should accept any text for header tag names, but when writing perhaps it should write some minimum set of standard tags, even if the values are null, e.g.:

[Event ""]
[Date "2009.5.10"]
[White ""]
[Black ""]
[Result "*"]
1. 34-29 17-21 2. 32-28

Other examples:
- When reading pdn the parser should perhaps accept moves with or without move counters, and with or without space separators between move counters and moves, so

1.34-29 17-21 2.32-28
34-29 17-21 32-28

should both be accepted on input, but on output it should be written one way consistently, e.g.:

1. 34-29 17-21 2. 32-28

or whatever the consensus is for what the writing format should look like.

- Capture notation: a parser should accept a non-ambiguous capture move as either e.g. 28x26 or 28x17x26 or even 28-26, but on output it should be written IMO 28x26 unless that does not uniquely describe the move.

- Case sensitivity: should a parser accept [Event "foo"], [EVENT "foo"], and [event "foo"] as the Event tag on reading, and then on writing output it as [Event "foo"]?

Regarding extensions like accepting 349 for 34-29: I don't think most existing parsers accept that. What has been proposed so far does not break any programs that I am familiar with. Most programs already consider the results codes following the list of moves as optional, and consider the header tags of the following game as a terminator for the previous game. So what has been proposed only confirms that as an accepted practice and would tell new programs to not write those result codes. But if you extend the standard in ways that break existing programs then I think there has to be a good reason for it. In the spirit of writing exactly, I don't think the standard should say that 34-29 should be written as 349, so we're only talking about accepting that during reading. But if we add that to the new pdn standard and then you create a pdn file with the move written as 349, that file can only be read by parsers that have been updated to conform to the new standard, and it will not be read correctly by any legacy draughts programs. There will always be some legacy programs that never update to a new standard, and new programs will never write moves in that format, so I think in the spirit of not gatuitously breaking legacy programs we should not include that kind of extension to the standard.

-- Ed

[Ed Gilbert]

Isn't the inverse also true? Almost all PDN is read by computers, so who cares that the FEN string is hard to read for humans?

I think a goal should be to make pdn readable by both humans and computers. At least I find myself reading pdn at times.

-- Ed

[FeikeBoomstra]

I agree, but you don't have to optimize for minimal typing for humans.

[Piet Bouma]

Another problem is that the '*' terminator conflicts with the strength field. This means that the string '32-28* 19-23' can be interpreted as one game of two moves (with * indicating a forced move) or two games of one move (with * indicating a game terminator). To get rid of this problem I see no other option than to entirely remove the game terminator. Instead I added the restriction that the header must contain at least one tag. This is enough to serve as a separator between games.

Finally it would be nice to have a possibility to do a setup of a new position at arbitrary points. This helps to store analyses of games, and it also makes it possible to store games with illegal moves.

Wieger,

I think you will have a conflict if you get rid of the * as seprator and only have the restriction that the header must contain at least one tag.
When you accept a FEN-tag in the PDN, this could be also considered as start of a new game.
I suggest that a new game must always start with the EVENT tag.
That can be the seperator between games.

[Wieger Wesselink]

Based on the comments so far I have made an improved version of a PDN grammar. The most important changes are:

* Spaces in moves are no longer allowed. In the previous version the fields and separators were different tokens, which creates the possibility of spaces between them. Now a move is a single token, so it cannot contain any spaces.

* There can no longer be spaces between a move and a 'strength' annotation (either *, ! or ?).

* Based on feedback from Klaas Bor comments and variations are accepted much more liberally.

* Moves can now have a 'Nag' annotation. This is adopted from PGN. It is an annotation like $1, $2, ... I don't know exactly what the purpose of it is, but in TurboDambase they are actually used.

* A game is no longer required to have any tags. But it must have either a tag or a move.

* A game separator has been reintroduced. If a game is not required to have any tags, then there must be some kind of separator. Otherwise it is not possible to store two sequences of moves without tags between them. Now that the tokens are more strict, it seems possible to use the old game separators 1-0, 0-1, 1/2-1/2 and *. The TPG parser that I use for testing still doesn't like 1-0 and 0-1, but I suspect this is a bug.

Code: Select all

separator space: '\s+' ;

token GameSeparator: '1-0|0-1|1/2-1/2|\*'
token Move:          '\d+([-x]\d+)+[*?!]?'
token Identifier:    '[a-zA-Z]\w*'        
token String:        '"[^"]*"'            
token Comment:       '{[^}]*}'            
token MoveNumber:    '\d+\.(\.\.)?'       
token Nag:           '\$\d+'              

PDNFile    -> Game (GameSeparator Game)*
Game       -> (GameHeader GameBody?) | GameBody
GameHeader -> (Tag)+
Tag        -> '\[' Identifier String '\]'
GameMove   -> MoveNumber? Move Nag?
GameBody   -> Annotation? (GameMove Annotation?)+
Variation  -> '\(' GameBody '\)'
Annotation -> (Variation | Comment)+

[Rein Halbersma]

I agree, but you don't have to optimize for minimal typing for humans.

There are online newspaper archives with diagrams written in FEN notation with seperators such as "t/m" or "-". E.g. the columns by Harm Wiersma have such descriptions of positions. I would like the standard to reflect this and let a PDN compliant program read such a text.

But also for writing I think the amount of space is relevant: one motivation for chess programmers to design the FEN in the first place was to have a description that fitted on a single screen line (less than 80 characters).

[Wieger Wesselink]

Hi Ed, thanks for your comments!

I am glad to see some one take an interest in cleaning up the pdn standard. I gave some inputs to Murray when he was drafting his document, but he seems to have stopped working on checkers programming.

I believe this is true. Even the email account of Nemesis doesn't seem to exist anymore.

I have never seen a colon used as a move separator though.

That's what I have seen Russian players do. But it can be easily removed from the standard.

I think the standard should allow a degenerate case of a single game without any header tags, as long as it has at least one move. This is the most common use case for my parser -- copying some list of moves from an email or web page and pasting into a draughts program.

I hadn't thought about that use case, but it is a good argument to allow games without headers. However, if a game doesn't need to have a header, game separators are needed.

Because there is so much existing pdn that does not obey all the new rules, a practical parser will have to accept some of the constructs that are not allowed. Result codes like 1-0 at the end of the moves can be treated like comments. Actually a forgiving parser can treat almost anything that is not recognized as one of the elements of pdn as a comment.

It is less difficult than I thought to support the existing habit of using the game result as a game terminator. After reorganizing the token definitions and disallowing spaces the grammar seems to work with a very simple parser. I suggest to drop the convention that the result of the game is used as a game terminator. Instead, one can use the * character to separate games. In this way there is still some kind of backwards compatibility.

[Wieger Wesselink]

I like the existing fen string notation. It does not give a pictoral representation like above, but it is compact, unambiguous, and is already widely used. The standard should probably spell out the correct syntax for a valid fen string.

-- Ed

One extension for the FEN notation that I would like very much is the possibility to let consecutive squares to be joined in a list with a seperator such as the character '-'. E.g. the initial position could be written as "W:W31-50:B1-20", the Woldouby position as ""W:W25,27,28,30,32-35,37,38:B12-14,16,18,19,21,23,24,26"

A second thing: does the currect PDN standard allow for the short notation (used by problem composers) that leaves out redundant information from moves. E.g. 32-28 becomes 328, 35-30 becomes 35 etc. It would be handy to incorporate this as well. Chess PGN does allow for it.

Does anyone have a formal definition of FEN for draughts? I only have seen examples of it. Personally I am not really pleased with the FEN notation, both for reasons of readability and of compactness. But it seems that the general opinion is that FEN is good enough for the standard.

I doubt that the short notation should be in the standard. It can only be done if someone comes up with a formal definition for it. In the past I have made a parser for the solutions of the problems in the Groeneveld archive that I published on my web page. There were many ambiguities and inconsistencies in these solutions.

[Rein Halbersma]

Perhaps we can structure the discussion a bit more. IMO, it might be a good idea to first come to a broad consensus on the functional requirements that the new PDN standard needs to satisfy. Only then should we look for a clean grammar.

Basic philosophy
-------------------

From the PGN standard http://www.saremba.de/chessgml/standard ... mplete.htm

Code: Select all

1: Introduction

PGN is "Portable Game Notation", a standard designed for the representation of
chess game data using ASCII text files.  PGN is structured for easy reading and
writing by human users and for easy parsing and generation by computer
programs.  The intent of the definition and propagation of PGN is to facilitate
the sharing of public domain chess game data among chessplayers (both organic
and otherwise), publishers, and computer chess researchers throughout the
world.

PGN is not intended to be a general purpose standard that is suitable for every
possible use; no such standard could fill all conceivable requirements.
Instead, PGN is proposed as a universal portable representation for data
interchange.  The idea is to allow the construction of a family of chess
applications that can quickly and easily process chess game data using PGN for
import and export among themselves.

I think it is important to appreciate the universality of this goal: PDN is not just for programmers, but also for players to exchange games. Readability is therefore not just eye candy but an ingredient that will facilitate standard compliance.

More basic ideas from the same PGN document:

Code: Select all

2.2: Specification goals
A specification for a portable game notation must observe the lessons of history and be able to handle probable needs of the future. The design criteria for PGN were selected to meet these needs. These criteria include:


The details of the system must be publicly available and free of unnecessary complexity. Ideally, if the documentation is not available for some reason, typical chess software developers and users should be able to understand most of the data without the need for third party assistance.

The details of the system must be non-proprietary so that users and software developers are unrestricted by concerns about infringing on intellectual property rights. The idea is to let chess programmers compete in a free market where customers may choose software based on their real needs and not based on artificial requirements created by a secret data format.

The system must work for a variety of programs. The format should be such that it can be used by chess database programs, chess publishing programs, chess server programs, and chessplaying programs without being unnecessarily specific to any particular application class.

The system must be easily expandable and scalable. The expansion ability must include handling data items that may not exist currently but could be expected to emerge in the future. (Examples: new opening classifications and new country names.) The system should be scalable in that it must not have any arbitrary restrictions concerning the quantity of stored data. Also, planned modes of expansion should either preserve earlier databases or at least allow for their automatic conversion.

The system must be international. Chess software users are found in many countries and the system should be free of difficulties caused by conventions local to a given region.

Finally, the system should handle the same kinds and amounts of data that are already handled by existing chess software and by print media.

Especially the fifth goal is laudable. E.g., I think there is a trend for more and more online broadcast games. Such games already include time information per move. Another idea might be to include the alpha-beta score after each move (to create graphs such as the Truus program does). This can be easily done using comments in variations. In any case, it would be nice if current programs can read such future PDN files simply by ignoring this information. This essentially captures Ed Gilbert's remarkt to be liberal in reading, conservative in writing.

Functional requirements
---------------------------

1) Encompass all known and future draughts variants. The file http://www.xs4all.nl/~mdgsoft/draughts/pdn.html gives a description how to specify variants:

Code: Select all

GameType "Type-number [,Start colour (W/B),Board width, Board height, Notation
		[,Invert-flag]]"

Type-number:     this is one of the following type-numbers
   0: Chess
   1: Chinese chess
   2-19: future chess expansion
  20: 10x10 draughts (international)
  21: English draughts (kings only move 1 step at a time)
  22: Italian draughts (as English, Men cannot take kings, must capture max)
  23: American pool draughts (as 10x10, not obliged to take max)
  24: Spanish pool  draughts (as 10x10 rules, but men cannot capture backwards)
  25: Russian draughts 
  26: Brazilian 8x8  draughts (same as 10x10 rules)
  27: Canadian 12x12  draughts (same as 10x10 rules)
  28: Portugese draughts
  29-49: Future draughts expansion
  50: Othello
  51..  Future expansion.

Start-colour:    Either W or B - white/black side starts (can vary in draughts)
Board-width:     Width of board..
Board-height:    Height of board..
Notation:        A=alpha/numeric like chess, N=numeric like draughts.
                 S=SAN - short-form chess notation.
                 Then follows a number 0-4 telling where square A1 or 1 is for
                 the side who starts the game (White or black)
                 0= Bottom left, 1=Bottom right, 2=Top left, 3=Top right..
Invert-flag:     0 = play on dark squares (like english & 10x10), 1 = play on light
                 squares (like italian draughts) This is only needed in draughts.

2) Backwards read-compatibility for all existing PDN archives on the web. This means being able to read output from the current version of TurboDambase, and being able to read existing archives for Russian, American and Italian draughts for programs that support these variants. Programs that do not support such variants should exit gracefully (i.e. with a notification, not by crashing). Note that Russian databases routinely use the short algebraic (chess-like) notation (and they conform to the convention of using Game-type==25). Also note that I do not propagate the default use of algebraic short notation for 10x10 draughts, but a program should be able to read such input or specify that it doesn't with a graceful exit.

3) Backwards write-compatibility to the most frequently used programs on the web (i.e. TurboDambase, Truus, Flits, Dam 2.2 for 10x10 draughts). Now this will be a difficult thing to achieve when adding a lot of new features to the standard, but I think a lot of current programs are already liberal in reading and will skip unrecognized tags etc. As long as a clean sequence of moves and a FEN string gets read without hiccups, this goal might be attainable.

Again from the PGN standard:

Code: Select all

3.2.4: Reduced export format
A PGN game represented using export format is said to be in "reduced export format" if all of the following hold: 1) it has no commentary, 2) it has only the standard seven tag roster identification information ("STR", see below), 3) it has no recursive annotation variations ("RAV", see below), and 4) it has no numeric annotation glyphs ("NAG", see below). Reduced export format is used for bulk storage of unannotated games. It represents a minimum level of standard conformance for a PGN exporting application.

4) Anticipate future online draughts games / fragments / problems. There is a trend that more and more newspapers, magazines etc. become online (freely or with subscription). The Google Book project may or may not get to such specialized literature, but it can't hurt to be ready for that. We already know that these sources contain features that are currently not in the standard, such as short numeric notation (heavily used and propagated by problem composers, it's a very sensitive matter for them, so forget about converting them to long numeric notation) and abbreviated FEN strings (with separators such as "-" or "t/m").

Then a final comment on the syntax for FEN strings. This was first described in Adrian Millet's attempt at a PDN standard http://homepages.tcp.co.uk/~pcsol/sagehlp1.htm#PDN

Code: Select all

The FEN format must be "SIDE_TO_MOVE:W(pieces):B(pieces)." A K indicates a king.

and elaborated into Murray Cash's PDN 2.0

Code: Select all

6.1.1.1.1.7 FEN_TEXT DEFINITION (Optional)

A description of the set up position of the board enclosed in double 
quotes ("). This header is only used when the game does not begin 
from the usual starting position. Typically the game is a 
continuation of a problem, or an 11-man ballot game.

The format of the quoted description is as follows: 

[TURN]:[COLOUR1][[K][SQUARE_NUM][,]...]:[COLOUR2][[K][SQUARE_NUM][,]...]

[TURN] is B or W defining whose turn it is to play first (B = 
Black/Red, W = White).

[COLOUR1] and [COLOUR2] are either B or W defining the colour of the 
pieces on the squares to follow. One must be B; the other W. The 
sequence is unimportant.

[K] is optional before each SQUARE_NUM and if used, indicates the 
piece on that square is a king, otherwise it is a man.

[SQUARE_NUM] indicates the square number that is occupied by a 
certain piece. This is in the range 1-32 according to checkers 
standards. These are comma-separated, and their sequence is 
unimportant.

THe only difference is the use of the "." as a closing character.