On record of captured stones, reference to #6

[tylerjw]

My original idea for storing the event of captured stones was to place a record of them in the game_tree using a SGF property. However I was unable to find a standard property for storing the record of a stone/group being captured in SGF. Here is a list of standard properties: (http://senseis.xmp.net/?SmartGameFormat). I don't want to reinvent the wheel but here are the options I see now:

1. Add a custom property
+ Simple to implement, least added overhead
+ Small overhead moving between moves in tree
- Input parser would have to these properties
- SGF output files may not be compatible with other software

2. Add capture note to comment property 
+ Simple to implement
+ Small overhead moving between moves in tree
- Method needed to parse comments into data
- Input SGF parser would have to add to the comments
- SGF output files would contain comments not added by the user

3. Change GameTree to handle storing captures internally
+ Would not modify SGF output or input files
+ Small overhead moving between moves in tree
- Input SGF parser would have to find capture cases
- Refactoring of existing code base

4. Walk the tree on every move to sense captures
+ Would not modify SGF output or input files
- Performance loss undoing moves and switching between branches

Thoughts?

[sphaso]

Quite a dilemma indeed. In my thoughts I had only considered editing the game, not inputting. I gave a quick look at the parser code and now (I think) I realize where the problem lies. At the moment we're using the classes used to parse the SGF for our internal game structure meaning we're pretty much writing SGF on the go. I didn't see that before. If we decouple this behavior we can manage our internal structure easily (as you mentioned SGFs don't care about board, captures...). My idea is to use the SGF classes only for inputting and outputting. At input we transform the SGF structure into our own structure, during output the opposite. Our internal structure is a tree of Moves where Move has a position (x, y), two lists of captures (or simply two integers? can it work?) and a board representation. Of course using the SGF DS can ease a lot of burden because we don't need to replicate a whole bunch of helper methods to navigate it, but I guess we can easily reimplement them. I know this is a major development and I'll certainly help you with it, we can easily divide the workload once we make the internal class and structure. Let me know what you think.

EDIT: perhaps we might try option number 4 first. If we navigate the tree each time we can avoid carrying boards and captures, and the performance loss might be minimal.

[tylerjw]

I like your idea of making a game_tree data structure of our own, with methods to input SGF through the parser and to build SGF to output it. That seems like the way to go. Storing the data within a data_structure of our own means we don't need to change it's form (sfg_to_move & move_to_sgf) or manipulate the structure of the SGF (undo) every time something changes in the game. This reduces the real time overhead of the program. The only expense is reading and writing SGF files takes more time, a real non-issue. I think we should build a tree data structure that can move both forward and backward and have methods to create branches and walk the tree, revealing all paths.

One feature I think we may need is that every node should store the path taken to get to that node. This would take very little overhead as all we need to do is copy the list of steps from the previous node and add the step for the current node. This way when the user jumps laterally through the game tree a method could walk the nodes forward to build the board without having to walk backwards first.

Node
------------------------------
previous - reference to previous Node object (None if first move)
next - list of next objects (type Node)
path - list of indexes in next lists to move forward from the beginning to this node
origin - link to the origin of the game tree
captures - list of captured stones (captured stone color can be figured by taking 
     the opposite of side)
move - the move of the given node
side - side of the move
board_hash - hash of the board object at the given position (hash of board.goban)

GameTree
------------------------------
firsts - list of Node objects (first moves)
white_placed - white stones placed before the game started
black_placed - white stones placed before the game started
current - current node (last move)
-
make_move(move,captures,board_hash) - makes a move, performs ko test with board 
        hash then assigns move (should be tested legal otherwise)
undo_move() - returns current move (the one being undone so it can be taken off) and 
        captures (so they can be added back)
walk(root) - walks forward depth first starting with root, if root is not given walks all 
        nodes (generator)
input_sgf(sgfdata) - build gametree from sgfdata
output_sgf() - outputs a string of data in sgf format

thoughts?

[sphaso]

I'm glad you like it and you've started thinking about it. I admit I've only worked with tree structures once and it was a long time ago. My first thought is: how does the SGF parser do? does it work by storing a reference to the node neighbours? can we simply keep a reference of the current node (and\or current variation)? in case of jumps we might search the tree for a unique ID we attach to the object. I hear your concern about performance loss, but we're still working with a small amount of data, so if we try to avoid recursion when it's not needed I think we're on a good run.

On Thu, Jul 18, 2013 at 2:58 PM, Tyler Weaver notifications@github.comwrote:

I like your idea of making a game_tree data structure of our own, with methods to input SGF through the parser and to build SGF to output it. That seems like the way to go. Storing the data within a data_structure of our own means we don't need to change it's form (sfg_to_move & move_to_sgf) or manipulate the structure of the SGF (undo) every time something changes in the game. This reduces the real time overhead of the program. The only expense is reading and writing SGF files takes more time, a real non-issue. I think we should build a tree data structure that can move both forward and backward and have methods to create branches and walk the tree, revealing all paths.

One feature I think we may need is that every node should store the path taken to get to that node. This would take very little overhead as all we need to do is copy the list of steps from the previous node and add the step for the current node. This way when the user jumps laterally through the game tree a method could walk the nodes forward to build the board without having to walk backwards first.

Node------------------------------previous - reference to previous Node object (None if first move)next - list of next objects (type Node)path - list of indexes in next lists to move forward from the beginning to this nodeorigin - link to the origin of the game treecaptures - list of captured stones (captured stone color can be figured by taking the opposite of side)move - the move of the given nodeside - side of the moveboard_hash - hash of the board object at the given position (hash of board.goban) GameTree------------------------------firsts - list of Node objects (first moves)white_placed - white stones placed before the game startedblack_placed - white stones placed before the game startedcurrent - current node (last move)-make_move(move,captures,board_hash) - makes a move, performs ko test with board hash then assigns move (should be tested legal otherwise)undo_move() - returns current move (the one being undone so it can be taken off) and captures (so they can be added back)walk(root) - walks forward depth first starting with root, if root is not given walks all nodes (generator)input_sgf(sgfdata) - build gametree from sgfdataoutput_sgf() - outputs a string of data in sgf format

thoughts?

— Reply to this email directly or view it on GitHubhttps://github.com/tylerjw/badukpy/issues/12#issuecomment-21181202 .

[tylerjw]

As to doing lateral jumps the walking function will allow us to build "flat" data structures for displaying the tree, allowing the user to select where he wants to jump to. The method should return node objects that contain the path variable telling us how to build the board to that location.

[sphaso]

Please feel free to investigate this way. I'd like to take some time to study the SGF parser code in more depth and see how it's implemented there, I'm pretty sure there must be an easier way.

On Fri, Jul 19, 2013 at 1:54 PM, Tyler Weaver notifications@github.comwrote:

As to doing lateral jumps the walking function will allow us to build "flat" data structures for displaying the tree, allowing the user to select where he wants to jump to. The method should return node objects that contain the path variable telling us how to build the board to that location.

— Reply to this email directly or view it on GitHubhttps://github.com/tylerjw/badukpy/issues/12#issuecomment-21245610 .

[tylerjw]

Check out what I just pushed. I haven't tested it yet, but that's the basic framework of what I think is needed. You can see that tree traversal is rather simple.