[jkafjanvnfaf]

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]

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]

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-... 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]

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]

> 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

For a more echo chess specific answer, see my answer above to @bazzargh

[bobmichael]

That's a brilliantly simple approach. You could even have an estimated difficulty score that updates based on number of moves, switches, etc. and ramp up target difficulty as the random run progresses.

[ramly]

Yep. Even the boring, topology-agnostic 'macro' variables can be good proxies for difficulty: obstacles count, empty squares count, counts per piece type, etc. I don't have a direct source for this but the original echo chess post has a good EDA section (+ feature importance plots) covering the impact of such variables on solvability. At scale, average solvability of random levels might be a half-decent proxy for how the difficulty of individual ones would fluctuate.

[ramly]

Very valid take - few thoughts to share on this. And thanks for linking the writeup about Linjat's procedural generation. That was a great read. Many interesting insights on the approach the author used for finding solutions to the puzzles in his logic game. The solver method with its conceptual layers seems particularly interesting. I think the challenge with this type of 'forward' puzzle generation, however, is that it tends to lead to more trivial levels by default. The Linjat author actually admits this limitation in the same post, shortly after introducing the neat solver:

> "This process will not always produce a solution, but it's pretty fast (on the order of 50-100 microseconds) so it can just be repeated a bunch of times until it generates a level. Unfortunately it'll generally produce a mediocre puzzle. There are too many obvious moves right at the start, the board gets filled in very quickly and the solution tree is quite shallow."

This tracks well with my own earlier experiments and my intuition about the (in)consistency of generating interesting echo chess levels by solution-tracing one random walk at a time. That said, could this forward-pass procedural generation be improved upon by adding some discriminator/scoring system after it to make sure we're not falling for the most trivial of solutions? Absolutely. In fact, the author continues by explaining how Linjat does that as well.

> "The above process produced a mediocre puzzle. In the final stage, we use that level as a seed for an optimization process. The optimizer sets up a pool of up to 10 puzzle variants. The pool is initialized with the newly generated random puzzle. On each iteration, the optimizer selects one puzzle from the pool and mutates it. [...] We then run the solver in the special level-generation mode [...] to make it solvable again. After that, we run the solver again, this time in the normal mode. [...] The new puzzle is then added to the pool. If the pool ever contains more than 10 puzzles, the worst one is discarded. This process is repeated a number of times (anything from 10k to 50k iterations seemed to be fine). After that, the version of the puzzle with the highest score is saved into the puzzle's level database."

In other words, what we'd truly be doing is: (1) some iterative process to generate a (trivially) solvable walk, (2) add random mutations to make the (solvable) level interesting, (3) readjust to make the (interesting) solvable again, (4) rinse and repeat until we have a (hopefully) interesting and solvable level.

To be clear, there's nothing wrong with this approach - it could even give us more granular control of difficulty curving explicitly. Indeed, with the right tweaks, I bet some solid solver + optimizer process could be devised to generate non-trivially solvable echo chess levels starting from a forward random walk.

Philosophically, in fact, the last step of the Linjat optimizer sounds actually pretty similar to the way the current 'Endless' mode in echo chess selects a level to be served to the player. 50 random gens get evaluated by the ML ensemble, they get ranked by majority-voting of solvability first, and probability of being solvable second, and the level with the highest score is the one that gets committed to the game.

Granted, the current echo chess generator directly starts from a parametrized random pool of 'mutations' before running them through its solvability discriminator, as opposed to starting from a definitionally solvable forward walk kernel to be mutated. Mutations first, solvability second. But the result is the same. And given that the starting pool is parametrized, there is still ample control (implicitly at least) in adjusting the distribution of components like obstacles, piece types, topology, etc. to vary the expected difficulty of the seeds.

TL;DR: we can start from random weights or fine-tune promising ones. But we still need to do something to get non-trivial levels generated.