home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / gnu / chess / 537 < prev    next >
Encoding:
Text File  |  1993-01-25  |  2.2 KB  |  48 lines
  1. Newsgroups: gnu.chess
  2. Path: sparky!uunet!retix.com!dspencer
  3. From: dspencer@spock.retix.com (David Spencer)
  4. Subject: Re: Iterative Deepening
  5. Message-ID: <1993Jan25.214918.18646@spock.retix.com>
  6. Organization: Retix, Santa Monica, CA USA
  7. References: <C15r40.D1r@sju.edu> <21659@ucdavis.ucdavis.edu> <JON.93Jan25110340@cas.org>
  8. Distribution: gnu
  9. Date: Mon, 25 Jan 1993 21:49:18 GMT
  10. Lines: 36
  11.  
  12. In article <JON.93Jan25110340@cas.org> jon@cas.org (Jon Vander Hill) writes:
  13. >>>>>> On 22 Jan 93 07:34:07 GMT, lim@toadflax.cs.ucdavis.edu (Lloyd Lim) said:
  14. >
  15. >> In article <C15r40.D1r@sju.edu> tmoody@sju.edu (T. Moody) writes:
  16. >>>
  17. >>>My real problem is with (b).  Levy and Newborn say
  18. >>>something about searching at a given level and storing lots of positions
  19. >>>in a hash table before moving to the next level.  Is this the only way
  20. >>>to do it?  I don't know a thing about hash tables and, from what I have
  21. >>>read it looks like it's over my head.
  22. >>>
  23. >>>So my question is, can iterative deepening be usefully (if not
  24. >>>optimally) accomplished without using hash tables?
  25. >
  26. >> Iterative deepening is commonly used with transposition (hash) tables,
  27. >> but it doesn't require them.  Iterative deepening just means increasing
  28. >> the search depth by one each time (i.e. - searching to a depth of 1,
  29. >> then 2, then 3, ...).  You don't need to use transposition tables.
  30. >> They are just used to speed things up, because many of the same nodes
  31. >> are encountered again when you search to depth n+1.
  32. >
  33. >One the the more expensive routines in a chess programs is the
  34. >move generation function.  The transposition table limits the
  35. >number of times that move generation is called to once per position.
  36.                                    ^^^^^
  37. Um, I don't think that this is so.  From the aritcles I've read and
  38. the source code I've seen, the "typical" transposition table entry
  39. has the best move for a position, but *not* all the pseudo-legal
  40. moves for that position. So it's possible that the stored bounds
  41. and stored move doesn't cause a cutoff, thus the legal moves for
  42. the current position may have to be generated *again*.
  43.  
  44. I guess that in general the move generation function may not be called
  45. more that once per pos, but it certainly doesn't limit the calls to
  46. once per position.
  47.  
  48.