Author: Gerd Isenberg
Date: 12:03:01 04/15/04
Go up one level in this thread
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. Yes, that should be even true for a recursive qsearch. But there is one additional, probably negligible pro for a non recursive search. See AMD64 optimization manual: 6.5 Recursive Functions Page 133 ... "If there are any other calls within the recursive function (except to itself) as shown in the next example, some returns can be mispredicted. If the number of recursive function calls plus the number of nonrecursive function calls within the recursive function is greater than 12, the return stack does not predict the correct return address for some of the returns once the recursion begins to unwind." So at least one should try to minimize other calls in recursive qsearch... Gerd > >Non-recursive offers some advantages in a parallel search, but as Crafty shows, >a recursive parallel search can (and does) work well. It is just more >complicated in a recursive search and there are things you can do in >non-recursive that you can't do in recursive easily. > > > >> >>Best Regards >>Rasjid
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.