Author: Robert Hyatt
Date: 09:31:27 04/16/04
Go up one level in this thread
On April 16, 2004 at 02:03:44, Tony Werten 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. > >A recursive search doesn't exclude that. You can still create your own global >stack, and push anything on it you want to have available at other plies. > >Tony There is one important issue for a parallel search that is not so easy to handle. When you recursively enter Search() at a ply, you have a _forced_ point to return to. But in a parallel search you might want to override that and send that thread to an idle loop to do more work, and that is tough. In a non-recursive search it is not so hard to do. > >> >>Thanks >>Rasjid >> >> >>> >>>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.