Re: [gnugo-devel] Patch: improve separation of similarly-valued moves

[Paul Pogonyshev]

I wrote:
> Arend Bayer wrote:
> > I actually haven't thought about the problem how hard it would be to 
> > compute the exact move probabilities in our current scheme, but it
> > should be doable. If nothing else, a Monte Carlo-approach would work
> > well enough (i.e. simulating the decision for 1000 gg_rand()s).
> 
> It must be quite simple, as long as we can tweak a new mode into
> engine in which it would _not_ apply random shifts to move values,
> but instead would report the scales of those shifts to the caller.
> I haven't looked at the exact math involved, but I'm sure it can
> be done strictly with theory of probability, not involving any
> statistical methods of probability assessment.

Here we are.

- new function compute_move_probabilities() in `value_moves.c'
- new GTP command `move_probabilities'

It would be nice if anyone made use of this in a test suite.  You
will likely have to implement more GTP commands (or change the one
I added).

Paul



Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.212
diff -u -p -r1.212 liberty.h
--- engine/liberty.h    12 Apr 2004 15:28:22 -0000      1.212
+++ engine/liberty.h    20 Apr 2004 15:33:58 -0000
@@ -396,6 +396,7 @@ void print_all_move_values(void);
 void record_top_move(int move, float val);
 void remove_top_move(int move);
 void scale_randomness(int pos, float scaling);
+void compute_move_probabilities(float probabilities[BOARDMAX]);
 
 void register_good_attack_threat(int move, int target);
 int is_known_good_attack_threat(int move, int target);
Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.121
diff -u -p -r1.121 value_moves.c
--- engine/value_moves.c        12 Apr 2004 15:22:44 -0000      1.121
+++ engine/value_moves.c        20 Apr 2004 15:34:14 -0000
@@ -3482,6 +3482,88 @@ prepare_move_influence_debugging(int pos
   estimate_territorial_value(pos, color, our_score, 1);
 }
 
+
+void
+compute_move_probabilities(float probabilities[BOARDMAX])
+{
+  int k;
+  int pos;
+  int num_moves = 0;
+  int moves[BOARDMAX];
+  double lower_values[BOARDMAX];
+  double upper_values[BOARDMAX];
+  double densities[BOARDMAX];
+  double common_lower_limit = 0.0;
+
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    probabilities[pos] = 0.0;
+
+    if (ON_BOARD(pos)) {
+      /* FIXME: what about point redistribution? */
+      if (move[pos].final_value > 0.0) {
+       double scale = 0.01 * (double) move[pos].randomness_scaling;
+
+       moves[num_moves] = pos;
+       lower_values[num_moves] = ((double) move[pos].final_value
+                                  - (scale * move[pos].random_number));
+       upper_values[num_moves] = lower_values[num_moves] + scale;
+       densities[num_moves] = 1.0 / scale;
+
+       if (lower_values[num_moves] > common_lower_limit)
+         common_lower_limit = lower_values[num_moves];
+
+       num_moves++;
+      }
+    }
+  }
+
+  for (k = 0; k < num_moves; k++) {
+    int i;
+    double lower_limit = common_lower_limit;
+
+    while (lower_limit < upper_values[k]) {
+      int j;
+      double upper_limit = upper_values[k];
+      double span_power;
+      double polynomial[BOARDMAX];
+      int degree;
+
+      degree = 0;
+      polynomial[0] = 1.0;
+
+      for (i = 0; i < num_moves; i++) {
+       if (upper_values[i] > lower_limit && upper_values[i] < upper_limit)
+         upper_limit = upper_values[i];
+      }
+
+      for (i = 0; i < num_moves; i++) {
+       if (i != k && upper_values[i] >= upper_limit) {
+         polynomial[++degree] = 0.0;
+         for (j = degree; j > 0; j--) {
+           polynomial[j] = (densities[i]
+                            * (polynomial[j - 1]
+                               + ((lower_limit - lower_values[i])
+                                  * polynomial[j])));
+         }
+
+         polynomial[0] *= densities[i] * (lower_limit - lower_values[i]);
+       }
+      }
+
+      span_power = 1.0;
+      for (j = 0; j <= degree; j++) {
+       span_power *= upper_limit - lower_limit;
+       probabilities[moves[k]] += (polynomial[j] * span_power) / (j + 1);
+      }
+
+      lower_limit = upper_limit;
+    }
+
+    probabilities[moves[k]] *= densities[k];
+  }
+}
+
+
 /*
  * Local Variables:
  * tab-width: 8
Index: interface/play_gtp.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/play_gtp.c,v
retrieving revision 1.145
diff -u -p -r1.145 play_gtp.c
--- interface/play_gtp.c        12 Apr 2004 15:28:22 -0000      1.145
+++ interface/play_gtp.c        20 Apr 2004 15:34:30 -0000
@@ -134,6 +134,7 @@ DECLARE(gtp_list_commands);
 DECLARE(gtp_list_stones);
 DECLARE(gtp_loadsgf);
 DECLARE(gtp_move_influence);
+DECLARE(gtp_move_probabilities);
 DECLARE(gtp_move_reasons);
 DECLARE(gtp_name);
 DECLARE(gtp_owl_attack);
@@ -272,6 +273,7 @@ static struct gtp_command commands[] = {
   {"list_stones",            gtp_list_stones},
   {"loadsgf",                        gtp_loadsgf},
   {"move_influence",          gtp_move_influence},
+  {"move_probabilities",      gtp_move_probabilities},
   {"move_reasons",            gtp_move_reasons},
   {"name",                    gtp_name},
   {"new_score",               gtp_estimate_score},
@@ -3730,6 +3732,34 @@ gtp_move_influence(char *s)
   prepare_move_influence_debugging(POS(i, j), color);
   
   return print_influence_data(&move_influence, s + n);
+}
+
+
+static int
+gtp_move_probabilities(char *s)
+{
+  float probabilities[BOARDMAX];
+  int pos;
+  int any_moves_printed = 0;
+
+  UNUSED(s);
+
+  compute_move_probabilities(probabilities);
+
+  gtp_start_response(GTP_SUCCESS);
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (ON_BOARD(pos) && probabilities[pos] != 0.0) {
+      gtp_mprintf("%m ", I(pos), J(pos));
+      gtp_printf("%.4f\n", probabilities[pos]);
+      any_moves_printed = 1;
+    }
+  }
+
+  if (!any_moves_printed)
+    gtp_printf("\n");
+  gtp_printf("\n");
+
+  return GTP_OK;
 }