home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / gnu / chess / 535 < prev    next >
Encoding:
Text File  |  1993-01-25  |  2.0 KB  |  48 lines
  1. Newsgroups: gnu.chess
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!malgudi.oar.net!chemabs!jon
  3. From: jon@cas.org (Jon Vander Hill)
  4. Subject: Re: Iterative Deepening
  5. In-Reply-To: lim@toadflax.cs.ucdavis.edu's message of 22 Jan 93 07:34:07 GMT
  6. Message-ID: <JON.93Jan25110340@cas.org>
  7. Sender: usenet@cas.org
  8. Organization: Chemical Abstracts Service, Columbus, Ohio
  9. References: <C15r40.D1r@sju.edu> <21659@ucdavis.ucdavis.edu>
  10. Distribution: gnu
  11. Date: Mon, 25 Jan 1993 16:03:40 GMT
  12. Lines: 34
  13.  
  14. >>>>> On 22 Jan 93 07:34:07 GMT, lim@toadflax.cs.ucdavis.edu (Lloyd Lim) said:
  15.  
  16. > In article <C15r40.D1r@sju.edu> tmoody@sju.edu (T. Moody) writes:
  17. >>
  18. >>My real problem is with (b).  Levy and Newborn say
  19. >>something about searching at a given level and storing lots of positions
  20. >>in a hash table before moving to the next level.  Is this the only way
  21. >>to do it?  I don't know a thing about hash tables and, from what I have
  22. >>read it looks like it's over my head.
  23. >>
  24. >>So my question is, can iterative deepening be usefully (if not
  25. >>optimally) accomplished without using hash tables?
  26.  
  27. > Iterative deepening is commonly used with transposition (hash) tables,
  28. > but it doesn't require them.  Iterative deepening just means increasing
  29. > the search depth by one each time (i.e. - searching to a depth of 1,
  30. > then 2, then 3, ...).  You don't need to use transposition tables.
  31. > They are just used to speed things up, because many of the same nodes
  32. > are encountered again when you search to depth n+1.
  33.  
  34. One the the more expensive routines in a chess programs is the
  35. move generation function.  The transposition table limits the
  36. number of times that move generation is called to once per position.
  37. I agree that a transpositon table is not necessary to do iterative
  38. deepening, but even shallow chess trees can involve thousands
  39. of positions.
  40.  
  41. The transposition table is can also speed up the search by giving
  42. a score for a position that my have been generated in a parallel
  43. branch of the tree.
  44.  
  45. Jon Vander Hill
  46. jon@cas.org
  47.  
  48.