piece lists advantage with bit-boards?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: piece lists advantage with bit-boards?

Post by syzygy » Wed Dec 26, 2018 9:05 pm

Sven wrote:
Tue Dec 25, 2018 12:30 am
MahmoudUthman wrote:
Mon Dec 24, 2018 10: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?
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.
Stockfish has exactly those additional piece lists. For unclear reasons all attempts to eliminate them so far have failed.

If I'm not mistaken, originally asmFish did not have piece lists but pedantFish did (pedantFish was asmFish modified to have the same node counts as Stockfish). asmFish was slightly faster than pedantFish but turned out to be a few Elo weaker (so pedantFish was renamed into asmFish).

Removing piece lists from SF without Elo loss might be a matter of returning a few parameters.

Michel
Posts: 2046
Joined: Sun Sep 28, 2008 11:50 pm

Re: piece lists advantage with bit-boards?

Post by Michel » Wed Dec 26, 2018 9:53 pm

syzygy wrote:
Wed Dec 26, 2018 9:05 pm
Sven wrote:
Tue Dec 25, 2018 12:30 am
MahmoudUthman wrote:
Mon Dec 24, 2018 10: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?
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.
Stockfish has exactly those additional piece lists. For unclear reasons all attempts to eliminate them so far have failed.

If I'm not mistaken, originally asmFish did not have piece lists but pedantFish did (pedantFish was asmFish modified to have the same node counts as Stockfish). asmFish was slightly faster than pedantFish but turned out to be a few Elo weaker (so pedantFish was renamed into asmFish).

Removing piece lists from SF without Elo loss might be a matter of returning a few parameters.
Lucas used to claim that the reason the removal of piece lists failed was that too many clients were still running 32 bit windows on their 64 bit processors. I assume this reason no longer applies. Or course there remains the possibility of bad luck (the SPRT(-3,1) has a 36% probability of failing on a neutral patch).
Ideas=science. Simplification=engineering.
Without ideas there is nothing to simplify.

Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: piece lists advantage with bit-boards?

Post by Sven » Wed Dec 26, 2018 10:36 pm

syzygy wrote:
Wed Dec 26, 2018 9:05 pm
Sven wrote:
Tue Dec 25, 2018 12:30 am
MahmoudUthman wrote:
Mon Dec 24, 2018 10: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?
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.
Stockfish has exactly those additional piece lists. For unclear reasons all attempts to eliminate them so far have failed.
[...]
Removing piece lists from SF without Elo loss might be a matter of returning a few parameters.
In most recent SF source the piece lists only serve for very special purposes as far as I can see:
1) to implement a method Position::square() which always returns the square of the only present piece of given color and type (e.g. the king, or the pawn/bishop/rook in a special endgame), and
2) to implement a method Position::squares() which returns (a pointer to) an array of squares associated to pieces of given color and type.

1) can simply be replaced by an implementation in standard bitboard manner.
2) is used for special endgames KRPPKRP, KBPPKB (to obtain the first and second pawn of the given color - replacement similar to 1) ) as well as for looping through all pieces of a given color and type in evaluation and move generation (at very few places, I see 3 such lines in evaluate.cpp, movegen.cpp, pawns.cpp). In each single case I am pretty sure that looping through a set of pieces (resp. their squares) can be done in the typical bitboard way without any Elo loss.

If these places of using the pieceList[] member of class Position would be eliminated then it would be possible to drop members pieceList[] and index[] (and their initialization/updating/consistency checking code) completely.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: piece lists advantage with bit-boards?

Post by syzygy » Wed Dec 26, 2018 11:00 pm

Michel wrote:
Wed Dec 26, 2018 9:53 pm
Lucas used to claim that the reason the removal of piece lists failed was that too many clients were still running 32 bit windows on their 64 bit processors. I assume this reason no longer applies. Or course there remains the possibility of bad luck (the SPRT(-3,1) has a 36% probability of failing on a neutral patch).
I don't think 32-bit clients on fishtests were the reason for all attempts to fail, as it does not explain why asmFish was weaker than pedantFish.

The main effect of using piece lists is that moves are generated in the order defined by the piece lists instead of in the A1-H1-A8-H8 order. If a piece is captured and uncaptured (in do_move()/undo_move()), the captured piece is moved to the end of the list. Perhaps this added "randomisation" is beneficial. Or perhaps this is just a matter of SF having been tuned to this.

Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: piece lists advantage with bit-boards?

Post by Sven » Thu Dec 27, 2018 1:35 am

syzygy wrote:
Wed Dec 26, 2018 11:00 pm
Michel wrote:
Wed Dec 26, 2018 9:53 pm
Lucas used to claim that the reason the removal of piece lists failed was that too many clients were still running 32 bit windows on their 64 bit processors. I assume this reason no longer applies. Or course there remains the possibility of bad luck (the SPRT(-3,1) has a 36% probability of failing on a neutral patch).
I don't think 32-bit clients on fishtests were the reason for all attempts to fail, as it does not explain why asmFish was weaker than pedantFish.

The main effect of using piece lists is that moves are generated in the order defined by the piece lists instead of in the A1-H1-A8-H8 order. If a piece is captured and uncaptured (in do_move()/undo_move()), the captured piece is moved to the end of the list. Perhaps this added "randomisation" is beneficial. Or perhaps this is just a matter of SF having been tuned to this.
Technically I got it working quickly without the piece lists. But you are right: based on the output of the "bench" command the modified version is significantly slower. It might be caused by the fact that pieces of both colors are retrieved in A1-H1-A8-H8 order.

Original (current master of today):

Code: Select all

Total time (ms) : 1913
Nodes searched  : 3451321
Nodes/second    : 1804140
Without piece lists:

Code: Select all

Total time (ms) : 2080
Nodes searched  : 3679242
Nodes/second    : 1768866
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

Post Reply