RE: computer-go: Ko

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> Waging ko fights is very difficult, but I'm interested in merely 
> checking for legal moves.  What do people do?

SmartGo falls in the "something else" category. It uses the points
changed at each move to check for full-board repetition, essentially
going backwards from the current position looking for a position with no
changes. The trick is to keep track of when each point was first played,
and terminate the search as soon as such a move is reached. In practice,
this terminates the search immediately most of the time. The performance
overhead is minimal, so full-board repetition is also checked during
tactical lookahead.

Here's a sketch of the C++ code:

bool GoBoard::FullBoardRepetition() const
{
   List  changes["BlackWhite"];
   bool  fSameToPlay = true;
   int   numMovesBack = 0;

   while ("going backwards through the move stack")
   {  switch ("top of stack")
      {  case Delimiter:
         {  if (  (numMovesBack > 0)
               && fSameToPlay
               && changes[black].IsEmpty()
               && changes[white].IsEmpty())
            {  return true; // repeated position
            }
            break;
         }
         case OppToPlay:
         {  fSameToPlay = !fSameToPlay;
            break;
         }
         case "Point p changed between color and empty":
         {  if (!changes[color].Exclude(p))
            {  if ("this was first move played at p")
                  return false; // no repetition possible before that
               changes[color].Append(p);
            }
            numMovesBack++;
            break;
         }
      }
   }
   return false;
} // FullBoardRepetition

Anders Kierulf
www.smartgo.com