Data Structure for a PGN Object?

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

User avatar
Steve Maughan
Posts: 1221
Joined: Wed Mar 08, 2006 8:28 pm
Location: Florida, USA

Data Structure for a PGN Object?

Post by Steve Maughan »

I'm about to create a PGN parsing / storing object. I'd like it to be able to handle variation and comments etc. Are there any obvious data structures for the variations? I was thinking of having a list of possible branching moves for each move. The game would then be parsed by moving from one move to the next e.g.

To move forward

Code: Select all

CurrentPosition.MakeMove(VariationIndex);
or to move back

Code: Select all

CurrentPosition.TakeBack;
I'm sure this would work but it doesn't seem elegant and considering that many (i.e. most games) do not have variations, I think it is probably quite slow.

So the question is, how do others implement a data structure for a PGN parser? Am I missing something obvious?

Thanks,

Steve
mathmoi
Posts: 286
Joined: Mon Mar 13, 2006 5:23 pm
Location: Québec

Re: Data Structure for a PGN Object?

Post by mathmoi »

Hi Steve,

I have also designed my own PGN parser in C++. I used polymorphism to handle this problem. I have a base class that I called CToken and derived class for the tokens types : CMove, CComment, CNAG, CVariation. A CVariation is basically a vector of CToken (and is also a CToken).

In my CGame class I have a CVariation object that contains the move list. It can also contain comments, numerical annotation glyphs and other variations.

If you (or anyone else) want i'm willing to send/licence you my code. Just ask.
Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 9:19 pm
Location: Oslo, Norway

Re: Data Structure for a PGN Object?

Post by Tord Romstad »

Hello Steve,

I use the following classes in Glaurung:

The ChessMove class:

Code: Select all

@interface ChessMove : NSObject {
  move_t move;          // Low-level C move, actually just an int.
  NSString *comment;    // Comment for this move.
  NSString *SANString;  // SAN representation of this move.
  int NAG;              // Numeric annotation glyph.
}
The GameNode class:

Code: Select all

@interface GameNode : NSObject {
  ChessPosition *position;   // The position at this node.
  ChessMove *move;           // The move that led to this position, equal to
                             // 'nil' for the root node of a game.
  GameNode *parent;          // The parent node, 'nil' for the root node.
  NSMutableArray *children;  // Array of all child nodes, the main variation
                             // is the first entry.
}

The Game class:

Code: Select all

@interface Game : NSObject {
  NSString *whitePlayer;  // PGN tag
  NSString *blackPlayer;  // PGN tag
  NSString *event;        // PGN tag
  NSString *site;         // PGN tag
  NSString *round;        // PGN tag
  NSString *date;         // PGN tag
  result_t result;        // The result of the game
  NSString *rootFEN;      // FEN of the starting position for the game
  GameNode *root;         // The root node of the game
  GameNode *currentNode;  // The current node of the game
}
Some example methods:

Code: Select all

// Add a new child node (i.e. start a new variation from this node):
-(void)insertMove:(ChessMove *)move {
  [currentNode addChildNode: move];
  currentNode = [[currentNode children] lastObject];
  [self pushClock];
} 

// Make a new move from the current position, remove the old move (if present)
// and all variations:
-(void)makeMove:(ChessMove *)move {
  [currentNode removeAllChildNodes];
  [self insertMove: move];
}

// Unmake the last move.  No moves are deleted, we simply step one move back
// in the move list.
-(void)unmakeMove {
  if(currentNode != root)
    currentNode = [currentNode parent];
}

// Step forward one move, by picking the first child node of the current
// position (i.e. the main line):
-(void)stepForward {
  if([[currentNode children] count] > 0)
    currentNode = [currentNode firstChildNode];
}

// Go back to the beginning of the game:
-(void)goToBeginningOfGame {
  while(currentNode != root)
    currentNode = [currentNode parent];
}

// Go to the end of the game:
-(void)goToEndOfGame {
  for(currentNode = root; [[currentNode children] count] > 0;
      currentNode = [currentNode firstChildNode]);
}

// Delete the variation beginning with the current node:
-(void)deleteVariation {
  if(currentNode != root) {
    GameNode *parent = [currentNode parent];
    [[parent children] removeObjectIdenticalTo: currentNode];
    currentNode = parent;
  }
}

// Are we at the beginning of the game?
-(BOOL)isAtBeginningOfGame {
  if(currentNode == root) return YES;
  else return NO;
}

// Are we at the end of the game?
-(BOOL)isAtEndOfGame {
  GameNode *node;

  if([[currentNode children] count] > 0) return NO;
  for(node = root; [[node children] count] > 0; node = [node firstChildNode]);
  if(node == currentNode) return YES;
  else return NO;
}

// Are there any variations before the current variation from the parent node?
-(BOOL)previousVariationExists {
  if(currentNode == root) return NO;
  if([[[currentNode parent] children] indexOfObject: currentNode] == 0)
    return NO;
  else
    return YES;
}

// Are there any variations after the current variation from the parent node?
-(BOOL)nextVariationExists {
  NSMutableArray *siblings;
  if(currentNode == root) return NO;
  siblings = [[currentNode parent] children];
  if&#40;&#91;siblings indexOfObject&#58; currentNode&#93; < &#91;siblings count&#93; - 1&#41;
    return YES;
  else 
    return NO;
&#125;

// Go to the previous variation from the parent node&#58;
-&#40;void&#41;goToPreviousVariation &#123;
  if&#40;&#91;self previousVariationExists&#93;) &#123;
    NSMutableArray *siblings = &#91;&#91;currentNode parent&#93; children&#93;;
    currentNode = &#91;siblings objectAtIndex&#58; 
			      &#91;siblings indexOfObject&#58; currentNode&#93; - 1&#93;;
  &#125;
&#125;    

// Go to the next variation from the parent node&#58;
-&#40;void&#41;goToNextVariation &#123;
  if&#40;&#91;self nextVariationExists&#93;) &#123;
    NSMutableArray *siblings = &#91;&#91;currentNode parent&#93; children&#93;;
    currentNode = &#91;siblings objectAtIndex&#58; 
			      &#91;siblings indexOfObject&#58; currentNode&#93; + 1&#93;;
  &#125;
&#125;    

// Move the current variation one place up among the variations from the
// parent node&#58;
-&#40;void&#41;moveVariationUp &#123;
  if&#40;&#91;self previousVariationExists&#93;) &#123;
    NSMutableArray *siblings = &#91;&#91;currentNode parent&#93; children&#93;;
    int index = &#91;siblings indexOfObject&#58; currentNode&#93;;
    id tmp = &#91;siblings objectAtIndex&#58; index - 1&#93;;
    &#91;tmp retain&#93;;
    &#91;siblings replaceObjectAtIndex&#58; index - 1 withObject&#58; currentNode&#93;;
    &#91;siblings replaceObjectAtIndex&#58; index withObject&#58; tmp&#93;;
    &#91;tmp release&#93;;
  &#125;
&#125;

// Move the current variation one place down among the variations from the
// parent node&#58;
-&#40;void&#41;moveVariationDown &#123;
  if&#40;&#91;self nextVariationExists&#93;) &#123;
    NSMutableArray *siblings = &#91;&#91;currentNode parent&#93; children&#93;;
    int index = &#91;siblings indexOfObject&#58; currentNode&#93;;
    id tmp = &#91;siblings objectAtIndex&#58; index + 1&#93;;
    &#91;tmp retain&#93;;
    &#91;siblings replaceObjectAtIndex&#58; index + 1 withObject&#58; currentNode&#93;;
    &#91;siblings replaceObjectAtIndex&#58; index withObject&#58; tmp&#93;;
    &#91;tmp release&#93;;
  &#125;
&#125;
Tord
Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Data Structure for a PGN Object?

Post by Gerd Isenberg »

Hi Tord,

what language is that? Somehow it looks C++ like and seems to have even pointers. I thought Interfaces are pure virtual or abstract classes without any member variables - to make multiple inheritance simpler...

Thanks,
Gerd
User avatar
smrf
Posts: 484
Joined: Mon Mar 13, 2006 11:08 am
Location: Klein-Gerau, Germany

Re: Data Structure for a PGN Object?

Post by smrf »

... seems to be Objective-C.
Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 9:19 pm
Location: Oslo, Norway

Re: Data Structure for a PGN Object?

Post by Tord Romstad »

Hello Gerd,

Reinhard is right: it's Objective-C. As strange as it may sound, Objective-C is a kind of hybrid between C and Smalltalk. Once you get used to the funny syntax, it's quite a decent language. I like it better than C++.

Tord
Gerd Isenberg
Posts: 2250
Joined: Wed Mar 08, 2006 8:47 pm
Location: Hattingen, Germany

Re: Data Structure for a PGN Object?

Post by Gerd Isenberg »

Tord Romstad wrote:Hello Gerd,

Reinhard is right: it's Objective-C. As strange as it may sound, Objective-C is a kind of hybrid between C and Smalltalk. Once you get used to the funny syntax, it's quite a decent language. I like it better than C++.

Tord
Thanks Tord and Reinhard,

I have heard about it but never had a closer look. Interesting concepts and nice to learn it by studying your concrete classes and methods. Ahh, it even links with C/C++ routines.

Cheers,
Gerd
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: Data Structure for a PGN Object?

Post by sje »

The methods with names starting with "NS" are from the NextStep toolkit produced by Next Computer. This was the company started by Steve Jobs after he was booted from Apple in 1985, a year after the introduction of the Macintosh. It was the same company that was bought by Apple for US$400 million in 1997, and that's how Apple finally got a decent operating system after twelve years of uninspired products.
User avatar
Steve Maughan
Posts: 1221
Joined: Wed Mar 08, 2006 8:28 pm
Location: Florida, USA

Re: Data Structure for a PGN Object?

Post by Steve Maughan »

Thanks everyone - it's all helpful and thought provoking stuff.

I think on I'm going to implement the PGN class as a mini database with each variation being a separate game i.e.

Code: Select all

Move &#58;= PGN_Game.Variation&#91;i&#93;.Move&#91;n&#93;;
The main variation is when i = 0. As for the internal storage, I think it'll be something like what Tord is doing.

Thanks again,

Steve