4 ms·

Hello and thank you for the neat article. I have not finished it yet (I'm still partway through the ML bit), so ignore me if this is explained somewhere, but as

Hello and thank you for the neat article. I have not finished it yet (I'm still partway through the ML bit), so ignore me if this is explained somewhere, but as far as I can see you only considered "generate and test for solvability" approaches. But isn't there a direct way to generate puzzles by solving the board "backwards"? Start with a single white piece on the board. Then, pick a random predecessor of that state; either the piece moved there normally or it was a capture. In the first case just move the white piece back, in the second replace it with a matching black piece and place a new white piece in a spot that could have captured it. Do this a few times until you are satisfied with the number of black pieces. The biggest issue I can see right now is matching up the starting piece with the previous puzzle's ending piece, but I feel that should be manageable with some heuristics and brute force. And one would have to test whether the puzzles generated like this are actually "random-looking" enough.

ramly 3y ago
100% exactly. This is a very smart observation and is actually one of the main approaches I attempted first when tackling the creation of 'endless' mode. There are a few nuances and adjustments that would actually turn what you're suggesting into a somewhat viable approach, but I think in general you're on the right track with both the hypothesis and its limitations. A lot of the early playtesting I did for 'endless' kept indicating, much to my initial dismay, that the continuity of the carryover white piece is pretty much essential. In hindsight, it kinda makes sense. Imagine playing Tetris or Temple Run but where every 30 sec you essentially start from scratch. I guess maybe that's why people are more likely to binge-watch a whole season of Breaking Bad back-to-back than a full season of Black Mirror? If we didn't have that constraint for echo chess, we could've easily just saved the crowdsourced pre-labeled solvable levels into a big 'test bank' db, and randomly served one of them any time a player needs a new level to play. Think SAT/GRE questions that are all pre-curated beforehand but that get 'generated' at random for every participant. Thankfully the ML classification approach I ended up going with completely sidesteps the carryover piece dilemma. It's like you said: you simply "generate [incl. carryover] and test for solvability". Plus it works, with 99%+ accuracy, and in real time. So I think we're good for a bit :)
- bazzargh 3y ago
  you don't need to run the puzzle backwards to generate solvable positions, you run it forwards and generate the pieces from the solution moves. Starting with the piece and square from the previous board, mark all squares but this one as unknown. Make a random move. Any unknown squares passed through get marked blank in the current board and in the puzzle. Randomly choose to keep the same piece (making this square blank in the puzzle) or switch (marking the chosen piece in the puzzle, but now blank in the current board). Continue making random moves (biasing slightly towards choosing unknown squares), eventually stop and randomly assign the remaining unknowns as obstactles or blanks. Because you've said you don't care if there's only one solution, this gives you solvable puzzles trivially. This isn't a new idea, eg https://www.snellman.net/blog/archive/2019-05-14-procedural-puzzle-generator/ https://www.snellman.net/blog/archive/2019-05-14-procedural-... talks about generating solvable puzzles using the forward moves, you'd generally pair it with a filter that weeds out puzzles that are not fun for some reason (eg, solutions that random walk blank squares; these can be avoided at generation time by having a budget for move-to-blank)
  - kwertyops 3y ago
    It's weird that I almost immediately had the thought for essentially exactly the same approach while reading the article. Not that this reflects on OP; flashes of solutions like that I think are often mostly random. But I wonder if this is a sign of things to come - rather than needing to find explicit deterministic solutions to many problems that might actually have one, because ML is getting much more powerful and accessible instead we'll just use ML models and get 99.9% accurate solutions, but say, well that's good enough.
    - ramly 3y ago
      > I wonder if this is a sign of things to come - rather than needing to find explicit deterministic solutions to many problems that might actually have one, because ML is getting much more powerful and accessible instead we'll just use ML models and get 99.9% accurate solutions, but say, well that's good enough. You're not alone: http://www.incompleteideas.net/IncIdeas/BitterLesson.html http://www.incompleteideas.net/IncIdeas/BitterLesson.html For a more echo chess specific answer, see my answer above to @bazzargh

ramly 3y ago

100% exactly. This is a very smart observation and is actually one of the main approaches I attempted first when tackling the creation of 'endless' mode. There are a few nuances and adjustments that would actually turn what you're suggesting into a somewhat viable approach, but I think in general you're on the right track with both the hypothesis and its limitations. A lot of the early playtesting I did for 'endless' kept indicating, much to my initial dismay, that the continuity of the carryover white piece is pretty much essential. In hindsight, it kinda makes sense. Imagine playing Tetris or Temple Run but where every 30 sec you essentially start from scratch. I guess maybe that's why people are more likely to binge-watch a whole season of Breaking Bad back-to-back than a full season of Black Mirror? If we didn't have that constraint for echo chess, we could've easily just saved the crowdsourced pre-labeled solvable levels into a big 'test bank' db, and randomly served one of them any time a player needs a new level to play. Think SAT/GRE questions that are all pre-curated beforehand but that get 'generated' at random for every participant. Thankfully the ML classification approach I ended up going with completely sidesteps the carryover piece dilemma. It's like you said: you simply "generate [incl. carryover] and test for solvability". Plus it works, with 99%+ accuracy, and in real time. So I think we're good for a bit :)

bazzargh 3y ago
you don't need to run the puzzle backwards to generate solvable positions, you run it forwards and generate the pieces from the solution moves. Starting with the piece and square from the previous board, mark all squares but this one as unknown. Make a random move. Any unknown squares passed through get marked blank in the current board and in the puzzle. Randomly choose to keep the same piece (making this square blank in the puzzle) or switch (marking the chosen piece in the puzzle, but now blank in the current board). Continue making random moves (biasing slightly towards choosing unknown squares), eventually stop and randomly assign the remaining unknowns as obstactles or blanks. Because you've said you don't care if there's only one solution, this gives you solvable puzzles trivially. This isn't a new idea, eg https://www.snellman.net/blog/archive/2019-05-14-procedural-puzzle-generator/ https://www.snellman.net/blog/archive/2019-05-14-procedural-... talks about generating solvable puzzles using the forward moves, you'd generally pair it with a filter that weeds out puzzles that are not fun for some reason (eg, solutions that random walk blank squares; these can be avoided at generation time by having a budget for move-to-blank)
- kwertyops 3y ago
  It's weird that I almost immediately had the thought for essentially exactly the same approach while reading the article. Not that this reflects on OP; flashes of solutions like that I think are often mostly random. But I wonder if this is a sign of things to come - rather than needing to find explicit deterministic solutions to many problems that might actually have one, because ML is getting much more powerful and accessible instead we'll just use ML models and get 99.9% accurate solutions, but say, well that's good enough.
  - ramly 3y ago
    > I wonder if this is a sign of things to come - rather than needing to find explicit deterministic solutions to many problems that might actually have one, because ML is getting much more powerful and accessible instead we'll just use ML models and get 99.9% accurate solutions, but say, well that's good enough. You're not alone: http://www.incompleteideas.net/IncIdeas/BitterLesson.html http://www.incompleteideas.net/IncIdeas/BitterLesson.html For a more echo chess specific answer, see my answer above to @bazzargh