Re: [gnugo-devel] Crash report for OS X Segmentation fault

[Dave Denholm]

Gunnar Farneback <address@hidden> writes:

> Dave wrote:
> > Incidentally, just noticed that matchpat is still 2d. There's
> > a small speedup available by mapping to 1d as part of the
> > transorm to rotate the pattern.
> > [...]
> > and so we just tabulate these 8 vectors, one for each rotation.
> > And that halves the work required to perform each rotation.
> 
> Yes, but there's a complication at line 500 of matchpat.c:
> 
>         TRANSFORM(pattern->mini, pattern->minj, &mi, &mj, ll);
>         TRANSFORM(pattern->maxi, pattern->maxj, &xi, &xj, ll);
>           [...]
>         /* now do the range-check */
>         if (!ON_BOARD2(m+mi, n+mj) || !ON_BOARD2(m+xi, n+xj))
>           continue;  /* out of range */
> 
> We can't do the range-check in 1D since we have lost too much
> information. Still I guess it would make sence to split the TRANSFORM


Yes, I saw that : thought I'd mentioned it, but maybe not.


Perhaps it's slightly more efficient to

  TRANSFORM(pattern->mini, pattern->minj, &mi, &mj, ll);
  if (!ON_BOARD2(m+mi, n+mj)
    continue;

  TRANSFORM(pattern->maxi, pattern->maxj, &xi, &xj, ll);
  if (!ON_BOARD2(m+xi, n+xj)
    continue;

so that the second transform is skipped if the first one fails.



> macro into a TRANSFORM1 and TRANSFORM2 producing a 1D or 2D result,
> and use TRANSFORM1 wherever we don't need the 2D coordinates.


yup - and if TRANSFORM2() is needed only to do the
min/max checking, we wouldn't actually need the 2d copy of
the board.


> 
> > ( I don't know if the pattern matcher is a performance problem
> >   at the moment
> > )
> 
> Yes, it is.



There may be another way of doing the min/max checks, but it
requires quite a lot more data per pattern.

What I'm thinking of is a horizonal and vertical bitmask for
each rotation of each pattern. Or maybe better would be
a separate table of data, and then each pattern contains
which entry in that table to use.

Anyway, what I'm thinking is the bitmask represents which
intersections are required by the pattern. Then as part of
the matcher setup, it computes a one-off bitmask to say
which parts are off the board. Then the test is to
shift the pattern's mask and compare (&) with the precalculated
mask. If any bits are set, the shifted pattern has fallen off
the board.

I'm probably not making myself terribly clear.

Say a simple pattern is

 X..
 *O.
 .x.


with the anchor in the centre.  (This is all based on the old
matcher BTW : I've never looked at the DFA matcher...)


So this pattern would have a horizonal bitmask of
00000011100000   since it is 3 elements wide.


Anyway, if we try to match somewhere in the middle
of the board, the calculated bitmask is going to be
something like  111100000000000000011111  where
the 1's represent off-board. So when we test

  (pattern_mask & board_mask)

we get zero to indicate all's well.

But if we were to attempt to match it near the edge of the board,
the board mask might be  0000011111111111111   and now
the test is going to find that the board_mask has 1's
where the pattern is trying to be.


We'd probably need  (pattern_mask << something) & board_mask
where 'something' is related to where the anchor stone is in
the pattern ..?



Trouble is, I think this costs a lot of extra data per pattern.
Well, maybe we just need one byte to see how wide/high it is,
and then one byte per rotation to say how to shift it to take
into account the anchor stone.



Sorry, I should stop thinking out loud.  Is this making any
sense ?   I may try to come up with something more concrete if
no-one can understand what I'm trying to say !




dd
-- 
address@hidden          http://www.insignia.com