On Wed, 2008-03-26 at 15:08 -0300, Mark Boon wrote: > Lately I have been putting some effort into pattern-matching. > Although I have made progress, the result was not as good as what I > had hoped for by about an order of magnitude. This makes me wonder > what is currently actually the state of the art of pattern matching > in Go.
My go-programming efforts are very much concentrated on patterns. (maybe I have been influenced by the Kojima-papers) My patterns are centered around the point_to_played. Currently a 11*11 square (120 points) area is covered. I use a polar coordinate system. The patterns themselves are basically stored in a n-Kd tree using a bitmask of 4 bits (for EBW+offboard) per stored point. Not all the points are stored, only the ones that are needed to build the tree. Currently, the pattern's payload consists of the number of times it was seen, and the prpposed value for Black or White to move here. I have the pattern database running as a separate process, communicating via UDP packets. (I don't care about performance, the idea is that the main process can do other usefull things while the patternmatcher fetches the patterns, and that -once hardware is cheap- I could add more pattern-servers). I estimate the pattern's values by making them compete (just like Kojima) Currently, it is about 1 GB in size and contains about 8M 'positions'. Values have been obtained by extracting from professional games (twice). To avoid bad moves beeing absent, I am currently training with (N=xxx) games obtained from the NNGS archives (clipped at ~10Kyu). I intend do do another run of the professional games, to resettle good ordering. Currently the patterns last upto about movenumber 100 (harvesting is ceased once there are no more patterns left to compete with), and in most games, upto about move 20-60, circa 50% of the moves are within the four top-ranked patterns. I don't do speedtests. (I am only in it for the data) I guess it does about 2 moves/sec ... Yes, I only refetch the (120) patterns for the locations that have been affected by the previous move (less < 120 for the edges and corners, of course). Yes, this makes the boardcode very heavy (basically, each point's surroundings are stored with the point data, to be used as an argument for the pattern search), but that is neglectable in relation to the network roundtrip + DB lookup / update. Recently, I started experimenting with 12 point(24 bits) patterns in a "swiss flag" shape; which can be kept in memory, since there are only 16M possible cells. Once it works, I may use it in a "pattern enhanced" UCT-experiment. Adriaan van Kessel. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
