An argument against direct recursion

[Dan Andersson]

Support for Continuations really isn't dependent on an algorithm being of certain form but a part of the language design goals of the language you use. The abilities of the language decides how painful the instrumentation becomes.

MvH Dan Andersson

[sje]

We have to distinguish here ...
1) there are the winboard command pause/resume (I dont know whether any interface or engine has them actually implemented). Upon receiving the pause command the engine just enters a loop with the only break being when the engine receives resume as an input. You dont need iterative search for that.

2) the engine stores it current search-state on disk and exits and the next time it loads it is able to continue its search from where it left before. This is a more extreme form of persistant hash, where not only position scores and best moves are stored but the whole search state gets collected. For this to work properly you indeed need an iterative search.
How would this be implemented in a most user friendly way for UCI / Winboard engines?

With Bozo's continuation support, it would be fairly easy to write the entire mate finder's search state to a file and load it at a later time or even on a different machine. However, note that Bozo's ply indexed record vector does not hold a transposition table, so any such tables would also have to be saved.

[sje]

There as been at least one, somewhat limited use of continuations in chess searching. This is seen in the case of a program which can solve a mate and then, upon user command, continue the mate search to locate any other mates in a given position. So there's a continuation in play, but it may be only available at the first ply of the search.

[stegemma]

An argument against direct recursion in a chess tree search:

I'd guess that nearly every modern A/B search routine uses direct recursion to call itself from ply to ply. This seems to be the natural way to do things, but is it the best?...

In my assembly programs i've used iterative search, instead of recursion. I was using edi/esi registers to point to nodes array and moves array. The program gets almost complicated, before of this. Now i use normal alfa-beta recursion, in C++, but even when tryed in assembly i've found that there are no advantage on using iteration instead of recursion. Maybe iteration is somehow hardest to debug but that is not fully true. With iteration, you can examine your own array of nodes instead of searching dat in the cpu stack. For me is more confortable to check against actual node value and 2 ply nodes before value, to do pruning but still the normal alfabeta function calling is just one line of code... so is simpler to code.

Iterative search maybe is more confortable to assembly programmer, in fact (IMHO).

[Gerd Isenberg]

An argument against direct recursion in a chess tree search:

I'd guess that nearly every modern A/B search routine uses direct recursion to call itself from ply to ply. This seems to be the natural way to do things, but is it the best?

In the Old Days, programming languages and their associated calling sequences did not support direct recursion. Chess program authors either had to code in assembly language with custom calling sequences or write non-recursive versions of a search; there was no other choice (outside of Lisp). Later, with the advent of new languages like C, Pascal, C++, and the like, direct recursion became widely supported and hand-made alternatives were dropped.

But consider some advantages of a non direct recursive approach:

1) There is zero danger of a stack overflow.

2) As there are no local (i.e., automatic) variables, each thread in a multithreaded search needs less stack space.

3) With no formal parameters or a return result, there can be less run time overhead. Also, less storage.

4) The programmer is forced to think more carefully during the design phase.

5) When a crash occurs, all the state variables can be read from a ply indexed vector of values; there is nothing hidden because there is nothing stored in local variables, formal parameters, or return results.

6) Less L1 cache thrashing as the search routine doesn't share stack space with any routines it might call.

7) Exception processing is simplified; a search can return from twenty ply deep just by changing a state variable. And none of the setjmp/longjmp bull.

8) You could write a chess program in Cobol. (Just joking!)

But see the pro Recursion notes by Jean-Christophe Weill, Mark Brockington and Niklaus Wirth.

[michiguel]

Another thing in the iterative scheme: continuation support. See the wiki article http://en.wikipedia.org/wiki/Continuation

We have to distinguish here ...
1) there are the winboard command pause/resume (I dont know whether any interface or engine has them actually implemented). Upon receiving the pause command the engine just enters a loop with the only break being when the engine receives resume as an input. You dont need iterative search for that.

Gaviota has implemented this for a long time. It is very important and I do not understand why GUIs have not implemented it.
1) You are playing a blitz game and you get a phone call... pause!
2) you are analyzing for hours, but now you have to use the computer for something else... pause! use your computer and then resume.

Gaviota does not go into a loop because it will consume resources beating the purpose of point 2. An appropriate mutex in the right place does the trick. I also need to check how much time has elapsed as "pause", because I need to subtract it to report the time used in real thinking.

2) the engine stores it current search-state on disk and exits and the next time it loads it is able to continue its search from where it left before. This is a more extreme form of persistant hash, where not only position scores and best moves are stored but the whole search state gets collected. For this to work properly you indeed need an iterative search.
How would this be implemented in a most user friendly way for UCI / Winboard engines?

The problem here is that to be practical, it will be needed to save 4-8 GiB of hashtables. This will be only useful if you are analyzing for hours or days and you do not want to lose the analysis. In those situations, you should be using huge hashtables. Saving all those gigantic files will be really a nuisance.

Miguel

[sje]

The problem here is that to be practical, it will be needed to save 4-8 GiB of hashtables. This will be only useful if you are analyzing for hours or days and you do not want to lose the analysis. In those situations, you should be using huge hashtables. Saving all those gigantic files will be really a nuisance.

Yes, but perhaps not too much of a nuisance if an SSD (Solid State Drive) is used with its big-data serial read/write transfer rates some seven times faster than a conventional hard drive.

I'm seriously considering getting an SSD just big enough to hold all my tablebase files. The 4 KB random read rate is nearly 50 times faster than a conventional hard drive.

[sje]

Now that I've got a non-recursive move search running in BozoChess, I can only say that I should have tried this long ago. Compared to a recursive search, the code is cleaner and doesn't have any lengthy, bug magnet if/while/repeat/for statements that span pages and pages of the source.

It's a lot easier to debug; all that's needed is to put a breakpoint at the state dispatch and then the search can be stepped on each state transition.

[sje]

But see the pro Recursion notes by Jean-Christophe Weill, Mark Brockington and Niklaus Wirth.

I read that, and I find it hard to believe that there can be a 30% run time difference between an iterative search vs a recursive search as long as both are coded properly.

As for the distinguished Niklaus Wirth, one must remember his work as a co-inventor of Pascal and its support of recursion which was a near revolutionary language feature back in the early 1970s. Of course he'll have a favorable opinion of recursion.

Yet I must say that I was impressed by Wirth's approach implementing recursion (activation frames, static lexical addressing displays, and the like) on the caveman era Control Data 6000 series mainframes. He put several of the CPU's eight B registers to work which otherwise saw duty only as holding Fortran do loop index variables. It was a much better way of calling a routine when compared to Seymour Cray's RJ (return jump) instruction the relied upon code modification at run time. Cray was a smart guy and knew hardware very, very well. But he wasn't a software engineer and he didn't listen much to any software engineers either. And that's why his 60 bit words, his 12 bit peripheral processors, his 6 bit characters, his one's complement arithmetic, and his non-hierarchical file system are all in the historical dustbin.