[computer-go] incremental liberty counts

[Mark Boon]

On 31-aug-06, at 12:48, Don Dailey wrote:

>
> It doesn't save time for me.   Yes, you do save time by not having to
> clear the marks,  but you have to do an extra test inside the tightest
> loop which you did not have to do before.   So you are doing an extra
> test and an extra memory reference to a different location inside a
> tight loop.
>
> The main difference is illustrated by just these 2 code fragments  
> of the
> fragment I already showed.   I again show the old way, and the new way
> with a description in english:
>
> OLD :
>        if (p->bd[t+1] == ene) {
>
> Here in english:  IF the board location t+1 has an UN-FLAGGED enemy
> stone ...
>
>
>
> NEW :
>        if (p->bd[t+1] == ene && clear[t+1] != age) {
>
>
> In english:  IF the board location t+1 has an enemy stone on it AND we
> did not look at location t+1 in the current invocation of this
> function ..
>
>
> Do you see that before, I could do one test to see if there was an
> un-flagged enemy stone but now I have to see if there is an enemy?
>
> Apparently, this cancels out the benefit of not having to clear the  
> flag
> bits once we exit.
>
> Another issue which isn't particularly relevant to this discussion is
> that if I make a parallel version of Lazarus,  I can't use this code
> unless I have separate board marker arrays for each process.
>

OK, I think I now see what you mean. Each assignment that clears the  
mark gets replaced by the extra test and thereby the savings are  
small. The one thing I could argue in favour of using the marking  
technigue is that it's more explicit and probably safer as a general  
means of marking.

In case of parallel processing, indeed you need an extra copy of most  
of your data-structures, including the data-structure used for  
marking. You also need an extra copy of the board etc. I assume. I  
don't see why this is something specific to parallel processing. More  
whether in general you prefer to save a few bytes by not having a  
separate marking array.

Mark