Skip to content

Only necessary cull steps exploration

Alex Komoroske edited this page Jun 24, 2016 · 4 revisions

This is an exploration of the logic to only return cull steps that are necessary in HumanSolve (issues #48 and #125)

Thinking out loud, maybe we need to overhaul all (most?) of the HumanSolve search pipeline.

Conceptually we maintain a frontier of possible answers. Each answer is a chain of steps to apply to the grid at its current state and has a goodness score. A "partial" answer is a chain that does not end in a fill step. A "Complete" answer is a chain that ends in a fill step. Once an answer becomes complete (which for fill steps is as soon as it is found), it goes into the poolOfPossibleAnswers. Once the poolOfPossibleAnswers has NumberOfAnswersToWaitFor, it picks the answer with the highest Goodness score immediately and returns (canceling the rest of the search).

The frontier can grow unbounded (it must; if it didn't, and the first complete answer was only to be found more than a ply or two away, we might just thrash and never find it). At each time step we choose the item on the frontier with the best goodness value and explore that one forward, looking for all* steps off of it and adding new items to the frontier for each. (When considering if we should add a brand new item to the frontier (that is, not exploring forward an item already on the frontier, but rather starting a new technique), we look at the rawGoodness value of that new technique. If it's lower than all of the other frontiers we don't start it. Special case: if the frontier is empty but the AnswerPool isn't big enough yet, we'll add one--this is the special case to kick off searching for non-fill steps, basically)

  • In practice it can't be all steps, because then the second ply would get extraordinarily large. In a perfect world we'd be able to have some kind of generator-like API that predicted the goodness of the next item wit would find if you let it do more work. Hmmm...

The goodness is basically just the humanLikliehood of every step in that chain additionally multiplied by each of the twiddleValues for each step in the chain. (Note: twiddlers currently work on a batch of all solveSteps to consider at once; in this case we'd have to tweak them slightly to apply them just to a single proposed move... all of the current twiddlers would work fine in this approach).

In practice all cull steps that could apply at a given grid state are compatible with one another. One approach would be to find and apply all cull steps until none more were available, and then do a fill-step search. But this is the worst case, because it will almost certainly have tons of unnecessary cull steps. We want to keep the length/badness of each answer chain as low as possible. The solution to this is in the goodness score and minimizing that. We include a twiddler that gives a boost to steps whose pointerCells are the targetCells of previous steps. (In a perfect world that twiddle would only apply if the previous steps directly removed a key possibility that now made our step work; in practice that's hard so hopefully this will be OK). This twiddler looks back through the whole answer chain being considered and sees if any of the targetCells overlap with this proposed step's pointerCells, with a falloff for older steps.

If we're just looking for a hint, this strategy is fine because we won't do to much duplicate work. If we're looking for a full solution, we'll likely have a bunch of duplicated work re-finding the same implied techniques. In a perfect world for a full solution we'd have something to optimize that. For example, a set of steps that have been generated on an earlier era that we can just try now (... but only if we had an IsImplied method...)

Note that in this world guesses would make the logic much harder to reason about. Our current system earnestly tries to guess which the right answer is in a constrained cell and solves forward. However, even if we go down one path and then discover it has an inconsistency, we throw out all evidence of that failed branch in the end result we return... so we might as well just cheat. If we have to guess, do a fastSolve of the grid and figure out which of the two possibilities that cell will end up in. Then just return that. Then we don't need any special logic for guess--it's just a fillTechnique with extraordinarily low goodness.

Clone this wiki locally