Computer Go Language Question
So you want to write a computer go program?
If you're a programmer, you probably know C or C++.
But are these the best languages for prototyping/experimenting with a go program?
Here are some other languages to consider: (I'll add "Go" specific info if/when I try them out)
- Basic: easy coding but a bit old fashioned.
- Common Lisp: Strong tradition in AI programming
- Haskell: Brilliant but brain squeezing, probably for the engine only (GUI? | Haskell isn't really suited for GUI).
- Java: GUI, platform independence
- OCaml: Fast, flexible, multi-paradigm (functional, imperitive, OO)
- Perl: Easy to learn, flexible
- Prolog: Rapid prototyping
- Python: Easy to learn, flexible
- Ruby: Similar to Perl and Python, some say better OO
If you are planning to write a Monte Carlo program, then it is vital that your playouts run as fast as possible. For this portion at least, you should choose a compiled language such as C, C++, Pascal, Ada, or OCaml. Or you can use an existing library for this part, such as lib EGO or Fuego.
Anonymous: If you are just gonna program a board and pick out random legal moves, any language will serve the purpose well. However, if you are not, please keep reading.
Writing a go program that plays better than 10k is a huge project. My suggestion is to think it through carefully before you decide to start. Consulting other documents to have a idea about how many different subroutines you need, and realize that you can't get away from at least a couple hundred hours of programming time if you are starting form scratch.
If you still decide to try, it will be best if you know at least two programming language - one high level and one low level.
You certainly need the high level one or you will never finish the program. There are way to many aspects of the game you need to consider (translation: lots and lots and lots of subroutines), if you don't have any idea about them yet, maybe it's not a bad idea to think through first.
Enough said, for the high level language, use anything that you can code the fastiest, and I meant it. "Coding fast" is the key here.
If you are not particularly strong at any high level language (or if you are familiar with one of these), use perl, python, or ruby. They are fast to learn, fast to code. My personal preference is perl - decent coding length and coding speed.
If you are strong (only if you are strong) at C or C++, it might not be a bad choice; if at some point you are stuck, you can always try to "borrow" codes from GNUgo.
Now let's talk about the low level language. You don't need this one if you are not planning to write a top class go program. Low level programming language is for running speed, it is useful to have fast running code for specific tectical analysis which recursives or loops a lot (eg, life death problem, tesuji problem)
Of course, another way to get around this is to invest in a supercomputer or a cluster with serveral computers. However, even so, a fast running code is still preferable.
So.. what's a low level language? Assembly. Nothing beats assembly at this aspect, it's your only choice. And no, you don't need 10 years of experience. You only need to know the basics well enough to release the "black magic" within.
- Ian: Ugh, no. Only one program I know of has been written in assembly (Handtalk), and the author later rewrote it in C. The main problems: long term maintenance and portability. Assembly locks you to one processor/OS, and processors go out of date rather quickly these days. Assembly also takes a lot of discipline to write well. Trust me, stick to C instead. In these days of complex pipelined, multicore processors, C compilers more easily give you optimized code than even straight assembly anyway.
These might be kind of off topic, but I still decide to put them in because I believe these will be very help for people who are not familiar with big programs.
If you are coding programs for living, you can skip the rest, because you shouldn't find anything that you don't know yet. However, if you are not, there are some suggestions I have:
Whatever programing language you choose, besides the basic variable operations, learn about building library\package\object first. They are important in terms of organizing your program. Don't expect to finish your go program in one giant page.
Second, familiarize with debuggers. Expect to run into lots of logic errors that you can't trace easily due to the size of the program. Many people I know stay at the stage of inserting a "print" function here and there to debug; get beyound that and it will save you a lot of time later on.
Finally, document well. Always put comments on every piece of code. Organization is very important. Trust me, if you are not coding for living, this go engine is probably going to be the biggiest program you have ever code.
Gorobei: Common Lisp gets my vote: fast, rich, interactive, and flexible. I'm no Lisp expert, so my attempt to write a Go Program is also an attempt to learn CL. Because I'm a novice Go player, my Go programs have been full of false assumptions and poor models of aspects of the game: CL's multi-dispatch object system has helped greatly in letting me reshuffle things without redesigning class hierarchies, etc. I've written over 500,000 lines of C/C++, so it is my first language, but I'm finding CL more expressive and less constraining.
MrKoala: As a CaML expert, I recommend OCaml. Not only because I like this language, but also because it is strongly typed. As far as I know, CL is an untyped language. I'm also trying as a personal research subject to use CaML syntax for generating optimized code in other languages.
(note from NeonSquare?: CL is not an untyped language. It is a strongly typed language too. The difference is that ML is statically typed and CL dynamically typed. For optimization CL supports optional weak static typing too.)
Jan: I'm writing my Go program in Haskell (a lazy, functional language). No real reason for the language choice except that I like it a lot and that it allows coding at a high level of abstraction. And besides, the name HaGo can also stand for Hand of God :-)
WilliamNewman: CL is nearly in a class by itself, both in good ways and in bad ways. Two good ways are its "macros" (actually general code-writing code) of unparallelled power, and its integration of interpreter and debugger with user-defined printing operations (so you can view your data in high level form, even inside debugger operations like backtraces). One bad way is the way that code-writing code makes life difficult for useful tools like "make". OCaml is extremely impressive in lots of ways, and full of powerful ideas (e.g. functors), but when I tried it (late 2001) I was very frustrated by its difficulties in expressing mutually recursive data structures (e.g. an object representing a square of the Go board, where one of the slots of the object is a hash table, and the hash table values include collections of squares on the Go board; or see here for more info). I think in a language for working with Go, you want that kind of thing to be easier than it is in C++, not harder!
- The "and" keyword is great for that, i.e.:
type foo = makes references to bar
and bar = makes references to foo
Hi, I've listed the languages you've given below with my personal thoughts of them. This will be heavily biased by my likes and dislikes, so take with more than a grain of salt.
I wouldn't use ML, not because it is a bad language, or inappropriate here, but simply because the tools for tracing and debugging it aren't good enough. Trying to find why your program did something stupid in a language like ML is slow and painful.
Lisp is fine if you know it, though novice lisp programmers seem to produce worse lisp than novice java programmers produce java. I like how lisp gives me 80% of the benefits of a functional language (I wish it had currying and lazy evaluation) and it lets you break the rules quickly and easily when you want.
- (Hmm, actually in standard ANSI Common Lisp you can do currying. See Paul Graham's site for an example. As for le, maybe see Steele's book (series is semi-standard and available) or various other places for various types. If you mean something different, can you make what you want using a macro? -- evpsych)
- Why write macros when Haskell has all of this built in, has a cleaner syntax, and I don't have to use Emacs! (bleh) -- Anonymous
- "cleaner syntax"? What can be cleaner than s-expressions? -- Harleqin
I'd choose python over perl and Ruby. They are very similar in their intended use, and python is easiest to read and write. I think the problem isn't especially suited to python, but it isn't especially unsuitable either.
Java's gui seems useless for writing a computer go program, which rules out your advantage. Also, you shouldn't have any OS dependent code in the program, just simple GTP stuff, so Java's machine independence becomes moot, too. The built in class libraries might be a point in Java's favour.
I dislike prolog because I find its search type logic very easy to emulate in a decent functional language, and it doesn't have the benefits of a functional language. But if you think you can write all the rules as logic tests, then prolog would help.
C/C++ have a number of advantages: Many tools, fast execution, lots of existing code. They also have their share of disadvantages: Hard to read, low level, so slow to write.
Personally I would be choosing between C++, Lisp, and Haskell, the choice depending on the goals. Any of the languages you've got could be used, although I wouldn't personally touch Ocaml (hiya MrKoala!) Well, I've tried to provide extra information rather than ruling anything out, I hope it helps rather than confuses you :-)
Kosh I recommend Python. Pro: easy to prototype, easy to learn. My final assignment for my study was done in Python, with a lot of experimenting (see Kosh). Contra: speed. When a good (computational intensive) idea has matured, it's generally a good idea to port it to C++, for example. Currently there are tools being developed to speed up python.
JaredBeck(3/3/05): I'm writing a GTP engine, with no GUI. My AI is a blackboard system, so a highly Object Oriented language would be helpful. With the exception of life+death searches, I want to do very little bruteforce searching, so I do not need the runtime efficiency of say, C. So I choose ... Java!
(atyk): This is really a stupid question. Any language will do if you have good ideas, no language will compensate for their lack. Program in what you're comfortable with!
Jeff: I have lots of good ideas -- far more good ideas than time to implement them. I suspect this is the case for many Computer Go programmers. Unfortunately, I often discard an idea even though it seems promising, just because it will be a pain to implement or difficult to fit into my current architecture. If this is something you experience also then I recommend a fast-prototyping or highly-flexible language. For many of your ideas, this will be the difference between the idea getting tested or not. And let's face it -- it's often hard to tell how well an idea will do until it is seen in action.
Frank: Pascal hasn't been mentioned yet? Pascal - a strongly typed language, can compile to just as efficient code as C can. The combination Free Pascal/Lazarus gives you IDE-based 64-bits cross-platform development incl. GUI widgets and various libraries.
What I like about Pascal is its easy string manipulation, the runtime bounds checking and especially its strong typed-ness. I also like its verbosity, my brain likes to see begin and end instead of curly braces. Another powerful feature is the ability to mix in Assembly right through your code, something that AFAIK the latest MS C++ compiler doesn't even offer any more.
Batavia? I don't think being able to add assembly is a powerful feature. In fact it is a horrible feature. It can easily break optimalizations a compiler might be able to make, and there are very few people who can do register allocation better than a compiler. (No, unless you have at least 10 year experience in assembly programming you are not one of them. Modern compilers are VERY good at it). Give me any non-trivial assembly program and i'll show you a C program that does it better.
Frank: I wrote a compiler 20 years ago so I qualify for the "10 year" condition :) In some cases, compiler technology just can't achieve what an experienced human can achieve.
jvloenen: Just program in the high level language you like. After finishing the program, find the hot spots in your project. Then analyse and optimize (on high level!) the algoritm first. The very last step is ML optimization of your hot spots. Most often the code generated is optimal (enough). Sometimes it isn't however and you can replace (small) parts by hand written routines.
Willemien not for realy a go playing program, but more quick (coding i mean) and dirty sgf editing I use old fashioned Basic. But that is more because i know that language. Advise for programmers, if you can do it by coding or by using an complicated but fixed array. USE an array
jvloenen?: Has there been any experience with moving the Monte Carlo simulation to the massive parallel possibilities of the modern GPU's yet?
- Sort of? At the last Computer Olympiad, one of the participants was running on a cluster of 8 PS3s! Programming their individual Cell processors is similar to programming a specialized GPU. I agree that this is an untapped resource for game searches, especially for pattern recognition and Monte Carlo playouts.
Alistair Turnbull I don't agree with very much of this page.
For the GUI: Don't write one. Instead implement the Go Text Protocol. It only takes a couple of hundred lines, in any programming language. It will allow your users to play using whatever GUI they like (I use gogui). As a side-benefit, there is lots of third-party plumbing that speaks GTP. For example, you can easily set up tournaments and unit tests. GTP is also the protocol you need to implement if you want your robot to play on the KGS Go Server. Therefore, this requirement does not in any way constrain your choice of programming language.
For performance: Don't write in assembler, or even in C, until your program already works well in a higher-level language, and somebody has offered to pay you to improve its performance. You do need to worry about performance a bit to write a Go computer. However, a language such as Java, ML, OCaml or Haskell is plenty fast enough: a factor of two slower at most, if you do it right. It is easy to recover a factor of two by algorithmic improvements, if you have not first ham-strung yourself by writing in a language that is insufficiently high-level. Disco demonstrates that you can even get reasonable performance using Python + Shed Skin. The only languages to avoid for reasons of performance are (interpreted) Python, Perl, Ruby, Basic, and their ilk.
For the record, I use Java for my Go programs, and my collaborator prefers ML. And yes, we both know C and assembler.