Claus Reinke wrote:
I finally got around to making my code for random Go playouts available. Here it is:
Cool!-) To reciprocate, I've temporarily put a snapshot of my code here: http://www.cs.kent.ac.uk/~cr3/tmp/SimpleGo.hs
I've not yet decided whether to be depressed or encouraged by the timings;-) without mercy rule, your code simulates at about 17k/s runs here, vs only about 3k/s for mine. There are some obvious aspects, such as hardcoding the boardsize isn't quite as straightforward when GTP allows to change it at runtime, but I don't think that explains the bulk of the difference.
Different board sizes would be best done by just compiling the code multiple times, for 9, 13 and 19.
I do hope there are lots of small things to learn (perhaps you could summarize your findings in a performance tips paper?-)
Partly it's making good representation choices: lots of unboxed mutable arrays, and the IntRef type. I happen to know that boxed mutable arrays expose poor behaviour in GHC's garbage collector :-) If I could unpack MutableByteArray# directly in an enclosing constructor, that would make this code a lot faster, by removing more indirections. Duncan Coutts has been thinking about similar things in the context of bytestring. Most of the other things I found were really just bugs in GHC. For example, I wanted to use newtypes in various places, but I didn't get as good code as just using a type synonym. We had problems with record selectors not optimising well, which is now fixed (I believe).
but at first glance, I suspect the difference in approach: my early experiments suggested that maintaining chains/strings wasn't going to be more efficient than following the affected parts of strings when needed - but I didn't think of representing strings as cyclicly referenced lists (which allows for string merge in constant instead of linear time). Nice idea!-)
It wasn't my idea - I don't know where it originally came from, but it was in the F# code I translated. String merge isn't really O(1), since you have to traverse one of the strings to update its string Id, maybe that would be better done by having another level of indirection. Cheers, Simon
Thanks, Claus
If someone were to make a nice library API on top of this and upload it to hackage, I'd be delighted. Hack away.
A GTP interface would be useful, to allow playing against other bots.
Cheers, Simon
Simon Marlow wrote:
Claus Reinke wrote:
Do you have an example of a mutable state/ IO bound application, like, hmm, a window manager or a revision control system or a file system...?
If you're looking for a challenge, how about this one (there used to be lots of Haskellers into this game, any of you still around?-):
http://computer-go.org/pipermail/computer-go/2008-October/016680.html
[ catching up with old haskell-cafe email ]
Interestingly, I did this a while ago. Here's my results:
$ ./Bench 1 100000 b: 14840, w: 17143 mercy: 67982 elapsed time: 3.42s playouts/sec: 29208
so, nearly 30k/sec random playouts on 9x9. That's using a hack that stops the game when the score is heavily in favour of one player, it drops to around 20k/sec with that turned off.
Not bad, but probably I'd guess an order of magnitude worse than you can do in tightly-coded C. The Haskell implementation isn't nice, as you predicted. Also the code is derived from some non-free internal MS code, so unfortunately I can't share it (but I could perhaps extract the free bits if anyone is really interested).
W wins slightly more often I think because komi 5.5 on a 9x9 board is a tad high.
It does parallelise too, of course:
$ ./Bench 8 100000 +RTS -N8 b: 14872, w: 17488 mercy: 67584 elapsed time: 1.00s playouts/sec: 99908
though still room for improvement there.
Cheers, Simon