Overview: Your challenge is to write a program that will play minesweeper optimally, giving the best move in any position. Moreover, you must do this on the largest board possible.
Game details: Minesweeper is a one player game, played on a rectangular board. At the beginning of the game, a specified number of mines are randomly distributed over the board, at most one to a cell. Each possible placement of the mines is equally likely. The mines' positions are hidden from the player.
On each of the player's turns, he or she chooses a square on the board to reveal. If the square contains a mine, the player loses the game. Otherwise, the number of mines in Moore neighborhood of the chosen square (orthogonally or diagonally adjacent) is revealed to the player.
The player repeats this until either a mine is revealed, or the number of unrevealed squares is equal to the number of mines. If the latter occurs, the player wins.
Program specification: Your program must take as input a board position, which should specify the locations and values of the revealed and unrevealed squares, as well as the number of mines on the board. It must return at least one move which has a maximal likelihood of winning if followed by optimal play. Returning more moves is allowed, as long as they all have the same, maximal, win rate.
In addition, the program must return the maximal number of possibilities that can be won under optimal play and the total number of possibilities for this revealed board state. From these values, the exact probability of winning under optimal play is known.
Examples:
Input (in any format you prefer):
4 mines
____
____
____
____
Output:
Best moves are [(0, 1), (0, 2), (1, 0), (1, 3), (2, 0), (2, 3), (3, 1), (3, 2)].
961 wins out of 1820 possibilities.
Input:
5 mines
_____
_1___
_3___
_____
Output:
Best moves are [(0, 2)].
285 wins out of 360 possibilities.
Challenge specification: Your challenge is to run your program on the initial position of a board of one of the following types:
- n x n board, n mines.
- n x n+1 board, n mines.
- n x n+1 board, n+1 mines.
Your program must find an optimal move on your machine at least as fast as the reference implementation solves the 4x5 board, 5 mines case on your machine. That case takes 6 minutes on my computer, for reference.
To run that instance of the reference implementation with timing, run python3 Minesweeper-challenge.py <<< "(4,5), 5, '____________________'"
The program that correctly identifies the optimal moves and exact number of possibilities that can be won with perfect play, on the initial position of the largest board of the above type, tiebreaker most mines, in the given time limit, wins the contest.
I will select a winner in two weeks, on July 24th.
Since writing a program like this is a big task, I will be awarding a bounty of 150 reputation, starting tomorrow and ending on the 18th.
Edit/bump: Well, that was a waste of 250 rep.