On and off, there has been discussions about using a 1-dimensional
board instead of a 2-dimensional, i.e. to use only one index when
addressing a point on the board.  I decided to do a proof of concept
and I now have the first result.  It was more difficult than I
expected, partly because of the sheer size of board.c and reading.c.

I used the following representation (example is 5x5):

######
#.....
#..OO.
#..OX.
#...X.
#.....
#######

Each '.' denotes an intersection on the board and each '#' is a border
marker (color == GRAY). The borders on the left and right side are
shared.  Offsets to the left and right are -1 and 1. Accessing the
intersection upwards you use offset -NS (north-south) and downwards
use offset NS.  The terminology is from an article by Martin Mueller.

Profiling of GNU Go shows that approximately 80% of the time is spent
in tactical reading, so I decided that it was useful to start there.
Most of the program still uses p[][], but on every call to attack()
and find_defense() the position gets converted to board[] using a
function called p_to_board, and the rest of the reading is done in 1
dimension.

Unfortunately, reading.c is over 6000 lines of code, so I haven't
converted everything yet. I started out with do_attack,
do_find_defense, attack1, attack2 and defend1. So the only thing that
we can read right now is ladders.  I tried it out on the reading tests
39 and 40 (the big reading mistake in the Honinbo game) and it works
fine.

The timing results are a bit difficult to evaluate. Right now, the
reading is slower than before. This is due to p_to_board, which takes
a long time to initialise the incremental data structures. This
dominates the reading time on simple cases, which this test case is,
using about 50% of the run time. I tried to get a feeling for how much
faster the actual reading was, and I think I got somewhere between 10%
and 20% speedup.  No caching is implemented yet.

But the really big advantage is that the code is much simpler and
easier to read. I expect the timing advantage to increase somewhat
when more of Gnu Go is 1-dimensional, but I also expect that we will
get rid of the i-j bugs that we have had completely.  We will also use
less memory and development will become easier.

If you are interested in what I have done, take a look at
http://www.lysator.liu.se/~inge/.  You can download the file
1D-0.1.diff.gz. This diff applies to Gnu Go version 2.7.237. I edited
the file manually somewhat, so you might get a few offsets in the
patch process, but otherwise everything should go cleanly.

I am interested in feedback. There is not much documentation right
now, and I have tried to comment the code everywhere, but more could
be done there. There are also some things left from dead ends that I
tried and I haven't cleaned everything up yet.

	-Inge

===================================================

Version 0.2 of the 1-dimensional reading patch is now finished.  All
of reading.c except naive_ladder_* is now converted.  Still no
hashing, though.

Timing is still not good, since every call to attack or find_defense
implies a call to p_to_board, which recalculates all incremental data
structures for the 1-D implementation.  However, I know how I shall
fix this, and that will be version 0.3.  At that time I might also be
able to give you some timing info.  0.4 will include hashing.

The diff can be found at
http://www.lysator.lui.se/~inge/1D-2.7.237-0.2.diff.gz, and of course
it applies to 2.7.237.

Now for the comments from Gunnar et al:

Teun Burgers wrote:
> To make it more obvious we are dealing with points I suggest to use
> 
> typedef int point;
>
> ...and some more

I think that Gunnar answered these remarks with my own feelings on the
subject.

Gunnar wrote:
> Inge wrote:
> > I used the following representation (example is 5x5):
> > 
> > ######
> > #.....
> > #..OO.
> > #..OX.
> > #...X.
> > #.....
> > #######
> 
> >From this figure it looks like one can move northeast from the upper
> left corner and get to a border marker, but if I read the macros
> correctly, you end up on index -1, which of course is invalid. In any
> case I think it's worthwhile to guarantee that a diagonal displacement
> from a vertex on the board will give a valid index and a border
> marker.

Absolutely.  This is not fixed yet.  It will be, though.

> I'm not particularly happy with this notation (but there's nothing
> wrong with the board representation). More precisely I'd prefer to
> have explicit EAST, NORTH, WEST, and SOUTH displacement macros rather
> than +1, -1, +NS, and -NS. Then the random code segment below
> 
>   if (board[pos-NS]==color)
>     remove_string_1d(pos-NS);
> 
> would become
> 
>   if (board[NORTH(pos)]==color)
>     remove_string_1d(NORTH(pos));

I don't agree.  I think that board[pos-NS] and so on are very easy
idioms to learn and to interpret.  Especially if you want to move away
some more, board[pos+2*NS-1] is much nicer than
board[WEST(SOUTH(SOUTH(pos)))] which is almost unreadable. 

> I have a very strong feeling that it would be better to embed smaller
> boards within the MAX_BOARD times MAX_BOARD one. Most importantly this
> would replace the board_size variable with the MAX_BOARD constant in
> the macros above, which simply has to allow more efficient code to be
> generated. Secondarily this would make the ON_BOARD assertions more
> effective due to additional padding, especially if one temporarily
> increases MAX_BOARD substantially.

You are probably right, but there is another (minor) problem with this.
See below.

> > +    for (k = POS(0, 0); k < POS(board_size - 1, board_size); k++) {
> 
> Ugh, this idiom must be simplified. I propose to add two new macros so
> that a loop over the board would become
> 
>   for (k = MINPOS; k < MAXPOS; k++)
>     if (board[k] != GRAY) {
>       [...]
>     }

If we instead let the representation be (board_size is 5 and MAX_BOARD
is 9):

                ##########
                #.....####
                #..OO.####
                #..OX.####
                #...X.####
                #.....####
                ##########

, then how would we express the loop above?  It would be inefficient
to loop over all the border intersections.  On the other hand, we
don't want to make two embedded loops any more.

	-Inge

Here is the third release of the 1-dimensional board code.  This time
I have managed to get a 20% speedup using it compared to ordinary
2-dimensional reading.  From reading profiling reports I expect the
tactical reading to actually be about 25% faster, but this is offset
by the rest of the program which is not yet 1-D yet.

I noticed that calls to trymove from the functions in reading.c were
appr. 50 times more common than calls from the rest of the engine.  So
I simply made the 2-dimensional trymove also call the 1-dimensional
one.  This imposes a small overhead in about 2% of all trymove calls.
On the other hand I managed to remove all calls to p_to_board except
for when a new position is entered through e.g. gnugo_genmove.

Unfortunately I have managed to break something in the process because
there are now 21 unexpected failures in reading.tst.  I hope to fix
this in the next version, where caching will be supported also.

Teun Burgers wrote:
> Inge Wallin wrote:
> > 
> > Teun Burgers wrote:
> > > One other aspect is that *two* things have been changed:
> > >
> > > 1) 1-D board
> > > 2) x and y of a liberty are now stored contiguously in memory
> > 
> > I don't understand what you mean with 2).
> 
> Currently liberty arrays are declare like libi[10], libj[10].
> libi[k] and libj[k] are some distance
> apart in memory. Fetching a liberty require 2 memory references.
> With 1-D you have lib[10]. lib[k] is one memory reference.
> 
> What I mean is that a similar speedup might perhaps be achieved by
> reorganising the liberty arrays without going to a 1-D board.
> Especially since approxlib is currently one of the more time consuming
> functions.

I don't expect this to have any impact at all.  Processor on-chip
caches tend to be at least 512 KB nowadays and this would encompass
all the lib[] arrays that are used at any point in the program (though
maybe not all at once).


> I am still a little bit worried that the 1-D board results in a speedup
> which is obviously very important, but may introduce new maintenance
> problems and might be more difficult to debug.  Moving from a 2-D
> representation of what is something 2-D (a board) to a 1-D
> representation
> to me feels a bit like moving in the direction of machine-code. But
> maybe I am exagerating...

I think you are exaggerating.  Take a look at the code and you will
see that it actually is simpler than before.

	-Inge