[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] Patch: improve separation of similarly-valued moves
From: |
Paul Pogonyshev |
Subject: |
Re: [gnugo-devel] Patch: improve separation of similarly-valued moves |
Date: |
Tue, 20 Apr 2004 18:41:34 +0300 |
User-agent: |
KMail/1.6.51 |
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;
}
- [gnugo-devel] Patch: improve separation of similarly-valued moves, Inge Wallin, 2004/04/14
- Re: [gnugo-devel] Patch: improve separation of similarly-valued moves, Evan Daniel, 2004/04/20
- Re: [gnugo-devel] Patch: improve separation of similarly-valued moves, Paul Pogonyshev, 2004/04/21
- Re: [gnugo-devel] Patch: improve separation of similarly-valued moves, Gunnar Farnebäck, 2004/04/21
- Re: [gnugo-devel] Patch: improve separation of similarly-valued moves, Evan Daniel, 2004/04/21
Re: [gnugo-devel] Patch: improve separation of similarly-valued moves, Gunnar Farneback, 2004/04/14