Visualization of Problem Solving with Constraint Processing: Case Study of the Minesweeper

Chase Resio Author

04/04/2021 Added

59 Plays

Description

Minesweeper is a logic-based computer game that has been popular since the 1990's. An automatic solver can be created by utilizing Constraint Processing. The goal of this research was to create a solver and learn more about Constraint Processing and its applications to the real world.

Searchable Transcript

Search:

[00:00:00.400]Hello, my name is Chase Resio,
[00:00:02.850]and welcome to my presentation
[00:00:04.440]on the Visualization of Problem Solving
[00:00:06.920]with Constraint Processing: Case Study of the Minesweeper.
[00:00:12.530]During these past few months,
[00:00:13.760]I have been working on a Minesweeper solver.
[00:00:16.040]Minesweeper is a computer game released in 1989,
[00:00:19.330]but its popularity soared when it became installed
[00:00:21.640]with Windows 3.1 in 1992.
[00:00:24.750]The goal of the game is to reveal all cells
[00:00:26.810]without exploding any mines.
[00:00:28.670]You click on a cell to reveal what is on it.
[00:00:31.270]The cell will contain either a mine or a number
[00:00:33.700]indicating how many adjacent cells contain mines.
[00:00:36.920]Deciding whether an instance of Minesweeper
[00:00:39.220]has a solution is NP-complete,
[00:00:41.780]which means that there's currently not a way
[00:00:43.960]to solve it completely and correctly every time
[00:00:47.000]without simply trying every combination.
[00:00:50.290]The goals of my research were to utilize
[00:00:52.400]constraint processing to solve instances of Minesweeper
[00:00:55.920]as an introduction to constraint processing.
[00:00:59.430]The solver needed to be a web application
[00:01:01.580]deployable using React JS and JavaScript.
[00:01:05.140]Additionally, the ultimate goal
[00:01:06.900]when working with any NP-complete problem
[00:01:09.420]is to be the first to ever solve one.
[00:01:12.980]Minesweeper at its core is a logic based game
[00:01:15.690]and can be modeled as a constraint satisfaction problem.
[00:01:19.170]At its simplest level,
[00:01:20.550]every cell must either be safe or a mine.
[00:01:23.480]The safe cells contain a number that constrains
[00:01:25.960]what its neighboring cells can be,
[00:01:27.720]as shown on the image on the right.
[00:01:30.070]The 3, for example, places a constraint
[00:01:32.330]on cells D, E, F, I, J, N, O, and P,
[00:01:36.990]that only three of them can contain a mine.
[00:01:39.530]So, if we later find that D, E, and F are all mines,
[00:01:43.340]we know that the other five are safe.
[00:01:46.010]Different constraint satisfaction approaches
[00:01:48.220]can then be used to determine if a cell is safe.
[00:01:52.240]Here's an image of the website that was created.
[00:01:55.280]The Minesweeper game was implemented
[00:01:57.200]to be read from an XML file,
[00:01:59.160]whose information is used to create the board.
[00:02:02.400]Just like the standard Minesweeper game,
[00:02:04.310]the player has the option to select different board sizes
[00:02:07.070]that change the difficulty of the game.
[00:02:09.420]The users can also load their own instance of the game
[00:02:12.710]and the cheats reveal single cells
[00:02:14.910]for when the player gets stuck.
[00:02:17.170]The other components are new functionalities
[00:02:19.340]that were added for use of automatically solving it.
[00:02:22.370]The Solve panel is where you use the Solver's functionality,
[00:02:26.930]and the History Log logs what is happening in the game,
[00:02:30.040]as well as which consistencies reveal which cells.
[00:02:33.370]The consistencies are the different constraint methods
[00:02:36.370]to propagate consistency on the game.
[00:02:39.030]These are what solve it.
[00:02:42.170]Six levels of consistency propagation have been implemented.
[00:02:46.330]Each one in the list is increasingly more powerful,
[00:02:49.660]but is also more costly on the program
[00:02:51.760]in terms of time, amongst other factors.
[00:02:54.720]Shown in the image on the right
[00:02:56.170]is an instance of the board with the Peek option active.
[00:02:59.700]Peek highlights the cells that can be solved
[00:03:01.860]and are color-coded to show which consistency solves it.
[00:03:05.720]The weakest consistency is unary,
[00:03:08.190]and it is shown in yellow on the board.
[00:03:10.780]A unary constraint acts on a single variable,
[00:03:13.270]which immediately determines the value of the cell.
[00:03:17.140]So, as you can see here,
[00:03:19.240]this cell can be solved with a unary constraint.
[00:03:23.950]This is because this 1 already has a mine next to it.
[00:03:28.850]Therefore, this one cannot be a mine
[00:03:31.800]since it is still neighboring the 1.
[00:03:36.590]Generalized arc consistency, or GAC,
[00:03:39.630]enforces each constraint and propagates
[00:03:41.730]the effects of these decisions repeatedly
[00:03:44.050]from one constraint to all the others
[00:03:45.870]through the shared cells until no change occurs.
[00:03:49.470]So, as an example here,
[00:03:51.170]looking at the same area of the board, we see that
[00:03:55.340]this cell already shows that this one must be free.
[00:04:01.380]GAC knows everything that unary knows
[00:04:03.680]because it is more powerful.
[00:04:05.490]So thus, since this one is free,
[00:04:08.320]we know that this one is a mine.
[00:04:10.630]Why is that?
[00:04:11.463]Because this cell right here and this cell,
[00:04:15.200]they both need to have a mine by it.
[00:04:17.840]All the other spots have been revealed to not be mines.
[00:04:21.960]So that leaves either this one must be a mine
[00:04:24.280]or this one must be a mine.
[00:04:26.000]But since we know that this one cannot be a mine,
[00:04:29.090]we know that this one must be a mine through GAC
[00:04:34.640]Pairwise consistency, or 2wC,
[00:04:37.570]looks at every pair of constraints with overlapping scopes.
[00:04:41.470]So here we go, showing this again.
[00:04:44.020]So through GAC, we know that these two are not mines
[00:04:48.390]because this 1 already has its mine next to it
[00:04:51.670]and these two cells neighbor it.
[00:04:53.750]However, on its own, we do not know
[00:04:56.220]what the value of this cell is supposed to be.
[00:04:59.290]But if we bring in this cell right here and it's constraint,
[00:05:03.309]we know that this cell does not contain a mine
[00:05:07.520]because of the unary constraint, since this cell right here
[00:05:11.800]already has three mines neighboring it.
[00:05:15.020]So we know that this one is free.
[00:05:17.230]So now this 2 needs another mine by it
[00:05:20.330]because it already has this one right here.
[00:05:22.460]The only available spaces, now that we know
[00:05:25.160]that this one is free, is either this square or this square.
[00:05:29.070]However, with the constraint of this one,
[00:05:31.590]there also has to be in mine either here, here, or here.
[00:05:35.520]Well since, if this one was to be a mine,
[00:05:40.250]then that is out of the scope of this 2.
[00:05:42.910]So then there would still need to be a mine here or here.
[00:05:45.680]However, these two cells are both
[00:05:48.370]inside of the constraint of this cell
[00:05:52.010]and there can only be one.
[00:05:53.670]So there could not be one here and one here
[00:05:55.870]or one here and one here.
[00:05:57.710]For that reason, we know that this cell is free through 2wC.
[00:06:05.730]Next are 3wC and 4wC.
[00:06:08.550]And they are the same as 2wC except they look at
[00:06:11.560]combinations of three and four respectively.
[00:06:16.020]Backbone is the most powerful form
[00:06:18.040]of consistency propagation implemented
[00:06:21.680]and ensures the consistency by generating
[00:06:23.850]all possible solutions and then finding the cell
[00:06:26.610]that has the same value in all solutions.
[00:06:31.230]There are currently no ways to solve all instances
[00:06:34.670]of Minesweeper in efficient time, that is,
[00:06:38.250]in time polynomial regarding the size of the input
[00:06:41.340]with constraint propagation.
[00:06:43.380]However, finding one would mean that all other problems
[00:06:46.220]that are considered NP-complete
[00:06:47.980]can be solved with the same method.
[00:06:50.520]This would show that P=NP
[00:06:52.850]and would impact the possibilities
[00:06:54.540]for different computing technologies.
[00:06:57.030]Future improvements for the app itself include
[00:06:59.380]creating a more user-friendly mobile view
[00:07:01.760]and implementing a technique to use the number of mines left
[00:07:04.950]to solve cells once constraint propagation
[00:07:07.350]cannot solve any more cells on its own.
[00:07:11.020]I would like to acknowledge previous developers
[00:07:13.200]that worked on this project.
[00:07:14.670]Kenneth Bayer, Tomo Bessho, Taylor DeMint,
[00:07:17.700]Joshua Snyder, and Robert Woodward.
[00:07:20.280]I would also like to acknowledge support by UNL's UCARE
[00:07:23.770]and NSF REU supplements supporting this research.
[00:07:28.310]Finally, I would like to thank you
[00:07:29.890]for listening to my presentation.
[00:07:31.910]Have a great day.

The screen size you are trying to search captions on is too small!

You can always jump over to MediaHub and check it out there.

Comments

0 Comments

Visualization of Problem Solving with Constraint Processing: Case Study of the Minesweeper

Description

Searchable Transcript

Comments icon comment

Related Channels

Comments