Bitboards using STL bitset

[Anonymous]

The bitset class template looks convenient for a lot of reasons, but I've only seen it mentioned once or twice in passing with regard to chess programming. Is there some horrible problem with the class I should be aware of?

I haven't run any tests on the bitwise operator speeds, but sizeof(bitset<64>) returns 8, so it's not exactly a memory hog.

I originally asked this over at the chess-engines group, but this place seems much more lively.

Thanks

[Dann Corbit]

I think it would be a good place to start writing a bitboard chess engine.
You could play with the abstract ideas more easily.

Since it is very doubtful that the STL will assume 64 bit integers, expect it to perform poorly in comarison with hand written code that assumes 64 bit integers.

Be that as it may, the speed difference in that respect will probably not prevent you from writing a good chess engine.

A chess engine that makes thorough use of the STL is Greko which comes with source code:
http://bearlodge.webservis.ru/chess/

I think it will give you some good food for thought. I rather enjoy the author's programming style.

[mathmoi]

The bitset class template looks convenient for a lot of reasons, but I've only seen it mentioned once or twice in passing with regard to chess programming. Is there some horrible problem with the class I should be aware of?

I haven't run any tests on the bitwise operator speeds, but sizeof(bitset<64>) returns 8, so it's not exactly a memory hog.

I originally asked this over at the chess-engines group, but this place seems much more lively.

Thanks

Hi,

The reason why bitset<64> is not used as a bitboard is simply that it is not as efficient as a ui64 (user defined type). This is the case because bitset<64> is built to be used in more general cases than a chess engine's bitboards.

And that is not hard to write your own bitboard class. This is mine (sorry, the comment are in french):

=== hpp file ===

Code: Select all

#ifndef INCLUDE_CBITBOARD_HPP_
#define INCLUDE_CBITBOARD_HPP_

#include "ui64.hpp"
#include "Constantes.hpp"
#include "OutilsDeDebugage.hpp"

#include <iostream>

namespace MatMoi
{

   ////////////////////////////////////////////////////////////////////////////
   /// <summary>Repr?sente un bitboard.</summary>
   /// <remarks>
   ///  Cette classe d?finit un Bitboard. Essentiellement la classe est un
   ///  ?wrapper? pour un entier de 64 bits, mais elle contient quelques
   ///  fonctions sp?ciales.
   /// </remarks>
   ////////////////////////////////////////////////////////////////////////////
   class CBitboard
   {
      friend std::ostream& operator<<(std::ostream& out, const CBitboard& bitboard);

      // L'entier de 64 bits
      ui64 m_ui64;

   public:

      /////////////////////////////////////////////////////////////////////////
      /// <summary>Constructeur ? partir d'un ui64</summary>
      /// <param name="valeur">
      ///  Entier de 64 bits, valeur de d?part de l'objet</param>
      /////////////////////////////////////////////////////////////////////////
      inline CBitboard(ui64 valeur = 0)
      {
         m_ui64 = valeur;
      };
      
      /////////////////////////////////////////////////////////////////////////
      /// <summary>Surcharge de l'op?rateur =</summary>
      /// <remarks>
      ///  Cette surcharge de l'op?rateur ?gale permet d'affecter des ui64 ? un
      ///  CBitboard. Cette surcharge ainsi que celle de l'op?rateur de cast en
      ///  ui64 permet d'utiliser un objet CBitboard comme s'il s'agissait d'un
      ///  ui64.
      /// </remarks>
      /// <param name="valeur">
      ///  Entier de 64 bits a affecter ? l'objet</param>
      /// <returns>
      ///  Une r?f?rence ? l'objet en cours. Permet les affectations en cascades
      /// </returns>
      /////////////////////////////////////////////////////////////////////////
      inline CBitboard& operator=(ui64 valeur)
      {
         m_ui64 = valeur;
         return *this;
      };

      /////////////////////////////////////////////////////////////////////////
      /// <summary>Surcharge de l'op?rateur de cast en ui64.</summary>
      /// <remarks>
      ///  Cette surcharge permet de transformer automatiquement l'objet en ui64.
      ///  De cette fa?on il est possible d'utiliser les op?rateur standards de
      ///  l'ui64 sur les objets de type CBitboard.
      /// </remarks>
      /////////////////////////////////////////////////////////////////////////
      inline operator ui64() const
      {
         return m_ui64;
      };

      /////////////////////////////////////////////////////////////////////////
      /// <summary>Retourne le bit le moin significatif ? 1.</summary>
      /// <remarks>
      ///  Cette fonction retourne le bit le moin significatif qui est ? 1.
      /// </remarks>
      /// <returns>La position du bit.</returns>
      /////////////////////////////////////////////////////////////////////////
      inline unsigned int GetLSB() const
      {
         return BitSearch(m_ui64);
      };

      /////////////////////////////////////////////////////////////////////////
      /// <summary>Retourne le bit le plus significatif ? 1.</summary>
      /// <remarks>
      ///  Cette fonction retourne le bit le plus significatif qui est ? 1.
      /// </remarks>
      /// <returns>La position du bit.</returns>
      /////////////////////////////////////////////////////////////////////////
      //unsigned int GetMSB();

      /////////////////////////////////////////////////////////////////////////
      /// <summary>Retire et retourne le bit le moin significatif ? 1.</summary>
      /// <remarks>
      ///  Cette fonction met ? z?ro le bit le moin significatif ? 1 et retourne
      ///  la position qu'il avait.
      /// </remarks>
      /// <returns>La position du bit.</returns>
      /////////////////////////////////////////////////////////////////////////
      inline unsigned int RemoveLSB()
      {
         return BitSearchAndReset(m_ui64);
      };

      /////////////////////////////////////////////////////////////////////////
      /// <summary>Retire et retourne le bit le plus significatif ? 1.</summary>
      /// <remarks>
      ///  Cette fonction met ? z?ro le bit le plus significatif ? 1 et retourne
      ///  la position qu'il avait.
      /// </remarks>
      /// <returns>La position du bit.</returns>
      /////////////////////////////////////////////////////////////////////////
      //unsigned int RemoveMSB();

      /////////////////////////////////////////////////////////////////////////
      /// <summary>Retourne le nombre de bit ? 1.</summary>
      /// <returns>Le nombre de bits ? 1.</returns>
      /////////////////////////////////////////////////////////////////////////
      inline int GetPopCount() const
      {
         return BitCount(m_ui64);
      };

      /////////////////////////////////////////////////////////////////////////
      /// <summary>
      ///  Met le bit dont la position est pass?e en param?tre ? 1.</summary>
      /// <param name="uiPosition">
      ///  Position du bit ? mettre ? 1.</param>
      /////////////////////////////////////////////////////////////////////////
      void SetBit(unsigned int uiPosition)
      {
         Assertion(uiPosition <= 63);

         m_ui64 = m_ui64 | gbitPositions[uiPosition];
      };

      /////////////////////////////////////////////////////////////////////////
      /// <summary>
      ///  Met le bit dont la position est pass?e en param?tre ? 0.</summary>
      /// <param name="uiPosition">
      ///  Position du bit ? mettre ? 0.</param>
      /////////////////////////////////////////////////////////////////////////
      void UnsetBit(unsigned int uiPosition)
      {
         Assertion(uiPosition <= 63);

         m_ui64 = m_ui64 & (~gbitPositions[uiPosition]);
      };

      /////////////////////////////////////////////////////////////////////////
      /// <summary>Retourne l'?tat d'un bit.</summary>
      /// <remarks>
      ///  Cette fonction retourne l'?tat du bit dont la position est pass? en
      ///  param?tre.
      /// </remarks>
      /// <param name="uiPosition">
      ///  Position du bit dont on veut connaitre l'?tat.</param>
      /// <returns>Vrai si le bit est ? 1. Faux sinon.</returns>
      /////////////////////////////////////////////////////////////////////////
      bool GetBit(unsigned int uiPosition) const
      {
         Assertion(uiPosition <= 63);

         return (m_ui64 & gbitPositions[uiPosition]) != 0;
      };

      /////////////////////////////////////////////////////////////////////////
      /// <summary>Change l'?tat d'un bit.</summary>
      /// <remarks>
      ///  Cette fonction change l'?tat du bit dont la position est pass? en
      ///  param?tre.
      /// </remarks>
      /// <param name="uiPosition">
      ///  Position du bit dont on veut changer l'?tat</param>
      /////////////////////////////////////////////////////////////////////////
      void SwitchBit(unsigned int uiPosition)
      {
         Assertion(uiPosition <= 63);

         m_ui64 = m_ui64 ^ gbitPositions[uiPosition];
      };
   };

   ////////////////////////////////////////////////////////////////////////////
   /// <summary>
   ///  Affiche un CBitboard sur le flux dans un format binaire.</summary>
   /// <remarks>
   ///  Cette fonction affiche l'?tat du bitboard sur le flux de sortie pass?e
   ///  en param?tre dans un format binaire. Par example :
   /// <c>
   ///    - - X - - - - -
   ///    X X - X - X - X
   ///    - X X X - X X X
   ///    X X X - X - X X
   ///    X X - - X - - X
   ///    - X - X X - - X
   ///    - X - X - - X -
   ///    X - - - X - - X
   /// </c>
   /// </remarks>
   /// <param name="out">
   ///  Flux de sortie sur lequel on doit afficher le Bitboard.</param>
   /// <param name="bitboard">
   ///  Le CBitboard ? afficher</param>
   /// <returns>
   ///  Une r?f?rence vers le flux de sortie pass? en param?tre.</returns>
   ////////////////////////////////////////////////////////////////////////////
   std::ostream& operator<<(std::ostream& out, const CBitboard& bitboard);

} // namespace MatMoi

#endif // INCLUDE_CBITBOARD_HPP_


=== cpp file ===

Code: Select all

#include "CBitboard.hpp"

#include <iostream>

namespace MatMoi
{

   std::ostream& operator<<(std::ostream& out, const CBitboard& bitboard)
   {
      unsigned int i;
      unsigned int j;

      for (i = 0; i < 64; i+=8)
      {
         out <<'\t';

         for (j = 0; j < 8; j++)
         {
            if (bitboard.GetBit(i+j))
            {
               out <<'X' <<' ';
            }
            else
            {
               out <<'-' <<' ';
            }
         }
         out <<std::endl;
      }

      return out;
   }

} // namespace MatMoi

=== ui64.hpp ===

Code: Select all

#ifndef INCLUDE_UI64_HPP_
#define INCLUDE_UI64_HPP_

#include "Configuration.hpp"

namespace MatMoi
{

   // On d?finit le type ui64
   #if defined(_MSC_VER)
      typedef unsigned __int64 ui64;
   #   define ULL(x) x##ui64
   #else
      typedef unsigned long long ui64;
   #   define ULL(x) x##ll
   #endif

   ////////////////////////////////////////////////////////////////////////////
   // Les fonctions suivantes (BitCount, BitSearchAndReset et BitSearch) sont
   // copi? d'un message de Gerd Isenberg sur le Computer Chess Club.
   // http://chessprogramming.org/cccsearch/ccc.php?art_id=236134
   ////////////////////////////////////////////////////////////////////////////

   #define LOWBOARD(bb) (*((unsigned int*)&(bb)))
   #define HIGHBOARD(bb) (*(((unsigned int*)&(bb))+1))

   inline int BitCount (ui64 bb)
   #if defined(_M_IX86) && UTILISER_ASSEMBLEUR == ON
   {
      __asm
      {
         mov ecx, dword ptr bb
         xor eax, eax
         test ecx, ecx
         jz l1
         l0: lea edx, [ecx-1]
         inc eax
         and ecx, edx
         jnz l0
         l1: mov ecx, dword ptr bb+4
         test ecx, ecx
         jz l3
         l2: lea edx, [ecx-1]
         inc eax
         and ecx, edx
         jnz l2
         l3:
      }
   }
   #else
   {
      static const unsigned int m1 = 0x55555555;
      static const unsigned int m2 = 0x33333333;
      static const unsigned int m3 = 0x0f0f0f0f;
      unsigned int l = LOWBOARD(bb);
      unsigned int h = HIGHBOARD(bb);
      l = l - ((l>>1) & m1);
      h = h - ((h>>1) & m1);
      l = (l & m2) + ((l>>2) & m2);
      h = (h & m2) + ((h>>2) & m2);
      l = (l & m3) + ((l>>4) & m3);
      h = (h & m3) + ((h>>4) & m3);
      l = (l & 0x0ffff) + (l>>16);
      h = (h & 0x0ffff) + (h>>16);
      return ((l & 0x0ff) + (l>>8) + (h & 0x0ff) + (h>>8));
   }
   #endif

   inline unsigned int BitSearchAndReset(ui64 &bb)
   {
   #if defined(_M_IX86) && UTILISER_ASSEMBLEUR == ON
         __asm
         {
            mov edx, [bb]
            bsf eax, [edx+4]
            xor eax, 32
            bsf eax, [edx]
            btr [edx],eax
         }
   #  else
         ui64 lsbb = bb & (-(__int64)bb);
         bb ^= lsbb;
         unsigned int lsb = LOWBOARD(lsbb) | HIGHBOARD(lsbb);
         return ((((((((((HIGHBOARD(lsbb)!=0) <<1)
         +((lsb & 0xffff0000)!=0))<<1)
         +((lsb & 0xff00ff00)!=0))<<1)
         +((lsb & 0xf0f0f0f0)!=0))<<1)
         +((lsb & 0xcccccccc)!=0))<<1)
         +((lsb & 0xaaaaaaaa)!=0);
   #  endif
   }


   inline unsigned int BitSearch(ui64 bb)
   {
   #if defined(_M_IX86) && UTILISER_ASSEMBLEUR == ON
      __asm
      {
         bsf eax,[bb+4]
         xor eax, 32
         bsf eax,[bb]
      }
   #  else
      ui64 lsbb = bb & (-(__int64)bb);
      unsigned int lsb = LOWBOARD(lsbb) | HIGHBOARD(lsbb);
      return ((((((((((HIGHBOARD(lsbb)!=0) <<1)
      +((lsb & 0xffff0000)!=0))<<1)
      +((lsb & 0xff00ff00)!=0))<<1)
      +((lsb & 0xf0f0f0f0)!=0))<<1)
      +((lsb & 0xcccccccc)!=0))<<1)
      +((lsb & 0xaaaaaaaa)!=0);
   #  endif
   }

} // namespace MatMoi

#endif // #ifndef INCLUDE_UI64_HPP_

[Gerd Isenberg]

Hi Mathieu,

as the author (i think) of some of your mentioned routines i strongly suggest to throw that inline assembly stuff away. Specially the awfull bsf,bsf,btr sequence.

For amd64 (mul/imul is 3 cycles direct path) pure C-routines are faster!
(Inlined) Inline assembly tends to confuse the compiler.


Try the popcount from amd's optimization manual with a final mul.
For 32-bit mode try Matt Taylor's folded de Bruijn multiplication for bitscanning.

Also note that the pointer casting used by the HIGHBOARD macro is not portable due to the little- versus big-endian thing - better use logical shift right 32.

Cheers,
Gerd

Code: Select all

inline 
int BitCount (BitBoard bb)
{
   unsigned int w = bb >> 32, v = bb;
   v = v - ((v >> 1) & 0x55555555);
   w = w - ((w >> 1) & 0x55555555);
   v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
   w = (w & 0x33333333) + ((w >> 2) & 0x33333333);
   v = (v + (v >> 4)) & 0x0F0F0F0F;
   w = (w + (w >> 4)) & 0x0F0F0F0F;
   v = ((v+w) * 0x01010101) >> 24;
   return v;
}

extern const unsigned int lsz64_tbl[64];

#define CACHE_LINE  64
#define CACHE_ALIGN __declspec(align(CACHE_LINE))

const unsigned int CACHE_ALIGN lsz64_tbl[64] =
{
 63,30, 3,32,59,14,11,33,
 60,24,50, 9,55,19,21,34,
 61,29, 2,53,51,23,41,18,
 56,28, 1,43,46,27, 0,35,
 62,31,58, 4, 5,49,54, 6,
 15,52,12,40, 7,42,45,16,
 25,57,48,13,10,39, 8,44,
 20,47,38,22,17,37,36,26,
};


// precondition: bb not null
inline 
unsigned int  BitSearch(BitBoard bb)
{
   BitBoard b = bb ^ (bb - 1);
   unsigned int fold = ((unsigned int) b) ^ ((unsigned int)(b>>32));
   return  lsz64_tbl[(fold * 0x78291ACF) >> (32-6)];
}

// precondition: bb not null
inline 
unsigned int  BitSearchAndReset(BitBoard &bb)
{
   BitBoard b = bb ^ (bb - 1);
           bb = bb & (bb - 1);
   unsigned int fold = ((unsigned int) b) ^ ((unsigned int)(b>>32));
   return  lsz64_tbl[(fold * 0x78291ACF) >> (32-6)];
}



[Anonymous]

Thanks for the information, and especially the link to Greko. Nice to see that chess programs can be written using methods that even I can understand. It's already helped solve a couple of weird compiler compatibility issues I was facing.

I'm not used to efficiency being the deciding factor in the programs I work on, so I have a lot to learn before my little chess program will be competitive.

Is there a good place to find out how efficient different types are, without running my own tests? It seems like one of those things other people just 'know'.

[Tord Romstad]

Hi Beth,

Welcome on board!

I'm not used to efficiency being the deciding factor in the programs I work on, so I have a lot to learn before my little chess program will be competitive.

Low-level efficiency is nowhere near as important in computer chess as most beginners seem to believe. The two most important factors which determine a program's strength are the number of bugs and the efficiency of the search algorithm. The frequently quoted advice that "premature optimisation is the root of all evil" is no less true for computer programs than for other types of software. Concentrate on writing solid, bug-free code and good algorithms, and don't worry about speed until later.

Is there a good place to find out how efficient different types are, without running my own tests? It seems like one of those things other people just 'know'.

Dann, Gerd and a handful of other experts know these things. The rest of us know no more than you.

Tord

[Dann Corbit]

What Tord says is right. The bit twiddle stuff is not important.

Let's suppose that you can increase the speed of your program by 4 times by a monumental increase in speed through very clever and cryptic bit manipulations...

Let's suppose further that you have a branching factor of 4. That means that you gained one whole ply.

If instead you improve your branching factor to 3 then in deep searches you will have gained several plies. And if you can trim the braching factor to 2 like Shredder and Fruit and still keep the best nodes to look at, then you will have a world beater.

On the other hand, the bit twiddle stuff is also FUN. So after you improve your branching factor and have excellent, well debugged algorithms implemented through and through, then have some fun with bit twiddling.

The first rule of optimiation is:
1. Don't do it.
The second rule, for experts only is:
2. Don't do it yet.

And when you do optimization, first and foremost:
PROFILE to find out where your program needs help.
Then, only after you know the slow spots, improve the algorithms.
Then, if nothing else can help, resort to bit twiddling.

Bit twiddling is a very bad way to start when you are beginning a chess program. Seriously, make a clean and simple design and try to keep it as abstract as possible. If you succed in that, you can always fiddle with the innards later.

[Anonymous]

On the other hand, the bit twiddle stuff is also FUN.

Exactly, and no-one likes to admit to themselves that their code will have bugs. Naturally my brilliant bit-twiddling will work the first time! (It's a nice dream, anyway.)

Right now I'm proceeding with a bitboard representation because it's interesting, and because it feels like an intuitive approach to evaluation and move generation. Setting up the tables has caused some headaches, but nothing too disheartening so far.

With my questions here, I'm mainly trying to make sure my early decisions don't preclude future optimization -- and some of them, like how to find different types' efficiency, are plain old curiosity.

I thank you all for the advice and information. It's good to know I'm not painting myself into a corner just yet.

[Richard Allbert]

A slightly late reply, but I've spent a some time over the past 24hrs playing with the bitset class, after being motivated to have a look at bitboards by Pradu. But with the STL bitset, one problem seems to be when you declare bitset<64> e.g.

Code: Select all


#include <iostream>
#include <bitset>


using namespace std;

int main()
{
    bitset<64> my64 = 4096;

    cout<<"\n"<<my64;
   
    return 0;
}


gives the result...

Code: Select all

0000000000000000000000000000000000000000000000000001000000000000


Which appears to be 64 bits... but it isn't, because if I try the declaration

Code: Select all

bitset<64> my64 = (1<<46);


I get a compiler warning saying I am shifting too far passed the size of 'my64'. This happened for anything more than (1<<31).. so I assume the real size here is 32 bits. This was confirmed when running the program using the (1<<46)... 64 '0's were printed off.

Code: Select all

0000000000000000000000000000000000000000000000000000000000000000


Did you, or anyone reading this, find a way to declare a real 64 bit bitset?
Thanks for any replies,

Richard

[Tony van Roon-Werten]

It's the 1 that is 32 bit

Code: Select all

bitset<64> my64 = ((unsigned __int64) 1<<46);


should do the trick.

Tony

[Richard Allbert]

It's the 1 that is 32 bit

Code: Select all

bitset<64> my64 = ((unsigned __int64) 1<<46);


should do the trick.

Tony

!!!! Lol.

Oh dear. Thank you.

Richard

[Richard Allbert]

I should have tried that before posting..

the same thing happens again..

Code: Select all


int main()
{
    bitset<64> my64 = ( (unsigned __int64)1<<31);

    cout<<"\n"<<my64;

    return 0;
}


gives

Code: Select all

0000000000000000000000000000000010000000000000000000000000000000


but

Code: Select all


int main()
{
    bitset<64> my64 = ( (unsigned __int64)1<<32);

    cout<<"\n"<<my64;

    return 0;
}


gives

Code: Select all

0000000000000000000000000000000000000000000000000000000000000000


[Tom Cant]

Code: Select all

bitset<64> my64 = ( (unsigned __int64)1<<32);

Change that to this:

Code: Select all

bitset<64> my64 = (1ull<<32);

I havn't tested, but I think that should do it.

[Gerd Isenberg]

It's the 1 that is 32 bit

Code: Select all

bitset<64> my64 = ((unsigned __int64) 1<<46);


should do the trick.

Tony

I fear not, there is only a bitset( unsigned long val );
constructor!

Code: Select all

   bitset<64> my64; // empty set
   my64.set(46);
   cout<<my64<<"\n";
   cout<<"my64 has "<<my64.count()<<" bit set\n";


I also miss some bitset iterators...

Gerd

[Richard Allbert]

Ok, that worked!

Thank you.

Code: Select all

 bitset<64> my64; // empty set
   my64.set(46);
   cout<<my64<<"\n";
   cout<<"my64 has "<<my64.count()<<" bit set, which is ";
   cout<<" bit number "<<my64._Find_first()<<"\n";

   bitset<64> my32; // empty set
   my32.set(8);
   cout<<my32<<"\n";
   cout<<"my32 has "<<my32.count()<<" bit set, which is ";
   cout<<" bit number "<<my32._Find_first()<<"\n";


gives

Code: Select all

0000000000000000010000000000000000000000000000000000000000000000
my64 has 1 bit set, which is  bit number 46
0000000000000000000000000000000000000000000000000000000100000000
my32 has 1 bit set, which is  bit number 8


Thank you all for the replies.

Richard