Pattern search module rollout today

Tomorrow, heaven permitting, I'll upload the new auto-update that has pattern search capability.

Some people prefer the very low resolution of 1024 x 768 and in that case it can occur that not all result tabs fit the current docking layout. You can cycle tabs by clicking the arrow buttons.

In this example there were 11 patterns found, with black in this position winning 90% of the games.

Not much functionality apart from playing through the result games in the diagram will be provided at first, but that will change fast.

A progress bar shows search progress, remember to enable/disable the databases that you want to use because if you use all of them, searches without board edges can take a long time.

"Kombilo" match diagram

I find myself thinking of, and sometimes calling the new pattern search feature "Kombilo", because there simply was no other program that could do pattern searches. Like people "Googled" the web, they also "Kombilo-ed" Go patterns..

I just added a feature that Kombilo lacks: Matching pattern highlighting in the result list. It works just like the "Example" preview, and you will be able to play through the game from the diagram toolbar, copy the SGF to the clipboard, save SGF etc.

From now on I will call MoyoGo's statistical, fixed patterns "examples", and free-search, Kombilo-style patterns will be "patterns".

Database Settings preview

With the recent addition of Fuseki search and the upcoming "free" pattern search, it became useful to be able to specify which databases should be searched by those functions.

Here is how - in the next update - the Database tab will look in the Settings dialog.

I have to apologize about the need to rebuild "Free Search" databases again with the next update. I decided to implement more functionality than Kombilo has, namely the ability to sort search results on player rank, date, komi etc. In order to be able to add this functionality, the databases have to change.
However, the new "Build database" Wizard will be easier to use, not requiring user interaction for every database.

Small stuff matters

The tabs of the docking control I use don't support hints (I bought the source so I can change that - I have to make it Unicode compliant as well anyway). So with all those funny icons and no room for explanatory text (there are still plenty people who use 1024x768), I decided to put those same tab icons on the Show - Windows menu.

Now, if you're wondering what a particular tab is for, you can compare its icon with those on the menu.

Even better: I added multiline hints to these menu items that explain how to use the functions they are associated with.

It works!

Absolute worst-case search time on my machine is 22 seconds to search through 43,000 games. This is for unrealisticly large, complex, edge-less patterns. A more typical search time for edgeless patterns is between 7 and 17 sec. Large edge patterns and Joseki patterns take half a second only! Smaller edge patterns take up to six seconds.

This test case takes 11.6 sec. (301 matches).

I'll make it multithreaded, so that on near-future mainstream machines, most searches will take less than a second.

It looks like I succeeded in being 10 times faster than Kombilo, but I'll do a benchmark later. Kombilo, as its main optimization, looks at the final positions whether a match could have happened in the game, and examins only those games further. This algorithm doesn't do that yet, neither has it been optimized for 64-bits, so there is ample room for optimization.

"Kombilo Killer" progress

The meds today appear to have excessive alliteration + smilies as a side effect :)

"Project Kombilo" is at a crucial crossroads - the data-generation code is done, the pre-processing code has been written and passed the initial tests, and now I'm about to write the search code.

Without optimizations, I expect it to be quite fast, but of course this has to be proven first. And in the meantime, I feel apprehensive as if about to leave for my first date. If the code performs as well as I hope it will, the rush will be comparable to one's first real kiss.

The code is very elegant. It's small. The search algorithm has many avenues open for optimization, and I am pretty sure that I will build a kickass free-pattern search monster - but it will take a little more time. Yesterday I reached an impasse: I realized that my rather exotic design required the copying of 1.7 MB of state per searched game. I felt like the boy who finally got her out of her panties, only to realize he forgot the condoms - and, without them, no business.

I did what I always do in such a case: I took a bath (without design bottlenecks I might have succumbed to scabies already :). This stimulates the blood circulation to the brain, relaxes the mind, and resulted in the required Eureka-event, the "Aha Erlebnis", so to speak, the profound realization that my ass was saved if I only added one extra level of indirection. With the current financial crisis, I'm more worried I'll end up in an appartment without a bath, than that they'll steal my sources because in spite of profuse documentation and following all the rules of the trade, even I don't understand my code :)

Most of my "cool" code is complex array processing, using an 4-dimensional array architecture unfolded into a one-dimensional array, for example. I never architect code without thoroughly considering the underlying machine architecture. Example: The Kombilo module needs to reset a large array of counters for each examined game. I use a single byte for each counter, so that I can reset them using a 64-bit memory fill routine. If I were to put them in ordinary integers and use a loop to initialize them, this would take at least ten, but most likely twenty times longer. I think there is absolutely no hope for a programmer to engage in long-term competitive Go-related software development if he isn't intimately aquainted with the hardware. Example: The data structures my "statistical" pattern search module manipulates are aligned on a cache line. If I don't do that, the slowdown of that code is fifteen-fold. The lazy programmer hopes that his compiler will magically do those things for him :)

Please don't take my "Kombilo Killer" as derogatory to Kombilo: As a tribute to Ulrich Goertz, I chistened the unit file ZH_Kombilo, ZH for ZenHacker (all MoyoGo's unit files have this legacy prefix). The class is called TKombilo as well. Kombilo has been "doing its thang" for ages, my design has yet to prove itself..

But I like the competitive aspect of software development. Just like topsport, but on a comfortable chair with a beer :)

Beer is great to get implementation ideas, but don't drink more than half a litre when you're coding :)

"Free pattern" match progress

The new databases are ready (and will be generated by the next auto-update of MoyoGo). New data is needed to be able to match any pattern very quickly to the games.

The pattern-definition selection code is 90% ready (you draw transparent green areas to indicate what pattern you want to search, similar to how it works in Kombilo).

The pattern-definition-to-preprocessed data algorithm is 90% ready and still has to be implemented.

The search algorithm to be used is ready, but still has to be implemented.

Go Problems

I'm so happy I have a color printer (Canon Pixma 4000 with CD printing tray - not available in the US due to patent issues). Go problem diagrams are much better readable that way, especially when you like to design algorithms on the couch and you don't own a laptop.

I want to dig deep into understanding the issues related to solving Go problems, to test ideas for a TsumeGo solver.

It turns out that Denis Feldmann has an interesting collection here.
As a terrible Go player, I need solutions as well, so his collection is exactly what I was looking for.

"Kombilo" module progress report

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.

Cross-platformness Musings

Borland has announced they want to dump Delphi, sell it off.
Microsoft finally managed to kill it.

I now hope that Delphi will die a quick death. I hope it will be utterly abandoned. I hope the buyer will neglect it, I hope Delphi will die. Reason?

MoyoGo is written in Delphi. Delphi remains by far the best Windows RAD tool. But it can't target Linux very well, or the pocket PC, or the Mac. And I am incessantly harassed by Mac owners that they would love to dish out the dough for my stuff, if only it would run on a Mac. Linux users reproach me for not having made a freeware version in Java, you got to admire the balls. A budding alternative to Delphi is Free Pascal/Lazarus, but as long as the majority of Object Pascal developers works with Delphi, Free Pascal will evolve slowly.

However when Delphi dies, there is little alternative for an army of Delphi programmers to start converting their libraries and components to Free Pascal/Lazarus. The result will be a 100% Delphi-compatible, open-source, multi-platform Object Pascal compiler/IDE widget library that compiles to 64-bit standalone executables. In no time.

Delphi has sold over a million licences (which are thousands of USD each nowadays - the best RAD IDE doesn't come as cheap as the Visual Studio crap), so perhaps a "serious" company will buy Delphi after all. There has been a bid of 150 million USD on it by Robert Coates, so perhaps Delphi and Free Pascal will continue side by side.

Multicore Hardcore

If there still was any doubt: Thanks to free market competition, we'll have desktop machines with hundreds of CPU cores in the foreseeable future.

Intel - nervous because their superior Itanium processor bit the dust and AMD's Opteron stole the glory - has announced they intend to put hundreds of CPU cores on a die.

This is good news for future Tsumego solvers..

I make Windows™ Software!

Just like a BMW dealer is in the business of providing services to BMW owners, I provide services to Windows™ licencees. Just like Lada or Škoda owners don't complain to a BMW dealer that their BMW headlights don't fit to their Lada's or Škoda's, Mac or Linux users should not complain to me that my software does not run on their machines.

I don't whine to Mac or Linux software developers that their stuff doesn't run on my machine either. It is my choice to run Windows™, and anyone who wants to run Linux or the Mac OS-du-jour is free to do so. I could have told you in advance that you were going to run into serious compatibility problems.

Politically incorrect enough already, I will refrain from elaborating but please stay out of my hair when you're a Mac or Linux user. I want to have nothing to do with either platform/OS. I run a Windows™ shop, and I have more than enough work catering for my Windows™ customers/users.

Customized Installer

The Avalanche Effect

Li Ang (3p) and Li Yue (6d) of www.aygoschool.com have generously donated their entire private game collection!

This altruism should benefit the Go community, so I have been writing some code that adds the handicap property when needed and a few other things that standardize the data. The player's names are in Simplified Chinese, but Moyo Go displays that just fine when you enable it in Windows, and Jean-Pierre Vesinet is working on an auto-romanization database for the CJK languages. I am building a new pro collection in which the Simplified Chinese is converted to UTF-8 (Unicode), so all SGF readers that support that will be able to display the names correctly. As an aside: I intend to make a free SGF Editor available Real Soon Now™.

In about a day or two I expect to be able to make available for download the new collection, which might end up with well over 43,000 pro games :)

Critical Mass Synergy

Amazing what some of my customers do to help improve MoyGo.

Jean-Pierre Vesinet is transliterating Korean, Chinese and Japanese players' names so I can let MoyoGo convert them to romanized equivalents at the import stage.

I already converted many Korean names in the Pro database that way, and the upcoming update will have auto-romanization (when not disabled).

Young H. Rhie sent me one and a half thousand okigo (handicap) games between pros and amateurs. I tweaked the SGF parser somewhat and reverse-engineered some non-standard SGF properties to extract the pro ranks and the date.

So, thanks to Young H. Rhie, MoyoGo now offers 43,175 Pro games, which is 7,000 more than for ex. SmartGo offers. (Pro games being defined by having at least one pro).

Alexandre Dinerchtein should receive kudo's as well, for publicizing a list of pro-aliases used on IGS. I haven't even counted those. MoyoGo translates pro aliases on IGS to their real names, so if I count those, MoyoGo has at least 44,000 pro games.

MasterGo 50% off

Since the MasterGo/AGA alliance hasn't been exactly nice to me, I thought, let's do a little comparison..

I had gotten a bit worried, since they are "dumping" MasterGo (they halved its price from 100 to 50 USD). It turns out I have nothing to fear :)

The upper left image is taken from the MasterGo user manual PDF, and illustrates how many Fuseki continuations are found (9) by their software, sorted by order of frequency. The image on the right is the same position in MoyoGo, with 26 Fuseki variations!

Why "only" 26? Because that's how many letters there are in the alphabet. (MoyoGo finds a few more exotic, low-frequency varations but doesn't display those, yet.)

Even when I disable all databases but the Pro database, I still get 14 continuations, all in the bottom half of the board.