Comment by wchargin
2 years ago
Nice work! I had a similar idea and also wrote a little solver in Rust [1]. I chose the same benchmark puzzle as is in your code, and it solves in ~25 microseconds on my laptop (i7-1165G7).
I haven't optimized my approach at all or even run it under a profiler, but it uses SIMD-within-a-register for computing the "flood fill" of which squares a piece can move to, which is a nice efficiency boost. For the simplest example, if you have a bit-vector `v: u64` of positions that a pawn might be in, then `v << 8` is the vector that denotes where it might be after one step, and `((v & can_move::LEFT) << 7) | ((v & can_move::RIGHT) << 9)` denotes what it might be able to capture.
I think the `Stepper` implementations and the way they flow into the top-level `captures` function is a cool and powerful approach; I encourage taking a look if it sounds interesting to you.
[1]: https://github.com/wchargin/echo-chess
Direct link to source:
https://github.com/wchargin/echo-chess/blob/main/src/main.rs
This is really neat. Thank you and @thethirdone for putting in the effort to tackle this! Love these creative takes to add efficiency boosts. You guys make HN awesome.
> Multiple white pieces makes the code significantly more complex, but it simply adds a little bit to the statespace.
That would be my guess too. Especially the sacrifice mechanic that needs to be timed just right after X moves/transformations of each white piece.