[gnugo-devel] Looping over the board

[Gunnar Farnebäck]

I've been thinking about possible simplifications of the common
operation to loop over the board. First some history. In the old times
the internal board representation was a 2D array and a typical board
loop would look like

for (ai = 0; ai < board_size; ai++)
  for (aj = 0; aj < board_size; aj++) {
    ...p[ai][aj]...
  }

When we switched to 1D board representation the same loop could be
used, like this

for (ai = 0; ai < board_size; ai++)
  for (aj = 0; aj < board_size; aj++) {
    int pos = POS(ai, aj);
    ...board[pos]...
  }

but it also allowed a more compact 1D loop

for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
  ...board[pos]...
}

However, this loop is not only over the board but also over some
off-board indices. Depending on what's being done that's not
necessarily a problem but one needs to be careful about it. The
canonical solution to avoid any complications is to use the
construction 

for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
  if (!ON_BOARD(pos))
    continue;
  ...board[pos]...
}

The last two constructions are typically what we use today, except in
some printing loops where it's easier to add formatting with a 2D
loop.

The main weaknesses are that the former construction invites to subtle
bugs if one is not sufficiently careful while the latter construction
is bigger than desirable. It does make a difference to readability and
code overview to have a loop construction which effectively takes
three lines instead of one.

I have two proposals for new constructions, where the second depends
on the first.

1. Introduce an array next_board_point[] which is set up to point from
   each point on the board to the next point on the board in the same
   order as the loop construction above and from the last point to
   NO_MOVE. Then we can loop with 

   for (pos = BOARDMIN; pos != NO_MOVE; pos = next_board_point[pos]) {
     ...board[pos]...
   }

   without having to worry about off-board points.

2. Introduce a macro

   #define LOOP_BOARD(pos) \
     for (pos = BOARDMIN; pos != NO_MOVE; pos = next_board_point[pos])

   and loop with the construction
   
   LOOP_BOARD(pos) {
     ...board[pos]...
   }

The drawback of the last construction is that it's doing a somewhat
scary amount of preprocesser magic, hiding a complete for statement in
a macro. On the other hand it's quite clear and considerably
simplifies the code. It also reduces typing effort for new code.

Comments?

/Gunnar