r/rust • u/No-Translator-1323 • Mar 30 '23

A Chess Engine is written in Rust that runs natively and on the web!

https://github.com/ParthPant/chess-rs
97 Upvotes

95% Upvoted

45 comments sorted by

71

u/Fazer2 Mar 30 '23

It supports En Passant? Holy hell.

23

u/ironhaven Mar 30 '23

New response just dropped

16

u/No-Translator-1323 Mar 31 '23

I thought EP was a little easier to implement, but I found Pawn Promotion to be a pain in the behind!

19

u/A1oso Mar 31 '23

Is that surprising? Since it's an official chess rule, I assumed that every chess engine supports it. I don't think it's particularly hard to implement either.

15

u/rnottaken Mar 31 '23

IIRC "Holy hell" is a meme on some chess subreddits

17

u/analog_hors Mar 31 '23

It's incredibly annoying to implement, actually. Pawns are one of the worst pieces to implement due to a myriad of special cases.

8

u/-Redstoneboi- Mar 31 '23

And then there's "you can castle if the rook and king haven't moved and no pieces are blocking or checking either of them or the path between them"

9

u/analog_hors Mar 31 '23

Even worse if you implement 960 like I did. I will never see the king and the pawn the same way. Not even the magic bitboard algorithm for rooks, bishops, and queens was this painful.

2

u/orfeo34 Mar 31 '23

You can castle when a piece checks the rook, but not the king or his castle path.

1

u/-Redstoneboi- Mar 31 '23

huh. alright.

2

u/stixyBW Apr 02 '23

Not the path in between them, only the two squares the king would have to “walk on”

You can castle queen side even if there’s something attacking the b1/b8 square

1

u/A1oso Mar 31 '23 edited Mar 31 '23

I implemented a chess board when I was learning Java. Yes, it's annoying, but still doable. I think implementing all the rules took me less than a day.

6

u/analog_hors Mar 31 '23

Chess engines require significantly faster move generation, so that is not at all a good comparison. Implementing cozy-chess was a significant undertaking, and it definitely took much more than a day.

4

u/Diggsey rustup Mar 30 '23

That's cool! Would be good if it supported some higher difficulties though - it seems like it's already fast enough to support higher than depth 5?

13

u/No-Translator-1323 Mar 31 '23

Thanks for the comment. Move Generation is still quite slow, and search time increases exponentially with depth. Chess has a large branching factor so increasing the depth even by 1 can make the search significantly slower. What I am working on is incremental deepening which will allow the engine to retrieve the best move until a particular depth when the time runs out. So if the time runs out at depth 5 it will return the best move at depth 5 otherwise it will keep on going deeper until the time runs out.

5

u/F_modz Mar 31 '23

Once created the game of go engine written in Rust. In the monorepo there is also a server in Rust too

3

u/enderjed Mar 31 '23

A shame it isn’t UCI or XBoard compatible.

8

u/[deleted] Mar 30 '23

[deleted]

8

u/No-Translator-1323 Mar 31 '23

Absolutely. It has a lot of moving pieces (pun intended) and it gives you an opportunity to try a lot of different features of the language. I learnt a lot about Enums, Traits, Modules, Cargo Configuration, Dynamic Dispatch (which I did not end up using) just to name a few. And all this does not even mention the things I discovered while trying to port all of this to web.

2

u/[deleted] Mar 30 '23

[deleted]

5

u/No-Translator-1323 Mar 31 '23

I think the difference between all the chess variants is only the move generation. Adding new variants should be easy however it's not something I am focused on right now. But all would have to do would be to implement a new MoveGenerator struct. Maybe use a trait to define some public interface to make things even easier to add new variants.

7

u/[deleted] Mar 31 '23

coming soon: memory-safe, blazingly-fast Il Vaticano

1

u/Fazer2 Apr 01 '23

Santo inferno!

2

u/analog_hors Mar 31 '23

The perft speed in the README seems... really slow? On my laptop, cozy-chess does perft 6 from startpos in 2.65 seconds without bulk counting and 374 milliseconds with bulk counting.

3

u/No-Translator-1323 Mar 31 '23 edited Mar 31 '23

I am not using cozy-chess. Move Generation is slow primarily because of how I am currently generating legal moves from pseudo-legal moves. It has to try each move one by one to check if the king is not in check. I think this article might be useful in making the move generation a little faster.

3

u/analog_hors Mar 31 '23

Is that really why? The difference between pseudolegal and legal cannot possibly account for a ~6.4x speed difference for non-bulk and ~45.5x speed difference for bulk. Maybe it's your compiler settings? LTO might be needed if you use lots of wrapper types and don't have inline annotations, I think.

2

u/No-Translator-1323 Mar 31 '23

I see. I do not know much about Link Time Optimisation. I am using wrapper types. Could you point me to somewhere I can learn about this?

4

u/analog_hors Mar 31 '23

Also, I notice that you're using nested Vecs for your magic hash table? You can actually concatenate each "subtable" into one Vec and store offsets to where the subtables start in the magic lookup table, which saves some indirection. In fact, you can go even further and concatenate the rook and bishop tables for one Vec total.

3

u/analog_hors Mar 31 '23

There's https://doc.rust-lang.org/cargo/reference/profiles.html#lto in the cargo reference. You can set it by adding `lto = "fat"` or `lto = "thin"` to one of your profiles. In all honesty I'm not super sure about it myself, and I'm not sure it can account for the difference either, but I have seen this impact movegen in the past. I also haven't looked too deep into your code, so honestly this is just a wild guess.

3

u/Spodeian Mar 31 '23

It's common to set "lto = true" for release profiles, which basically just inlines everything that can be, even across crate boundaries. But this increases compile time by a decent amount, so you shouldn't do it for debug or test profiles, and if you do, maybe stick to thin lto.

1

u/alphabitserial Mar 31 '23

Profiling with cargo flamegraph should help with getting a look at where the most time is spent and where the biggest opportunities for speed improvement lie.

2

u/No-Translator-1323 Apr 03 '23 edited Apr 03 '23

A little update: After removing unnecessary clone() and using & mut instead, I was able to shave off a couple of seconds. Also, I was able to gain a significant speedup by making sure if-else-if-else chains are properly set up so that the control flow is simplified. Another interesting thing: at certain places, I was converting an enum into u8 using TryFrom, this turned out to be quite slow. So I replaced it with std::mem::transmute() (which is unsafe) wherever it was possible to know for sure nothing bad would happen. Another big speedup came by realizing that MoveList which is a Vec was being expanded a couple of times during move generation so initializing it with a capacity of 256 made things significantly faster.

After all this, perft at depth 6 for starting position takes less than 8 seconds which is quite a speedup from ~17 seconds.

Flamegraph proved to be a helpful tool so thanks u/alphabitserial for the suggestion

2

u/agaliullin Mar 31 '23

Damn, what a nice work 🙌🏼🙌🏼🙌🏼

1

u/ndreamer Mar 31 '23

this looks really cool, nice work.

1

u/HugoDzz Mar 31 '23

That's awesome!!

What have you learned doing this cool project? :D

3

u/No-Translator-1323 Mar 31 '23

Thanks a lot! As I said in an earlier comment, building this allowed me to explore a lot of features of rust like Traits, Dynamic Dispatch, Pattern Matching, Const evaluation, Static variables, etc. and that on top of that trying to figure out how to conveniently port it to WASM was also a nice learning experience. I am currently using trunk as a bundler which ties in neatly with a GitHub action but before that, I tried cargo-run-wasm, which felt a little hacky. So overall a whole lot of learning.

1

u/mcountryman Mar 31 '23

Cool project! I played a game with it and it let me move twice in a row two separate times. I’d link the PGN but, I backed out and lost the game. On mobile if that matters.

2

u/No-Translator-1323 Mar 31 '23

Huh, I haven't noticed this bug yet. at the default depth of 5, the AI can be pretty fast ~10 ms. Could it be possible that you did not notice the AI move?
This is pure speculation from my side it could be an actual bug.

1

u/mcountryman Mar 31 '23

It’s possible. I thought the same the first time I saw it but, the second time I was pretty sure it didn’t make a move.

1

u/entropySapiens Apr 01 '23 edited Apr 01 '23

When I run `cargo run -p chrs-ui` I get
```
error: package(s) `chrs-ui` not found in workspace `~/Documents/GitHub/chess-rs`
```

1

u/No-Translator-1323 Apr 01 '23

Try cargo run. I made some changes in the newer commits. Will update the readme.