home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / programm / 2474 < prev    next >
Encoding:
Internet Message Format  |  1992-08-25  |  1.4 KB
  1. Path: sparky!uunet!munnari.oz.au!goanna!ok
  2. From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
  3. Newsgroups: comp.programming
  4. Subject: Re: Teaching the basics
  5. Message-ID: <14195@goanna.cs.rmit.oz.au>
  6. Date: 26 Aug 92 11:02:17 GMT
  7. References: <1992Aug19.154830.11787@uwm.edu> <MJN.92Aug23031941@pseudo.uucp> <1992Aug25.174243.10436@uwm.edu>
  8. Organization: Comp Sci, RMIT, Melbourne, Australia
  9. Lines: 19
  10.  
  11. In article <1992Aug25.174243.10436@uwm.edu>, markh@csd4.csd.uwm.edu (Mark) writes:
  12. > In article <7116@charon.cwi.nl> tromp@cwi.nl (John Tromp) writes:
  13. > >One of the prime applications of recursion, IMHO,
  14. > >and where you cannot hope to replace it by anything else,
  15. > >is in a tree search algorithm like alpha beta or plain old minimax.
  16.  
  17. > Wrong.  In fact, the non-recursive version (tree search) is far smaller and
  18. > simpler.  No stacks either.
  19.  
  20. The trouble is that (Mark) gives code for a BINARY SEARCH TREE (like
  21. UNIX "tsearch()), which doesn't even faintly resemble the problems that
  22. (John Tromp) explicitly named, which are ALPHA-BETA SEARCH and MINIMAX.
  23. Not the least of the difference is that alpha-beta and minimax are
  24. algorithms for searching a _game_ tree which is in practice either infinite
  25. in size or so very much larger than even virtual memory that one just does
  26. _not_ have (Mark)'s kind of tree stored in memory to walk around.
  27.  
  28. -- 
  29. You can lie with statistics ... but not to a statistician.
  30.