Author: Robert Hyatt
Date: 10:08:29 10/31/00
Go up one level in this thread
On October 31, 2000 at 11:35:49, Christophe Theron wrote: >On October 31, 2000 at 08:30:04, Steve Maughan wrote: > >>In my chess program I use recursion to carry out the basic alpha beta search. >>However while on one of the Delphi newsgroup I was told that recursion is a >>source of significant inefficiency and that _ALL_ recursive algorithms can be >>converted into an iterative form that is generally faster. Upon searching the >>net I found this site: >> >>http://www.geocities.com/zabrodskyvlada/aat/a_recu.html >> >>This basically shows that the recursive version of a sort runs at half the speed >>of the alternative version. Moreover, thinking back I remember that Ed Schroder >>mentioned that he doesn't use recursion. >> >>How many people do use recusion? >> >>Is there any literature on non recursive alpha / beta? >> >>Has anyone done any comparisons between recursive and none recursive searches? >> >>Regards, >> >>Steve > > > >Don't worry about the overhead of recursion, in a chess program it's almost >nothing. > >And the recursive version is so much more easy to read, it's a very important >advantage. > >I would not trust too much those recursive/non-recursive benchmarks. With a >little bit of manual optimizations, the recursive versions should be very close >to the iterative versions, unless the body of the recursion is empty... > > > > Christophe As I mentioned earlier, I agree if you ignore parallel search. The problem with recursion there is that it is hard to make an intelligent choice about where to use a processor when it becomes idle. All you can "see" is the current node in the tree. With an iterated approach, you can see _everything_ and you can attach the processor at any ply you want, easily. I'm not sure this is a killer issue, since I do parallel search with recursive negamax. But it does limit me a bit. But then again, I can actually read the search code easily... which is also important. I don't plan on changing back, myself... iterated search control was useful, but it made the search very messy to read and maintain... doing iterated negamax is even more messy to read...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.