Re: [Bug-gnubg] The match and game data structure

[Jim Segrave]

On Fri 30 Jun 2006 (11:03 +0200), Øystein Johansen wrote:
> Hi,
> 
> I have a bad feeling that our data structure for storing matches, games and 
> moverecords are not the best. I'm sometimes affraid it really sucks. I also 
> believe there is a releation between the end product quality and the internal 
> code quality, and I believe these data strutures, might be the Achilles heel 
> in our project.
> 
> Of course I would love to improve this, however I do not want to code 
> anything before I'm sure it's an improvement. I therefore hope that a small 
> discussion about this issue can help us design a better data structure for 
> holding the match data.
> 
> Todays system is simple. (I don't mind things beeing simple, I believe simple 
> is yet beautiful and functional. I'm an advocate of KISS principles). The 
> match is a global linked list of all games. It uses the linked list 
> implementation in the lib directory, which is actually a circular linked 
> list. Each game is a new linked list of moverecords.
> 
> The good thing about this circular list is that appending new elements 
> (moverecords) is a O(1) operation. However, the good things stop there. 
> Looping through a list is a bit cumbersome. It's hard to keep track of a 
> current move and a current game. (We actually have global pointers for this.) 
> This data structure has shown to be bad for working with positions, since it 
> depends on a global list (lMatch).
> 
> Short: I believe it's time for a redesign of the match holding data structure.
> 
> Any suggestions? What's the best redesign. Simply a double linked list (not 
> circular). Do we need match head and game head, to keep track of the size, 
> current move and state etc.? I'm willing to start implementing a better 
> structure if we agree on what we need.

By nature, a match or session should form a tree. The match/session is
the root, with leaves being game trees. A game is a tree with leaves
left to right representing moves/cube actions. I'd consider something
like:

typedef struct move move_t;
typedef struct game game_t;
typedef struct match match_t;
   
struct match {
  game_t *first_game;   
  game_t *last_game;     /* doubly linked seems nice and costs little */
  evalcontext *analysis;
  rolloutcontext *rollout;  
  /* match relevant data - player names, date, rules, etc. here */
};

Along with this, move the analysis and rollout contexts, if any
analysis or rollout is done to the match header. I think few analysed
matches have more than a single analysis context or rollout context
used, but having a linked list of the ones used means we could change
the sgf format to list the contexts in the head of the file and only
use an index to the context in the moves. This would make a major
reduction in the size of .sgf files, where the analysis context is
repeated for each move analysed.

struct game {
  game_t *next;
  game_t *prev;
  int     game_no;      /* useful to find a particular game by number,
                           without having to iterate the list counting
                           elements */
  match_t *parent;      /* don't know if this is useful or not */
  move_t *first_move;
  move_t *last_move;
  /* game relevant data here - scores, Crawford, whatever */
};

struct move {
  game_t *parent;
  move_t *next;
  move_t *prev;
  int     move_no;      /* allows going to a move by number without
                           iterating the move list and counting */
  /* move relevant data here */
};

-- 
Jim Segrave           address@hidden