When using a Trie type data structure, there's no hard limit to the size of
patterns in a pattern-matcher. It may be that some people only use small
pattern sizes because they use fixed-size patterns with no wild-cards.
Some years ago (late 2008 or early 2009) I outlined an incremental
pattern-matcher on this list using the 'bread-crumb' strategy. I think
you'll find it is quite competitive in speed. But since I never had anyone
ask me about any details I assume the need for a pattern-matcher you're
proposing is not all that great.
Maybe one of the people with a competitive bot can tell you how much time
they spend in a pattern-matcher.
Mark
On Wed, May 29, 2013 at 10:52 AM, Рождественский Дмитрий <[email protected]
> wrote:
> I'd probably need less than 64 of it because it scales like a square.
> Making a chip twice larger (and twice more expensive) doubles the pattern
> library size and at the same time doubles the number of moves that may be
> matched in parallel. And when you tell that it is not an order a magnitude
> faster, do you mean that CPU can match that much 7*7 or 9*9 patterns with
> wildcards? I was told that current programs use relatively small patterns,
> and could benefit much from large ones.
> Dmitry
>
> 29.05.2013, 23:13, "Mark Boon" <[email protected]>:
>
> Assuming the 2 microseconds mentioned is for the whole board (you don't
> mention what board-size, I assume 19x19) it sounds quite fast. But probably
> not an order of magnitude faster than a software solution. The question
> then becomes how well it scales. Would you need 64 of these to service a
> 64-core computer?
>
> Note: at some point you should decide for yourself what project you think
> is worth taking on. You'll always find that other people have 100 reasons
> why not to try something, but they're often wrong.
>
> Mark
>
>
> On Wed, May 29, 2013 at 8:02 AM, Detlef Schmicker <[email protected]> wrote:
>
> Hi,
>
> sounds interesting. I am not to experienced with large patterns at the
> moment, but we (oakfoam) are using >1000000 (circular) patterns up to 15
> (as the size is counted in several papers), so 30000 might be not enough
> for a strong program. Usually we need all pattern matches at the board
> at the same time, is your 2ms this time?
>
> I am very interested in GPU acceleration, as this might be very
> interesting in mobile devices. They usually have a strong GPU and I was
> thinking about accelerating exactly what you are talking about. It is
> somewhat difficult to calculate the performance this approach would
> offer.
>
> Another interesting acceleration might be real liberties (instead of
> pseudo liberties) in the playout moves. This might help to use more
> heavy playouts. But I do not have data, if this would help, as we do
> only have pseudo liberties.
>
> Detlef
>
>
> Am Mittwoch, den 29.05.2013, 21:38 +0400 schrieb Рождественский Дмитрий:
> > Hi,
> >
> > after thinking over your advices in the previous thread and making some
> investigation I have figured out two options of working on the hardware
> accelerator. One is to develop a totaly new algorithm that fits for a
> hardware acceleration better than current ones. Or to find what can be
> improved in current algorithms moreorless revolutionary, because just
> acceleration of an algorithm part is not a solution,
> >
> > I thought that maybe it will be interesting to improve pattern matching.
> Current programs can massively match relatively small patterns. Hardware
> may have the following parametres:
> > - pattern size up to 9x9 with wildcards ("does not matter" field state
> to eleminate influence of insignificant peripheral stones' positions);
> > - additional attributes as usual (liberties, ko, distance to an edge)
> > - internal position calculator with pattern extractor (just send a cell
> position and receive its belonging to a pattren back)
> > - several patterns' evaluation at a time (should further specify how
> much)
> > - about 30000 7*7 patterns in an $200 device
> > - about 2 microseconds time
> >
> > Does anyone have an idea will it be valuable?
> >
> > Dmitry
> > _______________________________________________
> > Computer-go mailing list
> > [email protected]
> > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
> >
>
>
> _______________________________________________
> Computer-go mailing list
> [email protected]
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
> ,
>
> _______________________________________________
> Computer-go mailing list
> [email protected]
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
>
> _______________________________________________
> Computer-go mailing list
> [email protected]
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
