Yet Another Novice Tries To Write A Go Program/SGF Parser

This is the high-level structure of my SGF handling classes. This is also the underlying parser in GoSuite. I don't know if it's the best way but, aside from a couple of things (see Learnings at the bottom), I've been pretty satisfied with it.

The SgfReaderWriter

This class handles the low-level details of well-formed SGF. It extends StreamReader which is a .NET class for reading from a stream (a file, network socket, etc.). It handles encoding (UTF-8, etc.). All I need is Peek() and Read(). Forward only, one character at a time, very fast.

The SgfReader has methods like:

  • ReadNode() - Attemps to read a child node (sets MayHaveSibling state)
  • ReadProperty() - Reads a property name (normalizes old-style names such as 'AddWhite' to 'AW')
  • ReadValue() - Reads a single property value (unescapes, converts soft line breaks)
  • Other various things like IsEnd, ReadStart(), MayHaveSibling, and SgfReaderState and enforcement of the semantics.

The SgfWriter again handles encoding and can be used atop any stream (raw memory, network, file, etc.). It has methods like:

  • WriteNodeStart(bool mayHaveSibling) - simply writes the '(' or ';' depending on whether the node has siblings.
  • WriteProperty(string name)
  • WriteValue(string text) - handles escaping reserved characters
  • WritePropertyAndValue(string name, string text) - convenience for single value properties
  • WriteNodeEnd()

Then there's an SgfUtility for Composing/Decomposing values, converting coordinates, etc.

The SgfDocument

The SgfDocument keeps a tree of nodes with properties with values. Load/saves itself via SgfReader/Writer. Very simply. Some special handling of nodes containing only moves to save memory.

The SgfDocument lets you serialize, deserialize and manipulate the tree. Obvious methods:

  • Load(string file)
  • Load(StreamReader reader)
  • Load(SgfReader reader)
  • Save(string file)
  • Save(StreamWriter writer)
  • Save(SgfWriter writer)

The tree supports game collections by having a super root which acts as the parent of all the game root nodes.

The tree is of SgfNodes. Each has a collection of child SgfNodes and of SgfProperties. SgfNode has basic methods to Get/Add/Remove/Replace properties.

SgfProperty has a Name and methods for getting/setting the value in proper SGF format (coordinates, etc.) and handles escaping, removal of line breaks (for SimpleText).

The SgfNavigator

The meat of it is in SgfNavigator where document tree traversal is done, properties are actually understood, and an SgfView is maintained as you move around.

Given an SgfDocument, the navigator lets you programmatically walk around the tree much like a user would in a GUI:

  • End()/Start() - move to end/start of current branch
  • Next()/Previous() - next/previous node
  • MainLine() - not the same as previous branch - skips past variations within variations.
  • Variation(int v) - choose a child
  • Record(int r) - choose a child of the super root
  • Next/PreviousAlternate() - move to next sibling node (if exists)
  • Next/PreviousBranch() - move to next branching node
  • Next/PreviousInteresting() - node with comment/markup/annotation
  • Next/PreviousMarkup()
  • Next/PreviousAnnotation()
  • Next/PreviousHotSpot()
  • Next/PreviousCheckedSpot()
  • Next/PreviousScored() - territory markup

A few other useful things like FindStonePlacement() which, given a point, navigates to the point in the game when that stone was placed. A bunch of properties like IsStart, IsEnd, IsRoot, HasAlternative, IsCollection, etc.

The SgfView

As you walk around an SgfView is maintained which contains everything about the current game and position. This is a data representation of what (presumably) the user will see - the actual board control providing a 'view' to the user is separate however. An SgfView contains the board arrangment of course, the game info, annotations, markup, comments, cropping, tracking of move number locations (even for captured stones), capture counts, etc. - lots of info. It actually has support for 100% of FF[4] (diagrams, lines/arrows, etc.) but not all is exposed in GoSuite.

The SgfPath

As you navigate around, an SgfPath is maintained. This describes the path from the root to the current node. It's useful for retracing your steps searching for something (e.g. PreviousHotSpot()) and at any point you can push the path onto a stack and later pop back from anywhere in the tree. I like this idea.


Learnings

Move Undo

The one thing I regret about this is how I handle walking backward in the tree. There's a lot of state to maintain; not just the stones - there are other inherited and incremental SGF properties (move number, to move, selected/dim, etc.) My first cut was to keep a stack of SgfViews and just pop to go back. This used too much memory. GoSuite today actually just modifies the SgfPath to go back one and retraces from the start! There is some optimization in processing non-inherited properties only for the destination node; not while retracing. Still, near the end of a 300+ move game the delay is noticable if you step backwards. This also happens when you move to a sibling node (really it moves back and follows a different child).

The author of PocketGo (Brian Dewey) had the same problem and solved it in the same way (the same delay is noticable in that product too). He has since written some undo code gave it to me. He only handles stone state though. With everything I keep track of in SgfView, it will be a bit of a pain.

Arno: funny, I used the same method (with the same delay) when coding on Primiview for the Amiga many years ago. I finally settled adding special properties in the parsed tree which held all the meta information (on demand - i.e. when entering a node not visited before). When editing a node I would invalidate all meta data on the nodes below while walking down the tree (i.e. invalidate all children if parent initial state is invalid). Using properties is handy, because you can use your standard routines when parsing them. Just add a "don't write" flag to them, so that they don't get written into the SGF file.

AshleyF: Thanks Arno! I finally got around to doing this. It's much, much faster now. It also makes some things such as previous branch nav easier (don't have to keep track of the last seen branch path) and may enable new features such as animating backward navigation. This will be included in the next build of GoSuite.

TimK: In GoGrinder I took a different approach. It's overkill for GoGrinder, since problems don't normally have long sequences of moves, but I have a Board class that maintains the state of the board, and when I parse an SGF node, I create a set of command objects that represent the changes made to the board when that move is played. Then I use the normal Command pattern for undo/redo - the command objects know how to undo themselves, so navigating back and forth through the game record is straightforward. I don't really like the way I stored the marks on the board, so ignore that part, please :)

The UndoController is [ext] here, and [ext] this is an example Command.

Load Time

Loading a large game tree (e.g. a huge collection, Kogos Joseki Dictionary, etc.) takes a while. On the PocketPC, the flash card is slower than a disk on a desktop machine. I would like to allow walking of the tree while it's still loading. My first thought was to load in a background thread and allow walking at least to nodes that have all their properties parsed and have all their children. If I make an exception for the super-root node, this works well for collections (you can see the first game while others load). For trees like KJD it doesn't work so well. Allowing viewing of nodes when not all the children have loaded would be interesting. I don't know how I'd present that to the user or if it would really be useful.


Yet Another Novice Tries To Write A Go Program/SGF Parser last edited by JesseChisholm on September 8, 2012 - 17:11
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library