Originally published at: https://boingboing.net/2018/04/19/watch-programmer-demonstrate-h.html
…
3 Likes
I remember reading that Minesweeper is NP complete. So, this guy in the video probably hasn’t created the perfect AI to play Minesweeper - or if he has then it’s the breakthrough of the century…
4 Likes
I have not read the video, but years ago I watched the NPC Minesweeper paper. My experience with Minesweeper is that there can be situations where you know one of two spots has a bomb, but you can’t tell which. The article claims that this “perfect ai” will randomly choose, which will lose 50% of the time.
I believe the NPC Minesweeper paper cleverly uses such situations to encode an NPC problem, such that solving the minesweeper problem will solve the NPC problem. Therefore Minesweeper is NPC.
Unless this guy’s “perfect AI” is both perfect and fast, he hasn’t made the breakthrough of the century.
5 Likes
My perfect minesweeping AI is this:
Why hire expensive programmers when you can just get some expendable minimum wage wannabe soldiers?
2 Likes
Thanks for the article! I knew someone smart would chime in with the math behind this phenomenon.
2 Likes
While not minesweeper, for those who like that sort of puzzle, may I recommend fillomino? It basically mashes up minesweeper and the cave puzzles @frauenfelder posted about awhile back.
5 Likes
As a weirdly-dedicated minesweeper player, I was skeptical, but this is actually moderately interesting. His program is definitely not “perfect” for the reasons described above, but I wonder if the fact that it’s playing differently than a human player–using mathematical probability of squares being a bomb rather than pattern logic–might give it a slight advantage in patterns where there’s less information available to base logic on, in that it could then make better guesses. Ultimately probably not, since minesweeper is just not actually that complex of a game, logic-wise, and a human player can pretty easily figure out the probability of any given square being a bomb with the same level of accuracy as a computer.
I mean, outside of the described luck-based scenarios, pretty much the only things limiting my minesweeper play at this point are the occasional error of human carelessness and overall hand-eye coordination speed. Could an AI outperform me in those areas? Well, duh. It doesn’t seem like his program is any better than a top human player in the sense of “success at playing the game,” but it’s certainly possible that it’s programmed more elegantly than other minesweeper-playing AIs.
2 Likes
I call bullshit on this explanation. Or at least, it is missing key insights.
The number of combinations (not arrangements, as he mistakenly calls them) of, say, 100 mines on a 64x36 grid, is about 2e177. Trying them all out is in the same order of work as bruteforcing a 580bit symmetric key. A fairly obvious optimisation is to only consider the edge of the unrevealed area, that makes the problem tractable.
Considering the individual mine probability for each cell loses the information about “entangled” cells, and is not a very useful trick either.
In the end, it is rather trivial to look at all the cells in the edge of the hidden area, plug all the clues into a SAT solver such as z3, pick a random mine and test if changing its assignment is falsifiable, mark it, repeat. The most impressive part of this work is the GUI automation.
This topic was automatically closed after 5 days. New replies are no longer allowed.
