Comment by X6S1x6Okd1st
2 years ago
Really odd to recognize we have a hard problem, but one that's very well specified & maps cleanly onto solvers (e.g. minizinc) and instead say this should be solved with a laundry list of sklearn.
This is one of the magical spaces where there is always a solution, the board space isn't that big & shrinks as you go
It's even simpler than that. You can randomly generate a valid sequence of moves (i.e you are a pawn at a2, move to a3, become knight, move to ..., move to ..., become ..., ...), instead of the initial board state and that guarantees the puzzle is solvable. The only thing you need to watch out for is that you are not allowed to touch squares that appear in previous moves.
This actually isn't too hard to make a solver for. Especially in the single white piece case. I made a solver [0] that can solve level 8 (the hardest single white level) in less than 100 ms. I believe that it can solve every single white puzzle, but I haven't tested it thoroughly.
It works by reducing the state to currently alive pieces and the current white piece right after conversion. It computes the transversable squares and possible captures for each state and does a basic DFS. One neat trick I used is that for simple traversability, the queen and the king are the same piece.
Multiple white pieces makes the code significantly more complex, but it simply adds a little bit to the statespace.
[0]: https://github.com/TheThirdOne/assorted-examples/blob/master...
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.