Re: [computer-go] Minimax with random evaluations

[Don Dailey <drd@xxxxxxx>]

>From the code you included, I see you don't do this.   But isn't the game
technically over after 2 passes in most rulesets?

I'm doing the same test with alpha/beta right now.  I'm using a 5x5 board
so I can get lots of results quickly.   I'm running with and without the
2 pass rule.

- Don

  


   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/

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