Author: Dann Corbit
Date: 18:37:55 04/15/04
Go up one level in this thread
On April 15, 2004 at 21:02:48, Uri Blass wrote: >On April 15, 2004 at 16:02:44, rasjid chan wrote: > >>On April 15, 2004 at 14:21:36, Robert Hyatt wrote: >> >>>On April 15, 2004 at 14:05:42, rasjid chan wrote: >>> >>>>On April 15, 2004 at 12:22:43, Stefano Gemma wrote: >>>> >>>>>On April 15, 2004 at 05:01:54, rasjid chan wrote: >>>>> >>>>>>After reading the recent post on non-recursive search, I decided to >>>>>>implement it. My guess is that maybe search function call overhead >>>>>>may be too high as I have a host of local variables that cannot be reduced. >>>>>> >>>>>>My approach is direct and simple, an attempt to immitate recursion by >>>>>>creating my own search stack and managing it instead of allowing C function >>>>>[...] >>>>> >>>>>In my old program Drago for Dos (1993's sources are at www.linformatica.com), i >>>>>don't use recursive search. The same was for Raffaela. Both are written in >>>>>assembly. I use a fixed area of memory to old variables for any node (it is >>>>>something like an array of struct, but in assembly). Debugging a non-recursive >>>>>engine in assembly, with a lot of conditional jump was very hard. My last >>>>>engine, Freccia, don't use non-recursive search but still i don't use stack for >>>>>variables but the old array of struct. I think this is the better way to do, in >>>>>my program. Debugging is easyer and i can preset some fixed constant depending >>>>>on the node depth. >>>>> >>>>>Ciao!!! >>>>> >>>>>Stefano Gemma >>>> >>>>To do non-recursive search in assembly would be too tough for me, even with >>>>easy C the debugging can be tricky. >>>> >>>>I am not sure I know or use programming terms / naming correct. What I mean >>>>by stack is my data of array of search_stack_struct type which I create. >>>>Then make/unmake a move becomes ++ply, ++ps, --ply, --ps >>>>where ps is a pointer to my search_stack_struct. So using this pointer ps, >>>>I store / restore my alpha,depth,pointer to current move made / first or >>>>last move in my move list, etc. In this way and with care we can try >>>>non-recursive search and I think there should not be reasons why it cannot >>>>be made better than recursive search. >>> >>> >>>I don't think there is enough difference to measure. Cray Blitz was >>>non-recursive as early Fortran didn't allow recursion. Crafty has been >>>recursive from the start. >> >> >> Procedure call overhead is _not_ significant on a PC, >>compared to all the work done inside one such call. >>=========== >> >>This is the thing i don't know nor am sure, and if measured >>would probably be as you say - so nothing gain. But I am also thinking >>that the a transparent stack may be of use later as there must be some >>usefulness to pruning, etc in knowing what the state of the >>nodes are nth ply down; I have yet to know what or how. >> >>Thanks >>Rasjid > >Yes but it can be done by global arrays. > >The question is how much speed improvement you can get by non recursive search >assuming that you decide to save all the information in the stack and you have >global arrays like >int alpha[max_depth]; >int beta[max_depth]; and global array for every varaible that is used in the >search function. It will be a colossal waste of time. Did you know that most modern compilers can eliminate tail recursion? If you to recode the algorithm, then the resultant program will be: 1. Harder to read, understand and debug (more than negating any possible value) 2. If faster, then by .001% There are a million better places to spend time writing a chess program. However, if you want to do it for the recreation of converting recursion into iteration then it has value. If you are doing it to speed up the program then: DON'T. IMO-YMMV.
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.