Re: computer-go: Sharing Go modules

[William Harold Newman <william.newman@xxxxxxxxxxx>]

(This reply mostly misses the point of the original poster's question,
looking for a way to fit together Go libraries written by different
people. It's more a response to the advantages claimed by people for
different representations.)

I like representing squares as objects. I switched to Lisp a few years
ago, but since more people understand C++ I'll express it that way.
Beware, though, the code is written off the top of my head, not
decorated with the const's and stuff it should really have, and not
tested in the least.

  class Sq {
  private:
    int x_, y_;
    int distance_from_edge_;
    int distance_from_corner_;
    Color *color_;
    /* plus other values like "what solidly connected group am I 
     * a part of, etc. */
  protected:
    /* These seem to end up needing to be accessible to derived classes so
     * that we can set things up correctly with e.g. a Decorated_Sq's 
     * adj_sqs_ slot containing only Decorated_Sq's. */
    Sq *adj_sqs_[1+max_possible_adj_sqs]; /* zero-terminated array */
    Sq *diag_sqs_[1+max_possible_diag_sqs];
  public:
    int x() { return x_; }
    /* etc.: other public wrappers for private fields */

    /* etc.: all sorts of other stuff which C++ requires to be 
     * declared in a header file in order to be allowed to work 
     * with the class */
  };

This approach makes it easier to write various things, e.g. this bit
of code from gnugo-2.7.207/engine/incremental_board.c

    /* Look in each direction for new liberties or new neighbors. Mark
     * already visited liberties and neighbors.
     */
    if (i > 0) {
      if (UNMARKED_LIBERTY(i-1, j)) {
        ADD_AND_MARK_LIBERTY(s, i-1, j);
      }
      else if (UNMARKED_OPPONENT_STRING(s, i-1, j)) {
        ADD_NEIGHBOR(s, i-1, j);
        MARK_STRING(i-1, j);
      }
    }
    
    if (i < board_size-1) {
      if (UNMARKED_LIBERTY(i+1, j)) {
        ADD_AND_MARK_LIBERTY(s, i+1, j);
      }
      else if (UNMARKED_OPPONENT_STRING(s, i+1, j)) {
        ADD_NEIGHBOR(s, i+1, j);
        MARK_STRING(i+1, j);
      }
    }
    
    if (j > 0) {
      if (UNMARKED_LIBERTY(i, j-1)) {
        ADD_AND_MARK_LIBERTY(s, i, j-1);
      }
      else if (UNMARKED_OPPONENT_STRING(s, i, j-1)) {
        ADD_NEIGHBOR(s, i, j-1);
        MARK_STRING(i, j-1);
      }
    }
    
    if (j < board_size-1) {
      if (UNMARKED_LIBERTY(i, j+1)) {
        ADD_AND_MARK_LIBERTY(s, i, j+1);
      }
      else if (UNMARKED_OPPONENT_STRING(s, i, j+1)) {
        ADD_NEIGHBOR(s, i, j+1);
        MARK_STRING(i, j+1);
      }
    }

which becomes something like

  for (Sq** p = sq->adj_sqs(); *p; ++p) {
    Sq* adj_sq = *p;
    if (adj_sq->is_unmarked_liberty()) {
      sq->add_and_mark_liberty(adj_sq);
    } else if (adj_sq->is_unmarked_opponent_string()) {
      sq->add_neighbor(adj_sq);
      adj_sq->mark_string();
    }
  }

or even (since even in C++ I'm a Lisp programmer at heart and think
that using macros to define new control structures once and for all in
order to reduce redundant coding is a good thing) something like

  FOR_ZERO_TERMINATED_VECTOR(adj_sq, sq->adj_sqs()) {
    if (adj_sq->is_unmarked_liberty()) {
      sq->add_and_mark_liberty(adj_sq);
    } else if (adj_sq->is_unmarked_opponent_string()) {
      sq->add_neighbor(adj_sq);
      adj_sq->mark_string();
    }
  }

or

  FOR_SQ_ADJ_SQS(adj_sq, sq) {
    if (adj_sq->is_unmarked_liberty()) {
      sq->add_and_mark_liberty(adj_sq);
    } else if (adj_sq->is_unmarked_opponent_string()) {
      sq->add_neighbor(adj_sq);
      adj_sq->mark_string();
    }
  }

Of course, the last form could quite possibly also be used to
abbreviate the code in the (x,y) representation of squares, given
enough determination.

Besides the macro-heavy approach above, another way to make the
calling code code not depend on what kind of representation you're
using is to make the adj_sq() member function return an STL-style
iterator.

I'm not sure what's the efficiency cost or advantage of doing an extra
indirection through a zero-terminated-vector instead of the index
arithmetic and bounds testing, or using a for() loop instead of
unrolling the code for the four possible neighbors. However, I doubt
it matters in most cases. And the conciseness advantage is always
nice.

This approach doesn't seem to have any advantages for matching
patterns. If I want to do that, I end up falling back to some sort of
array of Sq's. Furthermore, since I end up with several classes
derived from Sq at different levels of abstraction, there's either a
maintenance hassle of allocating the array as the most-derived type of
Sq and making sure that the pattern-matching code knows the size of
the most-derived type so that it can do fast array arithmetic, or the
runtime cost of doing an extra indirection for every Sq reference
through an array of Sq pointers. (This last design choice is only an
issue in C++, not in Lisp or Java, where the language designers know
best, forcing you always to use the clean but slow solution of
indirecting through an array of interface pointers.:-)

There's also a slight awkwardness, at least in C++, when you have a
value (like "what's the best move?") which might be a square, or
"pass", or even some sort of failure value like "not sure yet". But in
my experience those awkwardnesses are always far enough from inner
loops that small overheads don't matter, so you can deal with them
with any kind of abstraction you like (e.g. a Move interface class
from which both Pass_Move and Move_To_Sq are derived).

--
William Harold Newman <william.newman@xxxxxxxxxxxxxxxxx>
whose Go program is still stomped flat by Gnu Go every time he tests it
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C