bitboards like mailbox

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

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

Doubling threads from 1 to 2 yields 90 Elo on average. If your code is twice as fast - its like adding another core to the pc which is running it. You are not only generating moves - you are putting them into a list which means that slow memory is involved. Then you iterate over more moves than you should have to just to a legality check again - and ignore that move.
In short - the cpu needs to touch a bad move 4x and you add another if statement.

//Pseudo Legal
Generate - Iterate - Test for Legality - Ignore or Use

//Legal
Generate - Use

I dont think its valid to say that pseudo legal is better in any way - other than its easier to implement.

[Mergi]

I tend to agree that if you can get closer to a fully legal move gen, it should be overall better for the engine. But the biggest savings should be from not having to evaluate and sort as many moves, rather than the legality checks. This is especially true if you do a more complex move evaluation and sorting. Most moves should be fairly cheap to generate fully legal (obviously depending on the overall engine architecture).

I tried to implement both fully legal and pseudo legal generator in my engine. For fully legal, the biggest obstacles were king moves, castling and en passant. It turned out that for those it was better to just generate them pseudo legally and let the make/unmake function handle the legality. Theres only a very few of these moves available at any given point in the game, and even less if you are using a staged move generator, as even if there are such moves, the node usually gets pruned by the AB search before having to generate them. And even if you generate some illegal moves, chances are, they will get pruned before having to check their legality anyway. But honestly, these changes were barely noticeable in the grand scheme of things.

[tcusr]

final considerations
i decided to abandon this hybrid method and go back to (plain) magic bitboards. my L2 cache is less than 800kb so there's no reason to use the fancy approach (and to copy code from other engines).
also, as it says here https://www.chessprogramming.org/Magic_ ... ds#History, the size difference is nearly indistinguishable, why bother?

[dangi12012]

final considerations
i decided to abandon this hybrid method and go back to (plain) magic bitboards. my L2 cache is less than 800kb so there's no reason to use the fancy approach (and to copy code from other engines).
also, as it says here https://www.chessprogramming.org/Magic_ ... ds#History, the size difference is nearly indistinguishable, why bother?

Hey if your L2 is so small you can go the compressed route:
Not one lookup per piece - but one lookup per direction.

You can use PEXT or Fancy route - but the mask entries are H,V,D1,D2 - and not HV, D12
The tablesize will fit in your L2.

[Sopel]

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?

Doubling threads from 1 to 2 yields 90 Elo on average. If your code is twice as fast - its like adding another core to the pc which is running it. You are not only generating moves - you are putting them into a list which means that slow memory is involved. Then you iterate over more moves than you should have to just to a legality check again - and ignore that move.
In short - the cpu needs to touch a bad move 4x and you add another if statement.

//Pseudo Legal
Generate - Iterate - Test for Legality - Ignore or Use

//Legal
Generate - Use

I dont think its valid to say that pseudo legal is better in any way - other than its easier to implement.

All this is irrelevant because in a chess engine move generation is within single %s of runtime.

[tcusr]

sorry to revive this thread but i don't know where to ask these stupid questions.
1) what is the kogge stone algorithm used for?
out of all the engines i've read none of them uses this algorithm, only https://github.com/ankan-ban/perft_gpu seems to use it but only for test purposes, i think. which is not even a good idea since gerd said there are faster techniques to generate attacks on the fly from a single square

2) apart from a hand crafted eval, where do bitboards really prove to be better than a mailbox representation?
pruning/move ordering techniques do not the depend on the board representation so why should i use them when i only use a tapered eval with PSQT?

thanks in advance

[Karlo Bala]

sorry to revive this thread but i don't know where to ask these stupid questions.
1) what is the kogge stone algorithm used for?
out of all the engines i've read none of them uses this algorithm, only https://github.com/ankan-ban/perft_gpu seems to use it but only for test purposes, i think. which is not even a good idea since gerd said there are faster techniques to generate attacks on the fly from a single square

2) apart from a hand crafted eval, where do bitboards really prove to be better than a mailbox representation?
pruning/move ordering techniques do not the depend on the board representation so why should i use them when i only use a tapered eval with PSQT?

thanks in advance

IMO, just go with the kogge-stone. It is good enough and it is simple and straightforward. I doubt there is a faster generator that doesn't require additional data. Once you have a mature engine, and when you exhaust all ideas on search and eval then go back and change the generator. You can spend the time on more creative ways than optimizing the generator. Most programmers go for search because it is easier to test, but the eval is the true challenge.

As for bitboard vs. mailbox, it is not about the speed, is it about the way of thinking. I prefer bitboards, but of course, there are opposite opinions.

[Mike Sherwin]

sorry to revive this thread but i don't know where to ask these stupid questions.
1) what is the kogge stone algorithm used for?
out of all the engines i've read none of them uses this algorithm, only https://github.com/ankan-ban/perft_gpu seems to use it but only for test purposes, i think. which is not even a good idea since gerd said there are faster techniques to generate attacks on the fly from a single square

2) apart from a hand crafted eval, where do bitboards really prove to be better than a mailbox representation?
pruning/move ordering techniques do not the depend on the board representation so why should i use them when i only use a tapered eval with PSQT?

thanks in advance

Let's say the moves are being generated for a queen that attacks the enemy king. In mailbox that may not be discovered until the very last move is generated and stored in a move list. In bitboard as soon you have the bits it can be tested and no queen moves will be added. In RomiChess during the normal search when moves are generated, only the bits are generated and stored. Only after the ht move, promotions, winning captures, killers etc are the remaining bits spun into a move list. Keeping and using the bits makes for for fast verification that a ht or killer move etc are legal. Most of the time no move list is even created. Etc.

[tcusr]

sorry to revive this thread but i don't know where to ask these stupid questions.
1) what is the kogge stone algorithm used for?
out of all the engines i've read none of them uses this algorithm, only https://github.com/ankan-ban/perft_gpu seems to use it but only for test purposes, i think. which is not even a good idea since gerd said there are faster techniques to generate attacks on the fly from a single square

2) apart from a hand crafted eval, where do bitboards really prove to be better than a mailbox representation?
pruning/move ordering techniques do not the depend on the board representation so why should i use them when i only use a tapered eval with PSQT?

thanks in advance

IMO, just go with the kogge-stone. It is good enough and it is simple and straightforward. I doubt there is a faster generator that doesn't require additional data. Once you have a mature engine, and when you exhaust all ideas on search and eval then go back and change the generator. You can spend the time on more creative ways than optimizing the generator. Most programmers go for search because it is easier to test, but the eval is the true challenge.

As for bitboard vs. mailbox, it is not about the speed, is it about the way of thinking. I prefer bitboards, but of course, there are opposite opinions.

since i don't understand how to implement hgm's neighbor table i will go back to magic bitboards and use kogge stone to only initialize my tables, i was hoping to find some other use for them, maybe in the eval idk

[tcusr]

sorry to revive this thread but i don't know where to ask these stupid questions.
1) what is the kogge stone algorithm used for?
out of all the engines i've read none of them uses this algorithm, only https://github.com/ankan-ban/perft_gpu seems to use it but only for test purposes, i think. which is not even a good idea since gerd said there are faster techniques to generate attacks on the fly from a single square

2) apart from a hand crafted eval, where do bitboards really prove to be better than a mailbox representation?
pruning/move ordering techniques do not the depend on the board representation so why should i use them when i only use a tapered eval with PSQT?

thanks in advance

Let's say the moves are being generated for a queen that attacks the enemy king. In mailbox that may not be discovered until the very last move is generated and stored in a move list. In bitboard as soon you have the bits it can be tested and no queen moves will be added. In RomiChess during the normal search when moves are generated, only the bits are generated and stored. Only after the ht move, promotions, winning captures, killers etc are the remaining bits spun into a move list. Keeping and using the bits makes for for fast verification that a ht or killer move etc are legal. Most of the time no move list is even created. Etc.

is this some kind of attack table with a staged move generation? it's too advanced for me now