theY4Kman
commented
6 years ago Neo4j is pretty awesome for experimental graph work. Its browser GUI visualizes nodes and relationships from queries, and lets ya drag things around. It ain't perfect – for instance, you'll drag the nodes juuuuust right, try out some code, reload the query to see the deleted nodes disappear, but, uh, all the nodes explode, forgetting all node positions. Uh, but the query text editor is fantastic. So much of the interface is done well that all my remaining complaints are shallow.
Anyway, here's some example code: https://gist.github.com/theY4Kman/ec70d7ce5e2110de4bd9df8bdbaea378
And some progressive screenies. The GUI is really damn handy for general problem solving -- if you can break things down into bite-sized pieces and arrange them in some meaningful way, your mind may start recognizing novel relationships before you consciously realize it. Anyway, I'm blabbering.
These screenies are all based on this board state:
# = unknown/unclicked/unrevealed cell
1-9 = numbered cell
#|#|#|#|# a|b|c|d|e
1|2|2|2|# v|w|x|y|f
|1|# |z|g
board labels
not done, but i am up very late
At the moment, all the strategies implemented care only about the probability a cell contains a mine at one particular instant. Besides a few heuristics laid on top of random expansion (like expanding toward a border, or trenching into a pool of unrevealed cells by way of a numbered strait), each strategy only wants to know if its next click will be a mine or not.
When it comes to Minesweeper, any solver working discretely will eventually have to face fuzziness. The question which lead me to this ticket was: is clicking the cell with the lowest probability most effective?
That question begs a bunch of others. Like, what is the true probability a cell will contain a mine? Is it just the max probability as observed from its neighbouring numbers? What if the configuration of all numbers on the board invalidates a cell from containing a mine? Is "effectiveness" not clicking on a mine? Is there any way to click on cells away from the numbered border to expose more information from the board, perhaps opening up new possibilities, maybe all the way to winning?
I'd be lying if I said I didn't see "testing all possibilities" coming as the "ultimate" strategy to a Minesweeper solver. I'd also be lying if I said I knew what that meant at the start. "Seeing it coming" seems only to mean "I think I'd be able to differentiate it from other solutions" — it says nothing about being able to synthesize anything. At best, it means "I can probably tell who/what I'd learn from", which turns out to be pretty handy as a student.
Anyway, now that I've exhausted a lot of the fantasies I harbored about algorithms and their magic — as all students must do — "testing all possibilities" seems a lot less opaque. Maybe if I'd stayed at university, I'd've had the sorts of juicy conversations that effortlessly lift the veil on big solutions shrouded in paradox and confusion. It's not for the classes I ponder returning. But I digress!
"Testing all possibilities" now must fit other moulds I've collected over the years, a lot of which are essentially ways to avoid pitfalls into premature optimization. For instance, "all possibilities" must necessarily include invalid ones, which means "testing all possibilities" must actually be split into "collecting all possibilities" and "combining possibilities". In this world of oneness which doesn't appear so, all things can be broken down into components — if you can tell the difference between two things, you can categorize them. If you can categorize them, you can make a binary tree. And if you can make a binary tree of them, you can do arithmetic on them. (I guess.)
What used to be an opaque "test all possibilities" is now
The steps aren't very concrete, but now it's at least a little more obvious what to search for.
Now that all that's out of the way, this ticket is pointing toward a seemingly generic Bayesian-logical solution to solving Minesweeper; or, how can we account for all visible mine possibilities, including those affected by decisions made completely on the other side of the board?
It may seem edgy, but I think I nodés solution >_>