Re: [gnugo-devel] connection reader speed optimization

[Paul Pogonyshev]

Arend wrote:
> 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().)

Ok, then it's my fault.  But then i don't understand why you don't update the
goal.  For instance, owl always does and making it not update the goal would
lead to terrible results.  Isn't it the same for break-in?

> > > 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.

But what when a position is included in the queue because connection
distance was spread onto it from a stone?  Then the own_stones_visited[]
value for a position _does_ depend on what stone was used to spread
the distance from.  In other words, you get different values around
different parts of a same string, which looks wrong.

> > 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.

Hmm.  You should know better, but to me a jump of 0.9 in connection distance
on a same string looks like it might have severe consequences (and i don't
feel they are any good).

> > 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).

Hey, the old code does this expansion at every ENQUEUE() macro called on
a stone, so the expansion in spread_connection_distance() doesn't count as
new in the patch.

Paul