OpenCL perft() Technical Issues

[sje]

It looks like the Execute() and Retract() routines have stabilized.

So, here's Execute():

Code: Select all

static void PositionExecute(Position * const positionptr, const Move move)
{
  // This routine executes the given move for the given position.
  
  // Save the move
  
  if (positionptr->freemovelist.count == 0)
    MoveListAppendNode(&positionptr->freemovelist, MoveNodeNew());
  MoveNode * const movenodeptr = MoveListDetachTail(&positionptr->freemovelist);
  movenodeptr->move = move;
  MoveListAppendNode(&positionptr->usedmovelist, movenodeptr);
  
  // Save the preserved position data
  
  if (positionptr->freeppdlist.count == 0)
    PpdListAppendNode(&positionptr->freeppdlist, PpdNodeNew());
  PpdNode * const ppdnodeptr = PpdListDetachTail(&positionptr->freeppdlist);
  ppdnodeptr->ppd.fss = positionptr->fss;
  ppdnodeptr->ppd.apd = positionptr->apd;
  ppdnodeptr->ppd.msig = positionptr->msig;
  PpdListAppendNode(&positionptr->usedppdlist, ppdnodeptr);
  
  // Set up locals: pointer abbreviations
  
  Tracker * const trackerptr = &positionptr->tracker;
  Man * const manvec = positionptr->board.manvec;
  Hash * const msigptr = &positionptr->msig;
  
  // Set up locals: move components
  
  const Sq frsq = GetFrSq(move);
  const Sq tosq = GetToSq(move);
  const Man frman = GetFrMan(move);
  const Man toman = GetToMan(move);
  const Mc mc = GetMc(move);

  // Set up locals: FEN scalars
  
  const Color good = positionptr->fss.good;
  const Color evil = positionptr->fss.evil;
  const Cabs cabs = positionptr->fss.cabs;
  const Sq epsq = positionptr->fss.epsq;

  // Process motion according to move special case
  
  switch (mc)
  {
    case McReg:  // Regular
      if (IsManNotVacant(toman))
      {
        TrackerCapture(trackerptr, tosq);
        HashFoldManSq(msigptr, toman, tosq);
      };
      TrackerMovement(trackerptr, frsq, tosq);
      manvec[frsq] = ManVacant;
      manvec[tosq] = frman;
      HashFoldManSqSq(msigptr, frman, frsq, tosq);
      break;

    case McEPC:  // En passant
      {
        const Sq vpsq = NextSq[CvColorToAdvDir[evil]][epsq];

        TrackerCapture(trackerptr, vpsq);
        HashFoldManSq(msigptr, MapColorPieceToMan(evil, PiecePawn), vpsq);
        TrackerMovement(trackerptr, frsq, tosq);
        manvec[vpsq] = ManVacant;
        manvec[frsq] = ManVacant;
        manvec[tosq] = frman;
        HashFoldManSqSq(msigptr, frman, frsq, tosq);
      };
      break;

    case McCQS:  // Castle queenside
    case McCKS:  // Castle kingside
      {
        const Castling castling = CvColorMcToCastling[good][mc];
        const Sq r0sq = CvCastlingToRookHomeSq[castling];
        const Sq r1sq = CvCastlingToRookAwaySq[castling];
        const Man rookman = MapColorPieceToMan(good, PieceRook);

        TrackerMovement(trackerptr, frsq, tosq);
        TrackerMovement(trackerptr, r0sq, r1sq);
        manvec[frsq] = ManVacant;
        manvec[tosq] = frman;
        HashFoldManSqSq(msigptr, frman, frsq, tosq);
        manvec[r0sq] = ManVacant;
        manvec[r1sq] = rookman;
        HashFoldManSqSq(msigptr, rookman, r0sq, r1sq);
      };
      break;

    case McPPN:  // Pawn promotes to knight
    case McPPB:  // Pawn promotes to bishop
    case McPPR:  // Pawn promotes to rook
    case McPPQ:  // Pawn promotes to queen
      {
        const Man newman = MapColorPieceToMan(good, CvMcToPiece[mc]);

        if (IsManNotVacant(toman))
        {
          TrackerCapture(trackerptr, tosq);
          HashFoldManSq(msigptr, toman, tosq);
        };
        TrackerMovement(trackerptr, frsq, tosq);
        TrackerPromote(trackerptr, tosq, newman);
        manvec[frsq] = ManVacant;
        manvec[tosq] = newman;
        HashFoldManSq(msigptr, frman, frsq);
        HashFoldManSq(msigptr, newman, tosq);
      };
      break;

    default:
      break;
  };

  // Update: Colors
  
  positionptr->fss.good = evil;
  positionptr->fss.evil = good;

  // Update: Castling availability bits
  
  if (cabs != CabsNone)
  {
    positionptr->fss.cabs = (cabs & CabsPreservation[frsq] & CabsPreservation[tosq]);
    if (cabs != positionptr->fss.cabs)
    {
      HashFoldCabs(msigptr, cabs);
      HashFoldCabs(msigptr, positionptr->fss.cabs);
    };
  };
  
  // Update: En passant target square

  if (IsSqNotNil(epsq))
    HashFoldEpFile(msigptr, MapSqToFile(epsq));
  positionptr->fss.epsq = SqNil;

  if (IsManPawn(frman) && ((frsq ^ tosq) == (FileLen * 2)))
  {
    const Sq candepsq = NextSq[CvColorToAdvDir[good]][frsq];

    if (PositionTestEpSqCandPhase1(positionptr, candepsq))
    {
      positionptr->fss.epsq = candepsq;
      HashFoldEpFile(msigptr, MapSqToFile(positionptr->fss.epsq));
    };
  };
  
  // Update: Half move counter

  if (IsManPawn(frman) || IsManNotVacant(toman))
    positionptr->fss.hmvc = 0;
  else
    positionptr->fss.hmvc++;

  // Update: Full move number
  
  if (IsColorWhite(positionptr->fss.good))
    positionptr->fss.fmvn++;

  // Regenerate auxiliary position data
  
  PositionRegenerateApd(positionptr);
}

[sje]

And here's Retract():

Code: Select all

static void PositionRetract(Position * const positionptr)
{
  // This routine retracts the played move for the given position.
  
  // Restore the move
  
  MoveNode * const movenodeptr = MoveListDetachTail(&positionptr->usedmovelist);
  const Move move = movenodeptr->move;
  MoveListAppendNode(&positionptr->freemovelist, movenodeptr);

  // Restore the preserved position data
  
  PpdNode * const ppdnodeptr = PpdListDetachTail(&positionptr->usedppdlist);
  positionptr->fss = ppdnodeptr->ppd.fss;
  positionptr->apd = ppdnodeptr->ppd.apd;
  positionptr->msig = ppdnodeptr->ppd.msig;
  PpdListAppendNode(&positionptr->freeppdlist, ppdnodeptr);
  
  // Set up locals: abbreviations
  
  Tracker * const trackerptr = &positionptr->tracker;
  Man * const manvec = positionptr->board.manvec;
  
  // Set up locals: move components

  const Sq frsq = GetFrSq(move);
  const Sq tosq = GetToSq(move);
  const Man frman = GetFrMan(move);
  const Man toman = GetToMan(move);
  const Mc mc = GetMc(move);
  
  // Set up locals: FEN scalars

  const Color good = positionptr->fss.good;
  const Color evil = positionptr->fss.evil;
  const Sq epsq = positionptr->fss.epsq;
  
  // Process motion according to move special case

  switch (mc)
  {
    case McReg:  // Regular
      TrackerMovement(trackerptr, tosq, frsq);
      if (IsManNotVacant(toman))
        TrackerRestore(trackerptr);
      manvec[frsq] = frman;
      manvec[tosq] = toman;
      break;

    case McEPC:  // En passant
      {
        const Sq vpsq = NextSq[CvColorToAdvDir[evil]][epsq];

        TrackerMovement(trackerptr, tosq, frsq);
        TrackerRestore(trackerptr);
        manvec[vpsq] = MapColorPieceToMan(evil, PiecePawn);
        manvec[frsq] = frman;
        manvec[tosq] = ManVacant;
      };
      break;

    case McCQS:  // Castle queenside
    case McCKS:  // Castle kingside
      {
        const Castling castling = CvColorMcToCastling[good][mc];
        const Sq r0sq = CvCastlingToRookHomeSq[castling];
        const Sq r1sq = CvCastlingToRookAwaySq[castling];

        TrackerMovement(trackerptr, r1sq, r0sq);
        TrackerMovement(trackerptr, tosq, frsq);
        manvec[r0sq] = MapColorPieceToMan(good, PieceRook);
        manvec[r1sq] = ManVacant;
        manvec[frsq] = frman;
        manvec[tosq] = ManVacant;
      };
      break;

    case McPPN:  // Pawn promotes to knight
    case McPPB:  // Pawn promotes to bishop
    case McPPR:  // Pawn promotes to rook
    case McPPQ:  // Pawn promotes to queen
      {
        const Man newman = MapColorPieceToMan(good, CvMcToPiece[mc]);

        TrackerUnpromote(trackerptr, tosq, newman);
        TrackerMovement(trackerptr, tosq, frsq);
        if (IsManNotVacant(toman))
          TrackerRestore(trackerptr);
        manvec[frsq] = frman;
        manvec[tosq] = toman;
      };
      break;

    default:
      break;
  };
}

[sje]

The BeagleBone Black is a single board computer similar to the Raspberry Pi. Both have a 32 bit cellphone CPU, both have 512 MB RAM, both run Linux, etc. Although the BeagleBone Black costs US$55 vs US$35 for the Raspberry Pi, its clock is 1 GHz vs 700 MHz and it comes with from 2 GB to 4 GB flash standard vs 0 GB for the Raspberry Pi. The Raspberry Pi does have an advantage in that its user base is much larger.

Earlier today I fired up my BeagleBone Black, had it update itself (thank you, Debian), and did an rsync to copy over Oscar's source files. Using the compilation call:

Code: Select all

cc -O3 -Wall -pipe -o ~/tmp/operft Oscar.c operft.c

which is the same as it is with Mac OS/X, Oscar got itself compiled without any source modifications.

It ran, too, although it was a bit of a tight fit with Oscar's default 384 MB transposition table.

Code: Select all

sje@karen:~/tmp$ ./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 6
119060324   12.36 MHz
sje@karen:~/tmp$ ./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 7
3195901860   31.90 MHz
sje@karen:~/tmp$ ./operft "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1" 8
84998978956   67.47 MHz

Not too shabby for a computer that can run from a small battery.

[sje]

Pin detection without bitboards

Inside of each Position object, there lives an Apd object (Auxiliary Position Data):

Code: Select all

// Auxiliary position data; saved/restored on execute/retract

typedef struct
{
  bool incheck;  // In check status
  bool dbcheck;  // Double check status
  TiBV pinned;   // Target indexed bit vector: pinned targets
  TiBV frozen;   // Target indexed bit vector: frozen targets
} Apd;

A TiBV object is just a 32 bit unsigned integer with each bit corresponding to a single chessman. The bit position is like a five bit serial number stamped on the base of each man which remains constant throughout a game. (The man which is the result of a pawn promotion gets the serial number of the promoted pawn which is now back in the ethereal chess box.)

Code: Select all

// Ti: Target index (chessman fixed serial number)

typedef enum
{
  TiNil = -1,
  TiX00, TiX01, TiX02, TiX03, TiX04, TiX05, TiX06, TiX07,  // White man target indexes; 1st half
  TiX08, TiX09, TiX0a, TiX0b, TiX0c, TiX0d, TiX0e, TiX0f,  // White man target indexes; 2nd half
  TiX10, TiX11, TiX12, TiX13, TiX14, TiX15, TiX16, TiX17,  // Black man target indexes; 1st half
  TiX18, TiX19, TiX1a, TiX1b, TiX1c, TiX1d, TiX1e, TiX1f   // Black man target indexes; 2nd half
} Ti;

#define TiLen (TiX1f + 1)

#define IsTiNil&#40;ti&#41;    (&#40;ti&#41; <  0&#41;
#define IsTiNotNil&#40;ti&#41; (&#40;ti&#41; >= 0&#41;

#define MapColorToKingTi&#40;color&#41; (&#40;color&#41; * ArmyLen&#41;                        // King target index
#define MapColorToPeonTi&#40;color&#41; &#40;MapColorToKingTi&#40;color&#41; + 1&#41;              // First peon target index
#define MapColorToStopTi&#40;color&#41; &#40;MapColorToKingTi&#40;color&#41; + &#40;ArmyLen - 1&#41;)  // Last target index

#define TiWK TiX00  // White king target index synonym
#define TiBK TiX10  // Black king target index synonym

// Target index bit vector &#40;set of target indexes&#41;

typedef ui32 TiBV;

#define SetTi&#40;tibv, ti&#41;   &#40;tibv |=  BX&#40;ti&#41;)
#define ResetTi&#40;tibv, ti&#41; &#40;tibv &= ~BX&#40;ti&#41;)
#define TestTi&#40;tibv, ti&#41;  &#40;tibv &   BX&#40;ti&#41;)

As part of Oscar's Execute() routine, the RegenerateApd() routine is called for each move made to ensure that all of the Apd values are up to date. The regeneration takes a significant amount of time, but this time is regained later my making legal-only move generation fast and simple. The RegenerateApd() routine is also called when a position is first loaded from a FEN string.

Code: Select all

static void PositionRegenerateApd(Position * const positionptr)
{
  // This routine regenerates the auxiliary position data for the given position.

  const Sq goodkingsq = PositionGetGoodKingSq(positionptr);
  ui atkcount;

  // Handle the check and double check indicators

  if (IsSqNil(goodkingsq))
    atkcount = 0;
  else
    atkcount = PositionCountColorAttacksToSq(positionptr, positionptr->fss.evil, goodkingsq);

  if (atkcount == 0)
    positionptr->apd.incheck = positionptr->apd.dbcheck = false;
  else
  {
    positionptr->apd.incheck = true;
    positionptr->apd.dbcheck = (atkcount > 1);
  };

  // Calculate the pinned and frozen target index bit vectors

  const Board * const boardptr = &positionptr->board;
  const Man * const manvec = boardptr->manvec;
  const Tracker * const trackerptr = &positionptr->tracker;
  const TiBV sweepers = trackerptr->tbvs.sweepers;
  Color color;
  
  // Initialize the results

  positionptr->apd.pinned = positionptr->apd.frozen = 0;

  // Calculate for all targets; although only good target pinned/frozen are referenced at present 
  
  for &#40;color = ColorWhite; color <= ColorBlack; color++)
  &#123;
    const Color other = CvColorToOtherColor&#91;color&#93;;
    const Ti kingti = CvColorToKingTi&#91;color&#93;;
    const Sq kingsq = trackerptr->sqvec&#91;kingti&#93;;

    // Do not crash if king is not present
    
    if &#40;IsSqNotNil&#40;kingsq&#41;)
    &#123;
      const Ti stopti = CvColorToStopTi&#91;other&#93;;
      Ti otherti;

      // Loop through the other color's peon target indexes
      
      for &#40;otherti = CvColorToPeonTi&#91;other&#93;; otherti <= stopti; otherti++)
      &#123;
        // Only sweepers may pin
        
        if &#40;TestTi&#40;sweepers, otherti&#41;)
        &#123;
          const Sq othersq = trackerptr->sqvec&#91;otherti&#93;;
          const ui16 infoword = SqSqInfo&#91;othersq&#93;&#91;kingsq&#93;;

          // Need a sweep direction
          
          if &#40;infoword & InfoDSweep&#41;
          &#123;
            // The direction is from the sweeper to the king
            
            const Dir dir = &#40;Dir&#41; &#40;infoword & InfoDirMsk&#41;;

            // The sweep direction must match the sweeper's capability

            if &#40;CvManToSweepMask&#91;manvec&#91;othersq&#93;&#93; & BX&#40;dir&#41;)
            &#123;
              const Sq *sqptr = SweeperRunPtrs&#91;dir&#93;&#91;othersq&#93;;
              Sq candsq = *sqptr++;
              Man candman;
              
              // Skip empty squares while looking for a candidate pinned man

              while &#40;IsManVacant&#40;candman = manvec&#91;candsq&#93;))
                candsq = *sqptr++;

              // Was a candidate pinned man found?
              
              if (&#40;CvManToColor&#91;candman&#93; == color&#41; && !IsManKing&#40;candman&#41; &&
                  BoardTestClearPath&#40;boardptr, dir, candsq, kingsq&#41;)
              &#123;
                const Ti candti = trackerptr->tivec&#91;candsq&#93;;
                bool freeze = false;

                // Pinned status recording
                
                SetTi&#40;positionptr->apd.pinned, candti&#41;;

                // Determine frozen status based on pinned man and pinning direction
                
                switch &#40;candman&#41;
                &#123;
                  case ManWhitePawn&#58;
                    if &#40;IsDirPawnFreezeWhite&#40;CvDirToOtherDir&#91;dir&#93;))
                      freeze = true;
                    break;

                  case ManBlackPawn&#58;
                    if &#40;IsDirPawnFreezeBlack&#40;CvDirToOtherDir&#91;dir&#93;))
                      freeze = true;
                    break;

                  case ManWhiteKnight&#58;
                  case ManBlackKnight&#58;
                    freeze = true;
                    break;

                  case ManWhiteBishop&#58;
                  case ManBlackBishop&#58;
                    if &#40;IsDirOrtho&#40;dir&#41;)
                      freeze = true;
                    break;

                  case ManWhiteRook&#58;
                  case ManBlackRook&#58;
                    if &#40;IsDirDiago&#40;dir&#41;)
                      freeze = true;
                    break;

                  default&#58;
                    break;
                &#125;;
                
                // Frozen status recording
                
                if &#40;freeze&#41;
                  SetTi&#40;positionptr->apd.frozen, candti&#41;;
              &#125;;
            &#125;;
          &#125;;
        &#125;;
      &#125;;
    &#125;;
  &#125;;
&#125;

[sje]

Oscar, like Symbolic, does not support variations of orthodox castling rules such as are needed with Chess960 (i,e., Fischer Random Chess). This is in part because I am lazy, and in part because I don't have much of an interest with non-standard castling.

But others aren't as lazy as me, or perhaps do have an interest. Therefore, Oscar has table driven castling to make it easier for a coder to introduce support for heterodox castling variations.

The CastInfoRec structure:

Code: Select all

// Castling information record

typedef struct
{
  char  fenchar;  // FEN castling availabilty character
  ui    castbit;  // Cabs bit mask
  Color color;    // Color on the move
  Man   king;     // Moving king
  Man   rook;     // Moving rook
  Mc    mc;       // Move special case
  Sq    kinghome; // King home square
  Sq    kingaway; // King away square
  Sq    rookhome; // Rook home square
  Sq    rookaway; // Rook away square
  Sq    optsq;    // Optional square vacancy test (may be SqNil)
} CastInfoRec;

And the corresponding table with a constant initialization:

Code: Select all

static const CastInfoRec CastInfo[CastlingLen] =
{
  {'Q', BX(0), ColorWhite, ManWhiteKing, ManWhiteRook, McCQS, SqE1, SqC1, SqA1, SqD1, SqB1 },
  {'K', BX(1), ColorWhite, ManWhiteKing, ManWhiteRook, McCKS, SqE1, SqG1, SqH1, SqF1, SqNil},
  {'q', BX(2), ColorBlack, ManBlackKing, ManBlackRook, McCQS, SqE8, SqC8, SqA8, SqD8, SqB8 },
  {'k', BX(3), ColorBlack, ManBlackKing, ManBlackRook, McCKS, SqE8, SqG8, SqH8, SqF8, SqNil}
};

An example of its use:

Code: Select all

static bool PositionTestCastling(const Position * const positionptr, const Castling castling)
{
  const Man * const manvec = positionptr->board.manvec;
  const Color other = CvColorToOtherColor[CastInfo[castling].color];
  bool result;

  if ((positionptr->fss.cabs & CastInfo[castling].castbit) &&
      (CastInfo[castling].color == positionptr->fss.good) &&
      !positionptr->apd.incheck &&
      IsManVacant(manvec[CastInfo[castling].rookaway]) &&
      IsManVacant(manvec[CastInfo[castling].kingaway]) &&
      (IsSqNil(CastInfo[castling].optsq) || IsManVacant(manvec[CastInfo[castling].optsq])) &&
      !PositionColorAttacksSq(positionptr, other, CastInfo[castling].rookaway) &&
      !PositionColorAttacksSq(positionptr, other, CastInfo[castling].kingaway))
    result = true;
  else
    result = false;
  return result;
}

[sje]

And somewhere in the Position validity testing routine:

Code: Select all

  if (isvalid && (cabs != CabsNone))
  {
    Castling castling = CastlingWQ;

    while &#40;isvalid && &#40;castling <= CastlingBK&#41;)
    &#123;
      if &#40;cabs & CastInfo&#91;castling&#93;.castbit&#41;
      &#123;
        if (&#40;manvec&#91;CastInfo&#91;castling&#93;.kinghome&#93; != CastInfo&#91;castling&#93;.king&#41; ||
            &#40;manvec&#91;CastInfo&#91;castling&#93;.rookhome&#93; != CastInfo&#91;castling&#93;.rook&#41;)
          isvalid = false;
      &#125;;
      castling++;
    &#125;;
  &#125;;

The four possible castling moves are constants initialized at program start time:

Code: Select all

static void InitCastlingMoves(void)
{
  Castling castling;

  for &#40;castling = CastlingWQ; castling <= CastlingBK; castling++)
  &#123;
    Move move = VoidMove;

    PutFrSqFrMan&#40;move, CastInfo&#91;castling&#93;.kinghome, CastInfo&#91;castling&#93;.king&#41;;
    PutToSqToMan&#40;move, CastInfo&#91;castling&#93;.kingaway, ManVacant&#41;;
    PutMc&#40;move, CastInfo&#91;castling&#93;.mc&#41;;
    CastlingMoves&#91;castling&#93; = move;
  &#125;;
&#125;

Castling move execution:

Code: Select all

    case McCQS:  // Castle queenside
    case McCKS:  // Castle kingside
      {
        const Castling castling = CvColorMcToCastling[good][mc];
        const Sq r0sq = CastInfo[castling].rookhome;
        const Sq r1sq = CastInfo[castling].rookaway;
        const Man rook = CastInfo[castling].rook;

        TrackerMovement(trackerptr, frsq, tosq);
        TrackerMovement(trackerptr, r0sq, r1sq);
        manvec[frsq] = ManVacant;
        manvec[tosq] = frman;
        HashFoldManSqSq(msigptr, frman, frsq, tosq);
        manvec[r0sq] = ManVacant;
        manvec[r1sq] = rook;
        HashFoldManSqSq(msigptr, rook, r0sq, r1sq);
      };
      break;

Castling move retraction:

Code: Select all

    case McCQS:  // Castle queenside
    case McCKS:  // Castle kingside
      {
        const Castling castling = CvColorMcToCastling[good][mc];
        const Sq r0sq = CastInfo[castling].rookhome;
        const Sq r1sq = CastInfo[castling].rookaway;

        TrackerMovement(trackerptr, r1sq, r0sq);
        TrackerMovement(trackerptr, tosq, frsq);
        manvec[r0sq] = CastInfo[castling].rook;
        manvec[r1sq] = ManVacant;
        manvec[frsq] = frman;
        manvec[tosq] = ManVacant;
      };
      break;

[jdart]

What is a "frozen target"?

--Jon

[sje]

What is a "frozen target"?

A frozen target is a chessman with as much mobility as an ice statue.

Specifically, a frozen man is a pinned man which no mobility because of the combination of the pinning direction and the chessman's unpinned powers of movement.

A pinned knight is always frozen.
A pinned bishop is frozen when pinned orthogonally.
A pinned rook is frozen when pinned diagonally.
A pinned queen is never frozen.

Determining the frozen status of pinned pawns are a little more complicated.

A pinned pawn is frozen when pinned horizontally.
A pinned pawn is not frozen when pinned vertically.

Diagonal pins of pawns are handled according to the color of the pawn. Pawns pinned diagonally from behind are frozen, but not those pinned diagonally from ahead. Pawns pinned diagonally from ahead may have one move at most; to capture the pinning man.

Oscar keeps track of pinned targets in a 32 bit target bit vector. The same with frozen targets. At move generation time, frozen targets are skipped (a time saver); the pin status and direction of pinned targets is handled appropriately to ensure legal-only move output.

The PositionRegenerateApd() routine eats a lot of time, about 13% of the total. But knowing the mobility limitations pays off in both the generation routines and the bulk counting routines. It is possible to cut the time used in PositionRegenerateApd() by close to 50% by handling only pinned/frozen calculations for the side to move. However, if Oscar is used as part of a general purpose chess program, then it's possible that the pinned/frozen calculations will be need for both colors.

Note that all the calculation results of PositionRegenerateApd() are saved in a list, so the calculations need be done only once per position.

[sje]

Diagonal pins of pawns are handled according to the color of the pawn. Pawns pinned diagonally from behind are frozen, but not those pinned diagonally from ahead. Pawns pinned diagonally from ahead may have one move at most; to capture the pinning man.

Also, a pinned pawn can make an en passant capture if the pin direction is from the front and the path from the pinning piece intersects the en passant target square. However, this cannot help with check evasion.

[sje]

Path pre-calculation

Oscar uses path pre-calculation at program start time to generate all possible movement pathways for each direction for each square. Each pathway is just a linear sequence of square indexes terminated with the value SqNil (-1).

These paths are handy as they eliminate the need for fiddling with square indexes and directional offsets when determining the next square or the edge of the board. An example use from Oscar who has no bitboards:

Code: Select all

static bool BoardTestClearPath(const Board * const boardptr, const Dir dir, const Sq frsq, const Sq tosq)
{
  // This routine checks for a path of vacant squares along a sweep direction.

  bool result = true;
  const Sq *sqptr = SweeperRunPtrs[dir][frsq];
  Sq scansq = *sqptr++;

  while (result && (scansq != tosq))
  {
    if (IsManVacant(boardptr->manvec[scansq]))
      scansq = *sqptr++;
    else
      result = false;
  };
  return result;
}

There's similar code used for generating sweeper moves and for detecting pinned men.

The sweeper path data is stored here:

Code: Select all

static Sq SweeperRunSqs[SweepRunLen];                 // Sweeper square run sequences
static const Sq *SweeperRunPtrs[DirSweepLen][SqLen];  // Pointers into the above

Now, here's the trick: Most square run sequences are sub-sequences of longer square run sequences. Wouldn't it be nice if all the sequences were overlaid as much as possible? This would save space and increase the cache hit rate, too. I did this in Symbolic using a neat recursive approach, but had to re-write the code for Oscar as OpenCL disallows recursion.

Oscar's sweeper path data initialization routine:

Code: Select all

static void InitSweeperRuns(void)
{
  // This routine provides the constant values for the SweeperRunPtrs and the SweeperRunSqs arrays.

  Sq *nextptr = &SweeperRunSqs[0];
  Dir dir;

  // Pass 0: reset all pointers

  for &#40;dir = DirSweep0; dir <= DirSweep1; dir++)
  &#123;
    Sq frsq;

    for &#40;frsq = SqA1; frsq <= SqH8; frsq++)
      SweeperRunPtrs&#91;dir&#93;&#91;frsq&#93; = 0;
  &#125;;

  // Pass 1&#58; Assign pointers and squares for all paths without predecessor squares

  for &#40;dir = DirSweep0; dir <= DirSweep1; dir++)
  &#123;
    Sq frsq;

    for &#40;frsq = SqA1; frsq <= SqH8; frsq++)
    &#123;
      if &#40;IsSqNil&#40;NextSq&#91;CvDirToOtherDir&#91;dir&#93;&#93;&#91;frsq&#93;))
      &#123;
        Sq tosq = frsq;

        SweeperRunPtrs&#91;dir&#93;&#91;frsq&#93; = nextptr;
        do
        &#123;
          tosq = NextSq&#91;dir&#93;&#91;tosq&#93;;
          *nextptr++ = tosq;
        &#125; while &#40;IsSqNotNil&#40;tosq&#41;);
      &#125;;
    &#125;;
  &#125;;

  // Pass 2&#58;  Assign all remaining pointers

  for &#40;dir = DirSweep0; dir <= DirSweep1; dir++)
  &#123;
    Sq frsq;

    for &#40;frsq = SqA1; frsq <= SqH8; frsq++)
    &#123;
      if &#40;SweeperRunPtrs&#91;dir&#93;&#91;frsq&#93; == 0&#41;
      &#123;
        const Dir otherdir = CvDirToOtherDir&#91;dir&#93;;
        Sq tosq = frsq;
        ui count = 0;

        while &#40;SweeperRunPtrs&#91;dir&#93;&#91;tosq&#93; == 0&#41;
        &#123;
          tosq = NextSq&#91;otherdir&#93;&#91;tosq&#93;;
          count++;
        &#125;;
        SweeperRunPtrs&#91;dir&#93;&#91;frsq&#93; = SweeperRunPtrs&#91;dir&#93;&#91;tosq&#93; + count;
      &#125;;
    &#125;;
  &#125;;
&#125;

The above jams all the path data into an array of square indexes using only 512 elements.

There are similar arrays used for pawn, knight, and king motions.