piece lists advantage with bit-boards?
Moderators: hgm, Rebel, chrisw
-
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
piece lists advantage with bit-boards?
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?
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: piece lists advantage with bit-boards?
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.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: piece lists advantage with bit-boards?
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 wrote: ↑Mon Dec 24, 2018 11:35 pm 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?
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)
-
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: piece lists advantage with bit-boards?
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?Michael Sherwin wrote: ↑Tue Dec 25, 2018 1:24 am 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 meant something like thisSven wrote: ↑Tue Dec 25, 2018 1:30 amNot 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 wrote: ↑Mon Dec 24, 2018 11:35 pm 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?
Code: Select all
int pieceCount[PIECE_NB];
Square pieceList[PIECE_NB][16];
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: piece lists advantage with bit-boards?
Nobody Sven? I guess I'm nobody then.Sven wrote: ↑Tue Dec 25, 2018 1:30 amNot 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 wrote: ↑Mon Dec 24, 2018 11:35 pm 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?
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;
...
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: piece lists advantage with bit-boards?
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.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 737
- Joined: Wed Mar 08, 2006 8:08 pm
- Location: Orange County California
- Full name: Stuart Cracraft
Re: piece lists advantage with bit-boards?
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--
Much more interesting.
--Stuart--
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: piece lists advantage with bit-boards?
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.smcracraft wrote: ↑Tue Dec 25, 2018 2:20 am 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--
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 2559
- Joined: Fri Nov 26, 2010 2:00 pm
- Location: Czech Republic
- Full name: Martin Sedlak
Re: piece lists advantage with bit-boards?
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.
Martin Sedlak
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: piece lists advantage with bit-boards?
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.mar wrote: ↑Tue Dec 25, 2018 4:30 amWell, 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 Schüle (engine author: Jumbo, KnockOut, Surprise)