[computer-go] Pattern extraction using holographic reducedrepresentation

[Berk Ozbozkurt <ozbozkurt@xxxxxxxxxxxx>]

Hi All,

I found a way to use HRRs to represent board positions and game trees in 
an effective manner (ie. one that handles color reversal and all 
rotations of the pattern easily.) If I'm not totally mistaken, it should 
be possible to extract patterns and game trees representing possible 
continuations from that position in a manner suitable for both automatic 
extraction and generalization. Simple googling returns nothing but I 
wanted to check with members of this list before reinventing the wheel. 
Has anyone heard of a similar approach?

You might have heard about HRRs by a different name. So here is a brief 
sketch of the main idea. Each component in an HRR is a vector of n 
(typically >500, more the merrier) dimensions. It uses three basic 
operators, one to bind components (*), one to superimpose (+) them and 
one to compare (=). First two operators also have inverses. Binding 
operator is randomizing st. A*B is unlike both A and B, while 
superimposition operator is similarity preserving  st. A+B is like both 
A and B. One such scheme uses binary vectors, uses XOR to bind and a 
stochastic AND (ie. 1 sAND 0might be 1 or 0 with equal probability, 
while 1sAND1 is always 1 and 0sAND0 is always 0)  to superimpose. The 
Zorbist hash is equivalent to representing a go position with HRRs where 
each elementary vector (existence of a stone at position) is bound. 
Comparison operator is simply count of 1s in A AND B. Binary vectors get 
too noisy quickly, so I will use frequency domain circular convolution 
(*), addition (+) and cosine between vectors (=) instead (see 
http://citeseer.ist.psu.edu/plate95holographic.html.)

The nice thing about HRRs is that, they support structured 
representations (a tree, a list, or a simple collection) and automatic 
unification, generalization, noise tolerance, all in vector domain - 
without ever decomposing a vector to symbols.

My idea is simply representing a go pattern (eg. a configuration in 9x9 
window on a 19x19 board) both with a collection (eg. which positions are 
occupied and what color) and a game tree representing local order of 
moves in that window. After extracting those patterns from a set of 
professional games, similar vectors are superimposed to allow 
generalization and generate a library of patterns this way. To use them 
to play games, the board position is converted to HRR representation, 
and most similar patterns are used to determine a) possible 
continuations from that position b) how that pattern might evolve (so 
territory and a life and death status estimation can be more done 
accurately by an external agent)

Thanks in advance.

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/