[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Symmetry corrections (was: RE: [gnugo-devel] code maintenance pat ch
From: |
Gunnar Farneback |
Subject: |
Re: Symmetry corrections (was: RE: [gnugo-devel] code maintenance pat ch) |
Date: |
Thu, 03 Oct 2002 21:41:38 +0200 |
User-agent: |
EMH/1.14.1 SEMI/1.14.3 (Ushinoya) FLIM/1.14.2 (Yagi-Nishiguchi) APEL/10.3 Emacs/20.7 (sparc-sun-solaris2.7) (with unibyte mode) |
Arend wrote:
> This explanation isn't 100% accurate. The matching order doesn't change
> (the DFA doesn't know about symmetries of patterns) in this case.
Huh? Somehow the matcher has to come up with a match for the pattern
at only one rotation instead of two. Why couldn't this affect the
matching order?
> I am pointing this out because I think I should change that. (I just
> looked at the function again and realized _how bad_ the algorithm is
> in this respect.) It is annoying when adding a new pattern to have to
> filter out the real change in owl results from this random noise. Changing
> this function a little could at least reduce the noise.
Something like this (untested) patch?
/Gunnar
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.107
diff -u -r1.107 owl.c
--- engine/owl.c 26 Sep 2002 20:04:36 -0000 1.107
+++ engine/owl.c 3 Oct 2002 19:32:57 -0000
@@ -2870,6 +2870,11 @@
* pattern; then it is checked whether this move has not been tried before,
* and if the pattern constraint is valid. This is repeated until enough
* moves are found or the end of the list is reached.
+ *
+ * When two patterns have the same value, the address of the pattern
+ * is used for a secondary comparison. This is entirely arbitrary but
+ * improves the stability of the sorting, giving more predictable
+ * results.
*/
static int
@@ -2878,6 +2883,7 @@
{
int top, bottom;
float top_val;
+ struct pattern *top_pattern;
int k;
int i;
int move;
@@ -2897,14 +2903,18 @@
* by a value cutoff.
*/
top_val = list->pattern_list[top].pattern->value;
+ top_pattern = list->pattern_list[top].pattern;
if (top >= list->ordered_up_to) {
/* One bubble sort iteration. */
for (bottom = list->counter-1; bottom > top; bottom--)
- if (list->pattern_list[bottom].pattern->value > top_val) {
+ if (list->pattern_list[bottom].pattern->value > top_val
+ || (list->pattern_list[bottom].pattern->value == top_val
+ && list->pattern_list[bottom].pattern > top_pattern)) {
matched_pattern = list->pattern_list[bottom];
list->pattern_list[bottom] = list->pattern_list[top];
list->pattern_list[top] = matched_pattern;
top_val = list->pattern_list[top].pattern->value;
+ top_pattern = list->pattern_list[top].pattern;
}
list->ordered_up_to++;
}
- Re: Symmetry corrections (was: RE: [gnugo-devel] code maintenance pat ch),
Gunnar Farneback <=