bitboards like mailbox

[Karlo Bala]

The true power of bitboards is in the eval. For example, you want different mobility patterns, normal, through pieces but not pawns, exclude knights, exclude bishops, etc. Then future mobility through safe squares, 2 or 3 steps in advance. King paths in pawn endgames, a lot of patterns for trapped pieces. All you need to do is to set or clear some bits in bitboard and feed the attacks routine. There are countless uses. It would be almost impossible to do it with pure mailbox representation (efficiently). If you want PST + some simple patterns eval then bitboards are most probably an overkill.

Well, I understood that bitboard engines also use attack getters for Rooks and Bishops quite a lot, in evaluation. So I just tried to provide an alternative (less memory intensive) method for obtaining those. Just reading them from a board-size table, such as orth[s] for the Rook attacks from square s, seems a speed improvement over the usual magics, which would need several small-table lookups (for the mask and the multiplier), a multiply, a shift and a lookup in a large (non-L1-fitting) table.

The issue is just how much overhead it would take to maintain the table, as its contents should obviously be adapted to the board occupancy. Up to 8 elements could have to be changed because of a capture, and on a crowded board it is likely that most pieces indeed have neighbors in all 8 directions. (On a near-empty board this will of course sharply drop.) The time to make these updates can only be earned back if the attack getter is used often enough.

Unfortunately, in the last 20-25 years I lost my sources several times. One of the first "smart" versions keeps every attack of every piece as a bit on every square. Similar to Ed's solution, but with the full information. One bit corresponds to one piece in the piece list. 32 pieces fitted well in the 32-bit word. Whenever I need to move a piece just read which piece attacks the square and recalculate attacks for that piece. Everything was done in the Make-unmake, it worked like a charm. To generate a move list I just need to scan through the board and read the bitsets.

Had only one problem, it was slower than a simple solution
Never understood why. Perhaps I will try again, just for fun.

[hgm]

That sounds very much like the design I used in the mailbox trials. But there I acheived an enormous speedup compared to a simple solution. Perhaps it is critically dependent how you do the map update, and how often.

[dangi12012]

The true power of bitboards is in the eval. For example, you want different mobility patterns, normal, through pieces but not pawns, exclude knights, exclude bishops, etc. Then future mobility through safe squares, 2 or 3 steps in advance. King paths in pawn endgames, a lot of patterns for trapped pieces. All you need to do is to set or clear some bits in bitboard and feed the attacks routine. There are countless uses. It would be almost impossible to do it with pure mailbox representation (efficiently). If you want PST + some simple patterns eval then bitboards are most probably an overkill.

Well, I understood that bitboard engines also use attack getters for Rooks and Bishops quite a lot, in evaluation. So I just tried to provide an alternative (less memory intensive) method for obtaining those. Just reading them from a board-size table, such as orth[s] for the Rook attacks from square s, seems a speed improvement over the usual magics, which would need several small-table lookups (for the mask and the multiplier), a multiply, a shift and a lookup in a large (non-L1-fitting) table.

The issue is just how much overhead it would take to maintain the table, as its contents should obviously be adapted to the board occupancy. Up to 8 elements could have to be changed because of a capture, and on a crowded board it is likely that most pieces indeed have neighbors in all 8 directions. (On a near-empty board this will of course sharply drop.) The time to make these updates can only be earned back if the attack getter is used often enough.

Unfortunately, in the last 20-25 years I lost my sources several times. One of the first "smart" versions keeps every attack of every piece as a bit on every square. Similar to Ed's solution, but with the full information. One bit corresponds to one piece in the piece list. 32 pieces fitted well in the 32-bit word. Whenever I need to move a piece just read which piece attacks the square and recalculate attacks for that piece. Everything was done in the Make-unmake, it worked like a charm. To generate a move list I just need to scan through the board and read the bitsets.

Had only one problem, it was slower than a simple solution
Never understood why. Perhaps I will try again, just for fun.

I implemented this with bitboards. It was a bit slower than a dumb implementation unfortunately but it sounds cool.
With bitboards you have on uint64_t changemap of 2,3,4 set bits. Now you only need to update all pieces that can see those squares. This can be done with a seemap of uint64_t[64] where we know the source bit and seemap of each piece.
When something changes in the visible space for one piece you only need to update the seemap again.

Why didnt it work: Because one seemap is not enough we also need to know which indices of the seemap are taken - and then we have to iterate all pieces twice. Once to update - and then to iterate over it. this array costs more than a dumb implementation that recalculates sliders at once. I wish it werent the case - but for now thats it for bitbaords.

The cost of pawns that are stuck would go to literally zero operations - because the AND intersection of the seemap with the changemap would be zero.

[tcusr]

UPDATE:
while i was getting frustrated writing this new move generator i remembered that i still have my old engine which uses magic bitboards, why not run some tests?
i decided to do search on kiwipete at depth 8, but with 2 generators:
1) fancy magic bitboard (with a table of 800kb)
2) kogge stone generator

these are the results (the engine uses only mvv/lva for ordering and psqt tables for evaluation, so it's pretty lightweight)
magic bitboard: 6.2 seconds with 2.95 Mnodes/sec
kogge stone: 8.3 seconds with 2.2 Mnodes/sec

tbh i expected worse, even though in all the other tests kogge stone was always slower, on higher depths the difference was of, at most, 3 seconds.
in my generator i plan to use the kogge stone only in the generation of captures, so in the end it will be a tiny bit faster than pure kogge stone

[dangi12012]

UPDATE:
while i was getting frustrated writing this new move generator i remembered that i still have my old engine which uses magic bitboards, why not run some tests?
i decided to do search on kiwipete at depth 8, but with 2 generators:
1) fancy magic bitboard (with a table of 800kb)
2) kogge stone generator

these are the results (the engine uses only mvv/lva for ordering and psqt tables for evaluation, so it's pretty lightweight)
magic bitboard: 6.2 seconds with 2.95 Mnodes/sec
kogge stone: 8.3 seconds with 2.2 Mnodes/sec

tbh i expected worse, even though in all the other tests kogge stone was always slower, on higher depths the difference was of, at most, 3 seconds.
in my generator i plan to use the kogge stone only in the generation of captures, so in the end it will be a tiny bit faster than pure kogge stone

Do you have a repo - I can take a quick look at the fancy impl and give some feedback

[tcusr]

UPDATE:
while i was getting frustrated writing this new move generator i remembered that i still have my old engine which uses magic bitboards, why not run some tests?
i decided to do search on kiwipete at depth 8, but with 2 generators:
1) fancy magic bitboard (with a table of 800kb)
2) kogge stone generator

these are the results (the engine uses only mvv/lva for ordering and psqt tables for evaluation, so it's pretty lightweight)
magic bitboard: 6.2 seconds with 2.95 Mnodes/sec
kogge stone: 8.3 seconds with 2.2 Mnodes/sec

tbh i expected worse, even though in all the other tests kogge stone was always slower, on higher depths the difference was of, at most, 3 seconds.
in my generator i plan to use the kogge stone only in the generation of captures, so in the end it will be a tiny bit faster than pure kogge stone

Do you have a repo - I can take a quick look at the fancy impl and give some feedback

no i don't have a repo, i copied the most important parts here

Code: Select all

struct Magic {
	uint64_t bits;
	uint64_t mask;
	uint64_t mult;
	uint64_t *offset;

	uint64_t index(uint64_t blockers) const
	{
		return ((blockers & mask) * mult) >> bits;
	}
};

template<int P>
void init_sliders(Magic *magics, uint64_t *table, const uint64_t *mult)
{
	for (int s = 0; s < 64; ++s) {
		uint64_t b = 1ull << s;
		uint64_t edges = 0;

		if (!(b & RANK_1)) edges |= RANK_1;
		if (!(b & RANK_8)) edges |= RANK_8;
		if (!(b & FILE_A)) edges |= FILE_A;
		if (!(b & FILE_H)) edges |= FILE_H;

		Magic *m = magics + s;
		m->mask = multiple_attacks<P>(b, 0) & ~edges;
		m->bits = 64 - popcount(m->mask);
		m->mult = mult[s];
		m->offset = table;

		uint64_t blockers = 0;
		do {
			m->offset[m->index(blockers)] = multiple_attacks<P>(b, blockers);
			++table;
			blockers = (blockers - m->mask) & m->mask;
		} while (blockers);
	}
}

as you can see it's just a rearranged copy from stockfish. i took the magics from ethereal and to fill the attacks i use kogge stone generators
for rooks table is 0x19000 big and for bishops it's 0x1480

[Gerd Isenberg]

UPDATE:
while i was getting frustrated writing this new move generator i remembered that i still have my old engine which uses magic bitboards, why not run some tests?
i decided to do search on kiwipete at depth 8, but with 2 generators:
1) fancy magic bitboard (with a table of 800kb)
2) kogge stone generator

these are the results (the engine uses only mvv/lva for ordering and psqt tables for evaluation, so it's pretty lightweight)
magic bitboard: 6.2 seconds with 2.95 Mnodes/sec
kogge stone: 8.3 seconds with 2.2 Mnodes/sec

tbh i expected worse, even though in all the other tests kogge stone was always slower, on higher depths the difference was of, at most, 3 seconds.
in my generator i plan to use the kogge stone only in the generation of captures, so in the end it will be a tiny bit faster than pure kogge stone

Kogge-Stone is intended for a direction wise approach (similar to set-wise pawn attacks left and right) of multiple sliding pieces, i.e. rooks and queens for orthogonal and bishops and queens for diagonal directions. Otherwise for single pieces, there are faster approaches also with low memory consumption.

[tcusr]

UPDATE:
while i was getting frustrated writing this new move generator i remembered that i still have my old engine which uses magic bitboards, why not run some tests?
i decided to do search on kiwipete at depth 8, but with 2 generators:
1) fancy magic bitboard (with a table of 800kb)
2) kogge stone generator

these are the results (the engine uses only mvv/lva for ordering and psqt tables for evaluation, so it's pretty lightweight)
magic bitboard: 6.2 seconds with 2.95 Mnodes/sec
kogge stone: 8.3 seconds with 2.2 Mnodes/sec

tbh i expected worse, even though in all the other tests kogge stone was always slower, on higher depths the difference was of, at most, 3 seconds.
in my generator i plan to use the kogge stone only in the generation of captures, so in the end it will be a tiny bit faster than pure kogge stone

Kogge-Stone is intended for a direction wise approach (similar to set-wise pawn attacks left and right) of multiple sliding pieces, i.e. rooks and queens for orthogonal and bishops and queens for diagonal directions. Otherwise for single pieces, there are faster approaches also with low memory consumption.

i know (i wanted to use them to find pinned pieces quickly but i learned that pseudo-legal generators are better) but they fit really well in the structure of my program. everything is centered on directions, just look at the code i posted to generate sliders move on the fly

[dangi12012]

UPDATE:
while i was getting frustrated writing this new move generator i remembered that i still have my old engine which uses magic bitboards, why not run some tests?
i decided to do search on kiwipete at depth 8, but with 2 generators:
1) fancy magic bitboard (with a table of 800kb)
2) kogge stone generator

these are the results (the engine uses only mvv/lva for ordering and psqt tables for evaluation, so it's pretty lightweight)
magic bitboard: 6.2 seconds with 2.95 Mnodes/sec
kogge stone: 8.3 seconds with 2.2 Mnodes/sec

tbh i expected worse, even though in all the other tests kogge stone was always slower, on higher depths the difference was of, at most, 3 seconds.
in my generator i plan to use the kogge stone only in the generation of captures, so in the end it will be a tiny bit faster than pure kogge stone

Kogge-Stone is intended for a direction wise approach (similar to set-wise pawn attacks left and right) of multiple sliding pieces, i.e. rooks and queens for orthogonal and bishops and queens for diagonal directions. Otherwise for single pieces, there are faster approaches also with low memory consumption.

i know (i wanted to use them to find pinned pieces quickly but i learned that pseudo-legal generators are better) but they fit really well in the structure of my program. everything is centered on directions, just look at the code i posted to generate sliders move on the fly

Pseudolegal move generating is many times slower than having valid moves only to begin with.
You can find all pins on the board with the cost of one queen xray operation (from the kings square).

[tcusr]

UPDATE:
while i was getting frustrated writing this new move generator i remembered that i still have my old engine which uses magic bitboards, why not run some tests?
i decided to do search on kiwipete at depth 8, but with 2 generators:
1) fancy magic bitboard (with a table of 800kb)
2) kogge stone generator

these are the results (the engine uses only mvv/lva for ordering and psqt tables for evaluation, so it's pretty lightweight)
magic bitboard: 6.2 seconds with 2.95 Mnodes/sec
kogge stone: 8.3 seconds with 2.2 Mnodes/sec

tbh i expected worse, even though in all the other tests kogge stone was always slower, on higher depths the difference was of, at most, 3 seconds.
in my generator i plan to use the kogge stone only in the generation of captures, so in the end it will be a tiny bit faster than pure kogge stone

Kogge-Stone is intended for a direction wise approach (similar to set-wise pawn attacks left and right) of multiple sliding pieces, i.e. rooks and queens for orthogonal and bishops and queens for diagonal directions. Otherwise for single pieces, there are faster approaches also with low memory consumption.

i know (i wanted to use them to find pinned pieces quickly but i learned that pseudo-legal generators are better) but they fit really well in the structure of my program. everything is centered on directions, just look at the code i posted to generate sliders move on the fly

Pseudolegal move generating is many times slower than having valid moves only to begin with.
You can find all pins on the board with the cost of one queen xray operation (from the kings square).

not in a chess engine. some moves will never be played so why bother checking their legality?