Interesting Scorpio design

[Kerwin]

We have modified the Scorpio source code before and made minimal changes to make it work with the Pocket PC ThinkerBoard. But this is the first time that I have looked at the details.

I just noticed that it does not make use of recursive function calls. Instead, it "simulates" recursion by maintaining a "stack" of local information.

I wanted to contribute to the Scorpio project and hopefully improve it for the Pocket PC version, but now I think more time is needed to understand the code (more than what I was expecting).

[H.G.Muller]

I am doing the same thing in the new engine I am writing now. The advantage is that you can access all 'local' variables of any level of the search below you. This comes in very handy for scoring repetitions in Xiangqi, where the result (draw or loss) depends on every position in the repeat loop.

Another advantage is that you can 'return' arbtrarily large amounts of data, without having to pass through global variables. You can copy them directly into the underlying stack frame. This is useful for Joker, because its Search() returns the depth and move next to the score.

[Kerwin]

I am doing the same thing in the new engine I am writing now. The advantage is that you can access all 'local' variables of any level of the search below you. This comes in very handy for scoring repetitions in Xiangqi, where the result (draw or loss) depends on every position in the repeat loop.

Another advantage is that you can 'return' arbtrarily large amounts of data, without having to pass through global variables. You can copy them directly into the underlying stack frame. This is useful for Joker, because its Search() returns the depth and move next to the score.

I'm familiar with the method. I have coded like this in the past, long, long time ago when embedded systems had very few memory to work with, and stack space is premium. So much so that it is worth to conserve the return address needed to push to the stack when doing function calls (especially recursive calls).

I just never though I would have to deal with it again in these modern times.

[H.G.Muller]

I think it is still used quite often. I was told by Vincent that Diep also uses non-recursive search. And also from a hardware POV it still makes sense: todays L1 caches are similar in size to the memories of old 8-bit computers.

This, in fact, is the other reason I switched to non-recursive. Joker runs like sh*t on a Pentium IV, because the working set is too large to use the 2-way 8KB cache without severe thrashing. This is strongly exacerbated by the fact that in the recursive implementation, I have little control over where the stack data maps in cache compared to the software move stack and the global data (boards and piece lists). The non-recursive design allows me to have all data map to a different cache entry, as I can put it all in a single global structure.

I map it such that in an 8KB cache the non-captures in the move stack (if there are more than 16, which is usually the case) would flush the local data of the node 4 levels below it, but the captures (if there are not more than 16) would only flush the capture stack of the node 8 levels below. So my QS can go 8 levels deep without ever having to work outside L1 (except for has probes).

[Harald Lüßen]

What do you mean with 'no recursion'? Is search() not calling search() in some way?
You can use a global array[], a vector<> or stack accessed by any ply
AND have a local view to the current data inside a recursive search().
This is a very simple and obvious implementation. You have confused me.

Harald

[H.G.Muller]

I think 'no recursion' indeed means that Search() does not call Search(). So no return addresses are pushed. In a simple implemetation, the return address would always be the same anyway, except for the return from the root node. So a simple branch which is virtually always predicted correctly could take its place.

I could find no way to cast it in a structured form; I could only do it by a number of conditional backward gotos. I tend to think in assembly code, though, so gotos don't bother me. Search is something you make and debug only once anyway, and when it works it works.

[Teemu Pudas]

I could find no way to cast it in a structured form; I could only do it by a number of conditional backward gotos.

I hide it behind a bunch of macros:

Code: Select all

enum { RETURN, NEW_NODE };

#define be_recursive() \
   switch (state) { \
   case NEW_NODE
#define end_recursion() \
   default:assert(false); return best; }

#define return(foo) return best = foo, RETURN
#define recurse() return(best), NEW_NODE

#define search(depth,alpha,beta) do { \
   next->init(NEW_NODE,depth,alpha,beta); \
   state = __LINE__; \
   recurse(); \
   case __LINE__:; } while (0)


inline int Node::do_search() {
   
// any variable not declared inside this function is a member of Node
   
Node *const next = this + 1;

be_recursive(): // Please.

   gen_moves(list);
   if (list.empty()) return(in_check?MATE_IN_ONE:DRAW);

   while (move = list.next()) {
      make(move);
      search(depth-1,-beta,-alpha);
      unmake();
      if (ret_val > best) {
         best = ret_val;
         if (best >= beta) return(best);
      }
   }
   return(best);
     
end_recursion();
}

int drive_search(int depth, int alpha, int beta) { // called from root_search()
   Node stack[MaxPly];
   Node *node = &stack[1]; // stack[0] would be root
   node->init(NEW_NODE,depth,alpha,beta);
   while (true) {
      switch (node->do_search()) {
      case RETURN:
         node--;
         node->ret_val = -node[1].best;
         if (node == stack) return node->ret_val;
         break;
      case NEW_NODE:
         node++;
      }
   }
}


You can use a global array[], a vector<> or stack accessed by any ply
AND have a local view to the current data inside a recursive search().
This is a very simple and obvious implementation. You have confused me.

I think most of us do it for the DTS parallel search, which would be impossible (or *very* ugly) with a recursive search function.

[Zach Wegner]

I could find no way to cast it in a structured form; I could only do it by a number of conditional backward gotos.

I hide it behind a bunch of macros:

Code: Select all

enum { RETURN, NEW_NODE };

#define be_recursive() \
   switch (state) { \
   case NEW_NODE
#define end_recursion() \
   default:assert(false); return best; }

#define return(foo) return best = foo, RETURN
#define recurse() return(best), NEW_NODE

#define search(depth,alpha,beta) do { \
   next->init(NEW_NODE,depth,alpha,beta); \
   state = __LINE__; \
   recurse(); \
   case __LINE__:; } while (0)


inline int Node::do_search() {
   
// any variable not declared inside this function is a member of Node
   
Node *const next = this + 1;

be_recursive(): // Please.

   gen_moves(list);
   if (list.empty()) return(in_check?MATE_IN_ONE:DRAW);

   while (move = list.next()) {
      make(move);
      search(depth-1,-beta,-alpha);
      unmake();
      if (ret_val > best) {
         best = ret_val;
         if (best >= beta) return(best);
      }
   }
   return(best);
     
end_recursion();
}

int drive_search(int depth, int alpha, int beta) { // called from root_search()
   Node stack[MaxPly];
   Node *node = &stack[1]; // stack[0] would be root
   node->init(NEW_NODE,depth,alpha,beta);
   while (true) {
      switch (node->do_search()) {
      case RETURN:
         node--;
         node->ret_val = -node[1].best;
         if (node == stack) return node->ret_val;
         break;
      case NEW_NODE:
         node++;
      }
   }
}


That's pretty clean Teemu, very interesting design. I like your use of the LINE macro, though I use the name of the tag in other places so I can't steal it. When are we going to see this engine released?

It seems everyone's iterative search implementation is very different. ZCT looks mostly like a traditional search, Scorpio is, well honestly Scorpio is very weird. I never understood its search. And yours is pretty cool, it should allow for a very clean design (i.e. you can use separate search and qsearch functions).

ZCT and Zappa also use iterative search for DTS. Personally that was the only reason. I might be able to speed up my iterative design, but I think overall it is slower than recursive. I can see somebody like H.G. or Vincent making iterative faster than recursive, but I usually don't deal with that kind of low level detail, and I think it would make my code way messier.

BTW I'm pretty sure that I just fixed my last bug and ZCT is 100% stable on 4 processors. Idle time is way down to a couple percent usually, and it's now played 15 1'0" games with no problems (knock on wood). I don't know about the scaling, but that's peanuts compared to getting DTS bug free...

[F. Bluemers]

BTW I'm pretty sure that I just fixed my last bug and ZCT is 100% stable on 4 processors. Idle time is way down to a couple percent usually, and it's now played 15 1'0" games with no problems (knock on wood). I don't know about the scaling, but that's peanuts compared to getting DTS bug free...

Excellent
Does that include the windows version too?
Best
Fonzy

[Zach Wegner]

Excellent
Does that include the windows version too?
Best
Fonzy

Well, it should. I haven't tested it on my dual, I don't have a Windows computer with a quad. So I'll have to find somebody with one... Right now I'm concentrating on making it as strong as possible for the tournament tomorrow, mostly the parallel search. I'll give you a sneak preview a bit later. The next task is to see if it's stable on octals and 16-ways.