Is this a more viable long-term strategy than carefully extricating yourself in the manner described above?īut if so it would fundamentally change the character of how the board is solved. It's almost uncannily adept at getting out of tight situations.ġ note, astute reader, that 'riskier' in this context doesn't mean the most dangerous - choosing a 95% likely mine is rarely advised - but rather the most uncertain - closest to 50/50, likely to go either wayĢ another example is the popular strategy of clicking in the uncharted regions of the board in the hopes of getting a "cascade", i.e., opening up a new front of play, even though the uncharted region is typically risky. Looking several moves ahead may both pay off and be feasible in certain situations (such as the endgame), but this algorithm doesn't concern itself with that.Īnd the open-ended case, for "perfect" play, simply cannot be done.ĭespite these shortcomings, it's still impressive to watch the algorithm at work, even just one move ahead. So the safest move at the moment is not always the best move for long-term success.Ĭreating a perfect player that accounts for this - the outcome not just of this move, but the repurcussions of all possible subsequent moves - is intractable. There are known examples where this is indeed the case.Īnd anecdotally, gameplay often seems to play out this way, where the safer bets reveal less useful information than do the riskier 2. Now suppose there were a riskier 1 cell that, had we lived to tell the tale, would have removed that uncertainty right away.ĭid we expose ourselves to more accumulated risk through several low-risk guesses rather than making the bold move upfront? So we guess again, and again… until finally we get some new information that removes the remaining uncertainty and lets us escape from the trap. We're still alive, but it doesn't seem like it revealed much information about the surrounding cells. Imagine this typical situation: we must guess, so we make the logical 'best' move by clicking on the lowest-risk cell. (Or even choosing among equivalently-risky cells.) That is to say, "is there a riskier move we can make now, that will pay off in multiple safer moves later on?" To have the best chance of surviving the game, we must consider not only the next move, but the repurcussions on all potential future moves. This algorithm only computes the safest cell(s) for the very next move. Luckily, in practice, the exponent and board size are together small enough that boards can be solved quickly. It is strongly suspected that exponential time is the best we can do. The unfortunate truth, however, is that despite all these fancy tricks, minesweepr still requires exponential time to run - each new technique only serves to shave some amount off that exponent. This solver employs a number of techniques to cut down on the amount of work needed. This is easier said than done enumerating all possible mine configurations is a huge computational task ( "exponential-time algorithm", i.e., for each fixed amount increase in the problem size, the work needed to solve it doubles, i.e., the universe will probably freeze over before you finish). Thus, if there is no guaranteed-safe cell, we can still determine the least-likely cells to have mines, and play the game quite skillfully.Īny algorithm that hopes to exhaustively solve minesweeper must employ this basic concept: determine all possible placements of mines on the board (and the relative likelihoods thereof), and observe how often each cell has a mine in it. If, among all possible configurations, a cell is always a mine or always clear, we know for certain the cell is a mine or safe.Ī cell that appears in both states cannot be determined with any certainty however, we can compute its relative safety by counting how many configurations in which it appears empty, as a proportion of all possible configurations, assuming all configurations are equally likely. Our goal is to find configurations of mines that satisfy the given constraints. It achieves this through advanced combinatorial and probability analysis.Ī minesweeper board is essentially a set of logical constraints.Įach cell is a boolean state: mine or clear.Įach uncovered cell says how many of the adjacent cells are mines. It can solve any board, with any topology, and exactly compute every cell's chance of being a mine.
0 Comments
Leave a Reply. |