OpenCL perft() Technical Issues

[sje]

Simple and fast, the en passant legality tester is called at generation time to confirm or deny the validity of an en passant capture:

Code: Select all

static bool PositionTestEpCaptureMove(Position * const positionptr, const Move move)
{
  // This routine tests the legality of the given en passant capture in the given position.

  Tracker * const trackerptr = &positionptr->tracker;
  Man * const manvec = positionptr->board.manvec;
  const Color evil = positionptr->fss.evil;
  const Man frman = GetFrMan(move);
  const Sq frsq = GetFrSq(move);
  const Sq tosq = GetToSq(move);
  const Sq vpsq = NextSq[CvColorToAdvDir[evil]][tosq];

  TrackerCapture(trackerptr, vpsq);
  TrackerMovement(trackerptr, frsq, tosq);
  manvec[vpsq] = ManVacant;
  manvec[frsq] = ManVacant;
  manvec[tosq] = frman;

  const bool isbroken = PositionCalcGoodInCheck(positionptr);

  TrackerMovement(trackerptr, tosq, frsq);
  TrackerRestore(trackerptr);
  manvec[vpsq] = CvColorToPawn[evil];
  manvec[frsq] = frman;
  manvec[tosq] = ManVacant;

  return !isbroken;
}

[sje]

The following routine tests for an attack from one square to another. Oscar spends about 1/7th of its time here; a penalty for not having bitboards.

Code: Select all

static bool PositionSqAttacksSq(const Position * const positionptr, const Sq frsq, const Sq tosq)
{
  // This routine tests for an attack from one square to another in the given position.

  bool result = false;
  const ui16 infoword = SqSqInfo[frsq][tosq];

  if (infoword)
  {
    switch (positionptr->board.manvec[frsq])
    {
      case ManWhitePawn:
        if (infoword & InfoAtkfWP)
          result = true;
        break;

      case ManBlackPawn:
        if (infoword & InfoAtkfBP)
          result = true;
        break;

      case ManWhiteKnight:
      case ManBlackKnight:
        if (infoword & InfoDCrook)
          result = true;
        break;

      case ManWhiteBishop:
      case ManBlackBishop:
        if ((infoword & InfoDDiago) &&
            ((infoword & InfoAdjSqs) ||
             BoardTestClearPath(&positionptr->board, MapInfoWordToDir(infoword), frsq, tosq)))
          result = true;
        break;

      case ManWhiteRook:
      case ManBlackRook:
        if ((infoword & InfoDOrtho) &&
            ((infoword & InfoAdjSqs) ||
             BoardTestClearPath(&positionptr->board, MapInfoWordToDir(infoword), frsq, tosq)))
          result = true;
        break;

      case ManWhiteQueen:
      case ManBlackQueen:
        if ((infoword & InfoDSweep) &&
            ((infoword & InfoAdjSqs) ||
             BoardTestClearPath(&positionptr->board, MapInfoWordToDir(infoword), frsq, tosq)))
          result = true;
        break;

      case ManWhiteKing:
      case ManBlackKing:
        if (infoword & InfoAdjSqs)
          result = true;
        break;

      default:
        break;
    };
  };
  return result;
}

[sje]

Two routines for scanning all men of one side for attacks to a square:

Code: Select all

static ui PositionCountColorAttacksToSq(const Position * const positionptr, const Color color, const Sq tosq,
                                        TiBV * const tibvptr)
{
  // This routine counts the attacks from a color to a square in the given position.

  ui result = 0;
  const Sq * const sqvec = positionptr->tracker.sqvec;
  const TiBV occupied = positionptr->tracker.tbvs.occupied;
  const Ti stopti = CvColorToStopTi[color];
  Ti ti;

  // This routine also sets a target index bit vector with attacking targets.

  *tibvptr = 0;
  for &#40;ti = CvColorToKingTi&#91;color&#93;; ti <= stopti; ti++)
  &#123;
    if &#40;TestTi&#40;occupied, ti&#41; && PositionSqAttacksSq&#40;positionptr, sqvec&#91;ti&#93;, tosq&#41;)
    &#123;
      SetTi&#40;*tibvptr, ti&#41;;
      result++;
    &#125;;
  &#125;;
  return result;
&#125;

static bool PositionColorAttacksSq&#40;const Position * const positionptr, const Color color, const Sq tosq&#41;
&#123;
  // This routine tests for an attack from a color to a square in the given position.

  bool result = false;
  const Sq * const sqvec = positionptr->tracker.sqvec;
  const TiBV occupied = positionptr->tracker.tbvs.occupied;
  const Ti stopti = CvColorToStopTi&#91;color&#93;;
  Ti ti = CvColorToKingTi&#91;color&#93;;

  while (!result && &#40;ti <= stopti&#41;)
  &#123;
    if &#40;TestTi&#40;occupied, ti&#41; && PositionSqAttacksSq&#40;positionptr, sqvec&#91;ti&#93;, tosq&#41;)
      result = true;
    else
      ti++;
  &#125;;
  return result;
&#125;

[mvk]

I will gladly host a new version of the specification document. Thanks for your effort.

Thank you. I hope to put some time in on this soon, perhaps as soon as I get the first OpenCL version of Oscar running.

There was a change with EPD, too. Old style EPD had only the first four fields of a record match the FEN; now, all six FEN fields appear.

Nice. Just take your time. I'm obviously not in a hurry. P.S.

[sje]

Work unit wu7.964 is the last of the 965 work unit files in the Perft(14) project. The gzip version is here: https://dl.dropboxusercontent.com/u/316 ... wu7.964.gz

Because this work unit has only a 68 record size instead of a 100,000 record size for each of the first 964 work units, it'll be used for testing operft in work unit mode.

Operft says:

Code: Select all

File: wu7.964  records: 68   depth: 0   total: 68
File: wu7.964  records: 68   depth: 1   total: 1999
File: wu7.964  records: 68   depth: 2   total: 61251
File: wu7.964  records: 68   depth: 3   total: 1832565
File: wu7.964  records: 68   depth: 4   total: 56936830
File: wu7.964  records: 68   depth: 5   total: 1748390067
File: wu7.964  records: 68   depth: 6   total: 55612988156
File: wu7.964  records: 68   depth: 7   total: 1755725051762

The above are just the sum of the perft() values; calculating the sum of the products of the perft() and the occurrence count is still to come.

[sje]

I got the same results and also:

Code: Select all

Depth: 6   Total: 809264359148
Depth: 7   Total: 33043845819034

Oscar concurs. I ran those with a smaller transposition table with only 2^20 entries and it took quite a while.

[sje]

Two more FEN files

To test Oscar's capability to recognize checkmates and stalemates, I've added two FEN files to the testing repertoire. These are:

https://dl.dropboxusercontent.com/u/316 ... kmates.fen
https://dl.dropboxusercontent.com/u/316 ... emates.fen

Both files contain exactly 100,000 FEN records. The first file is composed of checkmate positions and the second is composed of stalemate positions.

I've made these public so that chess program authors may test their mate detection code for speed and accuracy.

[sje]

A FEN file containing only mate-in-1 positions

Although not necessary for perft() calculations, Oscar has a mate-in-1 detector which helps test the program's other code.

The mate-in-1 detector itself is tested with the assistance of a 100,000 record FEN file:

https://dl.dropboxusercontent.com/u/316 ... atein1.fen

Fer each position in the above, there is at least one checkmating move.

I've made this file public so that chess program authors may test their mate-in-1 detection code for speed and accuracy.

[sje]

One plus two, times three

Oscar has one main move generation routine which produces all legal-only moves for a position. It calls one of two other routines each time; one for check evasion moves and the other for non-evasion moves:

Code: Select all

static void PositionGenerate(Position * const positionptr, MoveSeg * const movesegptr)
{
  // This routine generates the moves for the given position.

  if (positionptr->apd.incheck)
    PositionGenerateEvasion(positionptr, movesegptr);
  else
    PositionGenerateNotInCheck(positionptr, movesegptr);
}

There is a second related routine which counts the moves in a position, and it has a similar structure:

Code: Select all

static ui PositionCountMoves(Position * const positionptr)
{
  // This routine counts the number of available moves for the given position.

  ui count;

  if (positionptr->apd.incheck)
    count = PositionCountMovesEvasion(positionptr);
  else
    count = PositionCountMovesNotInCheck(positionptr);
  return count;
}

And there is a third routine with the same structure as the first two; it determines if the given position is a mate (checkmate/stalemate):

Code: Select all

static bool PositionHasNoMoves(Position * const positionptr)
{
  // This routine is the checkmate/stalemate detector for the given position.

  bool hasnomoves;

  if (positionptr->apd.incheck)
    hasnomoves = PositionHasNoMovesEvasion(positionptr);
  else
    hasnomoves = PositionHasNoMovesNotInCheck(positionptr);
  return hasnomoves;
}

The three PositionGenerate() routines were written first and then carefully debugged and optimized. After this, the three PositionCountMoves() routines were written using the PositionGenerate() routines as a guide. Finally, the three PositionHasNoMoves() routines were written using the PositionCountMoves() routines as a guide.

This way, when there are bugs, at least the bugs are consistent!

[sje]

The treasure box

At start up time, Oscar calculates the constant values for the SqSqInfo[64][64] array where each element is a 32 bit integer with each bit representing the value of some boolean property of the corresponding ordered pair of squares. Throughout the rest of the program's execution, referencing these elements saves a great deal of processing time.

Currently, only 24 of the 32 bits are in use; the remaining eight bits are reserved for future expansion.

Code: Select all

// SqSqInfo[frsq][tosq] array element type

typedef ui32 InfoBits;

// SqSqInfo[frsq][tosq] array element coding

#define InfoHasDir BX(0x17)  // Has a directional relationship; if 0 then all bits are 0
#define InfoAdjSqs BX(0x16)  // Squares are adjacent
#define InfoSmRank BX(0x15)  // Squares are on same rank
#define InfoSmFile BX(0x14)  // Squares are on same file
#define InfoPromBP BX(0x13)  // Promotion: black pawn
#define InfoPromWP BX(0x12)  // Promotion: white pawn
#define InfoDAdvBP BX(0x11)  // Double square advance: black pawn
#define InfoDAdvWP BX(0x10)  // Double square advance: white pawn
#define InfoSAdvBP BX(0x0f)  // Single square advance: black pawn
#define InfoSAdvWP BX(0x0e)  // Single square advance: white pawn
#define InfoPathBP BX(0x0d)  // Forward path of black pawn on from square includes to square
#define InfoPathWP BX(0x0c)  // Forward path of white pawn on from square includes to square
#define InfoAtkfBP BX(0x0b)  // From square has a black pawn attack on the to square
#define InfoAtkfWP BX(0x0a)  // From square has a white pawn attack on the to square
#define InfoBdrBt1 BX(0x09)  // Bidirection bit 1
#define InfoBdrBt0 BX(0x08)  // Bidirection bit 0
#define InfoDOrtho BX(0x07)  // Direction is ortho
#define InfoDDiago BX(0x06)  // Direction is diago
#define InfoDCrook BX(0x05)  // Direction is crook
#define InfoDSweep BX(0x04)  // Direction is sweep
#define InfoDirBt3 BX(0x03)  // Direction bit 3
#define InfoDirBt2 BX(0x02)  // Direction bit 2
#define InfoDirBt1 BX(0x01)  // Direction bit 1
#define InfoDirBt0 BX(0x00)  // Direction bit 0

#define InfoDirMsk MX(4)   // Lowest four bits gives the from/to direction (if any)

#define MapInfoBitsToDir(infobits)   ((Dir)   ((infobits) & InfoDirMsk))
#define MapInfoBitsToBidir(infobits) ((Bidir) (((infobits) >> 8) & MX(2)))

#define InfoIpMaskWP (InfoSAdvWP | InfoDAdvWP)
#define InfoIpMaskBP (InfoSAdvBP | InfoDAdvBP)

#define InfoSAdvMask (InfoSAdvWP | InfoSAdvBP)
#define InfoDAdvMask (InfoDAdvWP | InfoDAdvBP)
#define InfoPromMask (InfoPromWP | InfoPromBP)

Anytime Oscar needs to know some constant property value of a pair of squares, it just looks at the corresponding SqSqInfo element and tests the appropriate bit or bits. The code is not only faster than a dynamic calculation, but it is also simpler. The biggest gains are seen in check evasion code when examining possible pawn interpositions.

The price to be paid is some start up overhead plus 16 KB of table storage. That's not much for most applications, but it might be too much for some embedded hosts with little RAM to spare.