piece lists advantage with bit-boards?

[mar]

now being corrected into "nobody except Michael would do that"

I can imagine a pure bitboard engine though; a sum of

Code: Select all

((bitboard[i] & square_mask) != 0)*piece_type[i]

(or something like that) shouldn't be all that bad. Reducing the board size, going for copy-make, this may be a nice simplification.
Less code and less bugs to hunt, I'd probably go for something like that when I were starting from scratch
(not going to happen, but tempting

[Sven]

now being corrected into "nobody except Michael would do that"

I can imagine a pure bitboard engine though; a sum of

Code: Select all

((bitboard[i] & square_mask) != 0)*piece_type[i]

(or something like that) shouldn't be all that bad. Reducing the board size, going for copy-make, this may be a nice simplification.
Less code and less bugs to hunt, I'd probably go for something like that when I were starting from scratch
(not going to happen, but tempting

Yes, but again, where is the "piece list" in that snippet above?

[syzygy]

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]

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).

[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.

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.

[syzygy]

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]

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