[Haskell-cafe] Re: Go Haskell!

[Simon Marlow]

Claus Reinke wrote:
>> I finally got around to making my code for random Go playouts 
>> available. Here it is:
>>
>>   http://www.haskell.org/~simonmar/goboard.tar.gz
> 
> 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
>>