Re: [gnugo-devel] connection reader speed optimization

[Arend Bayer]

Paul wrote:

> Arend wrote:
> > Paul wrote:
> > > However, i have a counter-proposal.  Is it really the intention to have
> > > partial strings in break-in goal array?  Maybe fixing this will give an
> > > improvement in break-in efficiency?  In other words i propose you to
> > > investigate the matter :)

> > I haven't seen an example of this yet, but yes, I need to improve the
> > code in compute_smaller_goal(), for example. (Are you sure this happens
> > without your patch?)
>
> Yes, when i looked into ego:10 (that subnode you pointed out in one of
> the previous messages), unpatched version had distances 0.0 and 0.9 on
> a same string -- this would have been completely impossible if the whole
> string had been in the goal, right?

Ok, then you mean strings as on the board during the break-in reading, not
when the break-in reading is called at the beginning. This will
certainly happen as long as we don't modify the goal during the reading,
which is ) a bigger change, of which I am not quite sure whether it is
worth it. (And it has nothing to do with compute_smaller_goal().)

> And if you look at the code in compute_smaller_goal() (unpatched), you
> can spot at least two places where results for stones of a same string
> can deviate.  Namely, the Manhattan distance calculation and the check
> for the number of neighbors in goal.

Yes, the number of neighbors-check should be disabled for occupied
intersections.

> > But I think it would be easier to do this if we revert your change
> > to the connection queues. For example, you have (inadvertently, I
> > believe) changed the logic in compute_smaller_goal(), and it would be
> > easier to restore (and improve) it in that case.
>
> No, the change was intentional.  As i mentioned above, the Manhattan
> distance stuff seemed bogus to me and i changed it, thus having fixed
> one fail which the patch used to cause on early stages.  Correct me if
> i missed something, but your version heavily depended on stone position
> and therefore could produce different results for stones of a same string.

I think you got mislead here. Yes, it does give different results for
stones of the same string, but only for those string that do not belong
to the goal from start on.

Its purpose is as follows:

..........
...OO.....
.QQ.O.....
...XX.....
..........

Assume Q is the string from which we want to break in. We compute the
goal for the break-in call as the intersection of the territory in which
we want to break in, with the intersections that are "close by" to Q
(i.e. which get added to the connection queue when computing the
distance map from Q).

Relevant is what own_stones_visited yields for the intersections around
the 2nd string:
..........
...OO.....
.QQ.O3....
...XX33...
...233....

We discard the intersections where we get 3 or higher.

This heuristic is extremely crude but was necessary; I should
replace/improve it.


> Basically, we need to clarify one thing: how bad is that break-in code
> puts incomplete strings into goal?  From your replies it seems that this
> is not a "feature".  Then we have two options: either it's a (severe)
> bug, or it was not specifically coded to work this way, but doesn't
> matter much.
It should not matter much.

> And finaly note that the connection reading code itself never needs to
> expand the queue.  Isn't that a well-written code? ;)
Well, instead you are expanding it by hand (in
spread_connection_distances).

But if you want to say that breakin.c is not entirely well-written code,
then I have to agree :)


Arend