Bitboard database code samples

[sje]

Bitboard database code samples

For those with an interest in bitboard database coding, I'm presenting some code snippets from Symbolic. The source is all original other than the theft of some identifiers from the Slate and Atkin report of Chess 4.x written some forty years ago.

Symbolic's code is different from some other programs in that it maintains the full attack-to-square bitboard vector at each node, and that it makes use of pre-computed tables as much as possible for the various square scanning loops.

First, from the Bitboard class definition in the bitboard database header file:

Code: Select all

  void AttackAdd(const Sq sq, const Color color, const Man man);
  void AttackDel(const Sq sq, const Color color);
  void AttackPro(const Sq sq);
  void AttackCut(const Sq sq);

  Bitboard merge;             // All men merged
  Bitboard sweep;             // Sweeper men merged (bishops, rooks, queens)
  Bitboard locbm[ManRCLen];   // Locus by man
  Bitboard locbc[ColorRCLen]; // Locus by color
  Bitboard atkbc[ColorRCLen]; // Attacked by color
  Bitboard atkfs[SqLen];      // Attacks from a square
  Bitboard atkts[SqLen];      // Attacks to a square

The Reset() routine:

Code: Select all

void BBDB::Reset(void)
{
  merge.Reset();
  sweep.Reset();

  ForEachManRC(man)
    locbm[man].Reset();

  ForEachColorRC(color)
  {
    locbc[color].Reset();
    atkbc[color].Reset();
  };

  ForEachSq(sq)
  {
    atkfs[sq].Reset();
    atkts[sq].Reset();
  };
}

The AttackAdd() routine:

Code: Select all

void BBDB::AttackAdd(const Sq sq, const Color color, const Man man)
{
  BitboardPtr const atkfsptr = &atkfs[sq];
  BitboardPtr const atkbcptr = &atkbc[color];

  switch (CvManToPiece[man])
  {
    case PiecePawn:
      {
        const Sq *scanptr = PawnRunPtrs[color][sq];
        Sq afssq;

        while (IsSqNotNil(afssq = *scanptr++))
        {
          atkts[afssq].SetSq(sq);
          atkfsptr->SetSq(afssq);
          atkbcptr->SetSq(afssq);
        };
      };
      break;

    case PieceKnight:
      {
        const Sq *scanptr = KnightRunPtrs[sq];
        Sq afssq;

        while (IsSqNotNil(afssq = *scanptr++))
        {
          atkts[afssq].SetSq(sq);
          atkfsptr->SetSq(afssq);
          atkbcptr->SetSq(afssq);
        };
      };
      break;

    case PieceBishop:
    case PieceRook:
    case PieceQueen:
      {
        const Dir dir1 = CvManToDir1[man];
        
        for &#40;Dir dir = CvManToDir0&#91;man&#93;; dir <= dir1; IncrDir&#40;dir&#41;)
          if &#40;Bitboard&#58;&#58;ShadowBBVec&#91;dir&#93;.IsSqSet&#40;sq&#41;)
          &#123;
            const Bitboard stopbb = merge | Bitboard&#58;&#58;EdgeBBVec&#91;dir&#93;;
            const si delta = CvDirToSqDelta&#91;dir&#93;;
            Sq afssq = sq;

            do
            &#123;
              ApplySqDelta&#40;afssq, delta&#41;;
              atkts&#91;afssq&#93;.SetSq&#40;sq&#41;;
              atkfsptr->SetSq&#40;afssq&#41;;
              atkbcptr->SetSq&#40;afssq&#41;;
            &#125; while &#40;stopbb.IsSqReset&#40;afssq&#41;);
          &#125;;
      &#125;;
      break;

    case PieceKing&#58;
      &#123;
        const Sq *scanptr = KingRunPtrs&#91;sq&#93;;
        Sq afssq;

        while &#40;IsSqNotNil&#40;afssq = *scanptr++))
        &#123;
          atkts&#91;afssq&#93;.SetSq&#40;sq&#41;;
          atkfsptr->SetSq&#40;afssq&#41;;
          atkbcptr->SetSq&#40;afssq&#41;;
        &#125;;
      &#125;;
      break;

    default&#58;
      SwitchFault&#40;"BBDB&#58;&#58;AttackAdd");
      break;
  &#125;;
&#125;

The AttackDel() routine:

Code: Select all

void BBDB::AttackDel(const Sq sq, const Color color)
{
  const Bitboard locbb = locbc[color];
  BitboardPtr const atkbcptr = &atkbc[color];
  Sq atssq;

  while (IsSqNotNil(atssq = atkfs[sq].NextSq()))
  {
    atkts[atssq].ResetSq(sq);
    if ((atkts[atssq] & locbb).IsReset())
      atkbcptr->ResetSq(atssq);
  };
}

The AttackPro() routine:

Code: Select all

void BBDB::AttackPro(const Sq sq)
{
  const Bitboard atrbb = atkts[sq] & sweep;

  ForEachColorRC(atsco)
  {
    BitboardPtr const atkbcptr = &atkbc[atsco];
    Bitboard atsbb = atrbb & locbc[atsco];
    Sq atssq;

    while (IsSqNotNil(atssq = atsbb.NextSq()))
    {
      const Dir dir = SqSqDir[atssq][sq];

      if (Bitboard::ShadowBBVec[dir].IsSqSet(sq))
      {
        BitboardPtr const atkfsptr = &atkfs[atssq];
        const Bitboard stopbb = merge | Bitboard::EdgeBBVec[dir];
        const si delta = CvDirToSqDelta[dir];
        Sq raysq = sq;

        do
        {
          ApplySqDelta(raysq, delta);
          atkts[raysq].SetSq(atssq);
          atkfsptr->SetSq(raysq);
          atkbcptr->SetSq(raysq);
        }
        while (stopbb.IsSqReset(raysq));
      };
    };
  };
}

The AttackCut() routine:

Code: Select all

void BBDB::AttackPro(const Sq sq)
{
  const Bitboard atrbb = atkts[sq] & sweep;

  ForEachColorRC(atsco)
  {
    BitboardPtr const atkbcptr = &atkbc[atsco];
    Bitboard atsbb = atrbb & locbc[atsco];
    Sq atssq;

    while (IsSqNotNil(atssq = atsbb.NextSq()))
    {
      const Dir dir = SqSqDir[atssq][sq];

      if (Bitboard::ShadowBBVec[dir].IsSqSet(sq))
      {
        BitboardPtr const atkfsptr = &atkfs[atssq];
        const Bitboard stopbb = merge | Bitboard::EdgeBBVec[dir];
        const si delta = CvDirToSqDelta[dir];
        Sq raysq = sq;

        do
        {
          ApplySqDelta(raysq, delta);
          atkts[raysq].SetSq(atssq);
          atkfsptr->SetSq(raysq);
          atkbcptr->SetSq(raysq);
        }
        while (stopbb.IsSqReset(raysq));
      };
    };
  };
}

[sje]

Sorry, wrong cut-n-paste for AttackCut(). The Real thing:

Code: Select all

void BBDB::AttackCut(const Sq sq)
{
  const Bitboard atrbb = atkts[sq] & sweep;

  ForEachColorRC(atsco)
  {
    const Bitboard locbb = locbc[atsco];
    BitboardPtr const atkbcptr = &atkbc[atsco];
    Bitboard atsbb = atrbb & locbb;
    Sq atssq;

    while (IsSqNotNil(atssq = atsbb.NextSq()))
    {
      const Dir dir = SqSqDir[atssq][sq];

      if (Bitboard::ShadowBBVec[dir].IsSqSet(sq))
      {
        BitboardPtr const atkfsptr = &atkfs[atssq];
        const Bitboard stopbb = merge | Bitboard::EdgeBBVec[dir];
        const si delta = CvDirToSqDelta[dir];
        Sq raysq = sq;

        do
        {
          ApplySqDelta(raysq, delta);
          atkts[raysq].ResetSq(atssq);
          atkfsptr->ResetSq(raysq);
          if ((atkts[raysq] & locbb).IsReset())
            atkbcptr->ResetSq(raysq);
        }
        while (stopbb.IsSqReset(raysq));
      };
    };
  };

[sje]

Some routines to move men in the bitboard database

These routines are all inline:

Code: Select all

  void LocusToggle(const Sq sq, const Color color, const Man man)
  {
    const Bitboard bb(SingleBitBB(sq));

    merge ^= bb;
    locbc[color] ^= bb;
    locbm[man] ^= bb;
    if (IsManSweeper(man))
      sweep ^= bb;
  }

  void LocusChange(const Sq frsq, const Sq tosq, const Color color, const Man man)
  {
    const Bitboard bb(SingleBitBB(frsq) | SingleBitBB(tosq));

    merge ^= bb;
    locbc[color] ^= bb;
    locbm[man] ^= bb;
    if (IsManSweeper(man))
      sweep ^= bb;
  }

  void AddMan(const Sq sq, const Color color, const Man man)
  {
    LocusToggle(sq, color, man);

    AttackCut(sq);
    AttackAdd(sq, color, man);
  }

  void DelMan(const Sq sq, const Color color, const Man man)
  {
    LocusToggle(sq, color, man);

    AttackDel(sq, color);
    AttackPro(sq);
  }

  void MoveMan(const Sq frsq, const Sq tosq, const Color color, const Man man)
  {
    LocusChange(frsq, tosq, color, man);

    AttackDel(frsq, color);
    AttackPro(frsq);
    AttackCut(tosq);
    AttackAdd(tosq, color, man);
  }

  void Capture(const Sq frsq, const Sq tosq,
               const Color frcolor, const Color tocolor,
               const Man frman, const Man toman)
  {
    LocusToggle(tosq, tocolor, toman);
    LocusChange(frsq, tosq, frcolor, frman);

    AttackDel(tosq, tocolor);
    AttackDel(frsq, frcolor);
    AttackPro(frsq);
    AttackAdd(tosq, frcolor, frman);
  }

  void RevCapt(const Sq frsq, const Sq tosq,
               const Color frcolor, const Color tocolor,
               const Man frman, const Man toman)
  {
    LocusChange(tosq, frsq, frcolor, frman);
    LocusToggle(tosq, tocolor, toman);

    AttackDel(tosq, frcolor);
    AttackCut(frsq);
    AttackAdd(frsq, frcolor, frman);
    AttackAdd(tosq, tocolor, toman);
  }

[sje]

Oops, left off a closing brace. Please append the following:

Code: Select all

}

[sje]

The database, the board, and the tracker

The routines presented above are all part of the BBDB (Bitboard Database) class. They are wholly separate from the Board (chessboard) class and the Tracker (inverse chessboard with history) classes. All three classes are siblings and live inside the Position class.

The idea was to be able to develop and test the classes separately and not to have one be dependent on any other. A couple of opportunities for minor optimizations were lost, but the result is clearer code; when a move is made or unmade, there are no restrictions on the update order of the three class instances.

----

Not shown is the Bitboard class. It is mostly what you'd expect except that it uses absolutely no assembly language. There is a self-setting compile time switch which selects either plain C++ code or GNU intrinsic functions; the program works both ways.

[sje]

In the attack routines above, there are various references to ShadowSqBBVec. This is an array of constant bitboards, one for each direction. Each bitboard contains the squares which are shadows of a sweep attack along a the direction to the square. A shadow square is the first square (if any) past the given square along the direction. The basic idea is to detect the case where a square is on the edge of the board AND does or does not have a retreat square along the direction.

Knowing about shadow squares is helpful in the above code for simplifying inner scanning loops or eliminating their execution entirely. The knowledge is also useful for generating check evasion moves.

----

In the AttackAdd() routine, there are references to the arrays PawnRunPtrs, KnightRunPtrs, and KingRunPtrs. These arrays contain pointers to the contents of pre-calculated lists of squares which give the target squares sequences, each ending with a SqNil value. This saves time by taking care of all the target square generation and edge detection work during program initialization.