Re: [computer-go] Data structures for Go

[Arend Bayer <arend.bayer@xxxxxx>]

Hi Don,

I doubt I need to explain this to you, but I think it is missing from
your discussion:

Don Dailey wrote:
> In my program,  I never explicitly "undo" a move, I  simply keep a new
> separate game state copy for each node visited during the search.
>
> In the past, a few have been critical of this idea, claiming it is way
> too slow to copy thousands of  bytes just to make small state changes,
> like placing a stone on an intersection.  I think this was true in the
> past, but processors  have changed a lot in a short  time.  The code I
> write now would not work very well on old processors.

> There are 2 possible disadvantages:
>
>   7. Your program MIGHT run slower.
>   8. Memory (data) footprint will probably be larger.

> The memory footprint will not increase much unless your position state
> is pretty huge.  But your code  will be smaller (even the code to make
> a move will  be smaller and simpler because you  won't have to provide
> all the undo hooks.)

The problem is IMHO not so much the memory footprint, but the performance
costs by potentially worse (processor) cache behaviour. In particular,
it is not sufficient to look at the time of the state copying function
in profiles.
Whether this is noticable for a particular program can depend on many
factors, of course; you will have to measure if you decide to care about
the performance.

Regards,
Arend


-- 
Arend Bayer, Flodelingsweg 27a, 53121 Bonn, 0228-9813803
arend.bayer@xxxxxxxxxxxxxxxxx

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go