Author: rasjid chan
Date: 00:31:48 04/16/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. > >Uri Hello Uri, You started me off to ETC which I think correct and almost most would agree. You're the one who first question recursion. Probably what the others wrote about no speed gain is true and that a transparent stack can easily be done by simply creating one. So it means everything in my non-recursion is now void. I don't or am unable to think or analyse things very deeply, only seeing things one ply ahead. So by creating an extra stack, there is duplication. Again it is a quetion of how well one understands how computers work - it may be back to square-one again - speed impact not measurable. All said it is still ok in my case but maybe not for Movei. Changing to non-recursion gives a speed improvement of 0.3 %, but in the process I optimize on some other things and all said the change is not difficult, a one time affair after which we don't need to attend to it. As for bad readability, it may be only for others when it becomes open-source, not to the author himself. 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.