Re: computer-go: random move execution speed

["Phil" <PhilippGarcia@xxxxxxxx>]

Thanks for the benchmark algorithm and code. I implemented it also and have
already found several places which need improvement. For example, I had cell
objects which represented each position on the board. I found that creating,
copying or destroying each of these 361 objects, on 19x19 board, adds an
enormous about of unnecessary overhead. I replaced the objects with a simple
integer array.

Our code looks very similar. Our point class is probably identicial, and the
board class has the same methods. The only key difference is I don't have an
Undo-method, so instead I keep a copy of the board object after each move on
the stack - this means I don't account undos as moves. I also haven't
factored in the random number generator (yet).

Here are my disappointing results:

Board::TimingTests()
---> Playing Random Game
***> 1600000 Moves
***> 191.453 seconds.
***> 8357 moves per second.
***> 1564822 legal moves were made.

I look forward to profiling the rest of my code to improve it. Seems, I have
a ways to go to get up to par with the rest of you.

Here's my implementation of the benchmark algorithm:

void Board::TimingTest()
{
 const int NUM_GAMES = 5000;
 const int NUM_MOVES = 320;
 const int N = BOARDSIZE * BOARDSIZE;

 clock_t start, finish;
 double  duration;

 const int totalNumMoves = NUM_GAMES*NUM_MOVES;
 int numLegalMoves = 0;


 std::cout << "Board::TimingTests()" << std:: endl;
 std::cout << "---> Playing Random Game" << std::endl;
 std::cout << "***> " << totalNumMoves << " Move" << std::endl <<
std::flush;

 Point p;
 Board back[NUM_MOVES];

 start = clock();

 srand((unsigned)time( NULL ) );
// srand(0);

 for (int g = 0; g < NUM_GAMES; g++)
 {
  Board b;
  b.Init();

  for (int n = 0; n < NUM_MOVES; n++)
  {
   // Keep generating random points until we find an empty point.
   do
   {
    int r = rand() % N;

    p.set(r % BOARDSIZE, r / BOARDSIZE); // create point from column and row

   }
   while
    (!b.isEmpty(p));

   // Try to execute one move at an empty point. May not be legal
   // due to suicide or board repetition.
   if (b.DoMove(p,true))
   {
    numLegalMoves++;
    b.Swap();
   }

   back[n] = b;    // keep a copy
  }

 }

 finish = clock();
 duration = (double)(finish - start) / CLOCKS_PER_SEC;

 std::cout << "***> " << duration << " seconds.\n";
 std::cout << "***> " << ((long) (totalNumMoves/duration)) << " moves per
second.\n";
// std::cout << "***> " << duration << " seconds per move.\n";
 std::cout << "***> " << numLegalMoves << " legal moves were made.\n";

 std::cout << std::flush;

}


----- Original Message -----
From: "Anders Kierulf" <anders@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Sent: Wednesday, January 03, 2001 10:57 AM
Subject: computer-go: random move execution speed


> > 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
>
>