[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] 9x9 opening stats against humans
|
From: |
Douglas Ridgway |
|
Subject: |
Re: [gnugo-devel] 9x9 opening stats against humans |
|
Date: |
Thu, 19 Aug 2004 18:31:23 -0600 (MDT) |
On Tue, 29 Jun 2004, I wrote:
> [stuff about GnuGo's KGS results from May 2004]
I've added June and July, and even patched examine_fuseki to automate
this.
> GnuGo as Black won 54% overall. By opening move this breaks down as
>
> 5-5: 12 - 9, 57%
> 3-3: 10 - 7, 59%
> 3-4: 4 - 9, 31%
> 4-4: 4 - 2, 67%
> 4-5: 3 - 1, 75%
> 3-5: missing
>
>From May through July, GnuGo played 139 games as Black, winning 50.4%
overall:
3-3: 17/46, 37%, dchisquare = 2.8
5-5: 24/38, 63%, 2.0
3-4: 14/35, 40%, 1.1
4-4: 8/12, 67%, 0.7
4-5: 7/8, 88%, 3.1
3-5: 0
Total chisquare: 9.7, differences are significant (p < 0.05). dchisquare
shows how much of the statistical significance is due to each move.
> The differences by opening move look substantial, but there aren't enough
> games to be statistically significant. Still, the relative success with
> 3-3 and failure with 3-4 seems surprising to me -- I'd have thought 3-3 to
> be mediocre, and 3-4 solid.
3-3 now looks bad, and there are (just barely) enough games to reach
significance.
> GnuGo as white won 60% overall, doing best against a 3-3 opening, worst
> against 4-4. The differences between black opening moves is significant,
> but the differences in responses, though sometimes substantial (why a 3-3
> invasion of 4-4 opening on 9x9?), do not reach significance.
GnuGo played 2551 games as White, winning 57% overall, with the breakdown
roughly similar to what I wrote before. No set of GG responses to any
position reach significance, but some particular responses stand out:
* 5-5 response to 3-3 is mediocre, 60% vs 74% overall, dchisq = 7.0
* 5-5 response to 4-4 looks good, 53% vs 39% overall, dchisq = 3.7
There are lots of significant differences among Black moves, for anyone
trying to play or tune against GnuGo.
WRT move weighting, Gunnar pointed out that unpredictability is maximized
not by equal weighting, but by whatever keeps us in the opening database
the longest, ie. weighting by popularity in the training set. (Exactly
what's currently done.)
One way to tune weights would be to rescale weights of patterns with
significant differences to give most of the weight (90%, say) to moves
which are better than average, and the rest to moves which are worse. So
for the opening, 5-5, 4-4, and 5-4 would get most of the weight, and 3-3,
and 3-4 would be deweighted. 5-3 is currently excluded by the "never play
unpopular moves" rule in the fuseki code. Perhaps it makes sense to get
rid of that and throw 5-3 in with the reasonable set. Below is a patch
which does this. This may be too heavy on 5-5 and 4-4, though.
I also include my examine_fuseki patch, although it doesn't really belong
in the code as-is.
19x19 should be interesting as well.
doug.
----
Index: patterns/fuseki9.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/fuseki9.db,v
retrieving revision 1.9
diff -u -r1.9 fuseki9.db
--- patterns/fuseki9.db 3 Mar 2004 22:14:12 -0000 1.9
+++ patterns/fuseki9.db 20 Aug 2004 00:15:39 -0000
@@ -43,6 +43,7 @@
attribute_map value_only
+# opening rescaled to move 90% at 5-5, 4-4, 4-5, 3-5, 10% at 3-3, 3-4
Pattern Fuseki1
# 504/1625
@@ -59,7 +60,7 @@
|.........|
+---------+
-:8,-,value(504)
+:8,-,value(948)
Pattern Fuseki2
@@ -77,7 +78,7 @@
|.........|
+---------+
-:8,-,value(461)
+:8,-,value(88)
Pattern Fuseki3
@@ -95,7 +96,7 @@
|.........|
+---------+
-:8,-,value(363)
+:8,-,value(69)
Pattern Fuseki4
@@ -113,7 +114,7 @@
|.........|
+---------+
-:8,-,value(202)
+:8,-,value(380)
Pattern Fuseki5
@@ -131,7 +132,7 @@
|.........|
+---------+
-:8,-,value(33)
+:8,-,value(62)
Pattern Fuseki6
@@ -149,7 +150,7 @@
|.........|
+---------+
-:8,-,value(16)
+:8,-,value(30)
# Pattern Fuseki7
Index: engine/fuseki.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/fuseki.c,v
retrieving revision 1.22
diff -u -w -u -r1.22 fuseki.c
--- engine/fuseki.c 24 Jan 2004 04:04:56 -0000 1.22
+++ engine/fuseki.c 20 Aug 2004 00:23:16 -0000
@@ -300,12 +300,9 @@
return 0;
/* Choose randomly with respect to relative weights for matched moves. */
- /* Do not choose moves with less value than 20% of the best move */
best_fuseki_value = fuseki_value[0];
q = gg_rand() % fuseki_total_value;
for (k = 0; k < num_fuseki_moves; k++) {
- if (fuseki_value[k] < (best_fuseki_value / 5))
- break;
q -= fuseki_value[k];
if (q < 0)
break;
Index: patterns/extract_fuseki.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/extract_fuseki.c,v
retrieving revision 1.23
diff -u -w -u -r1.23 extract_fuseki.c
--- patterns/extract_fuseki.c 25 May 2004 03:14:03 -0000 1.23
+++ patterns/extract_fuseki.c 20 Aug 2004 00:27:46 -0000
@@ -69,6 +69,7 @@
#include <stdio.h>
#include <string.h>
#include <limits.h>
+#include <math.h>
#include "liberty.h"
#include "gg_utils.h"
#include "random.h"
@@ -112,6 +113,9 @@
/* The number of games that could not be used for some reason. */
int *unused_games;
+/* Warn about unused games */
+#define WARN 1
+
/* Dynamically allocated list of sgf file names. */
char **sgf_names;
@@ -141,6 +145,7 @@
struct situation {
struct invariant_hash pre;
struct invariant_hash post;
+ int outcome;
};
/* Dynamically allocated table of situations encountered in the analysis. */
@@ -153,6 +158,7 @@
struct frequency {
int index;
int n;
+ int n_win;
};
/* Position frequency table. */
@@ -166,6 +172,8 @@
int index;
int position_frequency;
int move_frequency;
+ int position_success;
+ int move_success;
char pattern[MAX_BOARD][MAX_BOARD];
};
@@ -173,6 +181,13 @@
struct winner *winning_moves;
int number_of_winning_moves;
+/* critical values of chisquare distribution with n degrees of freedom */
+/* p < 0.05 */
+double chisquarecrit05[] = {3.8415, 5.9915, 7.8147, 9.4877, 11.0705, 12.5916,
14.0671, 15.5073, 16.9190, 18.3070, 19.6751, 21.0261, 22.3620, 23.6848,
24.9958, 26.2962, 27.5871, 28.8693, 30.1435, 31.4104};
+
+/* p < 0.10, should be same size as 05 */
+double chisquarecrit10[] = {2.7055, 4.6052, 6.2514, 7.7794, 9.2364, 10.6446,
12.0170, 13.3616, 14.6837, 15.9872, 17.2750, 18.5493, 19.8119, 21.0641,
22.3071, 23.5418, 24.7690, 25.9894, 27.2036, 28.4120};
+
/*
* Write the files that are sorted to a specific file
*/
@@ -423,10 +438,11 @@
/* Add a situation to the situation_table array. */
static void
-add_situation(struct invariant_hash *pre, struct invariant_hash *post)
+add_situation(struct invariant_hash *pre, struct invariant_hash *post, int
outcome)
{
situation_table[number_of_situations].pre = *pre;
situation_table[number_of_situations].post = *post;
+ situation_table[number_of_situations].outcome = outcome;
number_of_situations++;
}
@@ -616,12 +632,12 @@
}
/* Play through the initial moves of a game. If 'collect_statistics'
- * is one, store all encounterd situations in the situation_table
- * array. Otherwise, see if there are any winners among the situations
+ * is set, store all encountered situations in the situation_table
+ * array. 'collect_statistics' will be set to the color which won the
+ * game. Otherwise, see if there are any winners among the situations
* and store the corresponding pattern so that it can subsequently be
* printed. Return 0 if there was some problem with the game record,
- * e.g. fewer moves than expected.
- */
+ * e.g. fewer moves than expected. */
static int
examine_game(SGFNode *sgf, int collect_statistics)
{
@@ -649,8 +665,8 @@
gg_assert(m >= 0 && m < board_size && n >= 0 && n <= board_size);
hash_board(&prehash, color);
hash_board_and_move(&posthash, color, m, n);
- if (collect_statistics)
- add_situation(&prehash, &posthash);
+ if (collect_statistics != EMPTY)
+ add_situation(&prehash, &posthash, collect_statistics == color);
else
store_pattern_if_winner(&prehash, &posthash, color, m, n);
play_move(POS(m, n), color);
@@ -733,15 +749,15 @@
sgf = readsgffilefuseki(sgf_names[k], 0);
if (!sgf) {
- if (0)
+ if (WARN)
fprintf(stderr, "Warning: Couldn't open sgf file %s.\n", sgf_names[k]);
unused_games[k] = 1; /* the game could not be used */
continue;
}
else if (!sgfGetIntProperty(sgf, "SZ", &size) || size != board_size) {
- if (0)
- fprintf(stderr, "Warning: wrong size of board %d.\n", size);
+ if (WARN)
+ fprintf(stderr, "Warning: wrong size of board %d in sgf file %s.\n",
size, sgf_names[k]);
unused_games[k] = 1; /* the game could not be used */
continue; /* Board of wrong size, ignore the game. */
}
@@ -749,8 +765,8 @@
/* No handicap games */
else if (handicap_value == 0) {
if (sgfGetIntProperty(sgf, "HA", &handicap) && handicap > 1) {
- if (0)
- fprintf(stderr, "No handicap games allowed %d\n", handicap);
+ if (WARN)
+ fprintf(stderr, "No handicap games allowed, sgf file %s has handicap
%d\n", sgf_names[k], handicap);
unused_games[k] = 1; /* the game could not be used */
continue;
}
@@ -759,16 +775,16 @@
/* Only handicap games */
else if (handicap_value > 1) {
if (!sgfGetIntProperty(sgf, "HA", &handicap)) {
- if (0)
- fprintf(stderr, "Not a handicap game %d\n", handicap);
+ if (WARN)
+ fprintf(stderr, "Sgf file %s is not a handicap game\n", sgf_names[k]);
unused_games[k] = 1; /* the game could not be used */
continue;
}
/* only specific handicap games */
else if (handicap_value != 10 && handicap != handicap_value) {
- if (0)
- fprintf(stderr, "Wrong number of handicap stones %d\n", handicap);
+ if (WARN)
+ fprintf(stderr, "Sgf file %s has wrong number of handicap stones
%d\n", sgf_names[k], handicap);
unused_games[k] = 1; /* the game could not be used */
continue;
}
@@ -779,8 +795,8 @@
* with minimum player strength
*/
if (sgfGetCharProperty(sgf, "BR", &BR) && !enough_strength(BR)) {
- if (0)
- fprintf(stderr, "Wrong strength: %s.\n", BR);
+ if (WARN)
+ fprintf(stderr, "Wrong black strength %s in sgf file %s\n", BR,
sgf_names[k]);
unused_games[k] = 1; /* the game could not be used */
continue;
}
@@ -788,8 +804,8 @@
/* examine strength of players in the game and compare it with
* minimum player strength */
else if (sgfGetCharProperty(sgf, "WR", &WR) && !enough_strength(WR)) {
- if (0)
- fprintf(stderr, "Wrong strength: %s.\n", WR);
+ if (WARN)
+ fprintf(stderr, "Wrong white strength %s in sgf file %s\n", WR,
sgf_names[k]);
unused_games[k] = 1; /* the game could not be used */
continue;
}
@@ -811,6 +827,8 @@
int handicap;
char *WR; /* white rank */
char *BR; /* black rank */
+ char *RE; /* game result */
+ int winner; /* who won the game in question */
init_situations();
for (k = 0; k < number_of_games; k++) {
@@ -824,14 +842,14 @@
sgf = readsgffilefuseki(sgf_names[k], moves_per_game);
if (!sgf) {
- if (0)
+ if (WARN)
fprintf(stderr, "Warning: Couldn't open sgf file %s.\n", sgf_names[k]);
unused_games[k] = 1; /* the game could not be used */
continue;
}
else if (!sgfGetIntProperty(sgf, "SZ", &size) || size != board_size) {
- if (0)
+ if (WARN)
fprintf(stderr, "Warning: wrong size of board %d.\n", size);
unused_games[k] = 1; /* the game could not be used */
continue; /* Board of wrong size, ignore the game. */
@@ -840,7 +858,7 @@
/* No handicap games */
else if (handicap_value == 0) {
if (sgfGetIntProperty(sgf, "HA", &handicap) && handicap > 1) {
- if (0)
+ if (WARN)
fprintf(stderr, "No handicap games allowed %d\n", handicap);
unused_games[k] = 1; /* the game could not be used */
continue;
@@ -850,7 +868,7 @@
/* Only handicap games */
else if (handicap_value > 1) {
if (!sgfGetIntProperty(sgf, "HA", &handicap)) {
- if (0)
+ if (WARN)
fprintf(stderr, "Not a handicap game %d\n", handicap);
unused_games[k] = 1; /* the game could not be used */
continue;
@@ -858,7 +876,7 @@
/* only specific handicap games */
else if (handicap_value != 10 && handicap != handicap_value) {
- if (0)
+ if (WARN)
fprintf(stderr, "Wrong number of handicap stones %d\n", handicap);
unused_games[k] = 1; /* the game could not be used */
continue;
@@ -868,7 +886,7 @@
/* examine strength of players in the game and compare it with
* minimum player strength */
if (sgfGetCharProperty(sgf, "BR", &BR) && !enough_strength(BR)) {
- if (0)
+ if (WARN)
fprintf(stderr, "Wrong strength: %s.\n", BR);
unused_games[k] = 1; /* the game could not be used */
continue;
@@ -876,14 +894,31 @@
/* examine strength of players in the game and compare it with
* minimum player strength */
else if (sgfGetCharProperty(sgf, "WR", &WR) && !enough_strength(WR)) {
- if (0)
+ if (WARN)
fprintf(stderr, "Wrong strength: %s.\n", WR);
unused_games[k] = 1; /* the game could not be used */
continue;
}
- if (!examine_game(sgf, 1)) {
- if (0)
+ /* must have result */
+ if (!sgfGetCharProperty(sgf, "RE", &RE)) {
+ if (WARN)
+ fprintf(stderr, "No result\n");
+ unused_games[k] = 1; /* the game could not be used */
+ continue;
+ }
+ if (strncmp(RE, "B+", 2)==0 ) {
+ winner = BLACK;
+ } else if (strncmp(RE, "W+", 2)==0 ) {
+ winner = WHITE;
+ } else {
+ if (WARN)
+ fprintf(stderr, "No winner in result %s\n", RE);
+ unused_games[k] = 1; /* the game could not be used */
+ continue;
+ }
+ if (!examine_game(sgf, winner)) {
+ if (WARN)
fprintf(stderr, "Warning: Problem with sgf file %s.\n", sgf_names[k]);
unused_games[k] = 1; /* the game could not be used */
}
@@ -932,9 +967,12 @@
&situation_table[k-1]) != 0) {
frequency_table[number_of_distinct_positions].index = k;
frequency_table[number_of_distinct_positions].n = 0;
+ frequency_table[number_of_distinct_positions].n_win = 0;
number_of_distinct_positions++;
}
frequency_table[number_of_distinct_positions-1].n++;
+ frequency_table[number_of_distinct_positions-1].n_win +=
situation_table[k].outcome;
+
}
/* Sort the frequency table, in falling order. */
@@ -980,9 +1018,11 @@
&situation_table[i-1]) != 0) {
move_frequencies[number_of_moves].index = i;
move_frequencies[number_of_moves].n = 0;
+ move_frequencies[number_of_moves].n_win = 0;
number_of_moves++;
}
move_frequencies[number_of_moves-1].n++;
+ move_frequencies[number_of_moves-1].n_win += situation_table[i].outcome;
}
/* Sort the moves, in falling order. */
@@ -1000,6 +1040,7 @@
/* Add the moves to the list of winners. */
for (i = 0; i < number_of_moves; i++) {
/* This is where the cut-off of moves is decided */
+ if (0) {
if (10 * move_frequencies[i].n < move_frequencies[0].n
&& move_frequencies[i].n < 10)
break;
@@ -1007,11 +1048,15 @@
if (move_frequencies[i].n < 2)
break;
+ }
+
winning_moves[number_of_winning_moves].index = move_frequencies[i].index;
winning_moves[number_of_winning_moves].position_frequency =
frequency_table[k].n;
winning_moves[number_of_winning_moves].move_frequency =
move_frequencies[i].n;
+ winning_moves[number_of_winning_moves].position_success =
frequency_table[k].n_win;
+ winning_moves[number_of_winning_moves].move_success =
move_frequencies[i].n_win;
number_of_winning_moves++;
if (number_of_winning_moves == patterns_to_extract)
@@ -1074,15 +1119,67 @@
{
int k, l;
int m, n;
+ double chisq = 0.0;
+ int df = 0;
+ unsigned int pre = situation_table[winning_moves[0].index].pre.values[0];
l = 1;
for (k = 0; k < number_of_winning_moves; k++) {
/* do not print errornous patterns */
if (winning_moves[k].pattern[0][0] != '\0') {
+ double grand_sum = winning_moves[k].position_frequency;
+ double grand_wins = winning_moves[k].position_success;
+ double grand_losses = grand_sum - grand_wins;
+ double row_sum = winning_moves[k].move_frequency;
+ double wins = winning_moves[k].move_success;
+ double losses = row_sum - wins;
+ double expect_wins = row_sum*grand_wins/grand_sum;
+ double expect_losses = row_sum - expect_wins;
+ /* we're using a Yates corrected chisquare */
+ double dchisq = 0.0;
+
+ if (expect_wins > 0.0) dchisq += pow(gg_abs(wins -
expect_wins)-0.5,2)/expect_wins;
+ if (expect_losses > 0.0) dchisq +=
pow(gg_abs(losses-expect_losses)-0.5, 2)/expect_losses;
+
+ /* did we just finish a set? If so, print totals and reset */
+ if (situation_table[winning_moves[k].index].pre.values[0] != pre) {
+ /* p-value is 1- incomplete gamma function(d.o.f/2, chisq/2) */
+ /* df is number of moves, actual d.o.f is df-1 */
+ printf("\n### Summary of pattern pre 0x%08x\n### Chisquare, df: %g, %d
", pre, chisq, df-1);
+ /* and array is indexed at zero for d.o.f = 1... */
+ if (df-1 < 1) {
+ printf("NS\n\n");
+ } else if (df-1 < sizeof(chisquarecrit05)/sizeof(double) && chisq >
chisquarecrit05[df-2]) {
+ printf("!!! p < 0.05\n\n");
+ } else if (df-1 < sizeof(chisquarecrit10)/sizeof(double) && chisq >
chisquarecrit10[df-2]) {
+ printf("??? p < 0.10\n\n");
+ } else if (!(df-1 < sizeof(chisquarecrit05)/sizeof(double))) {
+ printf("df out of range...\n\n");
+ } else {
+ printf("NS\n\n");
+ }
+ pre = situation_table[winning_moves[k].index].pre.values[0];
+ chisq = 0.0;
+ df = 0;
+ }
+ /* increment totals */
+ chisq += dchisq;
+ df++;
+
printf("Pattern Fuseki%d\n", l);
- printf("# %d/%d\n\n",
+ printf("# pre : 0x%08x\n",
situation_table[winning_moves[k].index].pre.values[0]);
+ printf("# post: 0x%08x\n",
situation_table[winning_moves[k].index].post.values[0]);
+ printf("# frequency: %d/%d\n",
winning_moves[k].move_frequency,
winning_moves[k].position_frequency);
+ printf("# wins: %d/%d\n\n",
+ winning_moves[k].move_success,
+ winning_moves[k].position_success);
+ printf("# success: %.1f%% vs %.1f%% for this position overall, dchisq =
%g\n\n",
+ 100.0*winning_moves[k].move_success /
winning_moves[k].move_frequency,
+ 100.0*winning_moves[k].position_success /
winning_moves[k].position_frequency, dchisq);
+
+
printf("+");
for (n = 0; n < board_size; n++) {
printf("-");
@@ -1107,6 +1204,10 @@
printf("+");
printf("\n\n:8,-,value(%d)\n\n\n", winning_moves[k].move_frequency);
l++;
+ } else {
+ fprintf(stderr, "Skipping pattern pre 0x%08x post 0x%08x, stats may be
wrong...\n",
+ situation_table[winning_moves[k].index].pre.values[0],
+ situation_table[winning_moves[k].index].post.values[0]);
}
}
}
- Re: [gnugo-devel] 9x9 opening stats against humans,
Douglas Ridgway <=