Someone reviewed MoyoGo on Sensei's, and the only feature to be desired was mentioned to be a free-defined pattern search. This bumped up the priority for a "Kombilo" type search, where you can search for any random pattern with any random shape.
I mentioned my target of "instant" search. I do not want a worst-case of 5 minutes or one minute or even ten seconds, as is often the case with Kombilo. Most of the time my brain is unable to come up with clever algorithms, but I came up with something that should be extremely fast.
The "matching"-database required for 43,000 pro games is 11 MB, so that's no biggie. The system uses less data than Kombilo does. However, its complexity is mind boggling. I am going through page upon page of data structure description with deeply nested multiple indirections, orgies of bitfcking and utterly complex (a better word would be "Aufwand", in German) pre-calculations. In fact, the pre-calculations take perhaps half of the search time and a hefty chunk of the RAM needed for the search.
The only code of significant complexity will be the pre-calculation stuff. You give it a pattern, the system will do hundreds of millions of preparatory bit twiddlings (but that takes much less than a second), then it crunches - blazes - through a specially prepared form of the moves of the games.
The weird thing is: There will be no actual comparisons done. I learned my lesson well so I am not going to divulge how it works, but I am certain it will work and I am certain it is close to the fastest possible way to search patterns in go games. I am very bad at mathematics so it's just a guess, but intuition and common sense tells me there can't be a much faster way.
I'll do some calculations and round off the design before I start coding. Kombilo works with an array of end-positions in order to look which games might contain a pattern match, but my system won't use that method because it would make my system slower.
