[Computer-go] Hardware pattern matching acceleration

David Fotland fotland at smart-games.com
Wed May 29 23:32:25 PDT 2013


Many Faces of Go uses 8x8 patterns with all types of wildcards (any,
white-or-empty, black-or-empty, etc).  I have about 2000 patterns, which
would expand to over 100,000 without wildcards.  It uses about 5% of total
run time if I match patterns whenever I create a new node in the UCT tree
(for initial bias).

 

David

 

From: computer-go-bounces at dvandva.org
[mailto:computer-go-bounces at dvandva.org] On Behalf Of Mark Boon
Sent: Wednesday, May 29, 2013 4:34 PM
To: computer-go at dvandva.org
Subject: Re: [Computer-go] Hardware pattern matching acceleration

 

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, Рождественский Дмитрий
<divx4log at yandex.ru> 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" <tesujisoftware at gmail.com>:

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 <ds2 at physik.de> 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
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>


_______________________________________________
Computer-go mailing list
Computer-go at dvandva.org
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go

,

_______________________________________________
Computer-go mailing list
Computer-go at dvandva.org
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go


_______________________________________________
Computer-go mailing list
Computer-go at dvandva.org
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20130529/3c8d19dd/attachment.html>


More information about the Computer-go mailing list