Data Structure for a PGN Object?

[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]

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]

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([siblings indexOfObject: currentNode] < [siblings count] - 1)
    return YES;
  else 
    return NO;
}

// Go to the previous variation from the parent node:
-(void)goToPreviousVariation {
  if([self previousVariationExists]) {
    NSMutableArray *siblings = [[currentNode parent] children];
    currentNode = [siblings objectAtIndex: 
			      [siblings indexOfObject: currentNode] - 1];
  }
}    

// Go to the next variation from the parent node:
-(void)goToNextVariation {
  if([self nextVariationExists]) {
    NSMutableArray *siblings = [[currentNode parent] children];
    currentNode = [siblings objectAtIndex: 
			      [siblings indexOfObject: currentNode] + 1];
  }
}    

// Move the current variation one place up among the variations from the
// parent node:
-(void)moveVariationUp {
  if([self previousVariationExists]) {
    NSMutableArray *siblings = [[currentNode parent] children];
    int index = [siblings indexOfObject: currentNode];
    id tmp = [siblings objectAtIndex: index - 1];
    [tmp retain];
    [siblings replaceObjectAtIndex: index - 1 withObject: currentNode];
    [siblings replaceObjectAtIndex: index withObject: tmp];
    [tmp release];
  }
}

// Move the current variation one place down among the variations from the
// parent node:
-(void)moveVariationDown {
  if([self nextVariationExists]) {
    NSMutableArray *siblings = [[currentNode parent] children];
    int index = [siblings indexOfObject: currentNode];
    id tmp = [siblings objectAtIndex: index + 1];
    [tmp retain];
    [siblings replaceObjectAtIndex: index + 1 withObject: currentNode];
    [siblings replaceObjectAtIndex: index withObject: tmp];
    [tmp release];
  }
}

Tord

[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

[smrf]

... seems to be Objective-C.

[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]

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

[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.

[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 := PGN_Game.Variation[i].Move[n];

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