AI Minesweeper project

Question

I need to implement Minesweeper solver. I have started to implement rule based agent. I have implemented certain rules. I have a heuristic function for choosing best matching rule for current cell (with info about surrounding cells) being treated. So for each chosen cell it can decide for 8 surroundings cells to open them, to mark them or to do nothing. I mean. at the moment, the agent gets as an input some revealed cell and decides what to do with surrounding cells (at the moment, the agent do not know, how to decide which cell to treat).

My question is, what algorithm to implement for deciding which cell to treat?

Suppose, for, the first move, the agent will reveal a corner cell (or some other, according to some rule for the first move). What to do after that?

I understand that I need to implement some kind of search. I know many search algorithms (BFS, DFS, A-STAR and others), that is not the problem, I just do not understand how can I use here these searches.

I need to implement it in a principles of Artificial Intelligence: A modern approach.

Answer 1

BFS, DFS, and A* are probably not appropriate here. Those algorithms are good if you are trying to plan out a course of action when you have complete knowledge of the world. In Minesweeper, you don't have such knowledge.

Instead, I would suggest trying to use some of the logical inference techniques from Section III of the book, particularly using SAT or the techniques from Chapter 10. This will let you draw conclusions about where the mines are using facts like "one of the following eight squares is a mine, and exactly two of the following eight squares is a mine." Doing this at each step will help you identify where the mines are, or realize that you must guess before continuing.

Hope this helps!

Answer 2

To implement a Minesweeper solver using the principles of Artificial Intelligence: A Modern Approach, you can use search algorithms combined with heuristics to make informed decisions about which cell to treat next. One suitable algorithm for this problem is the A search algorithm*. A* is a best-first search algorithm that uses both the cost to reach a node and an estimate of the remaining cost to reach the goal (heuristic) to guide the search.

Here's an outline of how you can proceed:

State Representation: Represent the Minesweeper board as a state with hidden cells, revealed cells, and their respective values (number of adjacent mines). You can use a 2D array or a graph-based representation.

Heuristic Function: Develop a heuristic function that estimates the cost or utility of expanding a particular state. The heuristic function should guide the search towards the most promising cells to reveal or mark.

A Search*: Implement the A* search algorithm to explore the state space of the Minesweeper board. At each step, A* selects the cell that appears most promising based on the combination of the known cost to reach that cell and the estimated cost (heuristic) to reach the goal from there.

Rule-Based Agent: Combine the A* search with your rule-based agent. When the A* search chooses a cell to treat, apply your existing rule-based agent's rules to decide whether to open surrounding cells, mark them as mines, or take no action.

The A* search will guide the solver to make intelligent decisions based on the current state of the board and the estimated potential outcomes. The rule-based agent will then act on the selected cell and its surroundings, applying your predefined rules to continue exploring the board.

In the beginning, you can start with a simple heuristic function, such as considering the number of remaining hidden cells or the number of adjacent mines, but you can experiment and improve the heuristic over time to enhance the solver's performance.

Keep in mind that Minesweeper is NP-complete, which means that finding an optimal solution efficiently is challenging. However, using A* search with an appropriate heuristic will significantly improve the solver's chances of success compared to basic random moves or uninformed search algorithms.

Remember that your rule-based agent can also utilize information gathered during the A* search to make more informed decisions about cell treatment, such as adjusting the rules based on the patterns of revealed cells or detected mine clusters.