Using Python + OpenCV to realize automatic mine clearance and break the world record, let’s take a look at the effect first.
Intermediate – 0.74 seconds 3BV/S=60.81
I believe that many people have known about Minesweeper, a classic game (graphics card test) game (software) for a long time. Many people have heard of Chinese Minesweeper, which is also the No. 1 Minesweeper in China and the No. 2 overall player in the world. Guo Weijia’s top name.
As a classic game that was born in the Windows 9x era, Minesweeper still has its unique charm from the past to the present: fast-paced and high-precision mouse operation requirements, quick response capabilities, and the thrill of setting records. These are all the things Minesweeper brings to The unique excitement brought by minesweeper friends is unique to Minesweeper.
1. Preparation
Before preparing to make a set of mine clearance automation software, you need to prepare the following tools/software/environment
development environment
-
Python3 environment – 3.6 or above recommended [Anaconda3 is more recommended, many of the following dependencies-libraries do not need to be installed]
-
Numpy dependent library [No need to install if you have Anaconda]
-
PIL dependent libraries [No need to install if you have Anaconda]
-
Opencv-python
-
Win32gui, win32api dependent libraries
-
IDE that supports Python [optional, if you can tolerate using a text editor to write programs]
Minesweeper software
Minesweeper Arbiter (MS-Arbiter must be used for minesweeper!)
Okay, so our preparations are all done! Let’s get started~
2. Implementation ideas
What is the most important thing before doing something? It is to build a step-by-step framework in your mind for what you are going to do. Only in this way can we ensure that the process of doing this thing is as thoughtful as possible, so that there will be a good result in the end. When we write programs, we should try our best to have a general idea in mind before officially starting development.
For this project, the general development process is as follows:
-
Complete the form content interception part
-
Complete the thunder block segmentation part
-
Complete the thunder block type identification part
-
Complete minesweeper algorithm
Okay, now that we have an idea, let’s roll up our sleeves and work hard!
01 Form interception
In fact, for this project, form interception is a logically simple but quite troublesome part to implement, and it is also an indispensable part. We obtained the following two pieces of information through Spy++:
class_name = "TMain" title_name = "Minesweeper Arbiter"
-
The main form category of ms_arbiter.exe is “TMain”
-
The main form name of ms_arbiter.exe is “Minesweeper Arbiter”
Did you notice? There is a space after the name of the main form. It was this space that troubled the author for a while. Only by adding this space can win32gui obtain the handle of the form normally.
This project uses win32gui to obtain the position information of the form. The specific code is as follows:
hwnd = win32gui.FindWindow(class_name, title_name) if hwnd: left, top, right, bottom = win32gui.GetWindowRect(hwnd)
Through the above code, we get the position of the form relative to the entire screen. After that, we need to use PIL to intercept the chessboard of the minesweeper interface.
We need to import the PIL library first
from PIL import ImageGrab
Then perform specific operations.
left + = 15 top + = 101 right -= 15 bottom -= 43 rect = (left, top, right, bottom) img = ImageGrab.grab().crop(rect)
If you are smart, you must have noticed those weird Magic Numbers at a glance. Yes, these are indeed Magic Numbers. They are the position of the entire chessboard relative to the form that we get through a little subtle adjustment.
Note: These data are only tested under Windows 10. If used under other Windows systems, the correctness of the relative position is not guaranteed, because older versions of the system may have different widths of form borders.
The orange area is what we need
The orange area is what we need. Okay, we have the image of the chessboard. The next step is to segment the images of each mine block~
02 Thunder block segmentation
Before segmenting the thunder block, we need to know the size of the thunder block and its border size in advance. According to the author’s measurement, under ms_arbiter, the size of each mine block is 16px*16px.
Knowing the size of the thunder block, we can cut each thunder block. First we need to know the number of mine blocks in both horizontal and vertical directions.
block_width, block_height = 16, 16 blocks_x = int((right - left) / block_width) blocks_y = int((bottom - top) / block_height)
After that, we create a two-dimensional array to store the image of each thunder block, segment the image, and save it in the previously created array.
def crop_block(hole_img, x, y):
x1, y1 = x * block_width, y * block_height
x2, y2 = x1 + block_width, y1 + block_height
return hole_img.crop((x1, y1, x2, y2))
blocks_img = [[0 for i in range(blocks_y)] for i in range(blocks_x)]
for y in range(blocks_y):
for x in range(blocks_x):
blocks_img[x][y] = crop_block(img, x, y)
Encapsulate the entire image acquisition and segmentation part into a library, and you can call it at any time~ In the author’s implementation, we encapsulate this part into imageProcess.py, in which the function get_frame() is used to complete the above image acquisition and segmentation process.
03 Thunder block identification
This part may be the most important part of the entire project besides the minesweeper algorithm itself. The author uses relatively simple features when conducting mine block detection, which is efficient and can meet the requirements.
def analyze_block(self, block, location):
block = imageProcess.pil_to_cv(block)
block_color = block[8, 8]
x, y = location[0], location[1]
# -1:Not opened
# -2:Opened but blank
# -3:Un initialized
#Opened
if self.equal(block_color, self.rgb_to_bgr((192, 192, 192))):
if not self.equal(block[8, 1], self.rgb_to_bgr((255, 255, 255))):
self.blocks_num[x][y] = -2
self.is_started = True
else:
self.blocks_num[x][y] = -1
elif self.equal(block_color, self.rgb_to_bgr((0, 0, 255))):
self.blocks_num[x][y] = 1
elif self.equal(block_color, self.rgb_to_bgr((0, 128, 0))):
self.blocks_num[x][y] = 2
elif self.equal(block_color, self.rgb_to_bgr((255, 0, 0))):
self.blocks_num[x][y] = 3
elif self.equal(block_color, self.rgb_to_bgr((0, 0, 128))):
self.blocks_num[x][y] = 4
elif self.equal(block_color, self.rgb_to_bgr((128, 0, 0))):
self.blocks_num[x][y] = 5
elif self.equal(block_color, self.rgb_to_bgr((0, 128, 128))):
self.blocks_num[x][y] = 6
elif self.equal(block_color, self.rgb_to_bgr((0, 0, 0))):
if self.equal(block[6, 6], self.rgb_to_bgr((255, 255, 255))):
#Ismine
self.blocks_num[x][y] = 9
elif self.equal(block[5, 8], self.rgb_to_bgr((255, 0, 0))):
# Is flag
self.blocks_num[x][y] = 0
else:
self.blocks_num[x][y] = 7
elif self.equal(block_color, self.rgb_to_bgr((128, 128, 128))):
self.blocks_num[x][y] = 8
else:
self.blocks_num[x][y] = -3
self.is_mine_form = False
if self.blocks_num[x][y] == -3 or not self.blocks_num[x][y] == -1:
self.is_new_start = False
It can be seen that we use the method of reading the center point pixel of each mine block to determine the type of mine block, and further judge the situations such as flag placement, not clicked, clicked but blank, etc.
The specific color value is obtained by the author directly taking the color, and the color of the screenshot has not been compressed, so it is enough to judge the category through the center pixel combined with other feature points, and it is highly efficient.
In this project, we used the following annotation method when implementing it:
-
1-8: represents the numbers 1 to 8
-
9: Indicates it is a mine
-
0: Indicates planting a flag
-
-1: indicates not open
-
-2: means open but blank
-
-3: Indicates that it is not any block type in the Minesweeper game
Through this simple, fast and effective method, we successfully achieved high-efficiency image recognition.
04 Minesweeper algorithm implementation
This is probably the most exciting part of this article. Here we need to first explain the specific minesweeper algorithm idea:
-
Traverse each mine block that already has a number, and determine whether the number of unopened mine blocks in the nine squares around it is the same as the number itself. If they are the same, it means that all the surrounding nine squares are mines and mark them.
-
Traverse each numbered mine block again, take all the unopened mine blocks within the nine-square grid, remove the mine blocks that have been marked as mines by the previous traversal, record and click on them.
-
If the above method cannot continue, then it means that you have encountered a dead end and choose to click randomly among all the currently unopened mine blocks. (Of course, this method is not optimal, there are better solutions, but it is relatively troublesome to implement)
The basic mine clearance process is like this, so let’s implement it ourselves~
First, we need a method that can find the positions of all blocks within the nine-square grid of a mine block. Because of the particularity of the Minesweeper game, there are no edges of the nine-square grid on the four sides of the chessboard, so we need to filter to exclude access that may exceed the boundaries.
def generate_kernel(k, k_width, k_height, block_location):
ls = []
loc_x, loc_y = block_location[0], block_location[1]
for now_y in range(k_height):
for now_x in range(k_width):
if k[now_y][now_x]:
rel_x, rel_y = now_x - 1, now_y - 1
ls.append((loc_y + rel_y, loc_x + rel_x))
return ls
kernel_width, kernel_height = 3, 3
# Kernel mode:[Row][Col]
kernel = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
#Left border
if x == 0:
for i in range(kernel_height):
kernel[i][0] = 0
#Right border
if x == self.blocks_x - 1:
for i in range(kernel_height):
kernel[i][kernel_width - 1] = 0
# Top border
ify==0:
for i in range(kernel_width):
kernel[0][i] = 0
# Bottom border
if y == self.blocks_y - 1:
for i in range(kernel_width):
kernel[kernel_height - 1][i] = 0
#Generate the search map
to_visit = generate_kernel(kernel, kernel_width, kernel_height, location)
In this part, we delete the kernel by detecting whether the current mine block is on each edge of the chessboard (in the kernel, 1 is retained, 0 is discarded), and then the final coordinates are generated through the generate_kernel function.
def count_unopen_blocks(blocks):
count = 0
for single_block in blocks:
if self.blocks_num[single_block[1]][single_block[0]] == -1:
count + = 1
return count
def mark_as_mine(blocks):
for single_block in blocks:
if self.blocks_num[single_block[1]][single_block[0]] == -1:
self.blocks_is_mine[single_block[1]][single_block[0]] = 1
unopen_blocks = count_unopen_blocks(to_visit)
if unopen_blocks == self.blocks_num[x][y]:
mark_as_mine(to_visit)
After completing the generation of the core, we have an “address book” of mine blocks that need to be detected: to_visit. After that, we use the count_unopen_blocks function to count the number of unopened blocks in the surrounding nine-square grid, and compare it with the number of current mine blocks. If they are equal, all the mine blocks in the nine-square grid will be marked as mines through the mark_as_mine function.
def mark_to_click_block(blocks):
for single_block in blocks:
#NotMine
if not self.blocks_is_mine[single_block[1]][single_block[0]] == 1:
#Click-able
if self.blocks_num[single_block[1]][single_block[0]] == -1:
# Source Syntax: [y][x] - Converted
if not (single_block[1], single_block[0]) in self.next_steps:
self.next_steps.append((single_block[1], single_block[0]))
def count_mines(blocks):
count = 0
for single_block in blocks:
if self.blocks_is_mine[single_block[1]][single_block[0]] == 1:
count + = 1
return count
mines_count = count_mines(to_visit)
if mines_count == block:
mark_to_click_block(to_visit)
We also implemented the second step in the mine clearance process using a method similar to the first step. First use the same method as the first step to generate the core of the mine block that needs to be accessed, and then generate the specific mine block location. Use the count_mines function to obtain the number of all mine blocks within the nine-square grid, and determine all the mine blocks in the current nine-square grid. has been detected.
If so, use the mark_to_click_block function to exclude the mine blocks that have been marked as mines in the nine-square grid, and add the remaining safe mine blocks to the next_steps array.
# Analyze the number of blocks
self.iterate_blocks_image(BoomMine.analyze_block)
#Mark all mines
self.iterate_blocks_number(BoomMine.detect_mine)
# Calculate where to click
self.iterate_blocks_number(BoomMine.detect_to_click_block)
if self.is_in_form(mouseOperation.get_mouse_point()):
for to_click in self.next_steps:
on_screen_location = self.rel_loc_to_real(to_click)
mouseOperation.mouse_move(on_screen_location[0], on_screen_location[1])
mouseOperation.mouse_click()
In the final implementation, the author encapsulated several processes into functions, and all mine blocks can be processed using the passed function through the iterate_blocks_number method, which is somewhat similar to the role of Filter in Python.
Interested friends will receive a complete set of Python learning materials, including interview questions, resume information, etc. See below for details.
1. Python learning routes in all directions
The technical points in all directions of Python have been compiled to form a summary of knowledge points in various fields. Its usefulness is that you can find corresponding learning resources according to the following knowledge points to ensure that you learn more comprehensively.
2. Python essential development tools
The tools have been organized for you, and you can get started directly after installation! 
3. Latest Python study notes
When I learn a certain basic and have my own understanding ability, I will read some books or handwritten notes compiled by my seniors. These notes record their understanding of some technical points in detail. These understandings are relatively unique and can be learned. to a different way of thinking.
4. Python video collection
Watch a comprehensive zero-based learning video. Watching videos is the fastest and most effective way to learn. It is easy to get started by following the teacher’s ideas in the video, from basic to in-depth.
5. Practical cases
What you learn on paper is ultimately shallow. You must learn to type along with the video and practice it in order to apply what you have learned into practice. At this time, you can learn from some practical cases.
6. Interview Guide
Resume template
If there is any infringement, please contact us for deletion