Re: [computer-go] Minimax with random evaluations

[Don Dailey <drd@xxxxxxx>]

What does the search do when there are 2 passes in a row?   I assume
you return a random score?

- Don



   > But why speculate when it can be tested?

   Below is a straightforward implementation with absolutely no
   optimizations or other tricks, not even alpha-beta. It does not play
   suicide or immediate ko recapture, but all other empty vertices plus
   pass are considered. At depth 0 it chooses randomly among those moves
   with uniform distribution.

   You can see the results on 9x9 for different depths compared to the
   Brown algorithm (random play but no premature passes or filling in of
   one-point eyes) at the bottom of the list at
   http://www.lysator.liu.se/~gunnar/gtp/random_go_challenge.html

   Current mean handicaps are:

   Depth 2:  -5.36
   Depth 3:  -5.72
   Depth 0: -11.65
   Depth 1: -13.28

   I think this makes sense. Odd depths, in particular 1, are disfavored
   by Antti's observation that capturing multiple stones gives the
   opponent more moves to choose from, while increasing the depth by 2
   improves the chances to make and keep small eyes.

   You're welcome to check that the implementation looks correct. Pass is
   represented by the coordinates (-1, -1). The board logic (omitted) is
   from the Brown sources and the random number generator (also omitted)
   is from GNU Go.

   /Gunnar

   static unsigned int
   evaluate(int i, int j, int color, int maximize, int remaining_depth)
   {
     int best_score;
     int ai, aj;
     struct boardstate state;
     int other = OTHER_COLOR(color);

     if (remaining_depth == 0)
       return gg_urand();

     store_board(&state);
     play_move(i, j, color);

     best_score = evaluate(-1, -1, other, !maximize, remaining_depth - 1);

     for (ai = 0; ai < board_size; ai++)
       for (aj = 0; aj < board_size; aj++) {
	 if (legal_move(ai, aj, other)
	     && !suicide(ai, aj, other)) {
	   unsigned int score = evaluate(ai, aj, other, !maximize,
					 remaining_depth - 1);
	   if (maximize && score > best_score)
	     best_score = score;
	   else if (!maximize && score < best_score)
	     best_score = score;
	 }
       }

     restore_board(&state);

     return best_score;
   }

   void
   generate_move(int *i, int *j, int color)
   {
     int ai, aj;
     unsigned int best_score = evaluate(-1, -1, color, 0, depth);
     *i = -1;
     *j = -1;

     for (ai = 0; ai < board_size; ai++)
       for (aj = 0; aj < board_size; aj++) {
	 if (legal_move(ai, aj, color)
	     && !suicide(ai, aj, color)) {
	   int score = evaluate(ai, aj, color, 0, depth);
	   if (score > best_score) {
	     best_score = score;
	     *i = ai;
	     *j = aj;
	   }
	 }
       }
   }

   _______________________________________________
   computer-go mailing list
   computer-go@xxxxxxxxxxxxxxxxx
   http://www.computer-go.org/mailman/listinfo/computer-go/

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/