Table of content
(► Examiners comments)
‘’Minesweeper’’, the common household computer game installed in many Microsoft PC’s today. The game itself is on-par with Sudoku for being one of the world's most time-consuming mathematical puzzle game. As simple as the game may be,mathematical of the world toil over this game, hopes of looking strategies,theorems and perhaps solutions that lead to solving problems of mathematical applications. The ones who call themselves "experts" of this game truly possess great deduction, analytical and logical skills that can be applied to today’s mathematics.
(►A. Introduction but no aim or rationale.)
Overview
The original minesweeper computer game whose objective is to "clear a minefield without detonating a mine". There are many strategies involved in this common household game.
When the game is started, the player has presented a grid of squares. The size of the grid varies from the difficulty level chosen by the player. The larger the grid the higher the difficulty level and skills required. The number of mines also varies from difficulty level; usually at the beginner level, there are 10 mines in a 9x9 grid. The game progresses by the player’s clicks on a square. The square clicked will either be a mine or reveal a square with a digit. If the square revealed turns out to be a mine, the game is over. The game progresses as the player clicks on squares without mines and reveals digits with the highest digit being 8. The digit indicates the number of adjacent squares that contain mines. Using this information, players can deduce the certainties of other squares on whether they are mine-filled or free and continue on with the game by either flagging a square or proceed to clear other squares. For example, if you left-clicked a square, and an 8 digit appeared, then you would know that the square is surrounded by 8 mines, all 8 of its adjacent squares. You would then have to go elsewhere to test for non-mine squares. The player is declared the winner when either all mine are flagged or you cleared all the squares that do not contain mines.
The game can be played for two basic purposes; play for speed or play to just win. To play for speed simply try to clear the minefield as fast as you can without detonating a mine and to play to win; simply clear the minefield. Each contradicts each other as focusing for speed decreases your chances of winning and focusing on just winning decreases your speed.
(►D. Some reflection but very simplistic.)
Controls
For a player to clear a mine simply left-click a square.
Players can then ''flag'' a square by right-clicking on a square they believe to inhabit a mine thus eliminating it.
Right-clicking again on the flag symbol of a square will change the flag into a question mark graphic to indicate the possibility of the square may or may not be a mine.
Right-clicking once more on a question mark graphic transforms the square back to its original form.
The player can press down both left and right clicks at the same time on a square to show the square’s adjacent squares.
(►A. Lack of coherency through limited explaination.)
The key to minesweeper is the logical deduction from the digits of the squares. Simple logical strategies cases such as if there is a 3 in a corner, all the squares adjacent to is100% mines. Another example would be if an uncovered square is with a digit 1, and there is only one covered square touching it, that square must be a mine. In general, clearing a board with speed requires a form of pattern recognition and the brain to quickly identify as well as make connections in identifying the clues which state that there’s a 100% probability in a square being a mine.
(►B,E. No mathematical strategy outlined. Missed opportuinity for presentation using mathematical language.)
The first few moves of minesweeper without a doubt require luck. The player can only give wild guesses because of the fact the player has either no digits or anything to refer to. The chance of a player clicking on a mine on the first move is 0% as the mines generate randomly after your first click. On your second click, however, on a beginner’s difficulty would be around 12% and 38% on expert difficulty. (►A. No explaination of why these values were used.) Because the placement of the mines in every game is random, the choice of your starting move can’t be based on anything but luck. Even if you start in the corner, you may either be lucky enough to get a 3 or be unlucky and get a 1 which really doesn’t help a whole lot for your first move. Experts do however recommend beginning the middle area of the grid opposed to the corners.
It is only after the first few moves of minesweeper is complete when the player can truly deduct and rely on the logic of where the mines are for the rest of the game.
Minesweeper also have the factor of sheer luck in cases where the player has no choice but to take a guess in clearing a square as the digits of the squares show all the surrounding squares each having the same probability of possessing a mine.
(►C. Opportuinity for an example here.)
There are times when a grid generated can only be solved with the element of guessing.
Refer to Figure 3.
The player must guess whether a or b is the mine. The probability of A and B being mines are equal, 50/50. (►B. Incorrect terminology used.)
Another scenario that requires guessing is when an un-clicked square is completely or partially surrounded by mines. The player has no numbers touching the un-clicked square thus the player has again no information about the probability of whether or not the square will be a mine.
Strategies when facing this scenario that will allow the player to avoid simple guesses are to play the rest of the game and ignore the square. In the game when the number of un-clicked and un-flagged squares equals the number of mines left unmarked then all the remaining spaces are mines. Some versions of the game automatically flag these spaces once all the other squares in the game have been clicked as well as reveal them once all the flags have been placed.
(►C,D. An appropriate logical implication.)
Single Square Strategies
If the number of un-clicked squares adjacent to the number of the square equal to the number on that square, all the un-clicked squares are definitely all mines.
For any square with a digit, if the digit of mines you've found adjacent to that square is equal to the number of the square, all other squares adjacent to that numbered square must be safe. If you know the square to the right of a 1 is a mine, then you can deduce that all the other squares next to that 1 do not contain mines and you can clear them to obtain more digits to progress in the game.
(►B,E. Student work is descriptive rather than mathematical.)
(►C. Use of personal examples.)
Multiple square strategies are great for players who want to win in beginner difficulties quickly, and a must in the higher difficulties. For these complex puzzles, the the player would need to consider more than one square a time.
(►A. Lack of coherency.)
If you have two adjacent numbers, the difference between those numbers is equal to the difference in the number of mines for the 3 squares adjacent to each that are not adjacent to the other number. For example: if these numbers differ by 3, all of the adjacent squares to the higher number not shared by the other are mines and all the opposite ones are safe.
(►C. Opportuinity for example.)
Sometimes it can be known that there are a certain number of mines in a certain number of squares (without necessarily knowing which the mines are and which are safe) and you can often utilize this information to find out information about other squares.
A method used by Minesweeper Computers of artificial intelligence is to label the game as Constraint Satisfaction Problem; ‘’mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations’’
One would recognize the variables in the game are the unopened squares and the constraints are the adjacent squares that are opened.
The algorithm consists of trying every combination of mines that satisfies all the numbers in the adjacent squares, and making a conclusion from there.
In expert difficulty, this would be a time-consuming process for even the most powerful computer, but minesweeper players who are experienced at the expert level would be able to quickly see which squares need this procedure, and where one might expect it to succeed.
Analysis
According to Robert Kaye, Minesweeper is an NP-Complete Problem.
A problem is said to be NP-Complete if all other problems in NP can be solved easily using a solution to this problem. The main method for proving that a problem is NP-Complete is a reduction. By converting one problem into another one like finding a solution to the latter problem will let you solve the former, in other words ‘’breaking it down’’ or using "logical sense.". If one problem we call A is reducible to problem B, then solving B is just as difficult as solving for A as the solution for B gives the solution to A. If we reduce an NP-Complete problem to a new problem then we know that the new problem is NP-Complete as well.
(►C. Unfamiliar mathematics, but not explained well enough to justify understanding and not used.)
A computer powerful enough to win a minesweeper game would earn the title of one of the most powerful computers and best achievements of mankind.
The result of the powerful artificial intelligence is a solution that could enhance security measures on the web and data files in general.
(►C. General and dramatic statement without any support or evidence.)
It's surprising that such a simple game would put us at such a frontier of mathematics. But the big questions in math are not very far below the surface of everyday life.
(►E. Lack of mathematics actually presented.)
One of the outstanding problems in logic and computer science is determining whether questions exist whose answer can be quickly checked by artificial intelligence, however, it requires a much longer time to solve without knowing the answer. So far no one has proved that any of them really does require a long time to solve.
(►A. Lack of coherency)
Again, referring to Robert Kaye, Minesweeper is an NP-complete problem. The definition of an NP-complete problem is that all other NP problems can be reduced to using polynomial-time many one eductions. The problem attempts to determine whether questions that seem to be unsolvable within a reasonable period of time might actually have a relatively simple way of being solved, possibly by computer. Thusly algorithm that can solve minesweeper is speculated to be able to solve any and all NP problems.
(►D. Limited reflection.)
‘’If there was a way of playing Minesweeper efficiently, then there would also be away of cracking codes efficiently,’’ Kaye said.
If someone were to come up with an algorithm for successfully beating Minesweeper, that algorithm would also be instrumental in vastly improving encryption and code-cracking.
Through development in ‘’Minesweeping strategies’’, as represented by Mathematicians Patti Frazer Lock of St. Lawrence University in Canton, N.Y., and Allan A. Struthers of Michigan Technological University in Houghton, the game can be used to introduce students to formal mathematical proofs.
In the school’s courses, students play a few games and attempt to deduct and evaluate the various positions the squares that definitely possess mines and the squares definitely are safe. The exercise is proven to give students a sense of giving the rules, the evidence and conjecture, then prove or test. Students who become "masters" of this game learn truly useful reasoning, logic and deductive techniques such as proof by contradiction or the role of the counter, all of which can be applied to high levels of mathematics such as proving theorems.
(►A. Implicit aim here but incorrectly placed.)
"Putting a flag on a square is a theorem--you know there's a bomb there," Struthers explains.
It is indeed interesting how gaming can contribute “practical” things to people's lives and how this simple game such as minesweeper might just be the thing that can solve today’s mathematical mystery. It truly is no surprise, with the number of logical deductions, time and brainpower required to play this game.
(►D. Superficial reflection.)