Random Thoughts

I had a few minutes spare so I thought I'd make a very brief post on a couple ideas that occurred to me, which are probably distant-horizon possibilities for actual implementation but struck me as interesting.

GPGPU for pattern analysis

The basic pattern match algorithm is very simple, and very memory-localised for an individual pattern (the data to be considered only scales with the size of the pattern library really).  For a realistic shape library my guess is (including generated symmetric partners) we'll probably be looking at order of a thousand or so patterns.  It strikes me that parallel matching all the patterns against the board data in a highly threaded architecture could be extremely efficient.  This seems like a great candidate for GPGPU (which sadly is a pig to program with current tools) .  In reality we'd likely want to feed the GPU a bunch of position nodes at once because of the latency overhead of data exchange between CPU and GPU (this may reduce as APUs become more common over the next few years though).  Anyway, passing all the sibling nodes of one parent in the game tree would be fairly natural and mean we could have match results basically waiting for us if we have  tree search that can usefully consume breadth-first analysis.  This could easily buy a couple of orders of magnitude in pattern match performance...

Board sub-domains for transposition analysis

In many cases (certainly not always, but often) key variations are played out locally without reference to distant parts of the board.  In a naive tree analysis we're likely to re-evaluate the same move sequences in a local area many times when considering the whole-board game tree.  To avoid re-analysing whole-board sequences that occur by transposition (e.g. - swapping the order of two moves) it is  fairly common technique to use the Zobrist checkums of analysed positions to find matching subtrees and avoid the need to evaluate them multiple times.  Given the (frequent) local nature of fights in Go it strikes me we could divide the board into sub-domains, and construct Zobrist hashes of each sub-domain.  This would allow transposition-like detection of subtrees that take place entirely within one sub-domain.  By favouring early analysis of sub-domain-localised trees it should be possible to find alpha-beta (or other) cutoffs that cause large score swings by only operating within a subdomain, and applying them to other tree branches by use of sub-domain-equivalence tables (akin to full board transposition tables).  Sub-domains would probably be arbitrary (overlapping to avoid non-coverage of positions played out on boundaries) regions pre-determined (e.g. - 6X6 rectangles, spaced every 3 intersections or something), though maybe having them dynamically determined would be possible/desirable.  I haven't really thought this one through in detail, but it just struck me as interesting...