In the tree a node represents a position, so each visit after the first will have the same pattern matches. Your hardware would be quite a bit faster, but the overall program speedup is pretty small. My patterns are hand generated, so the size is limited by my ability to say interested in adding new patterns. For a program with automated pattern learning and no "don't care" your hardware might be interesting.
Since I sell software, no hardware will work for me. I can't ask my customers to open up their computers and install a PCI card. David From: [email protected] [mailto:[email protected]] On Behalf Of ?????????????? ??????? Sent: Thursday, May 30, 2013 3:27 AM To: [email protected] Subject: Re: [Computer-go] Hardware pattern matching acceleration So, the cheapest hardware might have several times larger pattern database and give an ability to check for patterns not only for initial node bias but at every first node visit after each move (as long as position changes). Is it seems to be valuable? Will it give an ability to build tree deeper? Dmitry 30.05.2013, 10:32, "David Fotland" <[email protected]>: 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: [email protected] [mailto:[email protected]] On Behalf Of Mark Boon Sent: Wednesday, May 29, 2013 4:34 PM To: [email protected] 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, Рождественский Дмитрий <[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
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
