[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[gnugo-devel] owl_speedup_1_28.1: constraint cost heuristics
|
From: |
Arend Bayer |
|
Subject: |
[gnugo-devel] owl_speedup_1_28.1: constraint cost heuristics |
|
Date: |
Fri, 8 Mar 2002 15:24:07 -0500 (EST) |
- heuristics to estimate cost of pattern constraint introduced
- constraint cost used in owl callback for speedup
As advertised, this is no. 1 of the speedups I had proposed. The
implementation goes basically along Gunnar's suggestions. The autohelper
functions as listed in mkpat.c now have an extra field that estimates
their time costs. (The values are certainly debatable, but they do not
matter much for know. I used Gunnar's suggestions for now, normalized to 1.00
as the default for a simple attack resp. find_defense call.)
>From these values, mkpat guesses the total cost of the constraint
check; it assumes that the i-th autohelper function appearing in the
constraint will be called with a probability of 0.6^(i-1). This is somewhat
nonsense (e.g. if the constraint reads "(cond1 || cond2 || cond3) && cond4"),
but works good enough and can be improved later if we feel like it. The
constraint check is done before the owl_safe_move check if the total
cost is < 0.45 (this is the only figure that I tried to optimize a bit, but
the changes were pretty small), unless the safe_move test can be done by a
cache lookup.
So a constraint
"lib(a) == 1 && lib(b) == 1 && attack(c)"
will still be evaluated before the safe move check.
The performance improvement is 252m instead of 282m (on a PIII-733 MHz)
for the complete regression set; this is ~10.5%. There were no changed
regressions tests.
However, there was a very small (0.1%) owl node fluctuation for nngs.tst.
I don't have time to look into this in detail in the moment; but this
might well be explained with a persistent reading cache problems.
The patch also includes a small cleanup in owl.c (moving the safe_move_cache
into the local owl data), and adds the node counting to nngs.tst (which
I used for optimization).
I did not implement Gunnar's suggestion to sort owl patterns of equal value
according to their constraint cost. I like this idea but wanted to the
part that does not change any behaviour first.
Arend
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.71
diff -u -r1.71 owl.c
--- engine/owl.c 4 Mar 2002 06:49:08 -0000 1.71
+++ engine/owl.c 8 Mar 2002 19:52:41 -0000
@@ -89,18 +89,10 @@
/* Node limitation. */
int local_owl_node_counter;
-};
-#if PATTERN_CHECK_ON_DEMAND
-/* Cache for owl_safe_move when called from owl_shapes. */
-static int *owl_safe_move_cache_stack;
-/* Cache for owl_safe_move when called for vital attack moves. */
-static int owl_safe_move_cache_size = 0;
-/* Set this before calling owl_shapes_callback or get_next_move_from_list. */
-static int *current_owl_safe_move_cache;
-#endif
+ char safe_move_cache[BOARDMAX];
+};
-static int owl_safe_move_cache[BOARDMAX];
static int result_certain;
/* Statistics. */
@@ -1248,10 +1240,7 @@
&probable_min, &probable_max);
current_owl_data = owl;
- memset(owl_safe_move_cache, 0, sizeof(owl_safe_move_cache));
-#if PATTERN_CHECK_ON_DEMAND
- current_owl_safe_move_cache = owl_safe_move_cache;
-#endif
+ memset(owl->safe_move_cache, 0, sizeof(owl->safe_move_cache));
matches_found = 0;
memset(found_matches, 0, sizeof(found_matches));
@@ -1905,10 +1894,7 @@
&probable_min, &probable_max);
current_owl_data = owl;
- memset(owl_safe_move_cache, 0, sizeof(owl_safe_move_cache));
-#if PATTERN_CHECK_ON_DEMAND
- current_owl_safe_move_cache = owl_safe_move_cache;
-#endif
+ memset(owl->safe_move_cache, 0, sizeof(owl->safe_move_cache));
/* We don't care about the moves, just whether matches are found.
* The content of shape_moves[] will be discarded when we call
@@ -2750,25 +2736,14 @@
moves[k].same_dragon = 2;
}
- /* We must reset the owl_safe_move_cache before starting the
+ /* We must reset the owl safe_move_cache before starting the
* pattern matching. The cache is used by owl_shapes_callback().
*/
+ memset(owl->safe_move_cache, 0, sizeof(owl->safe_move_cache));
#if PATTERN_CHECK_ON_DEMAND
init_pattern_list(pattern_list);
- if (stackp >= owl_safe_move_cache_size) {
- int new_size = gg_max(stackp+1, owl_reading_depth);
- owl_safe_move_cache_stack
- = realloc(owl_safe_move_cache_stack, new_size * BOARDMAX * sizeof(int));
- if (0)
- gprintf("New size for owl safe move cache stack: %d\n", new_size);
- gg_assert(owl_safe_move_cache_stack != NULL);
- owl_safe_move_cache_size = new_size;
- }
- memset(&owl_safe_move_cache_stack[stackp * BOARDMAX],
- 0, BOARDMAX * sizeof(int));
matchpat(collect_owl_shapes_callbacks, color, type, pattern_list, owl->goal);
#else
- memset(owl_safe_move_cache, 0, sizeof(owl_safe_move_cache));
matchpat(owl_shapes_callback, color, type, moves, owl->goal);
#endif
@@ -2790,11 +2765,33 @@
static int
check_pattern_hard(int move, int color, struct pattern *pattern, int ll)
{
+ int constraint_checked = 0;
+ int safe_move_checked = 0;
+
+ /* The very first check is whether we can disregard the pattern due
+ * due to an owl safe_move_cache lookup.
+ */
+ if (! (pattern->class & CLASS_s))
+ if (current_owl_data->safe_move_cache[move]) {
+ if (current_owl_data->safe_move_cache[move] == 1)
+ return 0;
+ else
+ safe_move_checked = 1;
+ }
+
+ /* If the constraint is cheap to check, we do this first. */
+ if ((pattern->autohelper_flag & HAVE_CONSTRAINT)
+ && (pattern->constraint_cost < 0.45)) {
+ if (!pattern->autohelper(pattern, ll, move, color, 0))
+ return 0;
+ constraint_checked = 1;
+ }
+
/* For sacrifice patterns, the survival of the stone to be played is
* not checked. Otherwise we discard moves which can be captured.
* Illegal ko captures are accepted for ko analysis.
*/
- if (! (pattern->class & CLASS_s)) {
+ if ((!(pattern->class & CLASS_s)) && (!safe_move_checked)) {
if (!owl_safe_move(move, color)) {
if (0)
TRACE(" move at %1m wasn't safe, discarded\n", move);
@@ -2823,7 +2820,7 @@
/* If the pattern has a constraint, call the autohelper to see
* if the pattern must be rejected.
*/
- if (pattern->autohelper_flag & HAVE_CONSTRAINT)
+ if (pattern->autohelper_flag & HAVE_CONSTRAINT && (!constraint_checked))
if (!pattern->autohelper(pattern, ll, move, color, 0))
return 0;
return 1;
@@ -2957,9 +2954,6 @@
sgf_dumptree = NULL;
count_variations = 0;
- gg_assert(owl_safe_move_cache_size > stackp);
- current_owl_safe_move_cache = &owl_safe_move_cache_stack[stackp * BOARDMAX];
-
/* The patterns above list->used have already been either discarded or
* used by the calling function.
*/
@@ -4098,14 +4092,6 @@
{
int acode, safe = 0;
-#if PATTERN_CHECK_ON_DEMAND
- if (current_owl_safe_move_cache[move])
- return current_owl_safe_move_cache[move]-1;
-#else
- if (owl_safe_move_cache[move])
- return owl_safe_move_cache[move]-1;
-#endif
-
if (trymove(move, color, "owl_safe_move", 0, EMPTY, 0)) {
acode = attack(move, NULL);
if (acode != WIN)
@@ -4115,11 +4101,7 @@
current_owl_data->lunches_are_current = 0;
popgo();
}
-#if PATTERN_CHECK_ON_DEMAND
- current_owl_safe_move_cache[move] = safe+1;
-#else
- owl_safe_move_cache[move] = safe+1;
-#endif
+ current_owl_data->safe_move_cache[move] = safe+1;
return safe;
}
Index: patterns/mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.60
diff -u -r1.60 mkpat.c
--- patterns/mkpat.c 6 Mar 2002 03:47:40 -0000 1.60
+++ patterns/mkpat.c 8 Mar 2002 19:52:53 -0000
@@ -151,6 +151,7 @@
struct autohelper_func {
const char *name;
int params;
+ float cost;
const char *code;
};
@@ -173,102 +174,128 @@
* by "lib2", "lib3", and "lib4".
*/
static struct autohelper_func autohelper_functions[] = {
- {"lib2", 1, "worm[%s].liberties2"},
- {"lib3", 1, "worm[%s].liberties3"},
- {"lib4", 1, "worm[%s].liberties4"},
- {"goallib", 0, "goallib"},
- {"lib", 1, "countlib(%s)"},
- {"alive", 1, "(dragon[%s].matcher_status == ALIVE)"},
- {"unknown", 1, "(dragon[%s].matcher_status == UNKNOWN)"},
- {"critical", 1, "(dragon[%s].matcher_status == CRITICAL)"},
- {"dead", 1, "(dragon[%s].matcher_status == DEAD)"},
- {"status", 1, "dragon[%s].matcher_status"},
- {"ko", 1, "is_ko_point(%s)"},
- {"xdefend_against", 2, "defend_against(%s,OTHER_COLOR(color),%s)"},
- {"odefend_against", 2, "defend_against(%s,color,%s)"},
- {"defend_against_atari",1,"defend_against_atari_helper(move,%s)"},
- {"does_defend", 2, "does_defend(%s,%s)"},
- {"does_attack", 2, "does_attack(%s,%s)"},
- {"attack", 1, "ATTACK_MACRO(%s)"},
- {"defend", 1, "DEFEND_MACRO(%s)"},
- {"weak", 1, "DRAGON_WEAK(%s)"},
- {"safe_xmove", 1, "safe_move(%s,OTHER_COLOR(color))"},
- {"safe_omove", 1, "safe_move(%s,color)"},
- {"legal_xmove", 1, "is_legal(%s,other)"},
- {"legal_omove", 1, "is_legal(%s,color)"},
- {"x_somewhere", -1, "somewhere(OTHER_COLOR(color), %d"},
- {"o_somewhere", -1, "somewhere(color, %d"},
- {"xmoyo", 1, "(influence_moyo_color(%s) == OTHER_COLOR(color))"},
- {"omoyo", 1, "(influence_moyo_color(%s) == color)"},
- {"xarea", 1, "(influence_area_color(%s) == OTHER_COLOR(color))"},
- {"oarea", 1, "(influence_area_color(%s) == color)"},
- {"xterri", 1, "(influence_territory_color(%s) ==
OTHER_COLOR(color))"},
- {"oterri", 1, "(influence_territory_color(%s) == color)"},
- {"genus", 1, "dragon[%s].genus"},
- {"approx_xlib", 1, "approxlib(%s,OTHER_COLOR(color), MAX_LIBERTIES,
NULL)"},
- {"approx_olib", 1, "approxlib(%s,color, MAX_LIBERTIES, NULL)"},
- {"xlib", 1, "accurate_approxlib(%s,OTHER_COLOR(color),
MAX_LIBERTIES, NULL)"},
- {"olib", 1, "accurate_approxlib(%s,color, MAX_LIBERTIES, NULL)"},
- {"xcut", 1, "cut_possible(%s,OTHER_COLOR(color))"},
- {"ocut", 1, "cut_possible(%s,color)"},
- {"edge_double_sente", 4, "edge_double_sente_helper(%s, %s, %s, %s)"},
- {"xplay_defend_both", -2,
- "play_attack_defend2_n(OTHER_COLOR(color), 0, %d"},
- {"oplay_defend_both", -2, "play_attack_defend2_n(color, 0, %d"},
- {"xplay_attack_either", -2,
- "play_attack_defend2_n(OTHER_COLOR(color), 1, %d"},
- {"oplay_attack_either", -2, "play_attack_defend2_n(color, 1, %d"},
- {"xplay_defend", -1, "play_attack_defend_n(OTHER_COLOR(color), 0, %d"},
- {"oplay_defend", -1, "play_attack_defend_n(color, 0, %d"},
- {"xplay_attack", -1, "play_attack_defend_n(OTHER_COLOR(color), 1, %d"},
- {"oplay_attack", -1, "play_attack_defend_n(color, 1, %d"},
- {"xplay_break_through", -3, "play_break_through_n(OTHER_COLOR(color), %d"},
- {"oplay_break_through", -3, "play_break_through_n(color, %d"},
- {"oplay_connect", -2, "play_connect_n(color, 1, %d"},
- {"xplay_connect", -2, "play_connect_n(OTHER_COLOR(color), 1, %d"},
- {"oplay_disconnect", -2, "play_connect_n(color, 0, %d"},
- {"xplay_disconnect", -2, "play_connect_n(OTHER_COLOR(color), 0, %d"},
- {"seki_helper", 1, "seki_helper(%s)"},
- {"threaten_to_save",1,"threaten_to_save_helper(move,%s)"},
- {"threaten_to_capture",1,"threaten_to_capture_helper(move,%s)"},
- {"not_lunch", 2, "not_lunch_helper(%s,%s)"},
- {"eye", 1, "is_eye_space(%s)"},
- {"proper_eye", 1, "is_proper_eye_space(%s)"},
- {"marginal_eye", 1, "is_marginal_eye_space(%s)"},
- {"halfeye", 1, "is_halfeye(half_eye,%s)"},
- {"max_eye_value", 1, "max_eye_value(%s)"},
- {"owl_topological_eye", 2, "owl_topological_eye(%s,board[%s])"},
- {"obvious_false_oeye", 1, "obvious_false_eye(%s,color)"},
- {"obvious_false_xeye", 1, "obvious_false_eye(%s,OTHER_COLOR(color))"},
- {"antisuji", 1, "add_antisuji_move(%s)"},
- {"add_connect_move",2, "add_connection_move(move,%s,%s)"},
- {"add_cut_move", 2, "add_cut_move(move,%s,%s)"},
-
{"add_attack_either_move",2,"add_either_move(move,ATTACK_STRING,%s,ATTACK_STRING,%s)"},
- {"add_defend_both_move",2,
"add_all_move(move,DEFEND_STRING,%s,DEFEND_STRING,%s)"},
- {"same_dragon", 2, "is_same_dragon(%s,%s)"},
- {"same_string", 2, "same_string(%s,%s)"},
- {"dragonsize", 1, "dragon[%s].size"},
- {"wormsize", 1, "countstones(%s)"},
- {"effective_size", 1, "dragon[%s].effective_size"},
- {"vital_chain", 1, "vital_chain(%s)"},
- {"potential_cutstone",1,"worm[%s].cutstone2>1"},
- {"amalgamate_most_valuable_helper",3,
- "amalgamate_most_valuable_helper(%s,%s,%s)"},
- {"amalgamate", 2, "join_dragons(%s,%s)"},
- {"owl_escape_value",1, "owl_escape_value(%s)"},
- {"owl_goal_dragon", 1, "owl_goal_dragon(%s)"},
- {"owl_eyespace", 2, "owl_eyespace(%s,%s)"},
- {"owl_big_eyespace",2, "owl_big_eyespace(%s,%s)"},
- {"owl_proper_eye", 2, "owl_proper_eye(%s,%s)"},
- {"has_aji",1,"(dragon[%s].owl_threat_status==CAN_THREATEN_DEFENSE)"},
- {"finish_ko_helper",1, "finish_ko_helper(%s)"},
- {"squeeze_ko_helper",1,"squeeze_ko_helper(%s)"},
- {"backfill_helper", 3, "backfill_helper(%s, %s, %s)"},
- {"connect_and_cut_helper", 3, "connect_and_cut_helper(%s, %s, %s)"},
- {"owl_threatens", 2, "owl_threatens_attack(%s,%s)"},
- {"replace", 2, "add_replacement_move(%s,%s)"},
- {"non_oterritory", 1, "influence_mark_non_territory(%s, color)"},
- {"non_xterritory", 1, "influence_mark_non_territory(%s,
OTHER_COLOR(color))"}
+ {"lib2", 1, 0.01, "worm[%s].liberties2"},
+ {"lib3", 1, 0.01, "worm[%s].liberties3"},
+ {"lib4", 1, 0.01, "worm[%s].liberties4"},
+ {"goallib", 0, 0.01, "goallib"},
+ {"lib", 1, 0.01, "countlib(%s)"},
+ {"alive", 1, 0.01,
+ "(dragon[%s].matcher_status == ALIVE)"},
+ {"unknown", 1, 0.01,
+ "(dragon[%s].matcher_status == UNKNOWN)"},
+ {"critical", 1, 0.01,
+ "(dragon[%s].matcher_status == CRITICAL)"},
+ {"dead", 1, 0.01, "(dragon[%s].matcher_status == DEAD)"},
+ {"status", 1, 0.01, "dragon[%s].matcher_status"},
+ {"ko", 1, 0.01, "is_ko_point(%s)"},
+ {"xdefend_against", 2, 1.00,
+ "defend_against(%s,OTHER_COLOR(color),%s)"},
+ {"odefend_against", 2, 1.00, "defend_against(%s,color,%s)"},
+ {"defend_against_atari", 1, 1.00,
+ "defend_against_atari_helper(move,%s)"},
+ {"does_defend", 2, 1.00, "does_defend(%s,%s)"},
+ {"does_attack", 2, 1.00, "does_attack(%s,%s)"},
+ {"attack", 1, 1.00, "ATTACK_MACRO(%s)"},
+ {"defend", 1, 1.00, "DEFEND_MACRO(%s)"},
+ {"weak", 1, 0.01, "DRAGON_WEAK(%s)"},
+ {"safe_xmove", 1, 1.00, "safe_move(%s,OTHER_COLOR(color))"},
+ {"safe_omove", 1, 1.00, "safe_move(%s,color)"},
+ {"legal_xmove", 1, 0.05, "is_legal(%s,other)"},
+ {"legal_omove", 1, 0.05, "is_legal(%s,color)"},
+ {"x_somewhere", -1, 0.01, "somewhere(OTHER_COLOR(color), %d"},
+ {"o_somewhere", -1, 0.01, "somewhere(color, %d"},
+ {"xmoyo", 1, 0.01,
+ "(influence_moyo_color(%s) == OTHER_COLOR(color))"},
+ {"omoyo", 1, 0.01,
+ "(influence_moyo_color(%s) == color)"},
+ {"xarea", 1, 0.01,
+ "(influence_area_color(%s) == OTHER_COLOR(color))"},
+ {"oarea", 1, 0.01, "(influence_area_color(%s) == color)"},
+ {"xterri", 1, 0.01,
+ "(influence_territory_color(%s) == OTHER_COLOR(color))"},
+ {"oterri", 1, 0.01,
+ "(influence_territory_color(%s) == color)"},
+ {"genus", 1, 0.01, "dragon[%s].genus"},
+ {"approx_xlib", 1, 0.03,
+ "approxlib(%s, OTHER_COLOR(color), MAX_LIBERTIES, NULL)"},
+ {"approx_olib", 1, 0.03,
+ "approxlib(%s, color, MAX_LIBERTIES, NULL)"},
+ {"xlib", 1, 0.05,
+ "accurate_approxlib(%s, OTHER_COLOR(color), MAX_LIBERTIES, NULL)"},
+ {"olib", 1, 0.05,
+ "accurate_approxlib(%s,color, MAX_LIBERTIES, NULL)"},
+ {"xcut", 1, 0.01, "cut_possible(%s,OTHER_COLOR(color))"},
+ {"ocut", 1, 0.05, "cut_possible(%s,color)"},
+ {"edge_double_sente", 4, 3.00,
+ "edge_double_sente_helper(%s, %s, %s, %s)"},
+ {"xplay_defend_both", -2, 3.00,
+ "play_attack_defend2_n(OTHER_COLOR(color), 0, %d"},
+ {"oplay_defend_both", -2, 3.00, "play_attack_defend2_n(color, 0, %d"},
+ {"xplay_attack_either", -2, 3.00,
+ "play_attack_defend2_n(OTHER_COLOR(color), 1, %d"},
+ {"oplay_attack_either", -2, 3.00, "play_attack_defend2_n(color, 1, %d"},
+ {"xplay_defend", -1, 1.00,
+ "play_attack_defend_n(OTHER_COLOR(color), 0, %d"},
+ {"oplay_defend", -1, 1.00, "play_attack_defend_n(color, 0, %d"},
+ {"xplay_attack", -1, 1.00,
+ "play_attack_defend_n(OTHER_COLOR(color), 1, %d"},
+ {"oplay_attack", -1, 1.00, "play_attack_defend_n(color, 1, %d"},
+ {"xplay_break_through", -3, 5.00,
+ "play_break_through_n(OTHER_COLOR(color), %d"},
+ {"oplay_break_through", -3, 5.00, "play_break_through_n(color, %d"},
+ {"oplay_connect", -2,10.00, "play_connect_n(color, 1, %d"},
+ {"xplay_connect", -2,10.00,
+ "play_connect_n(OTHER_COLOR(color), 1, %d"},
+ {"oplay_disconnect", -2,10.00, "play_connect_n(color, 0, %d"},
+ {"xplay_disconnect", -2,10.00,
+ "play_connect_n(OTHER_COLOR(color), 0, %d"},
+ {"seki_helper", 1, 0.0, "seki_helper(%s)"},
+ {"threaten_to_save", 1, 0.0, "threaten_to_save_helper(move,%s)"},
+ {"threaten_to_capture", 1, 0.0, "threaten_to_capture_helper(move,%s)"},
+ {"not_lunch", 2, 0.0, "not_lunch_helper(%s,%s)"},
+ {"eye", 1, 0.01, "is_eye_space(%s)"},
+ {"proper_eye", 1, 0.01, "is_proper_eye_space(%s)"},
+ {"marginal_eye", 1, 0.01, "is_marginal_eye_space(%s)"},
+ {"halfeye", 1, 0.01, "is_halfeye(half_eye,%s)"},
+ {"max_eye_value", 1, 0.01, "max_eye_value(%s)"},
+ {"owl_topological_eye", 2, 0.01, "owl_topological_eye(%s,board[%s])"},
+ {"obvious_false_oeye", 1, 0.01, "obvious_false_eye(%s,color)"},
+ {"obvious_false_xeye", 1, 0.01,
+ "obvious_false_eye(%s,OTHER_COLOR(color))"},
+ {"antisuji", 1, 0.0, "add_antisuji_move(%s)"},
+ {"add_connect_move", 2, 0.0, "add_connection_move(move,%s,%s)"},
+ {"add_cut_move", 2, 0.0, "add_cut_move(move,%s,%s)"},
+ {"add_attack_either_move", 2, 0.0,
+ "add_either_move(move,ATTACK_STRING,%s,ATTACK_STRING,%s)"},
+ {"add_defend_both_move", 2, 0.0,
+ "add_all_move(move,DEFEND_STRING,%s,DEFEND_STRING,%s)"},
+ {"same_dragon", 2, 0.01, "is_same_dragon(%s,%s)"},
+ {"same_string", 2, 0.01, "same_string(%s,%s)"},
+ {"dragonsize", 1, 0.01, "dragon[%s].size"},
+ {"wormsize", 1, 0.01, "countstones(%s)"},
+ {"effective_size", 1, 0.01, "dragon[%s].effective_size"},
+ {"vital_chain", 1, 0.05, "vital_chain(%s)"},
+ {"potential_cutstone", 1, 0.01, "worm[%s].cutstone2>1"},
+ {"amalgamate_most_valuable_helper", 3, 0.0,
+ "amalgamate_most_valuable_helper(%s,%s,%s)"},
+ {"amalgamate", 2, 0.0, "join_dragons(%s,%s)"},
+ {"owl_escape_value", 1, 0.01, "owl_escape_value(%s)"},
+ {"owl_goal_dragon", 1, 0.01, "owl_goal_dragon(%s)"},
+ {"owl_eyespace", 2, 0.01, "owl_eyespace(%s,%s)"},
+ {"owl_big_eyespace", 2, 0.01, "owl_big_eyespace(%s,%s)"},
+ {"owl_proper_eye", 2, 0.01, "owl_proper_eye(%s,%s)"},
+ {"has_aji", 1, 0.01,
+ "(dragon[%s].owl_threat_status==CAN_THREATEN_DEFENSE)"},
+ {"finish_ko_helper", 1, 0.05, "finish_ko_helper(%s)"},
+ {"squeeze_ko_helper", 1, 0.03, "squeeze_ko_helper(%s)"},
+ {"backfill_helper", 3, 1.50, "backfill_helper(%s, %s, %s)"},
+ {"connect_and_cut_helper", 3, 3.00, "connect_and_cut_helper(%s, %s, %s)"},
+ {"owl_threatens", 2, 0.01, "owl_threatens_attack(%s,%s)"},
+ {"replace", 2, 0.0, "add_replacement_move(%s,%s)"},
+ {"non_oterritory", 1, 0.0,
+ "influence_mark_non_territory(%s, color)"},
+ {"non_xterritory", 1, 0.0,
+ "influence_mark_non_territory(%s, OTHER_COLOR(color))"}
};
@@ -1163,7 +1190,7 @@
* We use a small state machine.
*/
static void
-parse_constraint_or_action(char *line)
+parse_constraint_or_action(char *line, float *cost)
{
int state = 0;
char *p;
@@ -1172,6 +1199,9 @@
int labels[MAXLABELS];
int N = sizeof(autohelper_functions)/sizeof(struct autohelper_func);
int number_of_params = 0;
+ float cost_factor = 1.0;
+
+ *cost = 0.0;
for (p = line; *p; p++)
{
switch (state) {
@@ -1181,6 +1211,8 @@
strlen(autohelper_functions[n].name)) == 0) {
state = 1;
p += strlen(autohelper_functions[n].name)-1;
+ *cost += autohelper_functions[n].cost * cost_factor;
+ cost_factor *= 0.6;
break;
}
}
@@ -1304,6 +1336,7 @@
finish_constraint_and_action(char *name)
{
unsigned int i;
+ float cost;
int have_constraint = (pattern[patno].autohelper_flag & HAVE_CONSTRAINT);
int have_action = (pattern[patno].autohelper_flag & HAVE_ACTION);
@@ -1353,12 +1386,13 @@
code_pos += sprintf(code_pos, " if (!action)\n ");
if (have_constraint) {
code_pos += sprintf(code_pos, " return ");
- parse_constraint_or_action(constraint);
+ parse_constraint_or_action(constraint, &cost);
+ pattern[patno].constraint_cost = cost;
code_pos += sprintf(code_pos, ";\n");
}
if (have_action) {
code_pos += sprintf(code_pos, " ");
- parse_constraint_or_action(action);
+ parse_constraint_or_action(action, &cost);
code_pos += sprintf(code_pos, ";\n");
code_pos += sprintf(code_pos, "\n return 0;\n");
}
@@ -1984,6 +2018,7 @@
else
fprintf(outfile, "NULL");
fprintf(outfile, ",%d", p->anchored_at_X);
+ fprintf(outfile, ",%f", p->constraint_cost);
#if PROFILE_PATTERNS
fprintf(outfile, ",0,0");
fprintf(outfile, ",0");
@@ -2002,7 +2037,7 @@
#if GRID_OPT
fprintf(outfile, ",{0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0}");
#endif
- fprintf(outfile, ",0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0,NULL,NULL,0");
+ fprintf(outfile, ",0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0,NULL,NULL,0,0.0");
#if PROFILE_PATTERNS
fprintf(outfile, ",0,0");
fprintf(outfile, ",0");
@@ -2198,7 +2233,8 @@
break;
case 7:
case 8:
- finish_constraint_and_action(argv[gg_optind]); /* fall through */
+ finish_constraint_and_action(argv[gg_optind]);
+ /* fall through */
case 0:
case 4:
check_constraint_diagram();
Index: patterns/patterns.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/patterns.h,v
retrieving revision 1.26
diff -u -r1.26 patterns.h
--- patterns/patterns.h 6 Mar 2002 03:47:40 -0000 1.26
+++ patterns/patterns.h 8 Mar 2002 19:52:56 -0000
@@ -252,6 +252,9 @@
/* function, or NULL */
int anchored_at_X; /* 3 if the pattern has 'X' at the anchor posn */
+
+ float constraint_cost; /* mkpat's estimate of the constraint complexity.*/
+
#if PROFILE_PATTERNS
int hits;
int dfa_hits;
Index: regression/nngs.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/nngs.tst,v
retrieving revision 1.13
diff -u -r1.13 nngs.tst
--- regression/nngs.tst 24 Feb 2002 17:40:10 -0000 1.13
+++ regression/nngs.tst 8 Mar 2002 19:52:59 -0000
@@ -933,3 +933,22 @@
loadsgf games/nngs/LordOfPi-gnugo-3.1.20-200201202014.sgf 36
2060 gg_genmove black
#? [C4|C1|F1]
+
+
+
+################## End of Tests #################
+# Report number of nodes visited by the tactical reading
+10000 get_reading_node_counter
+#? [0]&
+
+# Report number of nodes visited by the owl code
+10001 get_owl_node_counter
+#? [0]&
+
+# Report number of nodes visited by the life code
+10002 get_life_node_counter
+#? [0]&
+
+# Report number of trymoves/trykos visited by the test
+10003 get_trymove_counter
+#? [0]&
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [gnugo-devel] owl_speedup_1_28.1: constraint cost heuristics,
Arend Bayer <=