piece lists advantage with bit-boards?

[MahmoudUthman]

does a bit-board based position representation with piece lists offer any advantage over a bit-board? & is it dependent on the architecture & the presence of bit-scan instructions?

[Michael Sherwin]

Any scheme that allows more data to be stored and accessed cleanly and efficiently has potential to have substantial advantages if a use case exist. Having indexed pieces allows for a specific piece to piece structure mapping that a piece type bitboard would seem to lack. Maybe one might want to know how many times a piece has been moved during the search. Maybe that information could be useful for LMR. Maybe one wants to do an incremental move generation scheme. The index piece structure can contain a stack of ts bitboards with the top entry set to valid or invalid. Then that bitboard is only generated if it is invalid and pushed onto the stack. It all depends if you have a use case.

[Sven]

does a bit-board based position representation with piece lists offer any advantage over a bit-board? & is it dependent on the architecture & the presence of bit-scan instructions?

Not sure what exactly you mean. Bitboards are kind of piece lists already. Additional piece lists would cost a lot of additional memory and updating, therefore nobody would do that. And yes, looping through bitboards requires bitscan operations which are a lot faster when provided as HW instructions instead of SW functions.

[MahmoudUthman]

Any scheme that allows more data to be stored and accessed cleanly and efficiently has potential to have substantial advantages if a use case exist. Having indexed pieces allows for a specific piece to piece structure mapping that a piece type bitboard would seem to lack. Maybe one might want to know how many times a piece has been moved during the search. Maybe that information could be useful for LMR. Maybe one wants to do an incremental move generation scheme. The index piece structure can contain a stack of ts bitboards with the top entry set to valid or invalid. Then that bitboard is only generated if it is invalid and pushed onto the stack. It all depends if you have a use case.

I understand your point about the advantage when a use case exist, but I don't understand how Piece-lists help with the examples you provided, could you elaborate a little on this?

does a bit-board based position representation with piece lists offer any advantage over a bit-board? & is it dependent on the architecture & the presence of bit-scan instructions?

Not sure what exactly you mean. Bitboards are kind of piece lists already. Additional piece lists would cost a lot of additional memory and updating, therefore nobody would do that. And yes, looping through bitboards requires bitscan operations which are a lot faster when provided as HW instructions instead of SW functions.

I meant something like this

Code: Select all

int pieceCount[PIECE_NB];
Square pieceList[PIECE_NB][16];

stockfish uses them so I thought maybe they are there to offer a speed advantage over software bitscan & popcnt on platforms that doesn't support HW-instructions especially 32 bit ones, But while browsing the wiki I found out that asmFish removed them, so my assumption seems wrong.

[Michael Sherwin]

does a bit-board based position representation with piece lists offer any advantage over a bit-board? & is it dependent on the architecture & the presence of bit-scan instructions?

Not sure what exactly you mean. Bitboards are kind of piece lists already. Additional piece lists would cost a lot of additional memory and updating, therefore nobody would do that. And yes, looping through bitboards requires bitscan operations which are a lot faster when provided as HW instructions instead of SW functions.

Nobody Sven? I guess I'm nobody then.

How It is done in RomiChess.

Code: Select all

typedef     struct
{
            s32         typ;
            s32         fig;
            s32         val;
            s32         sq;
            s32         *tbl;
            u32         *key;
            u64         *sig;
} pieces;

s32 MoveGen()
{
  s32 id;
  s32 fs;
  s32 typ;
  u64 indexs;
  u64 aPieces;
  u64 empty;
  u64 notMe;

  if(wtm) {
    indexs = wIndexs;
    notMe = ~wPieces;
  } else {
    indexs = bIndexs;
    notMe = ~bPieces;
  }
  aPieces = wPieces | bPieces;
  empty = ~aPieces;
  h->attacked = 0;
  while(indexs)
  {
    id = FirstBit(indexs);
    indexs &= clrBit[id];
    fs = piece[id].sq;
    typ = piece[id].typ;
    switch(typ)
    {
      case WPRANK2:
        h->moves[id] = (wPawnMoves[fs] & below[FirstBit(wPawnMoves[fs] & aPieces)])
                     | (wPawnCapts[fs] & bPieces);
        h->attacked |= wPawnCapts[fs];
        continue;
      case WPRANK3:
      case WPRANK4:
      case WPRANK6:
      case WPRANK7:
        h->moves[id] = (wPawnMoves[fs] & empty)
                     | (wPawnCapts[fs] & bPieces);
        h->attacked |= wPawnCapts[fs];
        continue;
      case WPRANK5:
        h->moves[id] = (wPawnMoves[fs] & empty)
                     | (wPawnCapts[fs] & (bPieces | setBit[h->epsq]));
        h->attacked |= wPawnCapts[fs];
        continue;
      case WKNIGHT:
        h->moves[id] = knight[fs] & notMe;
        h->attacked |= knight[fs];
        continue;
        
       ... 
       
       void MakeMove(moves *m)
{
  s32 fsid;
  s32 tsid;
  s32 epsq;
 
  h->hashKey = hashKey;
  h->hashSig = hashSig;
  h->pawnKey = pawnKey;
  h->m = m->m;
  h->flag = 0;
  h->cap = EMPTY;
  
  switch(h->typ)
  { 
    case WPRANK2:
      fsid = board[h->fs];
      tsid = board[h->ts];
      if(h->ts < A4)
      {
        piece[fsid].typ = WPRANK3;
      }
      else
      {
        piece[fsid].typ = WPRANK4;
        (h+1)->epsq = h->ts - 8;
        hashKey ^= epsqKey[h->ts - 8];
        hashSig ^= epsqSig[h->ts - 8];
      }
      piece[fsid].sq = h->ts;
      wPawns &= clrBit[h->fs];
      wPawns |= setBit[h->ts];
      wPieces &= clrBit[h->fs];
      wPieces |= setBit[h->ts];
      hashKey ^= wPawnKey[h->fs];
      hashKey ^= wPawnKey[h->ts];
      hashSig ^= wPawnSig[h->fs];
      hashSig ^= wPawnSig[h->ts];
      pawnKey ^= wPawnKey[h->fs];
      pawnKey ^= wPawnKey[h->ts];
      (h+1)->fifty = 0;
      wPos -= wPawnTbl[h->fs];
      wPos += wPawnTbl[h->ts];
      break;
      
      ...
        

Seems the added memory overhead is quite small and there are advantages. But to a bitboard purest it might seem like heresy to have an indexed array of piece structures. I stand by what I said. It makes sense if there is a use case for it. And it really is not slow to use this indexed structure array. Afterall RomiChess searches 6,958 kN/sec using a single thread in the original position on an i7-3930k OC'd to 4.4 Ghz! But hey don't anyone listen to me. I'm just a nobody.

[Michael Sherwin]

Maybe my idea of an indexed piece is not the same. Maybe just have a look at my code to see what I mean by a piece list. My method just simply allows each piece to keep track of its own information. I also have a board[64] and the entries in that array are the piece indexes. So if I misunderstood anything, my apologies.

[smcracraft]

I spent quite a bit of time converting to a full bitboard program. Talish is full bitboard for both move generation and position evaluation. It's much easier to work with. Bob and I worked together at the time Crafty and Talish came into being. However, nowadays I am in AWE of the Open Source Community's Leela and, also, Google's DeepMind Chess.

Much more interesting.

--Stuart--

[Michael Sherwin]

I spent quite a bit of time converting to a full bitboard program. Talish is full bitboard for both move generation and position evaluation. It's much easier to work with. Bob and I worked together at the time Crafty and Talish came into being. However, nowadays I am in AWE of the Open Source Community's Leela and, also, Google's DeepMind Chess.

Much more interesting.

--Stuart--

When the 80386 50Mhz was the top of the line machine and CM5000 had just come out I wrote a simple incomplete chess engine that could win against CM5000. But I got side tracked and never finished it. In 2004 I returned to chess programming and got sidetracked writing a more traditional chess engine, RomiChess. My health turned bad and now I just don't have it in me anymore to write a chess engine. The partial engine that I wrote that could win against CM5000 did not have a positional evaluation function at all whatsoever. It chose its move purely by material and statistics gathered during the search. And the statistics it gathered was minimal. It only counted beta cutoffs for each side in the tree above each root move and created a ratio. I've posted about this several times but it seems nobody finds my idea interesting. It played a very interesting game of chess though.

[mar]

Additional piece lists would cost a lot of additional memory and updating, therefore nobody would do that.

Well, I used a hybrid approach in Cheng: bitboards plus 8x8 bytes for piece/color info for each board square.
Kings were completely separated, simply king position per color (2 bytes).
This is not exactly a piece list, but I can get one easily by iterating occupancy bitboard and looking up this information.
This may be one of the reasons why copy-make was never a winner for me, but the difference was rather small IIRC.
Anyway, this approach worked for me, I don't se why it shouldn't work for others. I don't claim it's the best thing to do,
but "nobody would do that" seems a bit too bold to me.

[Sven]

Additional piece lists would cost a lot of additional memory and updating, therefore nobody would do that.

Well, I used a hybrid approach in Cheng: bitboards plus 8x8 bytes for piece/color info for each board square.
Kings were completely separated, simply king position per color (2 bytes).
This is not exactly a piece list, but I can get one easily by iterating occupancy bitboard and looking up this information.
This may be one of the reasons why copy-make was never a winner for me, but the difference was rather small IIRC.
Anyway, this approach worked for me, I don't se why it shouldn't work for others. I don't claim it's the best thing to do,
but "nobody would do that" seems a bit too bold to me.

As you say: this is not exactly a piece list, not at all. I have a redundant 8x8 board as well to resolve access to piece type and color per square faster than by looking up all bitboards. I think that is common for bitboard engines. A piece list is basically a data structure for the opposite kind of access: give me all locations of pieces of color x [and of type y]. That is what I meant. So my claim "nobody would do that", now being corrected into "nobody except Michael would do that" , does not match your case.