OpenCL perft() Technical Issues

Discussion of chess software programming and technical issues.

Moderators: hgm, Rebel, chrisw

mvk
Posts: 589
Joined: Tue Jun 04, 2013 10:15 pm

Re: About that en passant target square

Post by mvk »

sje wrote:About that en passant target square in a FEN string:

The original FEN specification is incorrect concerning the en passant target square.

The correct version is: The en passant target square which appears as the fourth field of a FEN record shall be "-" (nil) if no en passant capture is available. If an en passant capture is available, then the en passant target square will be the name of the destination square of an en passant capture. Note that for a non-nil en passant target square in a FEN string there will be at least one en passant capture in the position described by the FEN string; there may be two.
Where can this updated version be obtained from? I googled for your proposed revised text (which I wholeheartedly agree with), but nothing shows up. All resources I can find point to the versions I mentioned, including the important references (chess programming wiki, wikipedia, ...)
sje wrote:Alas, there was no Internet in those days and so he [=Forsyth] couldn't do much about the half dozen variants that evolved over the years.
It seems that the impact of the Internet is indeed to standardise, but on the faulty version in this case.
[Account deleted]
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: About that en passant target square

Post by sje »

mvk wrote:Where can this updated version be obtained from? I googled for your proposed revised text (which I wholeheartedly agree with), but nothing shows up. All resources I can find point to the versions I mentioned, including the important references (chess programming wiki, wikipedia, ...)
Now that you know the correct information, perhaps you could help propagate it to those sites which haven't yet been updated.
mvk
Posts: 589
Joined: Tue Jun 04, 2013 10:15 pm

Re: About that en passant target square

Post by mvk »

I will gladly host a new version of the specification document. Thanks for your effort.
[Account deleted]
bob
Posts: 20943
Joined: Mon Feb 27, 2006 7:30 pm
Location: Birmingham, AL

Re: Pin detection without bitboards

Post by bob »

sje wrote:
jdart wrote: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.
Chess players usually call this an "absolute pin" which means "pinned on king so that it can't move out of the way."
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: Pin detection without bitboards

Post by sje »

bob wrote:Chess players usually call this an "absolute pin" which means "pinned on king so that it can't move out of the way."
You're right, of course.

But I wanted a structure component identifier which had the same number of letters as "pinned" and which meant "immovable". The word "frozen" won out over "jammed". This is all true.

This all came about in my first bitboard program long ago. There was a third btiboard of men which were pinned but not frozen; these men were called "restricted". This term lives in Oscar in the form of "resdir" (restriction direction) and resbidir" (restricted bidirection). "Bidirection" is a neologism of my own:

Code: Select all

// Chessboard square-to-square direction: 4 orthogonal, 4 diagonal, 8 crooked (White POV)

typedef enum
{
  DirNil = -1,
  DirE,   DirN,   DirW,   DirS,    // Orthogonal
  DirNE,  DirNW,  DirSW,  DirSE,   // Diagonal
  DirENE, DirNNE, DirNNW, DirWNW,  // Crooked (1st half)
  DirWSW, DirSSW, DirSSE, DirESE   // Crooked (2nd half)
} Dir;

#define DirLen (DirESE + 1)

#define DirOrtho0   DirE
#define DirOrtho1   DirS
#define DirOrthoLen (((si) DirS  ) - ((si) DirE  ) + 1)

#define DirDiago0   DirNE
#define DirDiago1   DirSE
#define DirDiagoLen (((si) DirSE ) - ((si) DirNE ) + 1)

#define DirSweep0   DirE
#define DirSweep1   DirSE
#define DirSweepLen (((si) DirSE ) - ((si) DirE  ) + 1)

#define DirCrook0   DirENE
#define DirCrook1   DirESE
#define DirCrookLen (((si) DirESE) - ((si) DirENE) + 1)

#define IsDirNil&#40;dir&#41;    (&#40;dir&#41; <  0&#41;
#define IsDirNotNil&#40;dir&#41; (&#40;dir&#41; >= 0&#41;

#define IsDirOrtho&#40;dir&#41; &#40;0x000f & BX&#40;dir&#41;)
#define IsDirDiago&#40;dir&#41; &#40;0x00f0 & BX&#40;dir&#41;)
#define IsDirSweep&#40;dir&#41; &#40;0x00ff & BX&#40;dir&#41;)
#define IsDirCrook&#40;dir&#41; &#40;0xff00 & BX&#40;dir&#41;)

#define IsDirPawnFreezeWhite&#40;dir&#41; &#40;0x00c5 & BX&#40;dir&#41;)
#define IsDirPawnFreezeBlack&#40;dir&#41; &#40;0x0035 & BX&#40;dir&#41;)

// Chessboard square-to-square bidirection

typedef enum
&#123;
  BidirNil = -1,
  BidirE,   // East      <-> West
  BidirN,   // North     <-> South
  BidirNE,  // Northeast <-> Southwest
  BidirNW   // Northwest <-> Southeast
&#125; Bidir;

#define BidirLen &#40;BidirNW + 1&#41;

#define IsBidirNil&#40;bidir&#41;    &#40;bidir <  0&#41;
#define IsBidirNotNil&#40;bidir&#41; &#40;bidir >= 0&#41;

#define IsBidirOrtho&#40;bidir&#41; &#40;0x0003 & BX&#40;bidir&#41;)
#define IsBidirDiago&#40;bidir&#41; &#40;0x000c & BX&#40;bidir&#41;)

Code: Select all

static const Bidir CvDirToBidir&#91;DirSweepLen&#93; =
&#123;
  BidirE, BidirN, BidirE, BidirN, BidirNE, BidirNW, BidirNE, BidirNW
&#125;;
Somewhat wordy, but it makes the legal-only generator code quick and easy to read.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Re: About that en passant target square

Post by sje »

mvk wrote: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.
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Code snippet: Move generation (check evasion)

Post by sje »

Oscar's move generation code is fairly stable now, so I'll post some of the routines.

The first is the code for generating moves when the side to move is in check:

Code: Select all

static ui PositionGenerateEvasion&#40;Position * const positionptr, MoveSeg * const movesegptr&#41;
&#123;
  // This routine generates the moves for the given position; it's called only when in check.

  const Sq * const sqvec = positionptr->tracker.sqvec;
  const Man * const manvec = positionptr->board.manvec;

  const Color good = positionptr->fss.good;
  const Color evil = positionptr->fss.evil;
  const Sq epsq = positionptr->fss.epsq;

  const Man goodking = CvColorToKing&#91;good&#93;;
  const Man goodpawn = CvColorToPawn&#91;good&#93;;
  const Sq goodkingsq = PositionGetGoodKingSq&#40;positionptr&#41;;
  const Dir advdir = CvColorToAdvDir&#91;good&#93;;
  const Rank cr2rank = CvColorRankToNormalRank&#91;good&#93;&#91;Rank2&#93;;
  const Rank cr4rank = CvColorRankToNormalRank&#91;good&#93;&#91;Rank4&#93;;
  const Rank cr8rank = CvColorRankToNormalRank&#91;good&#93;&#91;Rank8&#93;;

  const Ti goodpeonti = CvColorToPeonTi&#91;good&#93;;
  const Ti evilpeonti = CvColorToPeonTi&#91;evil&#93;;
  const Ti goodstopti = CvColorToStopTi&#91;good&#93;;
  const Ti evilstopti = CvColorToStopTi&#91;evil&#93;;

  const bool singlecheck = !positionptr->apd.dbcheck;

  const TiBV checkers = positionptr->apd.checkers;
  const TiBV goodguys = positionptr->tracker.tbvs.occupied & CvColorToTargetSetMask&#91;good&#93;;
  const TiBV goodpawns = goodguys & positionptr->tracker.tbvs.pawns;
  const TiBV helpers = goodguys & ~positionptr->apd.pinned;
  const TiBV helperdudes = helpers & ~goodpawns;
  const TiBV helperpawns = helpers & goodpawns;

  MoveSegReset&#40;movesegptr&#41;;

  Move *moveptr = movesegptr->baseptr;

  Ti checkerti = TiNil;
  Sq checkersq = SqNil;
  Man checkerman = ManNil;
  bool checkeropr = false;
  ui16 interposeinfoword = 0;
  Dir interposedir = DirNil;
  bool tryinterposition = false;

  // Initialize single checker items

  if &#40;singlecheck&#41;
  &#123;
    Ti evilti = evilpeonti;

    while &#40;IsTiNil&#40;checkerti&#41; && &#40;evilti <= evilstopti&#41;)
    &#123;
      if &#40;TestTi&#40;checkers, evilti&#41;)
      &#123;
        checkerman = manvec&#91;checkersq = sqvec&#91;checkerti = evilti&#93;&#93;;
        checkeropr = &#40;MapSqToRank&#40;checkersq&#41; == cr8rank&#41;;
        interposeinfoword = SqSqInfo&#91;goodkingsq&#93;&#91;checkersq&#93;;
        interposedir = MapInfoWordToDir&#40;interposeinfoword&#41;;
        tryinterposition = IsManSweeper&#40;checkerman&#41; && !&#40;interposeinfoword & InfoAdjSqs&#41;;
      &#125;
      else
        evilti++;
    &#125;;
  &#125;;

  // Attempt non en passant capture of a singleton attacker &#40;no king moves&#41;

  if &#40;singlecheck&#41;
  &#123;
    Ti goodti;
    Move move = VoidMove;

    PutToSqToMan&#40;move, checkersq, checkerman&#41;;
    for &#40;goodti = goodpeonti; goodti <= goodstopti; goodti++)
    &#123;
      if &#40;TestTi&#40;helpers, goodti&#41;)
      &#123;
        const Sq frsq = sqvec&#91;goodti&#93;;

        if &#40;PositionSqAttacksSq&#40;positionptr, frsq, checkersq&#41;)
        &#123;
          const Man frman = manvec&#91;frsq&#93;;

          PutFrSqFrMan&#40;move, frsq, frman&#41;;
          if (&#40;frman != goodpawn&#41; || !checkeropr&#41;
            *moveptr++ = move;
          else
          &#123;
            Mc mc;

            for &#40;mc = McPPN; mc <= McPPQ; mc++)
            &#123;
              PutMc&#40;move, mc&#41;;
              *moveptr++ = move;
            &#125;;
            PutMc&#40;move, McReg&#41;;
          &#125;;
        &#125;;
      &#125;;
    &#125;;
  &#125;;

  // Attempt king moves

  &#123;
    const TiBV sweepercheckers = positionptr->tracker.tbvs.sweepers & checkers;
    Move move = VoidMove;
    Dir dir;
    Sq flight&#91;DirSweepLen&#93;;
    Ti evilti;

    PutFrSqFrMan&#40;move, goodkingsq, goodking&#41;;

    // Initialize the flight square vector

    for &#40;dir = DirSweep0; dir <= DirSweep1; dir++)
    &#123;
      const Sq tosq = NextSq&#91;dir&#93;&#91;goodkingsq&#93;;

      if &#40;IsSqNil&#40;tosq&#41; ||
          &#40;CvManToColor&#91;manvec&#91;tosq&#93;&#93; == good&#41; ||
          PositionColorAttacksSq&#40;positionptr, evil, tosq&#41;)
        flight&#91;dir&#93; = SqNil;
      else
        flight&#91;dir&#93; = tosq;
    &#125;;

    // Remove shadows from the flight square vector

    for &#40;evilti = evilpeonti; evilti <= evilstopti; evilti++)
      if &#40;TestTi&#40;sweepercheckers, evilti&#41;)
        flight&#91;MapInfoWordToDir&#40;SqSqInfo&#91;sqvec&#91;evilti&#93;&#93;&#91;goodkingsq&#93;)&#93; = SqNil;

    // All remaining flight squares are legal king destinations

    for &#40;dir = DirSweep0; dir <= DirSweep1; dir++)
    &#123;
      const Sq tosq = flight&#91;dir&#93;;

      if &#40;IsSqNotNil&#40;tosq&#41;)
      &#123;
        PutToSqToMan&#40;move, tosq, manvec&#91;tosq&#93;);
        *moveptr++ = move;
      &#125;;
    &#125;;
  &#125;;

  // Attempt non-pawn interposition

  if &#40;tryinterposition&#41;
  &#123;
    const Sq *tosqptr = SweeperRunPtrs&#91;interposedir&#93;&#91;goodkingsq&#93;;
    Sq tosq = *tosqptr++;
    Move move = VoidMove;

    PutToMan&#40;move, ManVacant&#41;;
    while &#40;tosq != checkersq&#41;
    &#123;
      Ti goodti;

      PutToSq&#40;move, tosq&#41;;
      for &#40;goodti = goodpeonti; goodti <= goodstopti; goodti++)
      &#123;
        if &#40;TestTi&#40;helperdudes, goodti&#41;)
        &#123;
          const Sq frsq = sqvec&#91;goodti&#93;;

          if &#40;PositionSqAttacksSq&#40;positionptr, frsq, tosq&#41;)
          &#123;
            PutFrSqFrMan&#40;move, frsq, manvec&#91;frsq&#93;);
            *moveptr++ = move;
          &#125;;
        &#125;;
      &#125;;
      tosq = *tosqptr++;
    &#125;;
  &#125;;

  // Attempt pawn interposition

  if &#40;tryinterposition&#41;
  &#123;
    const ui pathmask = CvColorToPawnPathMask&#91;good&#93;;
    const Sq *tosqptr = SweeperRunPtrs&#91;interposedir&#93;&#91;goodkingsq&#93;;
    Sq tosq = *tosqptr++;
    Move move = VoidMove;

    PutFrMan&#40;move, goodpawn&#41;;
    PutToMan&#40;move, ManVacant&#41;;
    while &#40;tosq != checkersq&#41;
    &#123;
      const Rank torank = MapSqToRank&#40;tosq&#41;;
      Ti goodti;

      PutToSq&#40;move, tosq&#41;;
      for &#40;goodti = goodpeonti; goodti <= goodstopti; goodti++)
      &#123;
        if &#40;TestTi&#40;helperpawns, goodti&#41;)
        &#123;
          const Sq frsq = sqvec&#91;goodti&#93;;

          if &#40;SqSqInfo&#91;frsq&#93;&#91;tosq&#93; & pathmask&#41;
          &#123;
            const Sq advsq = NextSq&#91;advdir&#93;&#91;frsq&#93;;

            PutFrSq&#40;move, frsq&#41;;
            if &#40;advsq == tosq&#41;
            &#123;
              if &#40;torank != cr8rank&#41;
                *moveptr++ = move;
              else
              &#123;
                Mc mc;

                for &#40;mc = McPPN; mc <= McPPQ; mc++)
                &#123;
                  PutMc&#40;move, mc&#41;;
                  *moveptr++ = move;
                &#125;;
                PutMc&#40;move, McReg&#41;;
              &#125;;
            &#125;
            else
            &#123;
              if (&#40;torank == cr4rank&#41; &&
                  &#40;MapSqToRank&#40;frsq&#41; == cr2rank&#41; &&
                  IsManVacant&#40;manvec&#91;advsq&#93;))
                *moveptr++ = move;
            &#125;;
          &#125;;
        &#125;;
      &#125;;
      tosq = *tosqptr++;
    &#125;;
  &#125;;

  // Attempt en passant capture

  if &#40;IsSqNotNil&#40;epsq&#41;)
  &#123;
    Move epcmove = VoidMove;
    Ti goodti;

    PutFrMan&#40;epcmove, goodpawn&#41;;
    PutToSqToMan&#40;epcmove, epsq, ManVacant&#41;;
    PutMc&#40;epcmove, McEPC&#41;;

    for &#40;goodti = goodpeonti; goodti <= goodstopti; goodti++)
    &#123;
      if &#40;TestTi&#40;helperpawns, goodti&#41;)
      &#123;
        const Sq frsq = sqvec&#91;goodti&#93;;

        if &#40;SqSqInfo&#91;frsq&#93;&#91;epsq&#93; & CvColorToPawnAtkfMask&#91;good&#93;)
        &#123;
          PutFrSq&#40;epcmove, frsq&#41;;
          if &#40;PositionTestEpCaptureMove&#40;positionptr, epcmove&#41;)
            *moveptr++ = epcmove;
        &#125;;
      &#125;;
    &#125;;
  &#125;;

  movesegptr->count = &#40;ui&#41; &#40;moveptr - movesegptr->baseptr&#41;;
  return movesegptr->count;
&#125;
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Code snippet: Move generation (not in check)

Post by sje »

Code: Select all

static ui PositionGenerateNotInCheck&#40;Position * const positionptr, MoveSeg * const movesegptr&#41;
&#123;
  // This routine generates the moves for the given position; it's called only when not in check.

  const Sq * const sqvec = positionptr->tracker.sqvec;
  const Man * const manvec = positionptr->board.manvec;

  const Color good = positionptr->fss.good;
  const Color evil = positionptr->fss.evil;
  const Cabs cabs = positionptr->fss.cabs;
  const Sq epsq = positionptr->fss.epsq;

  const Sq kingsq = PositionGetGoodKingSq&#40;positionptr&#41;;
  const Dir advdir = CvColorToAdvDir&#91;good&#93;;
  const Rank cr2rank = CvColorRankToNormalRank&#91;good&#93;&#91;Rank2&#93;;
  const Rank cr7rank = CvColorRankToNormalRank&#91;good&#93;&#91;Rank7&#93;;

  const TiBV goodguys = positionptr->tracker.tbvs.occupied & CvColorToTargetSetMask&#91;good&#93;;
  const TiBV pinned = goodguys & positionptr->apd.pinned;
  const TiBV movers = goodguys & ~positionptr->apd.frozen;
  const Ti goodstopti = CvColorToStopTi&#91;good&#93;;

  MoveSegReset&#40;movesegptr&#41;;

  Move *moveptr = movesegptr->baseptr;

  Ti goodti;

  for &#40;goodti = CvColorToKingTi&#91;good&#93;; goodti <= goodstopti; goodti++)
  &#123;
    if &#40;TestTi&#40;movers, goodti&#41;)
    &#123;
      const bool ispinned = TestTi&#40;pinned, goodti&#41;;
      const Sq frsq = sqvec&#91;goodti&#93;;
      const Man frman = manvec&#91;frsq&#93;;
      const Dir dir0 = CvManToDir0&#91;frman&#93;, dir1 = CvManToDir1&#91;frman&#93;;
      Dir dir, resdir;
      Bidir resbidir;
      Move move = VoidMove;

      if &#40;ispinned&#41;
      &#123;
        resdir = MapInfoWordToDir&#40;SqSqInfo&#91;kingsq&#93;&#91;frsq&#93;);
        resbidir = CvDirToBidir&#91;resdir&#93;;
      &#125;
      else
      &#123;
        resdir = DirNil;
        resbidir = BidirNil;
      &#125;;

      PutFrSqFrMan&#40;move, frsq, frman&#41;;
      switch &#40;CvManToPiece&#91;frman&#93;)
      &#123;
        case PiecePawn&#58;
          &#123;
            const Rank frrank = MapSqToRank&#40;frsq&#41;;
            const Sq advsq = NextSq&#91;advdir&#93;&#91;frsq&#93;;
            const Sq * const basesqptr = PawnRunPtrs&#91;good&#93;&#91;frsq&#93;;
            const Sq *sqptr;
            Sq tosq;
            Man toman;
            Mc mc;

            if &#40;frrank != cr7rank&#41;
            &#123;
              // Starting from rank 2 through rank 6

              if (!ispinned || &#40;resbidir == BidirN&#41;)
              &#123;
                // Single advance

                toman = manvec&#91;tosq = advsq&#93;;
                if &#40;IsManVacant&#40;toman&#41;)
                &#123;
                  PutToSqToMan&#40;move, tosq, toman&#41;;
                  *moveptr++ = move;

                  if &#40;frrank == cr2rank&#41;
                  &#123;
                    // Double advance

                    toman = manvec&#91;tosq = NextSq&#91;advdir&#93;&#91;tosq&#93;&#93;;
                    if &#40;IsManVacant&#40;toman&#41;)
                    &#123;
                      PutToSqToMan&#40;move, tosq, toman&#41;;
                      *moveptr++ = move;
                    &#125;;
                  &#125;;
                &#125;;
              &#125;;

              // Simple capture

              sqptr = basesqptr;
              while &#40;IsSqNotNil&#40;tosq = *sqptr++))
              &#123;
                if (!ispinned || &#40;resbidir == MapInfoWordToBidir&#40;SqSqInfo&#91;frsq&#93;&#91;tosq&#93;)))
                &#123;
                  if &#40;CvManToColor&#91;toman = manvec&#91;tosq&#93;&#93; == evil&#41;
                  &#123;
                    PutToSqToMan&#40;move, tosq, toman&#41;;
                    *moveptr++ = move;
                  &#125;;
                &#125;;
              &#125;;

              // En passant capture

              if &#40;IsSqNotNil&#40;epsq&#41;)
              &#123;
                const ui16 infoword = SqSqInfo&#91;frsq&#93;&#91;epsq&#93;;

                if &#40;infoword & CvColorToPawnAtkfMask&#91;good&#93;)
                &#123;
                  if (!ispinned || &#40;resbidir == MapInfoWordToBidir&#40;infoword&#41;))
                  &#123;
                    PutToSqToMan&#40;move, epsq, ManVacant&#41;;
                    PutMc&#40;move, McEPC&#41;;
                    if &#40;PositionTestEpCaptureMove&#40;positionptr, move&#41;)
                      *moveptr++ = move;
                    PutMc&#40;move, McReg&#41;;
                  &#125;;
                &#125;;
              &#125;;
            &#125;
            else
            &#123;
              // Starting from rank 7

              if (!ispinned || &#40;resbidir == BidirN&#41;)
              &#123;
                // Non capture promotion

                toman = manvec&#91;tosq = advsq&#93;;
                if &#40;IsManVacant&#40;toman&#41;)
                &#123;
                  PutToSqToMan&#40;move, tosq, toman&#41;;
                  for &#40;mc = McPPN; mc <= McPPQ; mc++)
                  &#123;
                    PutMc&#40;move, mc&#41;;
                    *moveptr++ = move;
                  &#125;;
                  PutMc&#40;move, McReg&#41;;
                &#125;;
              &#125;;

              // Capture promotion

              sqptr = basesqptr;
              while &#40;IsSqNotNil&#40;tosq = *sqptr++))
              &#123;
                if (!ispinned || &#40;resbidir == MapInfoWordToBidir&#40;SqSqInfo&#91;frsq&#93;&#91;tosq&#93;)))
                &#123;
                  toman = manvec&#91;tosq&#93;;
                  if &#40;CvManToColor&#91;toman&#93; == evil&#41;
                  &#123;
                    PutToSqToMan&#40;move, tosq, toman&#41;;
                    for &#40;mc = McPPN; mc <= McPPQ; mc++)
                    &#123;
                      PutMc&#40;move, mc&#41;;
                      *moveptr++ = move;
                    &#125;;
                    PutMc&#40;move, McReg&#41;;
                  &#125;;
                &#125;;
              &#125;;
            &#125;;
          &#125;;
          break;

        case PieceKnight&#58;
          &#123;
            const Sq *sqptr = KnightRunPtrs&#91;frsq&#93;;
            Sq tosq;

            while &#40;IsSqNotNil&#40;tosq = *sqptr++))
            &#123;
              const Man toman = manvec&#91;tosq&#93;;

              if &#40;CvManToColor&#91;toman&#93; != good&#41;
              &#123;
                PutToSqToMan&#40;move, tosq, toman&#41;;
                *moveptr++ = move;
              &#125;;
            &#125;;
          &#125;;
          break;

        case PieceBishop&#58;
        case PieceRook&#58;
        case PieceQueen&#58;
          for &#40;dir = dir0; dir <= dir1; dir++)
          &#123;
            if (!ispinned || &#40;CvDirToBidir&#91;dir&#93; == resbidir&#41;)
            &#123;
              const Sq *sqptr = SweeperRunPtrs&#91;dir&#93;&#91;frsq&#93;;
              Sq tosq = *sqptr++;

              while &#40;IsSqNotNil&#40;tosq&#41;)
              &#123;
                const Man toman = manvec&#91;tosq&#93;;

                if &#40;CvManToColor&#91;toman&#93; == good&#41;
                  tosq = SqNil;
                else
                &#123;
                  PutToSqToMan&#40;move, tosq, toman&#41;;
                  *moveptr++ = move;
                  if &#40;IsManVacant&#40;toman&#41;)
                    tosq = *sqptr++;
                  else
                    tosq = SqNil;
                &#125;;
              &#125;;
            &#125;;
          &#125;;
          break;

        case PieceKing&#58;
          &#123;
            // Regular king moves

            const Sq *sqptr = KingRunPtrs&#91;frsq&#93;;
            Sq tosq;

            while &#40;IsSqNotNil&#40;tosq = *sqptr++))
            &#123;
              const Man toman = manvec&#91;tosq&#93;;

              if (&#40;CvManToColor&#91;toman&#93; != good&#41; &&
                  !PositionColorAttacksSq&#40;positionptr, evil, tosq&#41;)
              &#123;
                PutToSqToMan&#40;move, tosq, toman&#41;;
                *moveptr++ = move;
              &#125;;
            &#125;;

            // Castling moves

            if &#40;cabs & CvColorToCabs&#91;good&#93;)
            &#123;
              Castling castling;

              for &#40;castling = CvColorToCastling0&#91;good&#93;; castling <= CvColorToCastling1&#91;good&#93;; castling++)
                if &#40;PositionTestCastling&#40;positionptr, castling&#41;)
                   *moveptr++ = CastlingMoves&#91;castling&#93;;
            &#125;;
          &#125;;
          break;

        default&#58;
          break;
      &#125;;
    &#125;;
  &#125;;

  movesegptr->count = &#40;ui&#41; &#40;moveptr - movesegptr->baseptr&#41;;
  return movesegptr->count;
&#125;
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Code snippet: Other generation routines

Post by sje »

Code: Select all

static ui PositionGenerate&#40;Position * const positionptr, MoveSeg * const movesegptr&#41;
&#123;
  // This routine generates the moves for the given position.

  ui count;

  if &#40;positionptr->apd.incheck&#41;
    count = PositionGenerateEvasion&#40;positionptr, movesegptr&#41;;
  else
    count = PositionGenerateNotInCheck&#40;positionptr, movesegptr&#41;;
  return count;
&#125;

Code: Select all

static void PositionNotate&#40;Position * const positionptr, const MoveSeg * const movesegptr&#41;
&#123;
  // This routine fully notates the moves in the given move segment for the given position.

  PositionNotateChecks&#40;positionptr, movesegptr&#41;;
  PositionNotateCheckmates&#40;positionptr, movesegptr&#41;;
  PositionNotateDisambiguation&#40;positionptr, movesegptr&#41;;

  ui index;

  for &#40;index = 0; index < movesegptr->count; index++)
    SetMf&#40;movesegptr->baseptr&#91;index&#93;, MfNote&#41;;
&#125;

static void PositionGenerateCanonical&#40;Position * const positionptr, MoveSeg * const movesegptr&#41;
&#123;
  // This routine generates the moves canonically for the given position into the given move segment.

  PositionGenerate&#40;positionptr, movesegptr&#41;;
  PositionNotate&#40;positionptr, movesegptr&#41;;
  MoveSegSortSan&#40;movesegptr&#41;;
&#125;
User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 7:43 pm

Code snippet: The movepath counter

Post by sje »

Now this non-recursive routine has no depth limits; all storage is dynamically allocated.

Code: Select all

static NodeCount PositionEnumerateMovePaths&#40;Position * const positionptr, const ui depth, const ui ptqlen,
                                            const bool dobulk, const bool doply0, const bool dotran&#41;
&#123;
  // This routine enumerates the distinct movepaths of the given position for the given length.

  typedef enum
  &#123;
    EsInit,
    EsInitPly,
    EsGenerate,
    EsExecute,
    EsEndScan,
    EsTermPly,
    EsTerm,
    EsExit
  &#125; Es;

  Es state = EsInit;

  ui ply;
  NodeCount total;

  PiRecList *pireclistptr;
  PiRecNode *pirecnodeptr;
  PerftTable *perfttableptr;

  // Some initialization code appears here instead of in the switch to avoid bogus compilation diagnostics

  ply = 0;
  total = 0;

  pireclistptr = PiRecListNew&#40;);
  pirecnodeptr = PiRecNodeNew&#40;);
  PiRecListAppendNode&#40;pireclistptr, pirecnodeptr&#41;;
  perfttableptr = 0;

  while &#40;state != EsExit&#41;
  &#123;
    switch &#40;state&#41;
    &#123;
      case EsInit&#58;
        if &#40;dotran&#41;
          perfttableptr = PerftTableNew&#40;ptqlen&#41;;
        state = EsInitPly;
        break;

      case EsInitPly&#58;
        if &#40;ply == depth&#41;
        &#123;
          pirecnodeptr->pirec.sum = 1;
          state = EsTermPly;
        &#125;
        else
        &#123;
          if &#40;dobulk && &#40;ply == &#40;depth - 1&#41;) && &#40;ply > 0&#41;)
          &#123;
            pirecnodeptr->pirec.sum = PositionCountMoves&#40;positionptr&#41;;
            state = EsTermPly;
          &#125;
          else
          &#123;
            if &#40;dotran && PerftTableFetch&#40;perfttableptr, positionptr, ply, &pirecnodeptr->pirec.sum&#41;)
              state = EsTermPly;
            else
            &#123;
              pirecnodeptr->pirec.sum = 0;
              state = EsGenerate;
            &#125;;
          &#125;;
        &#125;;
        break;

      case EsGenerate&#58;
        if &#40;ply == 0&#41;
          PositionGenerateCanonical&#40;positionptr, pirecnodeptr->pirec.msptr&#41;;
        else
          PositionGenerate&#40;positionptr, pirecnodeptr->pirec.msptr&#41;;
        state = EsExecute;
        break;

      case EsExecute&#58;
        &#123;
          const Move move = MoveSegNextMove&#40;pirecnodeptr->pirec.msptr&#41;;

          if &#40;move == VoidMove&#41;
            state = EsEndScan;
          else
          &#123;
            pirecnodeptr->pirec.move = move;
            PositionExecute&#40;positionptr, move&#41;;
            ply++;

            if &#40;pirecnodeptr->next&#41;
              pirecnodeptr = pirecnodeptr->next;
            else
            &#123;
              pirecnodeptr = PiRecNodeNew&#40;);
              PiRecListAppendNode&#40;pireclistptr, pirecnodeptr&#41;;
            &#125;;
            state = EsInitPly;
          &#125;;
        &#125;;
        break;

      case EsEndScan&#58;
        if &#40;dotran&#41;
          PerftTableStash&#40;perfttableptr, positionptr, ply, pirecnodeptr->pirec.sum&#41;;
        state = EsTermPly;
        break;

      case EsTermPly&#58;
        if &#40;ply == 0&#41;
          state = EsTerm;
        else
        &#123;
          pirecnodeptr->prev->pirec.sum += pirecnodeptr->pirec.sum;
          PositionRetract&#40;positionptr&#41;;
          ply--;
          pirecnodeptr = pirecnodeptr->prev;

          if &#40;doply0 && &#40;ply == 0&#41;)
          &#123;
            SanRec sanrec;

            SanRecLoadFromMove&#40;&sanrec, pirecnodeptr->pirec.move&#41;;
#if UseStdio && DoPlyZeroOutput
            fprintf&#40;stdout, "%s %llu\n", sanrec.chvec, pirecnodeptr->next->pirec.sum&#41;;
#endif
          &#125;;

          state = EsExecute;
        &#125;;
        break;

      case EsTerm&#58;
        total = pirecnodeptr->pirec.sum;
        if &#40;dotran&#41;
          PerftTableDelete&#40;perfttableptr&#41;;
        state = EsExit;
        break;

      default&#58;
        break;
    &#125;;
  &#125;;

  // Some termination code appears here instead of in the switch to avoid bogus compilation diagnostics

  PiRecListDelete&#40;pireclistptr&#41;;

  return total;
&#125;