search

jordanbray / chess

A rust library to manage chess move generation
https://jordanbray.github.io/chess/
MIT License
243 stars 55 forks source link

Bitboard trait #5

Closed gnzlbg closed 7 years ago

gnzlbg commented 7 years ago

I would like to use the library with my own Bitboard (and maybe even different bitboard layouts), .

Would it be possible to make Bitboard a trait?

Or is the representation you are using fully tied to the algorithm implementations?

jordanbray commented 7 years ago

I'm not quite sure how I feel about that. That would be a lot of extra code to maintain, and you'd have to rationalize that with some pretty juicy features that could be added. Can you explain why you would need a custom BitBoard, so I can make a better judgement call?

That said, if you have an implementation of a bitboard that is somehow better, I'd be more than happy to merge that in.

Keep in mind that a lot of lookup tables (see: magic bitboards) use bitboards, and all the code that you write would have to not break those as well. This would require implementing multiplication, for example, on your custom bitboard type (for the perfect hashing magic bitboards provides). That code needs to be cleaned up regardless, but it would still be an issue.

gnzlbg commented 7 years ago

That would be a lot of extra code to maintain

I would expect a Bitboard trait to implement some of the methods of your current Bitboard struct (the ones you need in the algorithms). It will probably just be ~10 lines of code. One would need to change the algorithms that use bitboards to be parametrized over the bitboard type.

But then you just implement it for yours (which is basically already done, just forward the trait methods to the ones of your bitboard), and that allows it to implement it for mine.

Can you explain why you would need a custom BitBoard, so I can make a better judgement call?

Different algorithms for different parts of the engine work faster with different layouts, but you generally want all of them to be able to make correct moves. Chess programming wiki has a lot of info on bitboard layouts, in case you are interested. There are lots of them.

jordanbray commented 7 years ago

One would need to change the algorithms that use bitboards to be parametrized over the bitboard type.

This would be the main problem, not the actual trait itself. In particular, there are many lookup tables that would need to be rearchitectured to work with the trait, which would be difficult. Note that, the magic bitboards already needs reimplementation. It is very ugly and very slow. However, my plan for fixing it involved generating all those bitboards at compile time. This would not be possible if the BitBoard was a trait (at least not in a way I can think of). I'll think on it more tonight, and look through what exactly would need to change to get this to work, and I'll let you know.

gnzlbg commented 7 years ago

Can't you require those look-up tables in the trait? You have for example in your bitboard implementation the constants edges, ranks, files, ... and you don't provide those at compile time, but generate them at run-time. If you would instead would require in your trait associated functions edges, ranks, ... a different bit board implementation could provide those as static constants (instead of mutable statics).

Anyhow, for this to work anything bitboard specific should be accessed through the trait. You can require that information to be in a particular format, so that the rest of the library works. The trivial thing to do would be to require it in the same format than Bitboard uses now.

jordanbray commented 7 years ago

I've looked into this more, and I don't think this is a good fit for this project. I think that it adds complexity, and that I don't see a huge advantage. I'm gonna close this. If you submit a pull request that shows a performance increase given a different bitboard format, I'd be much more likely to consider it. I don't think, however, that I will allow multiple bitboard formats, as there will be a bunch of conversions needed, which I'm pretty sure will erase any performance gains.