Re: [gnugo-devel] bug fixed

[Gunnar Farnebäck]

Alain wrote:
> hmm still it is not very clear for me why B19 dragon is considered
> involved in a semeai near T3, when it is really not the case.

Consider this code:

  for (d1 = 0; d1 < num_dragons; d1++)
    for (k = 0; k < dragon2[d1].neighbors; k++) {
      int apos = DRAGON(d1).origin;
      int bpos = DRAGON(dragon2[d1].adjacent[k]).origin;
      int result_certain;
      
      d2 = dragon[bpos].id;

E.g. when d1=47 there may be a neighbor dragon with id d2=50. If it
turns out to be involved in a semeai, this call

      owl_analyze_semeai(apos, bpos,
                         &(semeai_results_first[d1][d2]), 
                         &(semeai_results_second[d1][d2]),
                         &(semeai_move[d1][d2]), 1, &result_certain);

will index the 2D arrays out of bounds on the second index. The effect
is that [47][50] points to the same address as [48][0]. When the
arrays later are traversed a semeai between dragon 48 and dragon 0
will be found, where the former tends to live in the lower right
corner and the latter in the upper left corner.

> i agree with your analyse, but i dont like exeptions in the code, i prefer a 
> "straightforward" engine which handle correctly all the cases. 
> Because for a newcomer (like me) each exception in the code need a lot of 
> thinking to be understood, and for coder it must be documented ...

Rest assured that this is one aspect of the code we always take into
account. But there are tradeoffs to make with factors like speed,
memory consumption, robustness, language limitations, portability
issues, and so on.

> Even in those rare pathological games (2 bug reports in nearly 2
> years),

Not really pathological, although the crashes are and should be rare.
This kind of game is somewhat common against very weak beginners.
There's no way for GNU Go to win by less than 200 points or so,
however, except by crashing.

> GNUgo behaves well, and is winning. With the
> timing-adaptative level we will have no fear to lose on time,
> because of obscure semeai search (this semeai are quickly solved by
> the engine).

Time is not much of an issue here at all.

> So i vote for coding  MAX_DRAGONS = MAX_WORMS and against introducing an 
> exception for 2 pathological cases. (even if gnugo will lose due to that ;-)

I wouldn't mind using that except that I'm doubtful about the wisdom
of spending 1 MB of stack space (13*(4/5*19*19)^2) for these arrays or
even the 324 kB they can be reduced to by changing type to signed char
(at the cost of some extra code complexity). In fact I'm fairly sure
that the former is not portable enough and I'd rather avoid the latter
as well. Especially since no more than a tiny fraction of the entries
will ever be used at any one time.

I think the cleanest solution is to special case this situation and
disable the semeai analysis for huge numbers of dragons.

/Gunnar