RE: computer-go: unmake move?

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> [...] In trying new moves, groups are restructured, requiring me to
> re-assign group numbers all the time.  To make matters worse, during
> the unmake move for minimax, I will have to re-assign group numbers
> when removing a piece from the board causes group structures to change.
> [...]
> Bryan McQuade

It's a tradeoff. In SmartGo, we've found that keeping the number of each
block (what you call a group) updated at all times is worth it, even if
it means reassigning block numbers when blocks get merged. The advantage
is that it allows direct access to any properties associated with the
block, such as liberties and number of liberties, and it e.g. speeds up
the search for blocks adjacent to a block. The more your algorithm
checks properties of blocks rather than simply making and taking back
moves, having the block number available for each point will pay off.

One alternative is to use some kind of union-find algorithm, which reduces
the block number changes, but requires a loop to get from each point to its
block number.

To speed up unmaking a move, SmartGo logs (almost) all changes to board data
structures as pairs of pointer to memory and old memory content. Undoing a
move then becomes a simple matter of restoring the old memory content.
Here's the undo method copied directly from SmartGo's code:

void UndoStack::DoUndo()
{
   // Fast and tight loop to restore all the changed memory locations to
their
   // old content. Using a local copy of the stack pointer gives the
compiler
   // a better chance to optimize and speeds up tactical search by almost
1%.
   int sp = m_sp;
   while (int* pMemory = reinterpret_cast<int*>(m_stack[--sp]))
      *pMemory = m_stack[--sp];
   m_sp = sp;
} // DoUndo

Even though lots of data gets logged when making a move, only about 1% of
the
total time in tactical search gets spent in DoUndo. The few items that have
not been integrated in this undo scheme yet take significantly more time to
undo.

Anders Kierulf
www.smartgo.com