pattern matcher (was Re: [gnugo-devel] Crash report for OS X Segmentation fault)

[Dave Denholm]

Dave Denholm <address@hidden> writes:


(BTW, the link to the legend go server from the home page
 seems broken ?
)


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


BTW : am I correct in recalling that the 1d board has "gray" at the
borders. This could be exploited for testing the edge constraints,
if desired.

All that would be needed would be to add a pattern element to check
that the board is gray at a particular offset. (and mask = val mask = 3)
(Two pattern elements for corner patterns) This would of course work
under all rotations automatically.


A comment in matchpat.c has it that

/* In the current implementation, the edge constraints depend on
 * the board size, because we pad width or height out to the
 * board size. (This is because it is easy to find the corners
 * of the rotated pattern, but it is harder to transform the
 * bitmask of edge constraints.)


so that would save having to worry about transforming the edge
contraints, and save all that code for padding out patterns to
match the variable board sizes, and fixing it up when the
board size changes, etc.



Maybe there is a faster algorithm for testing whether the
pattern fits on the board if it doesn't also have to
worry about enforcing edge constraints..? (Can't see
it off-hand, though)




BTW, noticed a FIXME in mkpat.c :

 case '\\' :
  case '/' :
    /* FIXME: Can't be bothered putting in the edge tests.
    *         (What does this mean?)
    */



It probably means that it should be checking consistency
of any edge constraints. ie if there is / or \ symmetry and there
is an edge pattern, it has to be a corner pattern.

ie for / symetry, there has to be both N&E edges, or S&W edges,
or no edges. Similarly for \



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