9 ms·
Echo Chess: The Quest for Solvability
- jxmorris12 3y agoGot addicted to this game over the summer. Fun twist on chess puzzles and the upper levels get increasingly sophisticated. I think I got stuck on Level 13.
- ramly 3y agoGlad you're enjoying it. Making it to Level 13 is pretty awesome. I remember one of the early playtesters calling it 'the level from hell'.
- deleted 3y ago[deleted]
- Choco31415 3y agoAre you sure that level 13 is possible? There doesn't seem to be a way to both take the f2 king and the a1 pawn. The b6 bishop can't reach either. The d1 pawn can only reach one or the other.
- ramly 3y agoAbsolutely :) It has more than one solution, with the optimal one using 35 moves. Have you tried solving level 12 first? The 'aha' moments in echo chess build up on each other one level at a time.
- Choco31415 3y agoI have! It was a light and fun level. c:
- ramly 3y agoPerfect. So the same mechanic learned in 12 can be leveraged in 13+. Obviously here timing is everything. I think 13 is a good example of a level where 'forward' or 'backward' passing alone won't be enough. It's almost like the best strategy to solve these mazes is 'middle out' (not to be confused with the infamous algorithm by Richard Hendricks).
- buzzin_ 3y agoSpoilers: Work your way to the a1 pawn, then a2 king can take the f2 king.
- ramly 3y ago#nospoilers :')
- stevage 3y agoI had that idea, but even with that, I'm still stuck. I get to a position with white king stuck behind the pawn on c3, with black pieces on a5, a6 and d6. Or I start with dxe, take the white rook with the pawn, and end up with black pawn on a1 and white bishop on e6. Another hint? EDIT Oh never mind, finally got there. Just a slight tweak to the move order, which took forever to discover.
- ramly 3y agoHey HN! I'm sami, the creator of echo chess. This is the true story of diving way too deep into a rabbit hole of chess, ML, and puzzle design. Hope you enjoy the read. Originally built this chess variant as a fun hack but it really escalated since then. It's a single-player puzzle game. You're playing white, there's no opponent, and you need to clear the board to win. Every time you capture a piece, you become the 'echo' of that piece. There's also an 'endless' mode with infinite levels generated in real time and validated by ML to ensure solvability. Took forever to make it work but it now has 99% accuracy. You can play the 'classic' mode here: https://echochess.com/ https://echochess.com/ and endless here: https://echochess.com/?endless https://echochess.com/?endless Happy to answer any questions.
- oessessnex 3y agoI implemented a partial generator based on the idea in my previous comment. It was quite a fun challenge. At each step it determines the reachable squares for the given piece, that are not occupied or block past moves, and chooses one at random, then it computes the shortest path to that square. This procedure is repeated until there are no squares available. Only pawns, knights and kings are supported so far. https://gist.github.com/oessessnex/bc617095675da44f857216f98e461bec https://gist.github.com/oessessnex/bc617095675da44f857216f98... Great game btw :)
- ramly 3y agoGlad you enjoyed the game - and the generator metagame. Thanks for pitching in and sharing your partial gen implementation! > the reachable squares for the given piece, that are not occupied or block past moves The last part is key. There's a similar discussion related to level generation here: https://news.ycombinator.com/item?id=37334186 https://news.ycombinator.com/item?id=37334186 If you do check it out, I'd be curious to hear your thoughts on the Linjat approach and the limitation around trivial solvability of gens without an optimizer step of some sort. Still unclear at this stage where the debate of ML vs deterministic solvers will land on this one, though there are already several insights discussed that can be meaningful for puzzle design in general. Let me know if you end up expanding the code and/or going through the 'forward solver' tangent debate. Thankful for your efforts in taking a stab at this challenge!
- sambernstein 3y ago[flagged]
- rariss 3y ago[flagged]
- goldenberry 3y ago[flagged]
- rraad 3y ago[flagged]
- gmchad 3y ago[flagged]
- bryanlanders 3y agoSami is brilliant. He demoed Echo Chess at a recent San Diego engineer event and everyone was blown away and asking tons of questions. A lot of love and intelligence went into building this game.
- ramly 3y agothank you for the support, glad you're enjoying echo chess. it's been a ton of fun building a chess variant with ML. happy to answer any questions.
- dimator 3y agoaside: i always hear about cool events like this after the fact. i have tried to find sites that have listings of hacker/engineering/conference type events, but most of them are very spammy, or low signal. is there a good resource for finding these?
- bryanlanders 3y agoYeah, you're right it can be tough. We started our own organization (https://sdx.community https://sdx.community) centered around hackers/builders because it felt like it was missing, exactly as you described! We share on Twitter, Luma, LinkedIn, and try to get other community groups to amplify, but there's a lot of noise out there, so we likely miss a lot of cool people. Sometimes you get lucky and there's a good community slack/discord (for example the San Diego Startups slack) where you'll see most events posted. Otherwise, startups that are hiring engineers tend to sponsor and share events. Beyond that you have to just find out from other hackers where they're speaking or joining something. Where do you live?
- dimator 3y agoquite a drive from San Diego, i'm afraid, but I'd love to make a trip of it if non-natives are welcome!
- stevage 3y agoA few comments on the game: - would be good to support two tap moves like on lichens rather than only drag and drop - drag and drop seems really buggy on my phone. Often had to repeat my move. - accidentally clicked give up instead of try again, then my game was over? Not really sure why there is a give up button at all. - the timer just adds stress instead of fun, for me. - hated the music being on by default - imho the obstacles should be symbols, not just a different square colour. I had trouble seeing them.
- JJCUBER 3y agoJust like you, I accidentally hit "give up" at one point by mistake. I actually found the music quite good. In a somewhat similar vein, I found the endless mode to be a bit tiring, since you have to keep up the pace to maintain enough time. It could be nice to have a pause button for endless mode (or both modes). Of course, it would defeat the purpose if someone could just pause right after seeing each board, but I feel like having a pause button with some sort of multi-minute cooldown could be an interesting addition. For some people, this might defeat the purpose of endless mode, but it's just a thought! I also ended up playing endless long enough to get a score that was too large; my score overlapped with my name on the leaderboard. (I reached level 157 with 136.7m score, then I let time run out due to my hands getting tired.)
- stevage 3y ago> I actually found the music quite good. I'm not expressing an opinion on whether the music is good or not. I just really don't want (or expect) any music to play. It's particularly annoying when I play on my phone in a quiet moment, and suddenly music is blasting out. It doesn't seem to remember the setting.
- ramly 3y agoThat's fair. Side note, unrelated to echo chess - which of these (very eclectic) TBS or puzzle games would you say have soundtracks that are more of a fit for the solo puzzle-solving experience you'd find ideal: Tetris (tanaka), HOMM (romero), Civ (knorr), or small indies like Monument Valley, Into the Breach, etc.?
- student2k 3y agoBest post ever? The level of details is beautiful. Any plan in releasing an Android app? Thank you
- ramly 3y agoPossibly soon. Should work fine on android mobile web in the meantime. Let me know if you run into any issues.
- lucb1e 3y ago+1 for keeping the web version usable on mobile. I don't need something that runs in the background and tracks which IP addresses my phone passes through with a carbon copy to facebook via their sdk or whatnot.
- ramly 3y agoCertainly. I'm always astonished how many games think turning into Cambridge Analytica is a prerequisite for doing basic ML on their own game-generated data.
- thomasfromcdnjs 3y agoThis could be a good coffee table book.
- ramly 3y agoDown to make a coffee table version if you know a good print shop. Can send you a copy for free.
- zzo38computer 3y agoMost of the pictures are not displayed. (This seems to be because they are WebP format even though the file name is ".png".) Do you have a full description of the rules, and do you have the FEN? I like to know the rules if I want to play game, and, it is not working so I made up my own, and if the levels is available then I can play game. The below is I made up my own (I don't even know, if it is the real rules or not; but it is what I had understood): ; Echo Chess (InputXY) (Control Input (INIT $Cursor 1 1 0 0 Create =@cur) (KEY IgnoreKey) ) ($Cursor (Image "Cursor0" "Cursor1") (DefaultImage ()) (Density -10) (CREATE LOOP 0 1 50 Animate) ) ($Tile (Image "Tile0" "Tile1") (Density 10) (INIT Loc + 1 band =Image) (CLICK @cur ,ObjBelow #Move Loc ,Send . 1) ) ($White (Image "P" "N" "B" "R" "Q" "K") (CLICK @cur Loc ,MoveTo) (#Move fork Image (case (0 :pawn) (1 :knight) (2 :bishop) (3 :rook) (4 :queen) (5 :king) ) then if Arg1 Arg2 MoveTo . Arg3 if From ,Image =Image From ,Destroy . (=P $Black) lnot if WinLevel then then @cur Loc ,MoveTo . then ) (:pawn Yloc Arg2 1 + eq Xloc Arg1 Delta Arg3 eq land) (:knight Xloc Arg1 Delta dup * Yloc Arg2 Delta dup * + 5 eq) (:bishop Xloc Arg1 Delta Yloc Arg2 Delta eq if =:queen else 0 then) (:rook Xloc Arg1 Delta Yloc Arg2 Delta land if 0 else =:queen then) (:queen From Seek =%d Loc begin %d NewXY over over ObjTopAt dup From eq if . . ret then ,Class $Tile ne until . . 0) (:king From Chebyshev 1 eq) ) ($Black (Image "PB" "NB" "BB" "RB" "QB" "KB") (CLICK @cur ,ObjBelow #Move Loc 1 ,SendEx . 1) )
- ramly 3y agoAre you referring to the images in the post or the actual game? Looks good on my side, might be the unexpected extra traffic. Sorry about that! In any case, you can try the game directly here: https://echochess.com/ https://echochess.com/ The rules are really simple: 1) You are playing White, there's no opponent. You must capture all pieces to win. 2) You become the "echo" of any piece you capture. Captured a bishop? Become that bishop. 3) You can’t pass through red obstacles. Find the best move order to clear the board. You can play it on any device, just drag and drop the white piece to move around. Let me know if you have any issues. p.s. love that you just made your own!
- Invictus0 3y agoThis post has 5 astroturfed (flagged and dead) comments from accounts less than 2 hours older than this post all within 1 hour of this being posted, and all with only a single comment on their account. Hmmm...
- ramly 3y agoYes I got schooled by dang about this as a n00b in the community :') Long time lurker, first time commenter. See comment thread from dang above, he was super nice to explain to me all this stuff. Thank you all for being kind and welcoming.
- X6S1x6Okd1st 3y agoReally 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
- thethirdone 3y agoThis 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/rust/echochess.rs https://github.com/TheThirdOne/assorted-examples/blob/master...
- wchargin 3y agoNice 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 https://github.com/wchargin/echo-chess Direct link to source: https://github.com/wchargin/echo-chess/blob/main/src/main.rs https://github.com/wchargin/echo-chess/blob/main/src/main.rs
- robertosalem 3y agoLove this game!!
- ramly 3y agoGlad you're enjoying it. What level did you reach?