Evolution of a Go program

About the development of Moyo Go Studio, software to (help) play the Oriental game of Go. Go is a two-player zero-sum game of perfect information. It is considered much harder than Chess. Currently, in spite of enormous effort expended, no computer program plays it above the level of a beginner.

Saturday, September 30, 2006

Audio Go Lessons Plug

Fernando Aguilar was so kind to make a sample Audio Go Lesson for Moyo Go.

Ladies - don't you just love that Spanish accent?

I am honored that he - someone who has wiped the floor with more than one 9p - took the time to do it, and perhaps he'll make a full-fledged lesson soon, for the users of Moyo Go Studio.

There is a growing market for Audio Go lessons, and there are more and more people using Moyo Go Studio. Those hundreds who've bought the program are obviously serious in improving at Go (otherwise, why pay sixty dollars for a Go information system, right?).

If there is interest for making Audio Go lessons with Moyo Go Studio, I will make a free SGF viewer available that can play those lessons.

Friday, September 29, 2006

Getting Rid Of The Chinese

Moyo Go has by far the biggest game collection but too many games had Chinese names & rank. And even though someone gave me a transliteration list, not too many names got translated. Today I discovered why. The names have stuff behind them, like how old the player was or which country he or she played for. And often the rank.

Naive sod as I am, always believing in the good of humanity, I simply did a literal search and if there was no exact match, I didn't translate a thing. So not much got translated. But a few hours ago I got off my lazy ass, figured out what all that extra crap meant and wrote some code that gets rid of it and converts it into standard SGF rank properties. One of the funny things I discovered that there's no such thing as a 1p rank, it's called "beginning stage" or something.

Tonight I'll start reading in all pro games again. I have two hundred thousand pro game files from many sources. Heaven permitting, after it has all been done, I will have the most complete, Romanized pro game collection. The code that is able to deal with all violations of the SGF standard is humongous.

Thursday, September 28, 2006

Publishing Proof-Of-Concept

Okay, so y'all thought I was losing myself in the avalanche of bugfixes!

Nope - there is something very major (still secret, due to the fact that my enemies will try to prevent it) coming up, and Moyo Go has to be as "clean" as possible for that event.

I finally got around to the Publishing (printing etc.) and I have a proof-of-concept:

xxx.rtf
xxx.pdf
xxx.htm

This is three times the same test output, but all I had to do was click another option. And there is more where that came from :-) As a first test, I'm very happy with it. It all looks like it should look, also on the printer. And this is using a very low quality output setting with only 4::1 antialiasing instead of 16::1.

The first version of publishing will only have one kind of diagrams: Column aligned ones. Will look very cool though. And you'll be able to plaster the same thing as normally comes out of the printer onto your website too! In three-columned pages, for example. I'll try to get this out the door ASAP.

"Drops" Download (Skin)

I have often used this image to show off Moyo Go's skinning capability, but now I realize that this skin never made it into the distribution! It can be downloaded here (Right-click and Save Link Target As).

Save it in C:\Program Files\Moyo Go Studio\Skins and it will become available as a board skin.

I would like to say something about the issue of ripping off a program's resources, like StoneBase did with my board texture, stones and Blake Habers' studio recorded stone sounds. I remember it took me an entire working day to make my board texture bitmap! It starts with finding the perfect texture. I ended up on wood websites looking for large, high-resolution images in non-compressed format. Those are extremely rare. Then I had to make sure the lines/cm and the hue were "just right", so I browsed the web for board samples of expensive Kaya gobans and others. I stretched/compressed the image and changed the RGB distribution to make it look like a nice golden Kaya.

But that was not all of it. I wanted to have the ability to use a small version for a board by using "tiling", but without apparent "seams". That is only possible when you do a trick: You have to flip & mirror the image three times so you get four images, put them together to form one large image, and then the left side merges seamlessly with the right side, and the top with the bottom.

Then I had to compress it just well. At the largest magnification, you should not see JPG artifacts, but neither should it be too large because it takes too long to load otherwise.

Finally, I encrypted the image and added it as a resource. A day of work. It was ripped not by decryption cracking, but by simply turning off board lines, hoshi points and indices, and copying the empty board at full screen size. Same with the encrypted sounds: They were played and recorded with a small utility that can record sounds that are played by "hooking" itself into the data that goes to the sound card. The stones (I draw them using OpenGL) were ripped by making screen captures of them. That became possible because they also stole the board itself, so the stones would blend in perfectly with the board, otherwise there would be an edge between the antialiased stone border and a board of different hue.

So indeed, the Go software world is dog-eat-dog. I wonder where that term came from ;-)

Go Game Assistant Baloney

"Baloney" is US slang for "nonsense".

Go Game Assistant claims to have 56,000 pro games.

Baloney.

20,000 are duplicates!

I do not suspect malice, however. I know for a fact that there is a large pro collection out there in the public domain that has all its games flipped (mirrored). They obviously read that collection and did not have safeguards in place to normalize their Dyer signature or Zobrist hash.

But this is no excuse to keep on advertizing the product with so many games.

I do not want to bitch and moan too much about the Chinese (they have nukes, after all), but I see a pattern here. This is the second time Chinese software does very questionable things. Last week I found StoneBase having ripped my stones (and sounds, and board, and the nicest glyphs), now I find Go Game Assistant well.. grossly "misrepresenting" their number of pro games so that they (what a coincidence) end up just a little above Moyo Go Studio. Sorry to break it to 'ya, guys - you aren't even close.

Update: Someone emailed me to inform me that there is no Chinese conspiracy against me. So they brainwashed him as well ;-)

Saturday, September 23, 2006

Antialiased Diagrams

The new diagramming code is done. It looks much better on small diagrams!

This is a 16 pixels - to - 1 antialiased image. Will look great on the web as well (Moyo Go will have "publish to HTML").

Without this sophisticated scaling method, it would have been impossible to read the stone numbers above 99. Ordinary font rendering technology in Windows (or Mac, Linux) is unable to produce such quality on such a small scale.

These neat little Go diagrams look "simple" at first sight, but when you examine closely, you'll see that no other Go software has it.

Because producing such an image is far from trivial. As I said, it is impossible to achieve with state-of-the-art TrueType font rendering technology. It requires all the tricks in the hacking book. I make a Windows API call to make sure font smoothing is enabled. Binary search to quickly determine the best fitting font size for each stone number. Highly optimized pointer arithmetic for the antialiasing code. Palette-handling stuff to be able to work with 8-bit grayscale bitmaps, because antialiasing is faster on less data. And a handful of heuristics to make the stones look good at all scales. Omit any of these tricks and the image looks either sub-optimal or takes too long to render. Don't forget that a 16::1 antialiased image of 300 x 300 pixels requires a bitmap of 1200 x 1200 pixels, and that the user expects to browse through found games at several per second. So you have to average 4 pixel intensities into one, and do that 1200 x 1200 = 1.5 million times, in a split second. Amongst several other time-consuming things, like doing it again, but 4::1, and converting the resulting 8 bit image to 24 bit, to be able to draw in color on top of it.

And it goes on and on. There are several more, highly technical "issues" with this that can literally crash a user's computer or make the image look terrible on other computers. I do not want to go into details, but I can tell you that it has to do with the graphic card hardware & driver, and with an error in Microsofts documentation of the Font Smoothing API. Apart from that, I discovered something very major and totally undocumented about font smoothing, and if that discovery is not made, it will also not work properly on all machines.

I am not trying to be boastful - it was pretty easy for me, someone who has mainly worked in the image analysis/manipulation/creation field. I just wanted to explain, it might be interesting to know how much effort and engineering goes into seemingly trivial things. At least in Moyo Go :-)

Friday, September 22, 2006

Not Invented Here

I'm working on the page rendering engine.
There are two parts - the positioning logic and the rendering code.

This is about the diagram rendering code.
It's impractical to use the Go font I purchased, called "Tokyo".
Several reasons.

One is that the Report Generator can't handle the font - each Go stone is represented by up to four characters - breaking the rendering code that assumes the rendering string has as much characters as its length. I could augment this - I have the source - but there are more impediments to using a font-based diagram rendering solution.

Another one is that although the font prints OK from PDF, a PDF reader is not able to display it perfectly, due to the fact that the font uses a clever trick to build a glyph out of a handful of characters.

Last but not least, I am not allowed, or even physically unable to embed that font into HTML, RTF etc. And I hate having to support two rendering engines.

My only good option is to render a bitmap image of the diagrams. But that is easier said than done, because I do not accept jaggy edges of circles, or coarse stone numbers when using a tiny font.

Fortunately I have made some very fast anti-aliasing code (used some years ago in the Go board), so what I will do is draw the image twice as large as it should be and then antialias it.

A positive side effect of making an antialiasing full-featured diagram rendering engine is that I can improve upon the existing "match" diagram.

Monday, September 18, 2006

Publishing Module - Good News

As far as I have been able to determine, there is no Go software that lets you "freely" format its printer output.

One should always strive for the best, so my spec required the ability for "wordprocessing-like" diagramming (not in the form of WYSIWYG but in the form of per-diagram placement hints, variable columns etc.) And output to all imaginable formats.

Output to two dozen formats (PDF, RTF, HTML etc.) is possible with a top-of-the-line Report Generator, so the past days I've been busy evaluating their feature sets. It turned out that there was only a single Report Generator with acceptable Unicode support and a rich set of output formats, but it did not have any formatting logic! Meaning, it is unable to auto-format text over columns or around images.

One would have to chop text up into text "boxes" to do that. But - there are no functions to know whether a string of text fits in a certain bounding box, so things are pretty bare-bones, with the report generators I need. There are more "clever" RG's, but they don't support Chinese mixed with Japanese and Korean, or they don't export to PDF, to give but an example.

So I purchased the source to the Report Generator I liked (Unicode & lots of output formats), and, good news, I was able to add a function that returns what part of a string does not fit in a specified bounding box! It was easier than I feared.

This will allow me to build a page generator with the capacity to format text in columns and around images - exactly what I need to offer flexibility in both output formats and page layout. Neither cost nor effort will be spared to make Moyo Go Studio a state-of-the-art Go Publishing tool. Hopefully I'll be able to produce a "technology preview" of Publishing in a few weeks.

Saturday, September 16, 2006

Go Diagram Publishing Format Support

I have chosen a publishing solution that will export to the following formats:

BMP, DIF, EMF, Excel, GIF, HTML, JPEG, Lotus 1-2-3, PDF, PNG, QuattroPro, RTF, SVG, SYLK, TIFF, TXT, WMF, XHTML. And of course to the good 'ole printer.

This will strike fear in the hearts of my adversaries.
A first version will be ready soon.

Have a nice day.

Publishing GUI Almost Done

The GUI is the mirror to the soul of the application, so I often design, experiment and tweak for a very long time before I decide it's "done".

Everything is connected to everything else. With such a complex feature as publishing Go diagrams, it's a good idea to start with the GUI first, because it forces you to think about the nitty-gritty.

Moyo Go is designed with user-friendliness as the highest goal, and in my philosophy, minimalism is often best. Minimalism in the Apple-arian sense of the word (fewer widgets but more usability).

The diagram glyph informs the user about the diagram layout. Because it's nice to have markup with per-diagram granularity, but the resulting layout needs to be clear at a glance by looking at the tree as well.

Friday, September 15, 2006

FG

SGF's FG ("figure") property provides for a bitfield that defines various flags.

After careful analysis (these things should not be rushed), and considerating existing extensions to the spec, I propose the following amendment:

0 Coordinates on/off
1 Figure name on/off
2 List moves not shown in figure on/off
3-6 Figure alignment 0..15 (0=In column, 1= Top aligned (left to right), 2=Bottom aligned (left to right), 3=Left aligned (top to bottom), 4=Right aligned (top to bottom)', 5=Top-left', 6=Top-center', 7=Top-right, 8=Bottom-left, 9=Bottom-center, 10=Bottom-right, 11=Center-left 12=Centered, 13=Center-right)
7 Generate new page
8 Remove captured stones on/off
9 Hoshi dots on/off
12 Show the range of moves as (From-To) in the caption.
13 The last move of the previous diagram is repeated.
14 Show sequence with small stones.
15 Ignore flags on/off
16-22 Diagram border width as a percentage of the figure: 0..63 (0..60%)
23-29 Diagram size as a percentage of the page width 0..127 (20..100)


This permits a per-figure specification of formatting parameters, allowing us to "word-process" an SGF file. Instead of being constrained to fixed layouts, we can make-up and edit a page layout. Of course, this can be overridden and a more traditional, "fixed" page layout chosen instead.

Thursday, September 14, 2006

Stonebase Stole My Stuff

The dodgy Chinese software StoneBase copied not just the stones used in Moyo Go, it also ripped the studio-recorded sounds by Blake Haber, and the board texture itself.

This is not very nice, but it was to be expected, sooner or later.

It is flattering, in a way. StoneBase even uses the same software as I do to make screen images for the Help file.

StoneBase did a bad copy job. Stone thickness/intensity/shadows are non-configurable, there is no 3D board, only two stone sounds, no board skinning, no drag & drop support, etc. A lousy imitation at best.

And as soon as I figure out who made it (for obvious reasons, the dude doesn't publish his name and address), I will file a Copyright infringement claim with his local Chinese authorities.

Tuesday, September 12, 2006

KGS Database Overhaul

50,000 games added. New games to existing databases and two new ones created: 5d vs. 5d and 4d vs. 4d+ (large database of strong handicap games)

Studying Ants

A few days ago my girfriend and I went to Glaskogen, a wonderful, wild little forest with 80 lakes in Sweden. It was mushroom time and the mosquitoes had not survived the chilly nights. We slept comfy in the car.

Resting after a long walk, I saw an ant dragging another ant. "He's hauling a corpse to the nest", I thought. But at closer inspection, one ant had the leg of the other between his mandibles, without showing signs of wanting to chew it off. The dragging ant seemed to hardly notice the draggee, but it slowed him down considerably.

I wondered what was going on. Both ants seemed of the same species. Both could easily cut off the other's limbs in a jiffy, yet they seemed pretty OK with the whole thing. One was carefully grabbing the other by the leg, and the other did nothing much else but trying to drag along.

I wondered why the ant kept holding on to that other ant's leg. And why that other ant didn't lose its patience and chew its own leg off, or - better yet - the other ant's head.

Then I saw it: The leg-locked ant started to cleanse his counterpart of lice, or so it seemed. Apparently, the other ant couldn't rid all of his body by itself. It would perhaps succumb to the infestation, if the parasites weren't eventually removed.

So these ants apparently needed some encouragement in the form of an annoying slowdown, for them to help their fellow ant. Things went according to rational rules. A simple, elegant solution. I marveled at the seemingly complex behavior, displayed by such a modest configuration of neurons. And I wondered what else I might discover, if I only had more time to study the ants.

Saturday, September 09, 2006

51,000+ Pro Games Amidst Organized Chaos

Thanks to the substantial intellectual efforts of a very talented and helpful person - Jean-Pierre Vesinet, I am able to add a thousand new pro-pro games and almost two thousand pro-ama games and/or handicap games between pros.

Heaven permitting, tomorrow, Moyo Go Studio will be the first Go software that breaks the 50,000 pro-game barrier with more than 51,000 games where at least one player is a pro!

We have spent quite some time (several days) ensuring the quality of the games and each and every one is unique and has all important data. I want to remind again that the Chinese, Korean and Japanese player's names can only be displayed when support for East-Asian languages has been enabled in Windows as explained in the Help file.

I added quite a few robustness filters to the game import wizard, to ensure that games with missing moves will not end up in the database. Other improvements include a "wrong-date-format-normalizer". Infinately many wrong ways to specify a date in SGF are used, and Moyo Go needs to know the date to be able to calculate the average playing date for fuseki, for example. So it is important that every crazy date format is recognized and normalized. One Chinese Go server uses outrageously wrong SGF and I had to make a converter for that as well, but Jean-Pierre did the real detective work. Things are still not perfect with Moyo Go's pro database, but it is bigger and better than any other pro database in existence, and it keeps getting better, thanks to half a dozen hard-core contributors. And it's not just size that matters - it's what you do with it. Moyo Go does things with its game databases that no other Go software can repeat, whether complex SQL queries or Statistical Move Likelihood queries (have you seen the new Ctrl + E clipboard feature for that? The next update will improve upon it - I forgot to include the SML percentage).

Building the new databases came as an interrupt on an interrupt (or a subroutine in a subroutine), because originally, I was working on the TsumeGo module, which became interupted by a publishing module that I want to have ready in early october (at least a "technology preview"). The reason I started a printing module "in between" has something to do with something that still is a secret :-)

Running a μISV is challenging stuff - you have to be able to manage interruptions within interruptions within interruptions. Of course one shouldn't let this get out of control, but bugfixing and support issues sometimes, or even often, have a higher priority than anything else. The bigger Moyo Go gets, the higher the demands on program architecture, overall stability, Help file etc.

To give an example of what goes on behind the scenes and what's involved in producing shrinkwrap software: I got a report of the selection in result lists not being properly visible under a certain XP theme. It turned out that several of the components that I use rather follow the theme's selection colors, and although one could argue that the user should be responsible for the color schemes he/she selected, it appears that the user typically does not realize that XP themes are more than just another color window. So I went deep into the source of a handful components and made sure they always look as I intended them to look.

Another issue was with a reported slowdown during Fuseki matching. My computer is a mega-monster with 4 GB RAM, four 64-bit Opteron cores and dual 15,000 RPM SCSI harddisks*, so (you feel it coming), I do not have many slowdown problems :-)

Yet, it would be too easy to dismiss those reports with "I do not see your problem here". Me being a diver and all, I went to the bottom of the problem (I hope it wasn't a false bottom) and decided it was caused by memory fragmentation. The code pointed to serious fragmentation, so - without going into the gory details - I fixed that for the next update.

Another support issue was about the precedence of the and and or operator in a database search, and how to get a list of games between certain players. That proved to be a non-intuitive one, but possible due to the power of the SQL engine I use. I found a way to do it and updated the Help file.

Norway still has a few nice late-summer days left and after that and the upcoming updates, it's back to the publishing (printing) module!

*Will be obsolete junk before I have gray hair

Friday, September 01, 2006

Diagram Toolbar

Sweet, aren't they?