Re: [computer-go] Data structures for Go

[Don Dailey <drd@xxxxxxx>]

>  The only way to do it is to run benchmarks, and I don't think ...

Run benchmarks and decide for yourself, that's what I advocate too.  I
am  only   suggesting  an  alternative  and  have   already  given  my
disclaimer, your results may or may not agree with mine.


> Could you say us what is a 'old' processor and a 'modern'
> one? Seems to me this a very fast varying concept :-)

I used  the term loosely.  I mean  stuff we are using  today which are
fast (by todays standards!)

I have heard  that "modern processors" are designed  to do fast memory
to memory  copies.  You  seem to believe  that memory copies  are done
serially, but I  had assumed that they must be  done in parallel.  I'm
sure someone on this group knows the answer and will comment.

Anecdotally, I  could not do state  copies many years ago  in my chess
programs  because they slowed  things down  too much,  and now  I can.
What  has changed?  Computer  hardware and  compilers.  It's  the same
with Go.   I would mention that I  do everything in 9x9  go which does
produce smaller  states, but I can  compiler for any  board size.  I'm
sure I did this experiment when I had undo on 19x19 though.

One thing you can  do to find out how important any  of this is, is to
see how much time your  program even spends making and unmaking moves.
Many have posted  really low numbers of nodes per  second for their Go
programs.  That tells me very little time is spent making and unmaking
moves in some  programs in which case it might not  matter at all.  In
such a case you might as well go for the simpler program that does not
need undo and all the supporting data structures for bookeeping.

If  your program  does spend  most of  the time  in  ladder/life death
searches, and most of this time  is making and unmaking moves, then it
behooves you to do the fastest  thing, whatever that is.  You might be
suprised to find the extra programming  effort is not worth it, or you
might not.   To me, it's  worth the trouble  to run the  benchmark and
find out.

Even if you get a slight slowdown, you may think it's worth it to have
cleaner code,  easier to understand  code, easier to debug,  easier to
experiment with etc.  Or you might not.

Incidently, my  program spends  a lot of  time making moves,  since it
does very little of anything else being a stupid program.  So the undo
test is a  fair measure of the realive merits of  getting rid of undo.
For comparison,  I have a Pentium  2.4 GHZ machine and  do around 450K
nodes  per  second.  I  believe  most  programs  are doing  much  more
sophisticated things and  thus look at fewer nodes  but I don't really
know this for sure.  In such a case, move making/unmaking speed is not
a bottleneck anyway.  Life is too short,  get rid of undo :-)

Don






   From: "Antoine de Maricourt" <antoine.de-maricourt@xxxxxxxxxxxxxxxxx>
   Date: Mon, 13 Oct 2003 21:37:15 +0200
   Content-Type: text/plain;
	   charset="iso-8859-1"
   X-Priority: 3
   X-MSMail-Priority: Normal
   X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2800.1165
   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,

   Could you say us what is a 'old' processor and a 'modern'
   one? Seems to me this a very fast varying concept :-)

   Memory bandwith is always increasing, but processor speed is also
   increasing at the same time. And the point is that if you perform only state
   copying, the 'computing' units of your processor are idle at the same time.
   On the other hand if you perform only computation, you could very well
   perform state copy at the same time for free (provided your computation
   uses only data within registers).

   The best performances are probably achieved with a well balanced
   strategy that makes sure the processor has no unit idle at any time
   (which is very difficult, and which is why Intel introduced hyper-threading
   technology).

   The only way to do it is to run benchmarks, and I don't think we can
   state that such or such strategy is better for "modern" hardware. It will
   mainly depend on the ratio between memory bandwith and clock
   speed (but processor's intrinsic parallelism should be taken into account
   also).

   To answer your last question, I use undo.

   Regards,

       Antoine

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