Re: [computer-go] Data structures for Go

[Don Dailey <drd@xxxxxxx>]

Yes, I'm glad you brought that up.

As you say,  how this affects cache could be a  big factor and may 
make the idea unworkable for some programs/hardware.

The experiment of doing the dummy  state copies as a kind of quick and
dirty  test  is  probably  still  a reasonable  test,  since  if  it's
succesful,  you  are  probably   safe.   This  assumes  that  you  are
simulating the memory usage farily accurately.

Thanks for bringing that up.  My email was longer than I wanted and I
decided not to go on about that originally.

Don


   X-Authentication-Warning: linux.local: arend owned process doing -bs
   Date: Wed, 8 Oct 2003 22:23:05 +0200 (CEST)
   From: Arend Bayer <arend.bayer@xxxxxxxxxxxxxxxxx>
   X-X-Sender: arend@xxxxxxxxxxxxxxxxx
   Content-Type: TEXT/PLAIN; charset=US-ASCII
   X-BeenThere: computer-go@xxxxxxxxxxxxxxxxx
   X-Mailman-Version: 2.1.2
   Precedence: list
   Reply-To: computer-go <computer-go@xxxxxxxxxxxxxxxxx>
   List-Id: computer-go  <computer-go.computer-go.org>
   List-Unsubscribe: <http://computer-go.org/mailman/listinfo/computer-go>,
	   <mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=unsubscribe>
   List-Archive: <http://computer-go.org/pipermail/computer-go>
   List-Post: <mailto:computer-go@xxxxxxxxxxxxxxxxx>
   List-Help: <mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=help>
   List-Subscribe: <http://computer-go.org/mailman/listinfo/computer-go>,
	   <mailto:computer-go-request@xxxxxxxxxxxxxxxxx?subject=subscribe>
   Sender: computer-go-bounces@xxxxxxxxxxxxxxxxx


   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

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