[computer-go] Minimax with random evaluations

[Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxx>]

I wrote:
> Otherwise, assuming at least one-stone suicide to be illegal, I would
> expect minimax over random evaluations to favor forming small eyes
> and, more crucially, not filling in small eyes. This is probably a
> significant advantage over a pure random player, although still way
> below measurable strength by human standards. If nothing else it
> should improve the chances of getting a game against itself to finish
> in some kind of reasonably settled state.
> 
> 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/