computer-go: random move execution speed

["Anders Kierulf" <anders@xxxxxxxxxxx>]

> After reviewing my random game test algorithm, I must state that is
> shouldn't be used as a benchmark (my mistake). It's main purpose was to
find
> bugs. It works by generating completely random moves and attempting to
play
> them. An illegal move is turned into pass (12% of all moves). This,
> unfortunately, inflates the performance figures. So that we can compare
> apples to apples, can anyone propose a benchmark algorithm?
>
> Phil

Okay, here's a proposed C++ benchmark algorithm for "random move execution
speed". It's not perfect, but at least it should allow better
apples-to-apples comparison. It plays through a number of random games, and
computes the time for combined playing and taking back moves. The random
moves are played on any empty point, and moves that turn out to be illegal
due to suicide or ko (a bit less than 2% of the moves) are also counted. The
time spent generating random moves is factored out, as it may be a
significant part of the total time.

Point RandomEmptyPoint(const GoBoard& board)
{
   const int S = board.Size();
   const int N = S*S;

   // Keep generating random points until we find an empty point.
   while (true)
   {  int r = Random() % N;
      Point p = Pt(r % S + 1, r / S + 1); // create point from column and
row
      if (board.IsEmpty(p))
         return p;
   }
} // RandomEmptyPoint

const int NUM_GAMES = 5000;
const int NUM_MOVES = 320;

void ExecuteRandomGames(GoBoard& board, int numRandom)
{
   for (int g = 0; g < NUM_GAMES; g++)
   {
      int numLegalMoves = 0;
      for (int n = 0; n < NUM_MOVES; n++)
      {
         // Call random point generation several times to be able to
         // subtract out that overhead.
         Point p;
         for (int r = 0; r < numRandom; r++)
            p = RandomEmptyPoint(board);

         // Try to execute one move at an empty point. May not be legal
         // due to suicide or board repetition.
         if (board.ExecuteOneMove(p, board.ToPlay()))
            numLegalMoves++;
      }
      for (int i = 0; i < numLegalMoves; i++)
         board.UndoMove();
   }
} // ExecuteRandomGames

void CheckExecuteMovePerformance(GoBoard& board)
{
   // Execute same code with random point generation first called once
   // and then called twice to determine overhead.
   clock_t startTime1 = clock();
   ExecuteRandomGames(board, 1);
   clock_t time1 = clock() - startTime1;

   clock_t startTime2 = clock();
   ExecuteRandomGames(board, 2);
   clock_t time2 = clock() - startTime2;

   // Also counts calls to ExecuteOneMove that turned out to be illegal
   // due to suicide or ko.
   const int totalNumMoves = NUM_GAMES*NUM_MOVES;

   ofstream results("perf.txt", ios::app);
   results << "\nCount     : " << totalNumMoves << " Execute+Undo";
   results << "\nTotal time: " << time1 << " mSec";
   results << "\nOverhead  : " << time2-time1 << " mSec";
   results << "\nSpeed     : " << CLOCKS_PER_SEC*double(totalNumMoves) /
(2*time1-time2)
                               << " Execute+Undo per second";
   results << "\n" << flush;
} // CheckExecuteMovePerformance

Please let me know if you have any questions. I've already gained some
benefit from this exercise: I found out that keeping the bitboards
up-to-date is no longer a significant cost of executing moves, so that is no
longer optional.

On a Pentium II 450 MHz, an average run produces the following result for
SmartGo:

  Count     : 1600000 Execute+Undo
  Total time: 8282 mSec
  Overhead  : 2249 mSec
  Speed     : 265208 Execute+Undo per second

And this is SmartGo's performance on a Pentium III 650 MHz:

  Count     : 1600000 Execute+Undo
  Total time: 4907 mSec
  Overhead  : 1512 mSec
  Speed     : 471281 Execute+Undo per second

Anders Kierulf
www.smartgo.com