[computer-go] Language War!

[Peter Drake]

Well, I'm glad to hear that it's not just me who rewrites his core  
data structures every year.  :-)

I had one version where I maintained two bitmaps (one for black, one  
for white) and did various shifting operations. It was fast, but if I  
ever wanted to traverse a block I had to convert it into a list of  
points, which cost me as much time as I saved.

Since I never have to do that in Monte Carlo, I should be able to  
make a lightning-fast implementation...

Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/


On Jul 29, 2006, at 10:53 AM, Don Dailey wrote:

> On Sat, 2006-07-29 at 18:19 +0200, Rémi Coulom wrote:
>> Peter Drake wrote:
>>> Yes. For example, GNU maintains the number of stone and liberty  
>>> counts
>>> of each string, and we don't need that information.
>>
>> It is better to have it.
>
> I am not so sure about this.    One of my programs incrementally  
> kept up
> with the liberty counts of every group.  I think I did it fast and
> efficiently.  I didn't maintain anything more than stone_count and
> liberty_count for each string.
>
> Then I rewrote for monte/carlo.   I threw away all the baggage of this
> and kept a very simple data structure.  It was clearly faster.
>
> The old program had the characteristic that it greatly sped up near  
> the
> end of the game,  while the newer data structure tended to remain
> constant.    But earlier in the game, the new data structure was  
> clearly
> faster and amortized over the whole game is was faster too.
>
> So it was a win no matter what, but when you consider that you should
> probably be optimizing for the early part of the game,  it's really a
> big win.    If you look at the games on CGOS, you will see that most
> games are "over" in just a few moves.
>
> I say I am "not so sure" because I don't know how good my OLD code was
> compared to the ideal.  It's possible that my old implementation was
> flawed somehow.
>
> When I test for captures I use a non-recursive flood fill type of
> algorithm using a loop.  There is very little conditional branching
> compared to incremental updating which has a lot.   I know this is  
> a big
> deal with processors but I don't know how much.   I know that with my
> method some moves take a lot longer to execute and some go a lot  
> faster.
> I believe the "common case" it is much faster.   But I could be wrong.
> Your program is a stronger so maybe I figured this wrong.
>
> My first go program did the incremental updating, because I was  
> sure it
> would be a big win even if I used it just for making moves.   You may
> have caused me to try again.
>
> - Don
>
>
>
>
>> ... You need the number of liberties to determine
>> rapidly that a string is captured. You need the size of the string to
>> merge the new added stone to the longest string.
>>
>> You need no undo for Monte Carlo. This is where you save the most.
>>
>> Rémi
>> _______________________________________________
>> computer-go mailing list
>> computer-go at computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/