goto thread (split)

[sje]

... work he has done with the chess standards of PGN, FEN, EPD...

Well, if I hadn't done those, eventually someone else would have and maybe they would have done a better job. Instead of being thanked, perhaps I should be criticized for not distributing them earlier; nearly all that work had been in existence for seven years or more before they became public. But this was all in the pre-Web days, so I can't be blamed too much.

[sje]

Here is some sample code; Symbolic's move maker routine. Notice how null moves are handled without fuss.

Code: Select all

void Position::Execute(const Move move)
{
  // Sanity test

  if (PfMvExecute)
    if (IsEvilInCheck())
      Die("Position::Execute", "Evil king in check/0");

  const Cabs savecabs = cabs;
  const Sq   saveepsq = epsq;

  // Save the move

  MoveNodePtr movenodeptr = movepool.AllocateNode();

  movenodeptr->PutMove(move);

  // Save restorable items

  PSPRNodePtr psprnodeptr = psprpool.AllocateNode();

  psprnodeptr->PutGood(good);
  psprnodeptr->PutEvil(evil);
  psprnodeptr->PutCabs(cabs);
  psprnodeptr->PutEpsq(epsq);
  psprnodeptr->PutHmvc(hmvc);
  psprnodeptr->PutFmvn(fmvn);
  psprnodeptr->PutInch(inch);
  psprnodeptr->PutIndc(indc);
  psprnodeptr->PutPmbb(pmbb);
  psprnodeptr->PutFmbb(fmbb);

  psprnodeptr->PutFullHash(fullhash);
  psprnodeptr->PutMtrlHash(mtrlhash);
  psprnodeptr->PutPawnHash(pawnhash);

  // Constant initialization

  const bool notnullflag = move.IsNotNull();
  const Sq frsq = move.GetFrSq(), tosq = move.GetToSq();
  const Man frman = move.GetFrMan(), toman = move.GetToMan();
  const Mc mc = move.GetMc();

  // Men movement

  if (notnullflag)
  {
    switch (mc)
    {
      case McReg:

        if (IsManNotVacant(toman))
        {
          Capture(frsq, tosq, good, evil, frman, toman);
          tracker.TargetCapture(tosq);
          tracker.SimpleMovement(frsq, tosq);
        }
        else
        {
          MoveMan(frsq, tosq, good, frman);
          tracker.SimpleMovement(frsq, tosq);
        };
        break;

      case McEPC:
        {
          const Sq vpsq = EPVictimSquare();

          DelMan(vpsq, evil, SynthPawn[evil]);
          MoveMan(frsq, tosq, good, frman);
          tracker.TargetCapture(vpsq);
          tracker.SimpleMovement(frsq, tosq);
        };
        break;

      case McCQS:
      case McCKS:
        {
          const Castling castling = CvColorMcToCastling[good][mc];
          const Sq rhsq = CvCastlingToRookHomeSq[castling];
          const Sq rasq = CvCastlingToRookAwaySq[castling];

          MoveMan(frsq, tosq, good, frman);
          MoveMan(rhsq, rasq, good, SynthRook[good]);
          tracker.SimpleMovement(frsq, tosq);
          tracker.SimpleMovement(rhsq, rasq);
        };
        break;

      case McPPN:
      case McPPB:
      case McPPR:
      case McPPQ:
        if (IsManNotVacant(toman))
        {
          DelMan(tosq, evil, toman);
          tracker.TargetCapture(tosq);
        };
        DelMan(frsq, good, frman);
        AddMan(tosq, good, CvColorMcToMan[good][mc]);
        tracker.SimpleMovement(frsq, tosq);
        break;

      default:
        SwitchFault("Position::Execute");
        break;
    };
  };

  // Scalar adjustment: colors

  FlipColor(good);
  FlipColor(evil);

  // Scalar adjustment: castlings

  if (notnullflag)
    if (cabs != 0)
      cabs = (Cabs) ((ui) cabs & ~(CastlingCancel[frsq] | CastlingCancel[tosq]));

  // Scalar adjustment: en passant target

  epsq = SqNil;
  if (notnullflag)
    if (move.IsPawnMove() && ((frsq ^ tosq) == (FileLen * 2)))
    {
      const Sq candepsq = (Sq) (frsq + CvColorToForwardDelta[evil]);

      if (HasAtLeastOneEPCapture(candepsq))
        epsq = candepsq;
    };

  // Scalar adjustment: half move counter

  if (move.IsResetsHmvc())
    hmvc = 0;
  else
    hmvc++;

  // Scalar adjustment: full move number

  if (IsColorWhite(good))
    fmvn++;

  // Hash adjustment: castlings

  if (cabs != savecabs)
    for &#40;Castling castling = &#40;Castling&#41; 0; castling < CastlingLen; IncrCastling&#40;castling&#41;)
      if (&#40;cabs & BX&#40;castling&#41;) != &#40;savecabs & BX&#40;castling&#41;))
        fullhash.FoldHashCastling&#40;castling&#41;;

  // Hash adjustment&#58; en passant target

  if &#40;epsq != saveepsq&#41;
  &#123;
    if &#40;IsSqNotNil&#40;saveepsq&#41;) fullhash.FoldHashEpsq&#40;saveepsq&#41;;
    if &#40;IsSqNotNil&#40;epsq&#41;)     fullhash.FoldHashEpsq&#40;epsq&#41;;
  &#125;;

  // Regenerate various status items

  RegenerateStatus&#40;);

  // Sanity test

  if &#40;PfMvExecute&#41;
    if &#40;IsEvilInCheck&#40;))
      Die&#40;"Position&#58;&#58;Execute", "Evil king in check/1");
&#125;

[Don]

I am not saying that recursion is bad. Symbolic uses recursion as part of its perft(). But perft() is much different from a regular search as I don't expect a perft() call to be interrupted by a time-out or user intervention. A regular search must be able to stop gracefully with its partial results intact. Throwing an exception or calling longjmp() should be used for a truly exceptional condition, like power failure or processor-on-fire.

A new problem occurs with the introduction of a multithreaded search where the search continues while individual threads must be repeatedly re-run with different data. In addition to the requirement to stop gracefully, there is now the need to share data among the threads. It's tough to do this when a lot of interesting data is hidden on the inaccessible activation frames on different stacks local to each thread. With an old style recursive approach, it can be very hard to pause a thread, save its state, and later resume that thread.

Now, with an non-recursive approach, all of the above problems may be solved without excessive anguish. Also, with the details of a thread's state explicitly available and not hidden, a thread could even be restarted on a different machine with a different architecture as long as the semantics remained constant. Indeed, this is one of my goals with Symbolic; to allow multiple machines on the LAN to contribute to a search in a very integrated, yet portable, manner.

Now this is actually a very compelling argument in favor of your approach - a breath of fresh air to see on this forum so often devoid of real content. I am happy to see there actually is a method to your madness!

General comment:

I have noted over many years of professional experience that if a shop allows coders to use unstructured techniques, then the result is nearly always crappy code. It is also expensive code, for it much more often needs costly maintenance and modification. Yet this is tolerated because that extra expense may be pushed to the next business quarter. Sadly, this has become the American Way.

[Don]

... work he has done with the chess standards of PGN, FEN, EPD...

Well, if I hadn't done those, eventually someone else would have and maybe they would have done a better job. Instead of being thanked, perhaps I should be criticized for not distributing them earlier; nearly all that work had been in existence for seven years or more before they became public. But this was all in the pre-Web days, so I can't be blamed too much.

Nobody is blaming you on this, I think it's a really solid standard. There is nothing above nit-picking but this is close to perfect in my opinion.

There is one issue that I think you (or was it someone else?) got wrong and that is the ep field in FEN - but I think even you admitted that once. The issue is that the spec says to set the field after any double pawn move - even if there is no enemy pawn is poised to capture. That makes many semantically equivalent positions look different and is a real pain to deal with in those cases where you are processing fen records for books usage and such. When I export FEN I just don't set that field and it's still correct fen.

Still, that is a minor annoyance - the standard is close to perfect in my opinion and obviously well thought out and your documentation of it is something that brings sanity to the world of computer chess when so often documentation for things like this is so poorly written.

[sje]

Now, with an non-recursive approach, all of the above problems may be solved without excessive anguish. Also, with the details of a thread's state explicitly available and not hidden, a thread could even be restarted on a different machine with a different architecture as long as the semantics remained constant. Indeed, this is one of my goals with Symbolic; to allow multiple machines on the LAN to contribute to a search in a very integrated, yet portable, manner.

Now this is actually a very compelling argument in favor of your approach - a breath of fresh air to see on this forum so often devoid of real content. I am happy to see there actually is a method to your madness!

Yes; I don't recall anyone having tried a general heterogeneous distributed, parallel sub-tree search. I do remember Jonathan Schaffer's Sun Phoenix program which ran on multiple Sun workstation, but I think that effort was a simple split-at-root approach.

In Symbolic, a sub-tree search state is kept in an instance of the class Branch which contains stuff like the root position, the current position, various search input parameters, and various output parameters (PV, expectation). It also contains a linked list of instances of the PlyRec class, one for each currently open in the search. Each PlyRec instance contains all the state information for a ply including the node processing phase. When the Node() routine is called, it just starts or restarts based entirely on the sub-tree state as given by the Branch instance.

Just try doing that with a traditional recursive search.

An open question is: How fast can a Branch instance be sent on a local LAN? There's a lot of data there, and the total size grows with the depth of the search and also the length of the game as a position also includes all position state history. Perhaps a millisecond or two, rather slower than assigning the instance to a local thread.

There is also the problem of having local machines with vastly varying throughput limits. How does this affect task assignment? What is the overhead of having to schedule distributed tasks. What about collecting the results? Also, should task receiving machines themselves be allowed to delegate non-local sub-tasks? Can I hijack my neighbor's WiFi and machine to assist the effort?

[michiguel]

Now, with an non-recursive approach, all of the above problems may be solved without excessive anguish. Also, with the details of a thread's state explicitly available and not hidden, a thread could even be restarted on a different machine with a different architecture as long as the semantics remained constant. Indeed, this is one of my goals with Symbolic; to allow multiple machines on the LAN to contribute to a search in a very integrated, yet portable, manner.

Now this is actually a very compelling argument in favor of your approach - a breath of fresh air to see on this forum so often devoid of real content. I am happy to see there actually is a method to your madness!

Yes; I don't recall anyone having tried a general heterogeneous distributed, parallel sub-tree search. I do remember Jonathan Schaffer's Sun Phoenix program which ran on multiple Sun workstation, but I think that effort was a simple split-at-root approach.

In Symbolic, a sub-tree search state is kept in an instance of the class Branch which contains stuff like the root position, the current position, various search input parameters, and various output parameters (PV, expectation). It also contains a linked list of instances of the PlyRec class, one for each currently open in the search. Each PlyRec instance contains all the state information for a ply including the node processing phase. When the Node() routine is called, it just starts or restarts based entirely on the sub-tree state as given by the Branch instance.

Just try doing that with a traditional recursive search.

I am not sure why this is a problem. The main difference between a recursion approach and iteration is that in the latter you have your own stack. So, you can do recursion and have your own independent stack too, and no local variables. Or at least, keep local only what you want.

In my SMP approach I have all the information of nodes being analyzed in parallel (people call this split nodes if I am not mistaken) in an "external" type of stack. That is addressed with pointers. It is likely I am missing something, but I do not see the advantage of making my search iterative.

Miguel

An open question is: How fast can a Branch instance be sent on a local LAN? There's a lot of data there, and the total size grows with the depth of the search and also the length of the game as a position also includes all position state history. Perhaps a millisecond or two, rather slower than assigning the instance to a local thread.

There is also the problem of having local machines with vastly varying throughput limits. How does this affect task assignment? What is the overhead of having to schedule distributed tasks. What about collecting the results? Also, should task receiving machines themselves be allowed to delegate non-local sub-tasks? Can I hijack my neighbor's WiFi and machine to assist the effort?

[Don]

Now, with an non-recursive approach, all of the above problems may be solved without excessive anguish. Also, with the details of a thread's state explicitly available and not hidden, a thread could even be restarted on a different machine with a different architecture as long as the semantics remained constant. Indeed, this is one of my goals with Symbolic; to allow multiple machines on the LAN to contribute to a search in a very integrated, yet portable, manner.

Now this is actually a very compelling argument in favor of your approach - a breath of fresh air to see on this forum so often devoid of real content. I am happy to see there actually is a method to your madness!

Yes; I don't recall anyone having tried a general heterogeneous distributed, parallel sub-tree search. I do remember Jonathan Schaffer's Sun Phoenix program which ran on multiple Sun workstation, but I think that effort was a simple split-at-root approach.

In Symbolic, a sub-tree search state is kept in an instance of the class Branch which contains stuff like the root position, the current position, various search input parameters, and various output parameters (PV, expectation). It also contains a linked list of instances of the PlyRec class, one for each currently open in the search. Each PlyRec instance contains all the state information for a ply including the node processing phase. When the Node() routine is called, it just starts or restarts based entirely on the sub-tree state as given by the Branch instance.

Just try doing that with a traditional recursive search.

I am not sure why this is a problem. The main difference between a recursion approach and iteration is that in the latter you have your own stack. So, you can do recursion and have your own independent stack too, and no local variables. Or at least, keep local only what you want.

It's obviously not an unsolvable problem or else we would not have MP programs.

With this approach (which I have some familiarity with due the palm checkers program I wrote) you can exit a search without unwinding the stack. Just exit the search routine and it's done. Or you can stop the search and return to it a week later (by saving the state on disk.)

That was basically a requirement in the PALM OS, you basically had to leave the application on demand and then present the illusion that it was just sitting there ready to be continued even though the reality is that the programmer had to create that illusion by saving the state on exit and restoring it on startup.

In my SMP approach I have all the information of nodes being analyzed in parallel (people call this split nodes if I am not mistaken) in an "external" type of stack. That is addressed with pointers. It is likely I am missing something, but I do not see the advantage of making my search iterative.

I think there was a time when recursion represented a fairly big loss in performance if the routines being recursed were small but that has not been so for years. But it is possible to do this without it being too ugly.

Miguel

An open question is: How fast can a Branch instance be sent on a local LAN? There's a lot of data there, and the total size grows with the depth of the search and also the length of the game as a position also includes all position state history. Perhaps a millisecond or two, rather slower than assigning the instance to a local thread.

There is also the problem of having local machines with vastly varying throughput limits. How does this affect task assignment? What is the overhead of having to schedule distributed tasks. What about collecting the results? Also, should task receiving machines themselves be allowed to delegate non-local sub-tasks? Can I hijack my neighbor's WiFi and machine to assist the effort?

[bob]

I am not saying that recursion is bad. Symbolic uses recursion as part of its perft(). But perft() is much different from a regular search as I don't expect a perft() call to be interrupted by a time-out or user intervention. A regular search must be able to stop gracefully with its partial results intact. Throwing an exception or calling longjmp() should be used for a truly exceptional condition, like power failure or processor-on-fire.

A new problem occurs with the introduction of a multithreaded search where the search continues while individual threads must be repeatedly re-run with different data. In addition to the requirement to stop gracefully, there is now the need to share data among the threads. It's tough to do this when a lot of interesting data is hidden on the inaccessible activation frames on different stacks local to each thread. With an old style recursive approach, it can be very hard to pause a thread, save its state, and later resume that thread.

Now, with an non-recursive approach, all of the above problems may be solved without excessive anguish. Also, with the details of a thread's state explicitly available and not hidden, a thread could even be restarted on a different machine with a different architecture as long as the semantics remained constant. Indeed, this is one of my goals with Symbolic; to allow multiple machines on the LAN to contribute to a search in a very integrated, yet portable, manner.

Now this is actually a very compelling argument in favor of your approach - a breath of fresh air to see on this forum so often devoid of real content. I am happy to see there actually is a method to your madness!

General comment:

I have noted over many years of professional experience that if a shop allows coders to use unstructured techniques, then the result is nearly always crappy code. It is also expensive code, for it much more often needs costly maintenance and modification. Yet this is tolerated because that extra expense may be pushed to the next business quarter. Sadly, this has become the American Way.

Iterated search is a good idea. See DTS. But it does offer drawbacks as well, one of which is less intuitive code (recursion is quite nice).

[bob]

Now, with an non-recursive approach, all of the above problems may be solved without excessive anguish. Also, with the details of a thread's state explicitly available and not hidden, a thread could even be restarted on a different machine with a different architecture as long as the semantics remained constant. Indeed, this is one of my goals with Symbolic; to allow multiple machines on the LAN to contribute to a search in a very integrated, yet portable, manner.

Now this is actually a very compelling argument in favor of your approach - a breath of fresh air to see on this forum so often devoid of real content. I am happy to see there actually is a method to your madness!

Yes; I don't recall anyone having tried a general heterogeneous distributed, parallel sub-tree search. I do remember Jonathan Schaffer's Sun Phoenix program which ran on multiple Sun workstation, but I think that effort was a simple split-at-root approach.

In Symbolic, a sub-tree search state is kept in an instance of the class Branch which contains stuff like the root position, the current position, various search input parameters, and various output parameters (PV, expectation). It also contains a linked list of instances of the PlyRec class, one for each currently open in the search. Each PlyRec instance contains all the state information for a ply including the node processing phase. When the Node() routine is called, it just starts or restarts based entirely on the sub-tree state as given by the Branch instance.

Just try doing that with a traditional recursive search.

I am not sure why this is a problem. The main difference between a recursion approach and iteration is that in the latter you have your own stack. So, you can do recursion and have your own independent stack too, and no local variables. Or at least, keep local only what you want.

In my SMP approach I have all the information of nodes being analyzed in parallel (people call this split nodes if I am not mistaken) in an "external" type of stack. That is addressed with pointers. It is likely I am missing something, but I do not see the advantage of making my search iterative.

Miguel

An open question is: How fast can a Branch instance be sent on a local LAN? There's a lot of data there, and the total size grows with the depth of the search and also the length of the game as a position also includes all position state history. Perhaps a millisecond or two, rather slower than assigning the instance to a local thread.

There is also the problem of having local machines with vastly varying throughput limits. How does this affect task assignment? What is the overhead of having to schedule distributed tasks. What about collecting the results? Also, should task receiving machines themselves be allowed to delegate non-local sub-tasks? Can I hijack my neighbor's WiFi and machine to assist the effort?

The advantage is this: When you choose to do a split, you can see the state of ALL parts of the tree being searched. You can pick any node in any active path and split there instantly, without having to abort or anything. But the code is not as clean as a recursive search, which is why I have (so far) elected to stick with recursive. With larger numbers of processors, seeing everything is probably going to tip the balance back toward iterated search. But I hate to give up the cleanliness of a recursive search.

[sje]

Iterated search is a good idea. See DTS. But it does offer drawbacks as well, one of which is less intuitive code (recursion is quite nice).

You're right: the first time I did one of these, yes, it was counter intuitive to an extent. The phase (case body of the big switch) which moved down one ply and the corresponding phase which handled the result from a lower ply were both tricky to write. Now that I've done it, it seems easy!

To help with the design, I decided to let the "caller" (less deeper ply in a transition) do all the work of executing the move, setting up input parameters, etc. for the "callee" (more deeper ply in a transition), and later recovering output parameter values. Only within the "caller" phase does the code access anything other than the current ply record.

Hint: It can be helpful to first write a non-recursive perft().

Hint: Doing IID or the like means adding an extra phase pair (down and up) corresponding to each recursive call in a recursive design.

Here is a recent version of Symbolic's PlyRec class specification. Note the member variables: constants, inputs, outputs, and working storage. That's everything needed to contain the state fof the Node() routine at any ply.

Code: Select all

class PlyRec
{
public:
  PlyRec(const ui plyvalue, BranchPtr branchptrvalue);
  ~PlyRec(void) {}

  void Reset(void);

  void Generate(void);
  void GenerateCanonical(void);
  void GenerateChecks(void);
  void GenerateGainers(void);
  
  ui        conply;      // Constant: Ply
  bool      isply0;      // Constant: True if at ply zero (root)
  bool      isply1;      // Constant: True if at ply one
  bool      isp0good;    // Constant: True if ply zero mover is active
  bool      isp0evil;    // Constant: True if ply zero mover is not active

  Phase     phase;       // Input parameter: Initial phase (mutable)
  Window    basewindow;  // Input parameter: A/B window (constant)
  si        depth;       // Input parameter: Remaining search depth (constant)

  MoveList  PV;          // Output parameter: Predicted variation
  SV        expectation; // Output parameter: Predicted expectation

  NodeKind  nodekind;    // Directs move generation and scanning
  Window    window;      // Mutable scoring window
  GMVec     gmvec;       // Move generation vector
  Move      move;        // Current move of interest
  ui        trycount;    // Count of moves tried so far
  NC        nodecount;   // Cumulative number of nodes

private:
  BranchPtr branchptr;   // Constant: Pointer to the containing Branch instance
};

And here's the current list of the Node() phase names (needs comments):

Code: Select all

typedef enum
{
  PhaseNil = -1,
  PhaseNodeEnter,
  PhaseNodeDetermineKind,
  PhaseNodeGenerate,
  PhaseNodeTryNext,
  PhaseNodePostRetract,
  PhaseNodePostScan,
  PhaseNodeExit,
  PhaseSearchEnter,
  PhaseSearchExit,
  PhaseSwitchExit
} Phase;