Re: computer-go: Most simple Go rules

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   > >  "Superfast" is relative. I'm sure my ladder-search would be
   > much slower if
   > >  it had to check for super-ko, so it only checks for simple ko.
   >
   > I'll  bet you are wrong.   Zobrist key overhead is absolutely minimal.
   > Not only  that, but you might   even gain a   few cutoffs in  a ladder
   > search that simple ko would miss.  You can store keys  in a hash table
   > for ko testing, you do not need to search linearly backwards.
   >

   Well, I published my search module, so you can try it :-)

   Updating the key is fairly fast. But in case of storing and looking up
   there's a trade-off between search-time and storage-space. If you want just
   a single array lookup you need a very big table to prevent accidental
   overwriting of values. If you want to use a reasonable size table, you'll
   need to do more work to store and look up the data.

No, you  only  need a tiny hash   table, with perhaps   a few thousand
entries to be super safe.  When you make a move on  the board, you add
the position to the table.  When you un-make a move,  you take it out.
Moves that have already  been played in the  game (before your search)
never get backed out.   Your table will never have more entries in it
than the longest line (actual game + longest search depth.)   

The only issue here is to not  overwrite entries.  Since you are doing
adds  and deletes  this  is slightly more  complicated,  but there are
complicated solution and simple workable solutions to this.  I will go
into this if you ask, but you probably already know this.


Don