[computer-go] Language War!

[Don Dailey]

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/