Re: computer-go: unmake move?

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

Yes,  my evaluation  is very  simple, almost  all of it  is calculated
before the search begins.   I do have a  specific move ordering I  use
but it  doesn't involve a full   blown sort.  The  program does little
serious work (and it probably shows  because it doesn't play very well
either!)

I  think this is   a  good argument  in favor  of  copying  state.  My
program, because  it does  very little, should   show state copying at
it's very worst  if it's  in fact a    bad idea.  If  I added  serious
evaluation then we could well imagine  that execution time would cease
to be dominated by making moves and copying state.  As you said, "With
very slow evaluations, unmake time is not an issue."  

So I think it probably  doesn't hurt me to avoid  unmake and just copy
the state  as I do.  And  I really enjoy the  virtue of  not having to
deal with the nitty gritty details of un-making.

Now, if only I knew how to write a strong go program ...  :-)

Don



   X-Sender: fotland@xxxxxxxxxxxxxxxxx
   X-Mailer: QUALCOMM Windows Eudora Light Version 3.0.5 (32)
   Date: Thu, 08 Jun 2000 08:03:28 -0700
   From: David Fotland <fotland@xxxxxxxxxxxxxxxxx>
   References: <3.0.5.32.20000607205243.015ecaf0@xxxxxxxxxxxxxxxxx>
   Mime-Version: 1.0
   Sender: owner-computer-go@xxxxxxxxxxxxxxxxx
   Precedence: bulk
   Reply-To: computer-go@xxxxxxxxxxxxxxxxx
   Content-Type: text/plain; charset="us-ascii"
   Content-Length: 1308


   You are running on a computer with a cache :)  Your state
   copies are in the cache, so they don't go to memory, so memory
   bandwidth is not a problem :)

   300K nps is very good.  You must have a very simple evaluation
   function, and a very fast move sorter. 

   Most of the strong go programs get less than 100 nps, since the
   evaluation is so slow and complex.  With very slow evaluations,
   unmake time is not an issue.

   Many Face's tactical analyzer gets about 50,000 nps on a fast PC.
   Its time is dominated by move selection and sorting.  Evaluation
   for string tactics is trivial (just count liberties).

   David

   At 02:14 AM 6/8/00 -0400, Don Dailey wrote:
   >
   >> Usually you are unmaking moves near the leafs, so the
   >> old position is still in the cache.  So memory bandwidth
   >> is not a problem.  Even if there is no cache, so copies
   >> go to memory, Pentium PCs should be able to copy over 100 MB/s.
   >> If the state is 1000 bytes, that limits performance to 100,000
   >> positions per second.
   >
   >But how can that be?  I know I am getting about 300,000 per second and
   >my state size is almost 5000 bytes!   I'm not cheating either, I don't
   >count a node unless I do a state copy.
   >
   >I will go over the code to see if there  is some error counting nodes,
   >but I am pretty sure I'm doing this correctly.
   >
   >Don
   >
   >