A recent IEEE article (in IEEE Intelligent Systems) mentioned Microsoft's "research" "progress" in computer Go, but failed to mention Microsoft's shameless ripoff of Moyo Go Studio's pattern system.
Even though there are more and more wannabe Moyo Go clones popping up (for the record - I must say that these are done by very talented programmers and generally likable human beings) - so far, none of them has duplicated the pattern system.
Sad how those who publish other people's achievements get the credit. I do a few years of work, Microsoft publishes a paper on it to steal the glory. Complaining with the IEEE and TheRegister.com doesn't help - they are there to make money, not to investigate the truth. It's easier to have a story on how Microsofts' boffins made a stride in comp. Go, than how some bad-at-math, non-Go-playing dude made a stride in comp. Go, and how Microsoft stole the idea from my website and claimed it was theirs.
I realize (especially with my reputation for being "strange") that this sounds highly paranoid, so here is MS's paper on "their" Go pattern system, in which they mention my name a few times, saying that they were "inspired" by my system, and that they "improved" upon it: PDF
Some people say I am "reading too much" in MS's paper - just STFU, will ya. My records show their R&D campus building in Richmond as one of my first customers - they bought TWO copies, and one of the sentences in their paper goes: "These are the same pattern templates as used by de Groot in his Moyogo System
[7]". And that's just about the templates, they also copied the entire principle, the idea and implementation details. Not that I'm proud - I'm pissed off - especially that some clowns call me "paranoid" about it.
Sunday, April 29, 2007
Monday, April 02, 2007
Early Optimization Considered Essential
The ink on the previous posting is not yet dry, or a posting appeared on a German Go site: "Moyo Go Studio partially throws the towel in the ring". The intention was honorable though - drawing attention to the precarious situation the software is/was in, in terms of its commercial survivability, as a consequence of illegal/immoral attacks on me and my activities in the comp. Go scene.
Hm.
Switching from semi- full-time to "hobby" isn't exactly "partially giving up", at least not with me, I have done lots of things as a hobby, including writing a commercially available 2D-CAD system that rendered faster than AutoCAD at the time.
Since yesterday, I did two things - fix a customers' PC that didn't want to POST - I made 800 NOK (about 100 Euro) on that - and I hobbied a little on Moyo Go. Programming is so much more fun when you don't rely on it to pay the bills!
Enfin, I just hobbied. I hobbied the translation into C++ of a Object-Pascal class definition that I wrote for the TsumeGo (Tactical Go-problem solving) module. The entire class is done (I mean written in Delphi), and now I'm porting it to C++. I said it before, C is beautiful for applications like TsumeGo.
As to the implentation, I have no idea how it works anymore (I only remember it was a work of either a raving madman or a genius ;-) and besides I optimized it so agressively that even if I did remember the particulars, it would be utterly impossible to map sourcecode back to high-level concepts.
That's not so bad, really, because this class is small and does nothing else but maintaining the board state. It's a black box. All I care about is the absolute fastest means of making and unmaking moves, and getting all state info I require. For the rest, all that matters is documenting the data formats. The thing should get the crap debugged out of it (the first time I will use automated testing, it would be insane to omit that in this case) and from that moment on it will be left untouched forever.
I really mean that, because I spent ages in optimizing the thing. Optimizing early is essential in this case, because otherwise you end up building a henhouse instead of a Gitmo, and you'll have to recycle the henhouse later anyway. Speed is not just part of the spec, it is the spec.
I mean, it's easy to hack up a state machine - what it's easy is to design one that maintains everything I need and is lightning fast. Wist lightning fast I mean as fast as possible. This needs explanation. "As fast as possible" depends on the following:
- choice of algorithm
- choice of language
- compiler optimization
The devil is in the details, however. Many people simply design an algorithm using what they learnt at comp. sci or from a book on algorithms (or perhaps they conjure up something clever), but I work a little differently. I look at the hardware at one end, and the problem at the other end, and I base my algorithm on the strengths of the hardware alone. Nothing else. I don't care about easy of implementation, I don't care about how much RAM is required, I don't care about anything, I just care about using the hardware as clever as possible to achieve the highest possible speed, when speed is requirement #1. In move generators, speed is the only requirement. All things being equal, more speed is better. Nobody cares that the code looks ugly when you make moves twice as fast, (and get high-level tactical data twice as fast) as the closest competitor.
So what did I do - I read the AMD optimization guide for their 64-bit CPU's and I based my design on the strengths of 64-bit processors and the peculiarities of caches, buses, RAM, pipeline stalls, instruction latencies and whathaveyou. I came up with a pretty bizarre solution, ending up with code that looks outlandish and, after optimization, does not look at all like a state machine for Go positions. It basically is a bunch of complex logical operations on a bunch of 64-bit registers. And what it yields is linked lists of chains and their adjacent chains (also empty chains) and their properties. Unique is that it generates Nth-order liberties with breakneck speed. Having access to the number of 4th-order libs at the same speed as other engines maintain the same state minus order-libs will yield an enormous advantage. Hence spending months on a fast state machine. Hell, even if it would take years I would still do it.
I had to switch to C for the TsumeGo engine - nothing else compiles to native 64-bit EXE and optimizes that code to the max. I turned off comments on this blog, to avoid having to explain why JITters and GC suck :-) The reason Java is so popular is mainly because the current generation of comp. sci profs don't understand pointers. The reason C# is popular is because C/C++ sucks at writing GUI-heavvy apps. But you can not, I repeat, can not, write a viable Go engine in those languages. To be viable, you have to be able to control what happens on the hardware level. Example: aligned_malloc and inlined prefetch instructions or NOPs. Is there such a thing in Java or C#? My definition of "viable" is the same as that of the top Chess-engine hackers.
The crux of this monologue is that sometimes, speed is the only requirement. And, perhaps counter-intuitively, you should not first make "something that works" and "optimize later", because you simply can't turn a llama into a leopard. Instead of performing expensive plastic surgery on the llama, go the extra mile to get a leopard.
Hm.
Switching from semi- full-time to "hobby" isn't exactly "partially giving up", at least not with me, I have done lots of things as a hobby, including writing a commercially available 2D-CAD system that rendered faster than AutoCAD at the time.
Since yesterday, I did two things - fix a customers' PC that didn't want to POST - I made 800 NOK (about 100 Euro) on that - and I hobbied a little on Moyo Go. Programming is so much more fun when you don't rely on it to pay the bills!
Enfin, I just hobbied. I hobbied the translation into C++ of a Object-Pascal class definition that I wrote for the TsumeGo (Tactical Go-problem solving) module. The entire class is done (I mean written in Delphi), and now I'm porting it to C++. I said it before, C is beautiful for applications like TsumeGo.
As to the implentation, I have no idea how it works anymore (I only remember it was a work of either a raving madman or a genius ;-) and besides I optimized it so agressively that even if I did remember the particulars, it would be utterly impossible to map sourcecode back to high-level concepts.
That's not so bad, really, because this class is small and does nothing else but maintaining the board state. It's a black box. All I care about is the absolute fastest means of making and unmaking moves, and getting all state info I require. For the rest, all that matters is documenting the data formats. The thing should get the crap debugged out of it (the first time I will use automated testing, it would be insane to omit that in this case) and from that moment on it will be left untouched forever.
I really mean that, because I spent ages in optimizing the thing. Optimizing early is essential in this case, because otherwise you end up building a henhouse instead of a Gitmo, and you'll have to recycle the henhouse later anyway. Speed is not just part of the spec, it is the spec.
I mean, it's easy to hack up a state machine - what it's easy is to design one that maintains everything I need and is lightning fast. Wist lightning fast I mean as fast as possible. This needs explanation. "As fast as possible" depends on the following:
- choice of algorithm
- choice of language
- compiler optimization
The devil is in the details, however. Many people simply design an algorithm using what they learnt at comp. sci or from a book on algorithms (or perhaps they conjure up something clever), but I work a little differently. I look at the hardware at one end, and the problem at the other end, and I base my algorithm on the strengths of the hardware alone. Nothing else. I don't care about easy of implementation, I don't care about how much RAM is required, I don't care about anything, I just care about using the hardware as clever as possible to achieve the highest possible speed, when speed is requirement #1. In move generators, speed is the only requirement. All things being equal, more speed is better. Nobody cares that the code looks ugly when you make moves twice as fast, (and get high-level tactical data twice as fast) as the closest competitor.
So what did I do - I read the AMD optimization guide for their 64-bit CPU's and I based my design on the strengths of 64-bit processors and the peculiarities of caches, buses, RAM, pipeline stalls, instruction latencies and whathaveyou. I came up with a pretty bizarre solution, ending up with code that looks outlandish and, after optimization, does not look at all like a state machine for Go positions. It basically is a bunch of complex logical operations on a bunch of 64-bit registers. And what it yields is linked lists of chains and their adjacent chains (also empty chains) and their properties. Unique is that it generates Nth-order liberties with breakneck speed. Having access to the number of 4th-order libs at the same speed as other engines maintain the same state minus order-libs will yield an enormous advantage. Hence spending months on a fast state machine. Hell, even if it would take years I would still do it.
I had to switch to C for the TsumeGo engine - nothing else compiles to native 64-bit EXE and optimizes that code to the max. I turned off comments on this blog, to avoid having to explain why JITters and GC suck :-) The reason Java is so popular is mainly because the current generation of comp. sci profs don't understand pointers. The reason C# is popular is because C/C++ sucks at writing GUI-heavvy apps. But you can not, I repeat, can not, write a viable Go engine in those languages. To be viable, you have to be able to control what happens on the hardware level. Example: aligned_malloc and inlined prefetch instructions or NOPs. Is there such a thing in Java or C#? My definition of "viable" is the same as that of the top Chess-engine hackers.
The crux of this monologue is that sometimes, speed is the only requirement. And, perhaps counter-intuitively, you should not first make "something that works" and "optimize later", because you simply can't turn a llama into a leopard. Instead of performing expensive plastic surgery on the llama, go the extra mile to get a leopard.
Saturday, March 31, 2007
Virus reported on MFOG 11 CD
My Avast virus scanner finds the trojan Win32:Trojan-gen.{VC} in dieorlivesetup.exe, a program published by Mr. Lyu shuzhi, 67 Meihuacun, zhongshan rd.1, Guangzhou, China.
This program comes with the Go software I purchased, Many Faces of Go v. 11.
This is the only virus found on all my 13-odd harddisks. I hope the virus checker is wrong!
This program comes with the Go software I purchased, Many Faces of Go v. 11.
This is the only virus found on all my 13-odd harddisks. I hope the virus checker is wrong!
Saturday, February 10, 2007
Japanese XP Installation Blues
I am the proud owner of no less than four SE Asian OSes. And I never, ever managed, over the past half decade, to install a single one of them, using a virtual machine (VMWare).What does this screen say? What should I press? F3 gives a red countdown progress bar with another message, followed by a black screen and the inability to re-install.
The only way to repeat the process is to create a new VM.
I am trying different VM's, but so far, no luck.
Parallel Workstation doesn't work on x64, and Microsoft's Virtual PC does not even download. Instead it tries to save a "DownloadDetails.aspx" to my machine. That's using Mozilla. When using IE, I get the error: "This site may be experiencing problems".
Problems indeed. When I click "Help", this happens:
Friday, February 02, 2007
Brute Force and Nailing Jelly to a Wall
Since I am a weak-at-maths, testosterone-producing choleric, I greatly advocate the use of brute force to solve problems.
Don't get me wrong - I don't neccessarily mean physical force against living beings! Although it often helps too.
Example: When I was nine years old (32 years ago), my father put a lock on the door to prevent me from making firebombs with paint thinner and generally to prevent me from using his soldering torch, circle saw, collection of salvaged, formerly-wet firecrackers and other interesting stuff.
I did not see an easy method of opening that lock, when my parents weren't at home. So I used the "brute force" method: Me and a friend went door-to-door with the story that school had a project about keys. I made it all up. The story was that our teacher wanted to show us the differences between cyllinder lock keys and old-fashioned keys, padlock keys etcetera, yada, yada. An whether they could donate, for our educational project, some old, lying-around-in-a-drawer, unused keys.
They swallowed it hook, line and sinker and some got really excited about the thing, thinking it was an excellent idea of our teacher. After two key-scrounging expeditions, we had about two hundred keys. I kept them in an old cigar box. I was lucky that the lock on our attic door was a very cheap generic one and the key extremely simple, because one of the keys we collected fit.
It took my father a couple of years to find out that I had cracked the security on that door. Perhaps he noticed that the flammable liquids ran out too rapidly, and that the gas tank on his torch was usually near-empty.
I was quite a character. I had my own laboratory since I was six, it was another part of the attic, on the opposing side of my room. I did "harmless" experiments there, or so they thought. Just in case, I had placed sensors* at the bottom of the stairs that warned me when my father would sneak up to see what I was doing before I could hide the concentrated nitrous acid, hydrochloric acid and sulphuric acid. If you have that stuff, a selection of metals, some library books from the adult section (I was allowed to borrow adult books in that tiny village library, a right that funnily got revoked half a decade later, after I had read a few thousand books from the adult section) and a friendly pharmacist, you can make just about anything :-)
My parents didn't know, neither did they suspect, that I was synthesizing Nitroglycerine at home without using proper precautions. With hindsight, maybe my parents weren't so bad after all. They didn't deserve to be blown up, that's for sure. I can confirm that the stuff burns with a blue flame. And that you develop terribly painful black crusts on your nose when you try to smell too carelessly what's in an unlabelled bottle of concentrated sulphuric acid and your nose comes into contact with the bottle's rim.
It's off-topic, but fun nevertheless:
http://graeme.woaf.net/otherbits/jelly.html
Initially, my lab was stocked with bits & bobs my father didn't need, like very large 1.5 V batteries that he had stolen from one of his jobs, lots of wire, bolts and smallfry metal thingies. I did electromagnetic experiments with it. And I set steel wool to flames by shortcutting it. I also played with substantial quantities of mercury that I squeezed out of hearing aid batteries with something we call "bankschroef", in Dutch. And I tinkered with magnets. A lot. Soon, I went every Wednesday afternoon, out of school, with my bicycle through the streets in the industrial area to see what kind of electronic equipment companies had thrown away to be collected by the "bulky waste" truck.
What I could use for desoldering to build electronic devices I kept, and more complex stuff that looked expensive I took as well, because I had a much older friend that I traded some of that stuff with. He also bought acids for me when I needed them. Other stuff (like glycerol or aluminium powder and potassium chlorate) I got myself, with a little bluffing. But later they didn't sell any nitrates or chlorates any more, to nobody.
Those were interesting times. Nothing much to boast of, because a while ago, a kid in the US built a nuclear breeder reactor, demonstrating the old adage that persistence outranks talent and intelligence when it comes to achieving success.
*Copper pipe braces that I had hammered flat, used carpet nails to hammer them into the stairs underneath the carpet, flathead pins as contact and let wires run up underneath the carpet, all the way up the stairs and underneath the carpet of my room. A 4.5 V battery and a bicycle lamp were included in the circuit.
Don't get me wrong - I don't neccessarily mean physical force against living beings! Although it often helps too.
Example: When I was nine years old (32 years ago), my father put a lock on the door to prevent me from making firebombs with paint thinner and generally to prevent me from using his soldering torch, circle saw, collection of salvaged, formerly-wet firecrackers and other interesting stuff.
I did not see an easy method of opening that lock, when my parents weren't at home. So I used the "brute force" method: Me and a friend went door-to-door with the story that school had a project about keys. I made it all up. The story was that our teacher wanted to show us the differences between cyllinder lock keys and old-fashioned keys, padlock keys etcetera, yada, yada. An whether they could donate, for our educational project, some old, lying-around-in-a-drawer, unused keys.
They swallowed it hook, line and sinker and some got really excited about the thing, thinking it was an excellent idea of our teacher. After two key-scrounging expeditions, we had about two hundred keys. I kept them in an old cigar box. I was lucky that the lock on our attic door was a very cheap generic one and the key extremely simple, because one of the keys we collected fit.
It took my father a couple of years to find out that I had cracked the security on that door. Perhaps he noticed that the flammable liquids ran out too rapidly, and that the gas tank on his torch was usually near-empty.
I was quite a character. I had my own laboratory since I was six, it was another part of the attic, on the opposing side of my room. I did "harmless" experiments there, or so they thought. Just in case, I had placed sensors* at the bottom of the stairs that warned me when my father would sneak up to see what I was doing before I could hide the concentrated nitrous acid, hydrochloric acid and sulphuric acid. If you have that stuff, a selection of metals, some library books from the adult section (I was allowed to borrow adult books in that tiny village library, a right that funnily got revoked half a decade later, after I had read a few thousand books from the adult section) and a friendly pharmacist, you can make just about anything :-)
My parents didn't know, neither did they suspect, that I was synthesizing Nitroglycerine at home without using proper precautions. With hindsight, maybe my parents weren't so bad after all. They didn't deserve to be blown up, that's for sure. I can confirm that the stuff burns with a blue flame. And that you develop terribly painful black crusts on your nose when you try to smell too carelessly what's in an unlabelled bottle of concentrated sulphuric acid and your nose comes into contact with the bottle's rim.
It's off-topic, but fun nevertheless:
http://graeme.woaf.net/otherbits/jelly.html
Initially, my lab was stocked with bits & bobs my father didn't need, like very large 1.5 V batteries that he had stolen from one of his jobs, lots of wire, bolts and smallfry metal thingies. I did electromagnetic experiments with it. And I set steel wool to flames by shortcutting it. I also played with substantial quantities of mercury that I squeezed out of hearing aid batteries with something we call "bankschroef", in Dutch. And I tinkered with magnets. A lot. Soon, I went every Wednesday afternoon, out of school, with my bicycle through the streets in the industrial area to see what kind of electronic equipment companies had thrown away to be collected by the "bulky waste" truck.
What I could use for desoldering to build electronic devices I kept, and more complex stuff that looked expensive I took as well, because I had a much older friend that I traded some of that stuff with. He also bought acids for me when I needed them. Other stuff (like glycerol or aluminium powder and potassium chlorate) I got myself, with a little bluffing. But later they didn't sell any nitrates or chlorates any more, to nobody.
Those were interesting times. Nothing much to boast of, because a while ago, a kid in the US built a nuclear breeder reactor, demonstrating the old adage that persistence outranks talent and intelligence when it comes to achieving success.
*Copper pipe braces that I had hammered flat, used carpet nails to hammer them into the stairs underneath the carpet, flathead pins as contact and let wires run up underneath the carpet, all the way up the stairs and underneath the carpet of my room. A 4.5 V battery and a bicycle lamp were included in the circuit.
Wednesday, January 31, 2007
Nostalgia
The mess on my desk (picture of three years ago - it's much better since I my girlfriend moved in with me and we got a new place) is inversely exponentially proportional to the mess inside the sourcecode of Moyo Go.I remember a fight I had with my manager, six years ago. He told me - in front of his manager - that my source "wasn't Pascal". He literally said: "What's that - that's not Pascal!". In a tone of: "What's that - that's a giant, man-eating cockroach you smuggled into here!".
Him being a former tractor repairman and a self-taught code hacker, had never seen properly indented code. Not that his auto-didactness matters - I am like that too. One learns (or doesn't..) coding hygiene from decades of experience, I guess. It's a learning-from-one's-mistakes kind of thing. I wrote about coding standards here. I think that my traumatic exposure to RPG II might have something to do with my penchant for columnizing declarations and assignments.
Anyway - In a fit of Lymerage I told him in no uncertain terms that it would be best for the company if he and everyone else would adopt my coding standards. Our mutual boss thought it was all very entertaining and took me out for dinner. Soon afterwards, my chef got promoted away to a place where he couldn't do any harm.
Saturday, January 27, 2007
Moyo Go: "Googling" Go patterns
Speaking of asses, look what I found :-)
Some Go players still don't understand how Moyo Go's pattern expert system works. (When you read that PDF, note that "pattern" is not a move, but a potential move). This is often due to laziness (not reading the Help file). They think they are presented with an "analized position" or that they are getting "the solution to Joseki/Fuseki problems" or that Moyo Go presents them with the "best move".
And then they get very angry, or envious, or frustrated, and then they try to do as much damage as they can, using any possible way they can. Mark Boon, a strong Go player and Go programmer, when I offended his ego, offered 1000 USD for the first person to reverse-engineer MoyoGo's pattern system and throw it in the public domain. Philip Waldron, an even stronger Go player and a strong opponent of computer-assisted Go, said in the AGA eJournal that Moyo Go was nothing special, and should be avoided. And now, someone calling himself "Big Fan Of North Korea" (at least we have something in common) got creative on my ass and is shouting everywhere that he posted this image on the net. As part of my ass-symmetrical warfare against enemy combatants, I repost it here.
So - about Moyo Go's pattern system. It's not like a "scientific calculator". It is a pattern-recognition device (17 million normalized patterns) and a statistical database, for those patterns. Also, it is a hyperfast pattern-matcher (no time delay).
So, you move the mouse over board points and immediately you see browsable diagrams of the same local positions in other people's games, and how popular that move was in terms of statistical move likelihood in the average global context, winning percentages, average rank and -date, etc.
Moyo Go Studio is the "Google" of Go information. It's not a "calculator", it is a superfast, sophisticated search engine. Up to you to make the right searches, and up to you to do something with its information. All Moyo Go does is showing you the most likely moves, you have to judge those moves in their global context and you have to explore the alternatives, with or without using the program's search engine and pattern expert system.
Anyway - it's attacks like these that keep me going :-) Note how buttbuddy talks about "ease of solving Joseki and Fuseki problems". Totally missing the mark. I guess it's easy to misinterpret this kind of software. The idea is new. "Googling" Go game patterns - a revolution in the Go software world.
When Google started, all through its early years, there was a lot of noise about how "What you find on the Internet is mostly useless crap". And how "You can't manage to find what you are looking for, with Google". And how "It's much better to go to the library and find a reliable book about the subject". And "The ease of using Google to find information on the Internet will rot your brain".
:-D
Some Go players still don't understand how Moyo Go's pattern expert system works. (When you read that PDF, note that "pattern" is not a move, but a potential move). This is often due to laziness (not reading the Help file). They think they are presented with an "analized position" or that they are getting "the solution to Joseki/Fuseki problems" or that Moyo Go presents them with the "best move".
And then they get very angry, or envious, or frustrated, and then they try to do as much damage as they can, using any possible way they can. Mark Boon, a strong Go player and Go programmer, when I offended his ego, offered 1000 USD for the first person to reverse-engineer MoyoGo's pattern system and throw it in the public domain. Philip Waldron, an even stronger Go player and a strong opponent of computer-assisted Go, said in the AGA eJournal that Moyo Go was nothing special, and should be avoided. And now, someone calling himself "Big Fan Of North Korea" (at least we have something in common) got creative on my ass and is shouting everywhere that he posted this image on the net. As part of my ass-symmetrical warfare against enemy combatants, I repost it here.
So - about Moyo Go's pattern system. It's not like a "scientific calculator". It is a pattern-recognition device (17 million normalized patterns) and a statistical database, for those patterns. Also, it is a hyperfast pattern-matcher (no time delay).
So, you move the mouse over board points and immediately you see browsable diagrams of the same local positions in other people's games, and how popular that move was in terms of statistical move likelihood in the average global context, winning percentages, average rank and -date, etc.
Moyo Go Studio is the "Google" of Go information. It's not a "calculator", it is a superfast, sophisticated search engine. Up to you to make the right searches, and up to you to do something with its information. All Moyo Go does is showing you the most likely moves, you have to judge those moves in their global context and you have to explore the alternatives, with or without using the program's search engine and pattern expert system.
Anyway - it's attacks like these that keep me going :-) Note how buttbuddy talks about "ease of solving Joseki and Fuseki problems". Totally missing the mark. I guess it's easy to misinterpret this kind of software. The idea is new. "Googling" Go game patterns - a revolution in the Go software world.
When Google started, all through its early years, there was a lot of noise about how "What you find on the Internet is mostly useless crap". And how "You can't manage to find what you are looking for, with Google". And how "It's much better to go to the library and find a reliable book about the subject". And "The ease of using Google to find information on the Internet will rot your brain".
:-D