基于概率分析的智能AI扫雷程序秒破雷界世界纪录

Biegral 2022/5/29 21:53:15 67020

大家好，我是小小明，上次的我带大家玩了数独：

今天我将带你用非常高端的姿势玩扫雷。本文涉及的技术点非常多，非常硬核，万字长文，高能预警。

本文从图像识别到windows消息处理，最终到直接的内存修改。中间写了一套基于概率分析的扫雷AI算法，模拟雷界的高阶玩家的操作，轻松拿下高级的世界纪录。

据说扫雷的世界记录是：

image-20210808001553811

对于中级我玩的大概就是这情况，直接超过世界纪录的7秒：

录制_2021_08_08_00_20_44_891

对于高级也轻松超过世界纪录：

录制_2021_08_08_22_42_56_24

初级世界记录居然是0.49秒，虽然有点难，但我们还是可以超越（0.4秒和0.37秒）：

录制_2021_08_09_18_38_11_832

录制_2021_08_09_19_01_27_219

文章目录

扫雷游戏的介绍

简介

《扫雷》是一款大众类的益智小游戏，游戏的基本操作包括左键单击（Left Click）、右键单击（Right Click）、双击（Chording）三种。其中左键用于打开安全的格子；右键用于标记地雷；双击在一个数字周围的地雷标记完时，相当于对数字周围未打开的方块均进行一次左键单击操作。

基本游戏步骤：开局后，首先要用鼠标在灰色区域点一下，会出现一些数字，1代表在这个数字周围有1个地雷，2表示在它周围有2个雷，3表示在它周围有3个雷；在确信是雷的地方，点一下右键，用右键标识出该出的地雷；确信不是雷的地方，按一下鼠标左键，打开相应的数字。

扫雷程序下载

OD和win98扫雷下载

链接：http://pan.baidu.com/s/1gfA10K7 密码：eiqp

Arbiter版扫雷下载

http://saolei.wang/BBS/

image-20210807203150231

基于图像分析的桌面前端交互程序

获取扫雷程序的窗口位置

这步需要调用windows API查找扫雷游戏的窗口，需要传入扫雷游戏得标题和类名，这个可以通过inspect.exe工具进行获取。

inspect.exe工具是系统自带工具，我通过everything获取到路径为：

C:\Program Files (x86)\Windows Kits\8.1\bin\x64\inspect.exe

image-20210807204248838

打开扫雷游戏后，就可以通过以下代码获取扫雷游戏的窗口对象：

import win32gui

# 扫雷游戏窗口
# class_name, title_name = "TMain", "Minesweeper Arbiter "
class_name, title_name = "扫雷", "扫雷"
hwnd = win32gui.FindWindow(class_name, title_name)

if hwnd:
    left, top, right, bottom = win32gui.GetWindowRect(hwnd)
    print(f"窗口坐标，左上角：({left},{top}),右下角：({right},{bottom})")
    w, h = right-left, bottom-top
    print(f"窗口宽度：{w}，高度：{h}")
else:
    print("未找到窗口")

窗口坐标，左上角：(86,86),右下角：(592,454)
窗口宽度：506，高度：368

可以通过代码激活并前置窗口：

https://docs.microsoft.com/zh-cn/windows/win32/api/winuser/nf-winuser-setforegroundwindow

不过有时SetForegroundWindow调用有一些限制导致失败，我们可以再调用之前输入一个键盘事件：

import win32com.client as win32


def activateWindow(hwnd):
    # SetForegroundWindow调用有一些限制，我们可以再调用之前输入一个键盘事件
    shell = win32.Dispatch("WScript.Shell")
    shell.SendKeys('%')
    win32gui.SetForegroundWindow(hwnd)
    
activateWindow(hwnd)

根据窗口坐标抓取雷区图像

前面我们获取到了扫雷程序的窗口坐标，下面我就可以获取雷区的图像：

from PIL import ImageGrab

# 根据窗口坐标抓取雷区图像
rect = (left+15, top+101, right-11, bottom-11)
img = ImageGrab.grab().crop(rect)
print(img.size)
img

image-20210807205708705

注意：15，101等偏移量是我对98版扫雷反复测试得到的坐标，若你使用扫雷网下载的Arbiter可能坐标会发生变化。

基于雷区图像可以计算出雷盘大小：

# 每个方块16*16
bw, bh = 16, 16


def get_board_size():
    # 横向有w个方块
    l, t, r, b = (left+15, top+101, right-11, bottom-11)
    w = (r - l) // bw
    # 纵向有h个方块
    h = (b - t) // bh
    return (w, h), (l, t, r, b)


# 获取雷盘大小和位置
(w, h), rect = get_board_size()
print(f"宽：{w},高：{h}，雷盘位置：{rect}")

宽：30,高：16，雷盘位置：(1425, 108, 1905, 364)

读取剩余地雷数量

先截图显示地雷数量的图片：

num_img = ImageGrab.grab().crop((left+20, top+62, left+20+39, top+62+23))
num_img

image-20210807210432831

然后拆分出每个数字图像并灰度处理：

for i in range(3):
    num_i = num_img.crop((13*i+1, 1, 13*(i+1)-1, 22)).convert("L")
    print(num_i.size)
    display(num_i)

image-20210807210712152

把雷数设置成8后重新运行上面的代码，在执行以下代码，则可以看到各个像素点的演示值：

pixels = num_i.load()
print("yx", end=":")
for x in range(11):
    print(str(x).zfill(2), end=",")
print()
for y in range(21):
    print(str(y).zfill(2), end=":")
    for x in range(11):
        print(str(pixels[x, y]).zfill(2), end=",")
    print()

yx:00,01,02,03,04,05,06,07,08,09,10,
00:00,76,76,76,76,76,76,76,76,76,00,
01:76,00,76,76,76,76,76,76,76,00,76,
02:76,76,00,76,76,76,76,76,00,76,76,
03:76,76,76,00,00,00,00,00,76,76,76,
04:76,76,76,00,00,00,00,00,76,76,76,
05:76,76,76,00,00,00,00,00,76,76,76,
06:76,76,76,00,00,00,00,00,76,76,76,
07:76,76,76,00,00,00,00,00,76,76,76,
08:76,76,00,00,00,00,00,00,00,76,76,
09:76,00,76,76,76,76,76,76,76,00,76,
10:00,76,76,76,76,76,76,76,76,76,00,
11:76,00,76,76,76,76,76,76,76,00,76,
12:76,76,00,00,00,00,00,00,00,76,76,
13:76,76,76,00,00,00,00,00,76,76,76,
14:76,76,76,00,00,00,00,00,76,76,76,
15:76,76,76,00,00,00,00,00,76,76,76,
16:76,76,76,00,00,00,00,00,76,76,76,
17:76,76,76,00,00,00,00,00,76,76,76,
18:76,76,00,76,76,76,76,76,00,76,76,
19:76,00,76,76,76,76,76,76,76,00,76,
20:00,76,76,76,76,76,76,76,76,76,00,

于是可以很清楚知道，每个数字都由7个小块组成，我们可以对这7块每块任取一个像素点获取颜色值。将这7块的颜色值是否等于76来表示一个二进制，最终转成一个整数：

def get_pixel_code(pixels):
    key_points = np.array([
        pixels[5, 1], pixels[1, 5], pixels[9, 5],
        pixels[9, 5], pixels[5, 10],
        pixels[1, 15], pixels[9, 15], pixels[5, 19]
    ]) == 76
    code = int("".join(key_points.astype("int8").astype("str")), 2)
    return code

经过逐个测试，最终得到每个数字对应的特征码，最终封装成如下方法：

code2num = {
    247: 0, 50: 1, 189: 2,
    187: 3, 122: 4, 203: 5,
    207: 6, 178: 7, 255: 8, 251: 9
}

def get_mine_num(full_img=None):
    full_img = ImageGrab.grab()
    num_img = full_img.crop((left+20, top+62, left+20+39, top+62+23))
    mine_num = 0
    for i in range(3):
        num_i = num_img.crop((13*i+1, 1, 13*(i+1)-1, 22)).convert("L")
        code = get_pixel_code(num_i.load())
        mine_num = mine_num*10+code2num[code]
    return mine_num

get_mine_num()

经测试可以准确读取，左上角雷区的数量。

读取雷区数据

通过以下代码可以拆分出雷区每个格子的图像：

img = ImageGrab.grab().crop(rect)
for y in range(h):
    for x in range(w):
        img_block = img.crop((x * bw, y * bh, (x + 1) * bw, (y + 1) * bh))

可以获取每个格子的灰度图片的颜色列表：

colors = img_block.convert("L").getcolors()
colors

[(54, 128), (148, 192), (54, 255)]

结果表示了(出现次数，颜色值)组成的列表。

为了方便匹配，将其转换为16进制并文本拼接：

def colors2signature(colors):
    return "".join(hex(b)[2:].zfill(2) for c in colors for b in c)

然后就可以得到整个雷区的每个单元格组成的特征码的分布：

from collections import Counter

counter = Counter()
img = ImageGrab.grab().crop(rect)
for y in range(h):
    for x in range(w):
        img_block = img.crop((x * bw, y * bh, (x + 1) * bw, (y + 1) * bh))
        colors = img_block.convert("L").getcolors()
        signature = colors2signature(colors)
        counter[signature] += 1
counter.most_common(20)

[('368094c036ff', 388),
 ('4d001f8090c004ff', 87),
 ('281d1f80b9c0', 2),
 ('414b1f80a0c0', 1),
 ('3e4c1f80a3c0', 1),
 ('4d00904c1f8004ff', 1)]

经过反复测试终于得到各种情况的特征码：

rgb_unknown = '368094c036ff'
rgb_1 = '281d1f80b9c0'
rgb_2 = '414b1f80a0c0'
rgb_3 = '3e4c1f80a3c0'
rgb_4 = '380f1f80a9c0'
rgb_5 = '46261f809bc0'
rgb_6 = '485a1f8099c0'
rgb_7 = '2c001f80b5c0'
rgb_8 = '6b8095c0'
rgb_nothing = '1f80e1c0'
rgb_red = '1600114c36806dc036ff'
rgb_boom = '4d001f8090c004ff'
rgb_boom_red = '4d00904c1f8004ff'
rgb_boom_error = '34002e4c1f807ec001ff'
# 数字1-8表示周围有几个雷
#  0 表示已经点开是空白的格子
# -1 表示还没有点开的格子
# -2 表示红旗所在格子
# -3 表示踩到雷了已经失败
img_match = {rgb_1: 1, rgb_2: 2, rgb_3: 3, rgb_4: 4,
             rgb_5: 5, rgb_6: 6, rgb_7: 7, rgb_8: 8, rgb_nothing: 0,
             rgb_unknown: -1, rgb_red: -2, rgb_boom: -3, rgb_boom_red: -3, rgb_boom_error: -3}

尝试匹配雷区数据：

import numpy as np
board = np.zeros((h, w), dtype="int8")
board.fill(-1)
for y in range(h):
    for x in range(w):
        img_block = img.crop((x * bw, y * bh, (x + 1) * bw, (y + 1) * bh))
        colors = img_block.convert("L").getcolors()
        signature = colors2signature(colors)
        board[y, x] = img_match[signature]
print(board)

image-20210807220843540

image-20210807221133191

可以看到雷区的数据都能正确匹配并获取。

自动操作扫雷程序

下面我们封装一个控制鼠标点击的方法：

import win32api
import win32con


def click(x, y, is_left_click=True):
    if is_left_click:
        win32api.SetCursorPos((x, y))
        win32api.mouse_event(
            win32con.MOUSEEVENTF_LEFTDOWN, 0, 0, 0, 0)
        win32api.mouse_event(
            win32con.MOUSEEVENTF_LEFTUP, 0, 0, 0, 0)
    else:
        win32api.SetCursorPos((x, y))
        win32api.mouse_event(
            win32con.MOUSEEVENTF_RIGHTDOWN, 0, 0, 0, 0)
        win32api.mouse_event(
            win32con.MOUSEEVENTF_RIGHTUP, 0, 0, 0, 0)


(w, h), (l, t, r, b) = get_board_size()


def click_mine_area(px, py, is_left_click=True):
    x, y = l+px*bw + bw // 2, t+py*bh + + bh // 2
    click(x, y, is_left_click)

调用示例：

import time
import win32con

activateWindow(hwnd)
time.sleep(0.2)
click_mine_area(3, 3)

注意：第一次操作程序，需要点击激活窗口，激活需要等待几毫秒生效后开始操作。

更快的操作方法：

可以直接发生windows消息，来模拟鼠标操作，这样组件直接在底层消息级别接收到鼠标点击的事件，缺点是看不到鼠标的移动。封装一下：

def message_click(x, y, is_left_click=True):
    if is_left_click:
        win32api.SendMessage(hwnd,
                             win32con.WM_LBUTTONDOWN,
                             win32con.MK_LBUTTON,
                             win32api.MAKELONG(x, y))
        win32api.SendMessage(hwnd,
                             win32con.WM_LBUTTONUP,
                             win32con.MK_LBUTTON,
                             win32api.MAKELONG(x, y))
    else:
        win32api.SendMessage(hwnd,
                             win32con.WM_RBUTTONDOWN,
                             win32con.MK_RBUTTON,
                             win32api.MAKELONG(x, y))
        win32api.SendMessage(hwnd,
                             win32con.WM_RBUTTONUP,
                             win32con.MK_RBUTTON,
                             win32api.MAKELONG(x, y))

# 雷区格子在窗体上的起始坐标
offest_x, offest_y = 0xC, 0x37
# 每个格子方块的宽度和高度 16*16
bw, bh = 16, 16

def message_click_mine_area(px, py, is_left_click=True):
    x, y = offest_x+px*bw + bw // 2, offest_y+py*bh + + bh // 2
    message_click(x, y, is_left_click)

调用示例：

message_click_mine_area(3, 4, False)

注意：windows消息级的鼠标操作不需要激活窗口就可以直接操作。

前端交互程序整体封装

import win32api
import win32con
import numpy as np
import win32com.client as win32
from PIL import ImageGrab
import win32gui


# 每个方块16*16
bw, bh = 16, 16
# 剩余雷数图像特征码
code2num = {
    247: 0, 50: 1, 189: 2,
    187: 3, 122: 4, 203: 5,
    207: 6, 178: 7, 255: 8, 251: 9
}
# 雷区图像特征码
rgb_unknown = '368094c036ff'
rgb_1 = '281d1f80b9c0'
rgb_2 = '414b1f80a0c0'
rgb_3 = '3e4c1f80a3c0'
rgb_4 = '380f1f80a9c0'
rgb_5 = '46261f809bc0'
rgb_6 = '485a1f8099c0'
rgb_7 = '2c001f80b5c0'
rgb_8 = '6b8095c0'
rgb_nothing = '1f80e1c0'
rgb_red = '1600114c36806dc036ff'
rgb_boom = '4d001f8090c004ff'
rgb_boom_red = '4d00904c1f8004ff'
rgb_boom_error = '34002e4c1f807ec001ff'
rgb_question = '180036807cc036ff'
# 数字1-8表示周围有几个雷
#  0 表示已经点开是空白的格子
# -1 表示还没有点开的格子
# -2 表示红旗所在格子
# -3 表示踩到雷了已经失败
# -4 表示被玩家自己标记为问号
img_match = {rgb_1: 1, rgb_2: 2, rgb_3: 3, rgb_4: 4,
             rgb_5: 5, rgb_6: 6, rgb_7: 7, rgb_8: 8, rgb_nothing: 0,
             rgb_unknown: -1, rgb_red: -2, rgb_boom: -3, rgb_boom_red: -3,
             rgb_boom_error: -3, rgb_question: -4}
# 雷区格子在窗体上的起始坐标
offest_x, offest_y = 0xC, 0x37


def get_board_size(hwnd):
    left, top, right, bottom = win32gui.GetWindowRect(hwnd)
    # 横向有w个方块
    l, t, r, b = (left+15, top+101, right-11, bottom-11)
    w = (r - l) // bw
    # 纵向有h个方块
    h = (b - t) // bh
    return (w, h), (l, t, r, b)


def get_pixel_code(pixels):
    key_points = np.array([
        pixels[5, 1], pixels[1, 5], pixels[9, 5],
        pixels[9, 5], pixels[5, 10],
        pixels[1, 15], pixels[9, 15], pixels[5, 19]
    ]) == 76
    code = int("".join(key_points.astype("int8").astype("str")), 2)
    return code


def get_mine_num(hwnd, full_img=None):
    if full_img is None:
        full_img = ImageGrab.grab()
    left, top, right, bottom = win32gui.GetWindowRect(hwnd)
    num_img = full_img.crop((left+20, top+62, left+20+39, top+62+23))
    mine_num = 0
    for i in range(3):
        num_i = num_img.crop((13*i+1, 1, 13*(i+1)-1, 22)).convert("L")
        code = get_pixel_code(num_i.load())
        mine_num = mine_num*10+code2num[code]
    return mine_num


def colors2signature(colors):
    return "".join(hex(b)[2:].zfill(2) for c in colors for b in c)


def update_board(board, full_img=None):
    if full_img is None:
        full_img = ImageGrab.grab()
    left, top, right, bottom = win32gui.GetWindowRect(hwnd)
    rect = (left+15, top+101, right-11, bottom-11)
    img = full_img.crop(rect)
    for y in range(h):
        for x in range(w):
            img_block = img.crop((x * bw, y * bh, (x + 1) * bw, (y + 1) * bh))
            colors = img_block.convert("L").getcolors()
            signature = colors2signature(colors)
            board[y, x] = img_match[signature]
    return board


def get_hwnd(name="扫雷"):
    if name == "扫雷":
        class_name, title_name = "扫雷", "扫雷"
    else:
        class_name, title_name = "TMain", "Minesweeper Arbiter "
    return win32gui.FindWindow(class_name, title_name)


def activateWindow(hwnd):
    # SetForegroundWindow调用有一些限制，我们可以再调用之前输入一个键盘事件
    shell = win32.Dispatch("WScript.Shell")
    shell.SendKeys('%')
    win32gui.SetForegroundWindow(hwnd)


def new_board(w, h):
    board = np.zeros((h, w), dtype="int8")
    board.fill(-1)
    return board


def click(x, y, is_left_click=True):
    if is_left_click:
        win32api.SetCursorPos((x, y))
        win32api.mouse_event(
            win32con.MOUSEEVENTF_LEFTDOWN, 0, 0, 0, 0)
        win32api.mouse_event(
            win32con.MOUSEEVENTF_LEFTUP, 0, 0, 0, 0)
    else:
        win32api.SetCursorPos((x, y))
        win32api.mouse_event(
            win32con.MOUSEEVENTF_RIGHTDOWN, 0, 0, 0, 0)
        win32api.mouse_event(
            win32con.MOUSEEVENTF_RIGHTUP, 0, 0, 0, 0)


def click_mine_area(px, py, is_left_click=True):
    x, y = l+px*bw + bw // 2, t+py*bh + + bh // 2
    click(x, y, is_left_click)


def message_click(x, y, is_left_click=True):
    if is_left_click:
        win32api.SendMessage(hwnd,
                             win32con.WM_LBUTTONDOWN,
                             win32con.MK_LBUTTON,
                             win32api.MAKELONG(x, y))
        win32api.SendMessage(hwnd,
                             win32con.WM_LBUTTONUP,
                             win32con.MK_LBUTTON,
                             win32api.MAKELONG(x, y))
    else:
        win32api.SendMessage(hwnd,
                             win32con.WM_RBUTTONDOWN,
                             win32con.MK_RBUTTON,
                             win32api.MAKELONG(x, y))
        win32api.SendMessage(hwnd,
                             win32con.WM_RBUTTONUP,
                             win32con.MK_RBUTTON,
                             win32api.MAKELONG(x, y))


def message_click_mine_area(px, py, is_left_click=True):
    x, y = offest_x+px*bw + bw // 2, offest_y+py*bh + + bh // 2
    message_click(x, y, is_left_click)


hwnd = get_hwnd()
activateWindow(hwnd)
# 获取雷盘大小和位置
(w, h), rect = get_board_size(hwnd)
print(f"宽：{w},高：{h}，雷盘位置：{rect}")
mine_num = get_mine_num(hwnd)
print("剩余雷数：", mine_num)
board = new_board(w, h)
# message_click_mine_area(5, 5)
update_board(board)
print(board)

新开中级后，测试一下：

hwnd = get_hwnd()
activateWindow(hwnd)
# 获取雷盘大小和位置
(w, h), rect = get_board_size(hwnd)
print(f"宽：{w},高：{h}，雷盘位置：{rect}")
mine_num = get_mine_num(hwnd)
print("剩余雷数：", mine_num)
board = new_board(w, h)
message_click_mine_area(5, 5)
update_board(board)
print(board)

宽：16,高：16，雷盘位置：(230, 240, 486, 496)
剩余雷数： 40
[[-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1  1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]
 [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]]

自动扫雷算法

Monkey随机算法玩中级扫雷

在完成了前面的前端交互程序后，我们就可以开始开发自动扫雷的算法逻辑了。首先用一个最基础的规则玩中级。

基础规则：

  • 如果当前点周围雷数=未点+插旗，说明所有未点位置都是雷，可以全部插旗
  • 如果当前点周围雷数=插旗，说明所有未点位置都没有雷，可以全部点开
  • 遍历完所有位置后，未发现能够点开或标记为雷的点，则随机选一个点
from itertools import product
import time
import random
from collections import Counter


def get_bound(x, y):
    "获取指定坐标周围4*4-9*9的边界范围"
    x1, x2 = np.array((x-1, x+2)).clip(0, w)
    y1, y2 = np.array((y-1, y+2)).clip(0, h)
    return x1, y1, x2, y2


def getItemNum(x, y):
    "获取指定坐标点周围已经点开、没有点开和已确定有雷的格子的数量"
    #  0 表示已经点开是空白的格子
    # -1 表示还没有点开的格子
    # -2 表示红旗所在格子
    x1, y1, x2, y2 = get_bound(x, y)
    count = Counter(board[y1:y2, x1:x2].reshape(-1))
    return count[0], count[-1], count[-2]


def getUnknownPointList(x, y):
    "获取指定坐标点周围还没有点开的格子坐标列表"
    x1, y1, x2, y2 = get_bound(x, y)
    for py in range(y1, y2):
        for px in range(x1, x2):
            if px == x and py == y:
                continue
            if board[py, px] == -1:
                yield px, py


hwnd = get_hwnd()
activateWindow(hwnd)
# 获取雷盘大小和位置
(w, h), rect = get_board_size(hwnd)
print(f"宽：{w},高：{h}，雷盘位置：{rect}")
mine_num = get_mine_num(hwnd)
print("剩余雷数：", mine_num)
board = new_board(w, h)
update_board(board)
# 点击剩余雷数位置激活窗口
l, t, r, b = rect
click(l+16, t-30)
time.sleep(0.1)
# 标记周围已经完全确定的数字位置
flag = np.zeros_like(board, dtype="bool")
while True:
    # 筛选出所有未确定的数字位置   坐标
    pys, pxs = np.where((1 <= board) & (board <= 8) & (~flag))
    res = set()
    for x, y in zip(pxs, pys):
        boom_number = board[y, x]
        # 统计当前点周围4*4-9*9范围各类点的数量
        openNum, unknownNum, redNum = getItemNum(x, y)
        if unknownNum == 0:
            # 周围没有未点过的点可以直接忽略
            flag[y, x] = True
            continue
        # 获取周围的点的位置
        points = getUnknownPointList(x, y)
        if boom_number == unknownNum+redNum:
            # 如果当前点周围雷数=未点+插旗，说明所有未点位置都是雷，可以全部插旗
            flag[y, x] = True
            for px, py in points:
                res.add((px, py, False))
        elif boom_number == redNum:
            # 如果当前点周围雷数=插旗，说明所有未点位置都没有雷，可以全部点开
            flag[y, x] = True
            for px, py in points:
                res.add((px, py, True))
    for px, py, left in res:
        click_mine_area(px, py, left)

    if len(res) == 0 and (board == -1).sum() != 0:
        # 本轮循环没有进行任何操作，说明没有任何可以确定点击的地方，只能随机点击
        py, px = random.choice(list(zip(*np.where(board == -1))))
        click_mine_area(px, py)
    if (board == -1).sum() == 0:
        print("顺利！！！")
        break
    if (board == -3).sum() != 0:
        print("踩到雷了，游戏结束！")
        break
    update_board(board)

然后就可以体验一把中级了：

录制_2021_08_08_00_10_30_147

不过据说中级世界纪录仅7秒：

啧啧，程序会比人玩的还慢？那我缩小一下延迟，再玩一下：

录制_2021_08_08_00_20_44_891

不过咱们要是用这种取随机的方法来玩高级，胜率简直会惨不忍睹：

录制_2021_08_08_00_25_17_67

基于概率分析的扫雷算法

前面的基本规则在高级下，胜率过于低下，下面我们完善我们的扫描算法。

熟悉扫雷的高玩们都非常清楚扫雷的减法公式，21定式和变形等。不过对于程序而言不见得一定要记录这些固定规则，经过实测基于概率模型已经能够包含所有的定式结果。

算法的总体思想

对于一个雷区，是否有雷会存在多个互相制约的联通块区域，不同联通块之间不存在互相制约。例如下面的雷区存在两个联通块区域：

image-20210808205114187

对于每一个连通块共有n个格子没有打开，每个格子都存在有雷和没有雷两种情况，那么至多存在 2 n \large 2^n 2n种可能的解，除与已知格子矛盾的解后一共有m种可能的解。我们统计出每一个格子在多少种解中是有雷的，除以m就得到这一格是雷的概率。显然当概率百分比等于0时，一定不是雷；当概率百分比等于100时，一定是雷。

如果没有概率等于0或100的格子，则需要根据概率取有雷概率最低的格子，多个格子概率最低时取周围未点开格子数最多的格子。

搜索连通区域

首先第一步，我们需要找出这些连通区域的坐标：

def getOpenNum(x, y):
    "获取指定坐标点周围有雷数标志的格子的数量"
    x1, y1, x2, y2 = get_bound(x, y)
    num = 0
    for py in range(y1, y2+1):
        for px in range(x1, x2+1):
            if px == x and py == y:
                continue
            num += (1 <= board[py, px] <= 8)
    return num


def srhAdjBlock(x, y):
    "搜索与数字位置相邻的未打开块，,使用flags标记已经访问过的位置"
    stack = [(x, y)]
    block = []
    while stack:
        x, y = stack.pop()
        if flags[y, x]:
            continue
        flags[y, x] = True
        block.append((x, y))
        for px, py in getUnknownPointList(x, y):
            if flags[py, px] or getOpenNum(px, py) <= 0:
                continue
            stack.append((px, py))
    return block

update_board(board)

flags = np.zeros_like(board, dtype="bool")
# 联通块列表
block_list = []
# 孤立位置列表
single_list = []
pys, pxs = np.where(board == -1)
for px, py in zip(pxs, pys):
    if flags[py, px]:
        continue
    if getOpenNum(px, py) > 0:
        block_list.append(srhAdjBlock(px, py))
    else:
        single_list.append((px, py))

为了查看我们找到的连通块是否准确，我定义了如下方法进行测试：

def show_dest_area(area):
    for px, py in area:
        message_click_mine_area(px, py, False)
        message_click_mine_area(px, py, False)
    img = ImageGrab.grab().crop(rect)
    for px, py in area:
        message_click_mine_area(px, py, False)
    return img

activateWindow(hwnd)
time.sleep(0.1)
print("single:")
display(show_dest_area(single_list))
print("block:")
for block in block_list:
    display(show_dest_area(block))

通过二次右击得到的问号知道每个连通块区域的位置（运行完会自动清除问号，只留下图像）：

image-20210808211543786

统计每个连通块中的每个格子在多少种解中是有雷的

在拆分出连通块区域后，我们就可以开始统计统计每个连通块中的每个格子在多少种解中是有雷的。

def getOpenNumList(x, y):
    "获取指定坐标点周围有雷数标志的格子坐标列表"
    x1, y1, x2, y2 = get_bound(x, y)
    num = 0
    for py in range(y1, y2+1):
        for px in range(x1, x2+1):
            if px == x and py == y:
                continue
            if 1 <= board[py, px] <= 8:
                yield px, py


def update_block(x, y, result):
    # 根据随机算法的基础规则更新board周边块
    result.clear()
    for px, py in getOpenNumList(x, y):
        unknownNum, redNum = getItemNum(px, py)
        # 实际雷数 小于 标记雷数目
        if board[py, px] < redNum:
            return False
        # 实际雷数 大于 未点开的格子数量+标记雷数目
        if board[py, px] > unknownNum + redNum:
            return False
        if unknownNum == 0:
            continue
        unknownPoints = getUnknownPointList(px, py)
        # 如果当前点周围雷数=未点+插旗，说明所有未点位置都是雷，可以全部插旗
        if board[py, px] == unknownNum + redNum:
            for px2, py2 in unknownPoints:
                result.append((px2, py2))
                board[py2, px2] = -2
        # 如果当前点周围雷数=插旗，说明所有未点位置都没有雷，可以全部点开
        if board[py, px] == redNum:
            for px2, py2 in unknownPoints:
                result.append((px2, py2))
                # 9表示临时无雷标记
                board[py2, px2] = 9
    return True


def updateNm2schemeCnt(block, mine_flag, nm2schemeCnt):
    "根据搜索得到的方案更新 nm2schemeCnt"
    nm = sum(mine_flag)
    if nm not in nm2schemeCnt:  # 新增一种方案
        nm2schemeCnt[nm] = [1, mine_flag.copy()]
    else:  # 更新
        v = nm2schemeCnt[nm]
        v[0] += 1
        v[1] += mine_flag


def srhScheme(block, mine_flag, k, nm2schemeCnt):
    """
    :param block: 连通块中的格子列表
    :param mine_flag: 是否有雷标记列表
    :param k: 从位置k开始搜索所有可行方案，结果存储于 nm2schemeCnt
    :param nm2schemeCnt: nm:(t,lstcellCnt)，
    代表这个联通块中,假设有nm颗雷的情况下共有t种方案，
    lstcellCnt表示各个格子中共有其中几种方案有雷
    :return: 
    """
    x, y = block[k]
    res = []
    if board[y, x] == -1:  # 两种可能：有雷、无雷
        # 9作为作为临时无雷标记，-2作为临时有雷标记
        for m, n in [(0, 9), (1, -2)]:
            # m和n 对应了无雷和有雷两种情况下的标记
            mine_flag[k] = m
            board[y, x] = n
            # 根据基础规则更新周围点的标记，返回更新格子列表和成功标记
            if update_block(x, y, res):
                if k == len(block) - 1:  # 得到一个方案
                    updateNm2schemeCnt(block, mine_flag, nm2schemeCnt)
                else:
                    srhScheme(block, mine_flag, k+1, nm2schemeCnt)
            # 恢复
            for px, py in res:
                board[py, px] = -1
        # 恢复
        board[y, x] = -1
    else:
        if board[y, x] == -2:
            mine_flag[k] = 1  # 有雷
        else:
            mine_flag[k] = 0  # 无雷
        # 根据规则1判断并更新周边块board标记，返回更新格子列表和成功标记
        if update_block(x, y, res):
            if k == len(block) - 1:  # 得到一个方案
                updateNm2schemeCnt(block, mine_flag, nm2schemeCnt)
            else:
                srhScheme(block, mine_flag, k+1, nm2schemeCnt)
        # 恢复
        for px, py in res:
            board[py, px] = -1

调用：

nm2schemeCnt_list = []
nmin = 0
nmax = 0
for block in block_list:
    # 搜索联通块k的可行方案
    # 当前连通块中，每个可能的总雷数对应的方案数和每个格子在其中几种方案下有雷
    nm2schemeCnt = {}
    mine_flag = np.zeros(len(block), dtype='int16')
    srhScheme(block, mine_flag, 0, nm2schemeCnt)
    nm2schemeCnt_list.append(nm2schemeCnt)
    nmin += min(nm2schemeCnt)
    nmax += max(nm2schemeCnt)
nm2schemeCnt_list

[{10: [28,
   array([ 4,  4,  4,  4,  4,  4,  0,  0,  0,  0,  0,  0,  0,  0, 14,  0,  0,
           0,  0,  0, 14, 14,  0, 28,  0,  0,  0, 14,  4, 14, 14, 24,  0, 28,
          24,  4,  4, 24, 16, 12,  4], dtype=int16)],
  11: [136,
   array([ 20,  20,  20,  20,  20,  16,  24,   0,   0,   0,   0,   0,   0,
            0,  68,   0,   0,   0,  14,  14,  54,  54, 112,  52,  28,  28,
           28,  68,  40,  54,  82,  96,   0, 136,  96,  40,  40,  96,  80,
           56,  20], dtype=int16)],
  12: [96,
   array([16, 16, 16, 16, 16,  0, 96,  0,  0,  0,  0,  0,  0,  0, 48,  0,  0,
           0, 12, 12, 36, 36, 96, 24, 24, 24, 24, 48, 96, 36, 60,  0,  0, 96,
           0, 96, 96,  0, 64, 32, 16], dtype=int16)]},
 {1: [3, array([1, 1, 1], dtype=int16)]}]

考虑剩余雷数，计算精确概率

因为有剩余雷数的限制，联通块内部的概率并不准确。

在枚举过程中，对每个联通块我们可以统计出 b l o c k C n t s \Large blockCnt_{s} blockCnts​ ，代表这个联通块的未知格中一共有 s 颗雷的方案数。 对每个格子 x 可以统计出: c e l l C n t x , s \Large cellCnt_{x,s} cellCntx,s​ 代表当格子所在的联通块中一共有 s 颗雷时，多少种方案中这个 x 格子是雷。

那么我们依次考虑每个格子的胜率。除开格子本身所在的联通块不看，考虑其它所有联通块（假设一共有 n n n 个连通块），我们可以计算出计算 D P i , j \Large DP_{i,j} DPi,j​ 代表前 i i i 个连通块共 j j j 个雷的方案数，这里是一个背包问题，转移方程：

D P i , j = ∑ s = 0 m a x D P i − 1 , j − s ∗ b l o c k C n t s \Large DP_{i,j} = \sum_{s = 0}^{max}{DP_{i-1, j-s} * blockCnt_s} DPi,j​=s=0∑max​DPi−1,j−s​∗blockCnts​

假设当前剩下 mine 个雷，枚举当前格子所在联通块的雷数 s ，有 b l o c k C n t s ∗ D P n − 1 , m i n e − s \Large blockCnt_s * DP_{n-1,mine - s} blockCnts​∗DPn−1,mine−s​ 种可行方案，其中 c e l l C n t x , s ∗ D P n − 1 , m i n e − s \Large cellCnt_{x, s} * DP_{n - 1, mine - s} cellCntx,s​∗DPn−1,mine−s​ 种方案中当前格有雷，对这两个值分别求和，就可以得到当前格有雷的精确概率。

首先向前面的方案列表加入孤立位置列表，使剩余格子参与概率计算：

# 如果非联通块中包含的雷数大于0，考虑剩余雷数对概率影响
if single_list:
    block_list.append(single_list)
    rnm2schemeCnt = {}  # 剩余格子概率计算
    n2 = len(single_list)
    for i in range(nmin, nmax + 1):
        n1 = mine_num - i
        mine_flag = [n1 for _ in range(n2)]
        rnm2schemeCnt[n1] = [n2, mine_flag]
    nm2schemeCnt_list.append(rnm2schemeCnt)

然后进行计算：

# 考虑剩余雷数的可能方案数计算
def calDP(lk, nm, nm2schemeCnt_list):
    ndp = 0
    k = lk[0]
    nm2schemeCnt = nm2schemeCnt_list[k]
    if len(lk) == 1:
        if nm in nm2schemeCnt:
            cnt, cnt_list = nm2schemeCnt[nm]
            ndp = cnt
    else:
        for k1 in nm2schemeCnt:
            lk1 = lk[1:]
            n1 = calDP(lk1, nm - k1, nm2schemeCnt_list)
            cnt, cnt_list = nm2schemeCnt[k1]
            ndp += n1 * cnt
    return ndp


pboard = np.zeros_like(board, dtype="int8")
# 基准有雷概率百分比
pboard.fill(mine_num*100//nb)

# 计算概率
for k in range(len(nm2schemeCnt_list)):
    lk = [t for t in range(len(nm2schemeCnt_list)) if t != k]
    # 考虑剩余雷数的可能方案数计算
    NBcnt = 0
    block = block_list[k]
    Ncnt = [0]*len(block)
    for nm, (cnt, cnt_list) in nm2schemeCnt_list[k].items():
        if len(lk) > 0:
            ndp = calDP(lk, mine_num - nm, nm2schemeCnt_list)
        else:
            ndp = 1
        NBcnt += cnt * ndp
        for i in range(len(Ncnt)):
            Ncnt[i] += cnt_list[i] * ndp
    # print("k,NBcnt,Ncnt=",k,NBcnt,Ncnt)
    for i in range(len(Ncnt)):
        x, y = block[i]
        pboard[y, x] = Ncnt[i] * 100 // NBcnt

基于概率的贪心算法

思想：如果没有确定有雷或无雷的格子，那么点击概率最小的格子，概率相同时点附近5*5的地图里未点开格子数最少的格子。

首先筛选出筛选出有雷概率为100和0的位置，用于后续点击和标记：

pys, pxs = np.where(board == -1)
res = set()
for x, y in zip(pxs, pys):
    if pboard[y, x] == 100:
        # 有雷概率为100说明必定有雷，插旗
        res.add((x, y, False))
    elif pboard[y, x] == 0:
        # 有雷概率为0说明必定没有雷，点开
        res.add((x, y, True))
res

{(8, 10, True),
 (9, 10, True),
 (10, 10, True),
 (12, 9, True),
 (13, 7, True),
 (13, 9, True),
 (14, 9, True),
 (15, 7, False),
 (15, 9, True),
 (16, 7, True),
 (16, 8, True),
 (16, 9, True)}

一下子就找出了这么多确定有雷和无雷的格子。

通过以下代码全部点击掉：

for r in res:
    message_click_mine_area(*r)

假如没有必定有雷和无雷的位置就只能基于概率进行选取：

if len(res) == 0:
    # 计算最小比例列表
    pys, pxs = np.where((board == -1) & (pboard == pboard[board == -1].min()))
    points = list(zip(pxs, pys))
    if len(points) > 10:
        # 超过10个以上这样的点则随机选一个
        x, y = random.choice(points)
        elif len(points) > 0:
            # 否则取周围未点开格子最少的格子
            x, y = min(points, key=getFiveMapNum)
            else:
                return res
            res.add((x, y, True))

概率分析算法代码的整体封装

def getOpenNum(x, y):
    "获取指定坐标点周围有雷数标志的格子的数量"
    x1, y1, x2, y2 = get_bound(x, y)
    num = 0
    for py in range(y1, y2+1):
        for px in range(x1, x2+1):
            if px == x and py == y:
                continue
            num += (1 <= board[py, px] <= 8)
    return num


def srhAdjBlock(x, y):
    "搜索与数字位置相邻的未打开块，,使用flags标记已经访问过的位置"
    stack = [(x, y)]
    block = []
    while stack:
        x, y = stack.pop()
        if flags[y, x]:
            continue
        flags[y, x] = True
        block.append((x, y))
        for px, py in getUnknownPointList(x, y):
            if flags[py, px] or getOpenNum(px, py) <= 0:
                continue
            stack.append((px, py))
    return block


def getOpenNumList(x, y):
    "获取指定坐标点周围有雷数标志的格子坐标列表"
    x1, y1, x2, y2 = get_bound(x, y)
    num = 0
    for py in range(y1, y2+1):
        for px in range(x1, x2+1):
            if px == x and py == y:
                continue
            if 1 <= board[py, px] <= 8:
                yield px, py


def update_block(x, y, result):
    "根据随机算法的基础规则更新board周边块"
    result.clear()
    for px, py in getOpenNumList(x, y):
        unknownNum, redNum = getItemNum(px, py)
        # 实际雷数 小于 标记雷数目
        if board[py, px] < redNum:
            return False
        # 实际雷数 大于 未点开的格子数量+标记雷数目
        if board[py, px] > unknownNum + redNum:
            return False
        if unknownNum == 0:
            continue
        unknownPoints = getUnknownPointList(px, py)
        # 如果当前点周围雷数=未点+插旗，说明所有未点位置都是雷，可以全部插旗
        if board[py, px] == unknownNum + redNum:
            for px2, py2 in unknownPoints:
                result.append((px2, py2))
                board[py2, px2] = -2
        # 如果当前点周围雷数=插旗，说明所有未点位置都没有雷，可以全部点开
        if board[py, px] == redNum:
            for px2, py2 in unknownPoints:
                result.append((px2, py2))
                # 9表示临时无雷标记
                board[py2, px2] = 9
    return True


def updateNm2schemeCnt(block, mine_flag, nm2schemeCnt):
    "根据搜索得到的方案更新 nm2schemeCnt"
    nm = sum(mine_flag)
    if nm not in nm2schemeCnt:  # 新增一种方案
        nm2schemeCnt[nm] = [1, mine_flag.copy()]
    else:  # 更新
        v = nm2schemeCnt[nm]
        v[0] += 1
        v[1] += mine_flag


def srhScheme(block, mine_flag, k, nm2schemeCnt):
    """
    :param block: 连通块中的格子列表
    :param mine_flag: 是否有雷标记列表
    :param k: 从位置k开始搜索所有可行方案，结果存储于 nm2schemeCnt
    :param nm2schemeCnt: nm:(t,lstcellCnt)，
    代表这个联通块中,假设有nm颗雷的情况下共有t种方案，
    lstcellCnt表示各个格子中共有其中几种方案有雷
    :return: 
    """
    x, y = block[k]
    res = []
    if board[y, x] == -1:  # 两种可能：有雷、无雷
        # 9作为作为临时无雷标记，-2作为临时有雷标记
        for m, n in [(0, 9), (1, -2)]:
            # m和n 对应了无雷和有雷两种情况下的标记
            mine_flag[k] = m
            board[y, x] = n
            # 根据基础规则更新周围点的标记，返回更新格子列表和成功标记
            if update_block(x, y, res):
                if k == len(block) - 1:  # 得到一个方案
                    updateNm2schemeCnt(block, mine_flag, nm2schemeCnt)
                else:
                    srhScheme(block, mine_flag, k+1, nm2schemeCnt)
            # 恢复
            for px, py in res:
                board[py, px] = -1
        # 恢复
        board[y, x] = -1
    else:
        if board[y, x] == -2:
            mine_flag[k] = 1  # 有雷
        else:
            mine_flag[k] = 0  # 无雷
        # 根据规则1判断并更新周边块board标记，返回更新格子列表和成功标记
        if update_block(x, y, res):
            if k == len(block) - 1:  # 得到一个方案
                updateNm2schemeCnt(block, mine_flag, nm2schemeCnt)
            else:
                srhScheme(block, mine_flag, k+1, nm2schemeCnt)
        # 恢复
        for px, py in res:
            board[py, px] = -1


def calDP(lk, nm, nm2schemeCnt_list):
    "考虑剩余雷数的可能方案数计算"
    ndp = 0
    k = lk[0]
    nm2schemeCnt = nm2schemeCnt_list[k]
    if len(lk) == 1:
        if nm in nm2schemeCnt:
            cnt, cnt_list = nm2schemeCnt[nm]
            ndp = cnt
    else:
        for k1 in nm2schemeCnt:
            lk1 = lk[1:]
            n1 = calDP(lk1, nm - k1, nm2schemeCnt_list)
            cnt, cnt_list = nm2schemeCnt[k1]
            ndp += n1 * cnt
    return ndp


def getCLKPoints(board):
    "获取节点列表"
    flags.fill(0)
    # 联通块列表
    block_list = []
    # 孤立位置列表
    single_list = []
    pys, pxs = np.where(board == -1)
    for px, py in zip(pxs, pys):
        if flags[py, px]:
            continue
        if getOpenNum(px, py) > 0:
            block_list.append(srhAdjBlock(px, py))
        else:
            single_list.append((px, py))

    nm2schemeCnt_list = []
    nmin = 0
    nmax = 0
    for block in block_list:
        # 搜索联通块k的可行方案
        # 当前连通块中，每个可能的总雷数对应的方案数和每个格子在其中几种方案下有雷
        nm2schemeCnt = {}
        mine_flag = np.zeros(len(block), dtype='int16')
        srhScheme(block, mine_flag, 0, nm2schemeCnt)
        nm2schemeCnt_list.append(nm2schemeCnt)
        nmin += min(nm2schemeCnt)
        nmax += max(nm2schemeCnt)

    # 如果非联通块中包含的雷数大于0，考虑剩余雷数对概率影响
    if single_list:
        block_list.append(single_list)
        rnm2schemeCnt = {}  # 剩余格子概率计算
        n2 = len(single_list)
        for i in range(nmin, nmax + 1):
            n1 = mine_num - i
            mine_flag = [n1 for _ in range(n2)]
            rnm2schemeCnt[n1] = [n2, mine_flag]
        nm2schemeCnt_list.append(rnm2schemeCnt)

    pboard = np.zeros_like(board, dtype="int8")
    # 基准有雷概率百分比
    pboard.fill(mine_num*100//nb)

    # 计算概率
    for k in range(len(nm2schemeCnt_list)):
        lk = [t for t in range(len(nm2schemeCnt_list)) if t != k]
        # 考虑剩余雷数的可能方案数计算
        NBcnt = 0
        block = block_list[k]
        Ncnt = [0]*len(block)
        for nm, (cnt, cnt_list) in nm2schemeCnt_list[k].items():
            if len(lk) > 0:
                ndp = calDP(lk, mine_num - nm, nm2schemeCnt_list)
            else:
                ndp = 1
            NBcnt += cnt * ndp
            for i in range(len(Ncnt)):
                Ncnt[i] += cnt_list[i] * ndp
        # print("k,NBcnt,Ncnt=",k,NBcnt,Ncnt)
        for i in range(len(Ncnt)):
            x, y = block[i]
            pboard[y, x] = Ncnt[i] * 100 // NBcnt

    pys, pxs = np.where(board == -1)
    res = set()
    for x, y in zip(pxs, pys):
        if pboard[y, x] == 100:
            # 有雷概率为100说明必定有雷，插旗
            res.add((x, y, False))
        elif pboard[y, x] == 0:
            # 有雷概率为0说明必定没有雷，点开
            res.add((x, y, True))
    if len(res) == 0:
        # 计算最小比例列表
        pys, pxs = np.where((board == -1) & (pboard == pboard[board == -1].min()))
        points = list(zip(pxs, pys))
        if len(points) > 10:
            # 超过10个以上这样的点则随机选一个
            x, y = random.choice(points)
        elif len(points) > 0:
            # 否则取周围未点开格子最少的格子
            x, y = min(points, key=getFiveMapNum)
        else:
            return res
        res.add((x, y, True))
    return res

调用示例：

update_board(board)
flags = np.zeros_like(board, dtype="bool")
getCLKPoints(board)

引入概率分析算法进行测试

"""
小小明的代码
CSDN主页：https://blog.csdn.net/as604049322
"""
__author__ = '小小明'
__time__ = '2021/8/8'

import functools
import random
import time
from collections import Counter
from concurrent import futures

import numpy as np
import win32api
import win32com.client as win32
import win32con
import win32gui
from PIL import ImageGrab

# 每个方块16*16
bw, bh = 16, 16
# 剩余雷数图像特征码
code2num = {
    247: 0, 50: 1, 189: 2,
    187: 3, 122: 4, 203: 5,
    207: 6, 178: 7, 255: 8, 251: 9
}
# 雷区图像特征码
# 数字1-8表示周围有几个雷
#  0 表示已经点开是空白的格子
# -1 表示还没有点开的格子
# -2 表示红旗所在格子
# -3 表示踩到雷了已经失败
# -4 表示被玩家自己标记为问号
rgb_signs = [
    '281d9cc0', '414b83c0', '3e4c86c0', '380f8cc0',
    '46267ec0', '485a7cc0', '2c0098c0', '4c8078c0', 'c4c0',
    '198092c019ff', '1600114c19806bc019ff', '4d0073c004ff',
    '4d00734c04ff', '34002e4c61c001ff', '180019807ac019ff'
]
values = [
    1, 2, 3, 4,
    5, 6, 7, 8, 0,
    -1, -2, -3,
    -3, -3, -4, -4
]
img_match = dict(zip(rgb_signs, values))
# 雷区格子在窗体上的起始坐标
offest_x, offest_y = 0xC, 0x37


def get_board_size(hwnd):
    left, top, right, bottom = win32gui.GetWindowRect(hwnd)
    # 横向有w个方块
    l, t, r, b = (left + 15, top + 101, right - 11, bottom - 11)
    w = (r - l) // bw
    # 纵向有h个方块
    h = (b - t) // bh
    return (w, h), (l, t, r, b)


def get_pixel_code(pixels):
    key_points = np.array([
        pixels[5, 1], pixels[1, 5], pixels[9, 5],
        pixels[9, 5], pixels[5, 10],
        pixels[1, 15], pixels[9, 15], pixels[5, 19]
    ]) == 76
    code = int("".join(key_points.astype("int8").astype("str")), 2)
    return code


def get_mine_num(hwnd, full_img=None):
    if full_img is None:
        full_img = ImageGrab.grab()
    left, top, right, bottom = win32gui.GetWindowRect(hwnd)
    num_img = full_img.crop((left + 20, top + 62, left + 20 + 39, top + 62 + 23))
    mine_num = 0
    for i in range(3):
        num_i = num_img.crop((13 * i + 1, 1, 13 * (i + 1) - 1, 22)).convert("L")
        code = get_pixel_code(num_i.load())
        mine_num = mine_num * 10 + code2num[code]
    return mine_num


def colors2signature(colors):
    return "".join(hex(b)[2:].zfill(2) for c in colors for b in c)


def update_board(board, full_img=None):
    if full_img is None:
        full_img = ImageGrab.grab()
    left, top, right, bottom = win32gui.GetWindowRect(hwnd)
    rect = (left + 15, top + 101, right - 11, bottom - 11)
    img = full_img.crop(rect)
    for y in range(h):
        for x in range(w):
            img_block = img.crop((x * bw + 1, y * bh + 1, (x + 1) * bw - 1, (y + 1) * bh - 1))
            colors = img_block.convert("L").getcolors()
            signature = colors2signature(colors)
            board[y, x] = img_match[signature]
    return board


def get_hwnd():
    class_name, title_name = "扫雷", "扫雷"
    return win32gui.FindWindow(class_name, title_name)


def activateWindow(hwnd):
    # SetForegroundWindow调用有一些限制，我们可以再调用之前输入一个键盘事件
    shell = win32.Dispatch("WScript.Shell")
    shell.SendKeys('%')
    win32gui.SetForegroundWindow(hwnd)


def new_board(w, h):
    board = np.zeros((h, w), dtype="int8")
    board.fill(-1)
    return board


def click(x, y, is_left_click=True):
    if is_left_click:
        win32api.SetCursorPos((x, y))
        win32api.mouse_event(
            win32con.MOUSEEVENTF_LEFTDOWN, 0, 0, 0, 0)
        win32api.mouse_event(
            win32con.MOUSEEVENTF_LEFTUP, 0, 0, 0, 0)
    else:
        win32api.SetCursorPos((x, y))
        win32api.mouse_event(
            win32con.MOUSEEVENTF_RIGHTDOWN, 0, 0, 0, 0)
        win32api.mouse_event(
            win32con.MOUSEEVENTF_RIGHTUP, 0, 0, 0, 0)


def click_mine_area(px, py, is_left_click=True):
    x, y = l + px * bw + bw // 2, t + py * bh + + bh // 2
    click(x, y, is_left_click)


def get_bound(x, y):
    "获取指定坐标周围4*4-9*9的边界范围"
    x1, x2 = max(x - 1, 0), min(x + 1, w - 1)
    y1, y2 = max(y - 1, 0), min(y + 1, h - 1)
    return x1, y1, x2, y2


def getItemNum(x, y):
    "获取指定坐标点周围没有点开和已确定有雷的格子的数量"
    # -1 表示还没有点开的格子
    # -2 表示红旗所在格子
    x1, y1, x2, y2 = get_bound(x, y)
    count = Counter(board[y1:y2 + 1, x1:x2 + 1].reshape(-1))
    return count[-1], count[-2]


def getUnknownPointList(x, y):
    "获取指定坐标点周围还没有点开的格子坐标列表"
    x1, y1, x2, y2 = get_bound(x, y)
    for py in range(y1, y2 + 1):
        for px in range(x1, x2 + 1):
            if px == x and py == y:
                continue
            if board[py, px] == -1:
                yield px, py


def getOpenNum(x, y):
    "获取指定坐标点周围有雷数标志的格子的数量"
    x1, y1, x2, y2 = get_bound(x, y)
    num = 0
    for py in range(y1, y2 + 1):
        for px in range(x1, x2 + 1):
            if px == x and py == y:
                continue
            num += (1 <= board[py, px] <= 8)
    return num


def srhAdjBlock(x, y):
    "搜索与数字位置相邻的未打开块，,使用flags标记已经访问过的位置"
    stack = [(x, y)]
    block = []
    while stack:
        x, y = stack.pop()
        if block_flag[y, x]:
            continue
        block_flag[y, x] = True
        block.append((x, y))
        for px, py in getUnknownPointList(x, y):
            if block_flag[py, px] or getOpenNum(px, py) <= 0:
                continue
            stack.append((px, py))
    return block


def getOpenNumList(x, y):
    "获取指定坐标点周围有雷数标志的格子坐标列表"
    x1, y1, x2, y2 = get_bound(x, y)
    num = 0
    for py in range(y1, y2 + 1):
        for px in range(x1, x2 + 1):
            if px == x and py == y:
                continue
            if 1 <= board[py, px] <= 8:
                yield px, py


def update_block(x, y, result):
    "根据随机算法的基础规则更新board周边块"
    result.clear()
    for px, py in getOpenNumList(x, y):
        unknownNum, redNum = getItemNum(px, py)
        # 实际雷数 小于 标记雷数目
        if board[py, px] < redNum:
            return False
        # 实际雷数 大于 未点开的格子数量+标记雷数目
        if board[py, px] > unknownNum + redNum:
            return False
        if unknownNum == 0:
            continue
        unknownPoints = getUnknownPointList(px, py)
        # 如果当前点周围雷数=未点+插旗，说明所有未点位置都是雷，可以全部插旗
        if board[py, px] == unknownNum + redNum:
            for px2, py2 in unknownPoints:
                result.append((px2, py2))
                board[py2, px2] = -2
        # 如果当前点周围雷数=插旗，说明所有未点位置都没有雷，可以全部点开
        if board[py, px] == redNum:
            for px2, py2 in unknownPoints:
                result.append((px2, py2))
                # 9表示临时无雷标记
                board[py2, px2] = 9
    return True


def updateNm2schemeCnt(block, mine_flag, nm2schemeCnt):
    "根据搜索得到的方案更新 nm2schemeCnt"
    nm = sum(mine_flag)
    if nm not in nm2schemeCnt:  # 新增一种方案
        nm2schemeCnt[nm] = [1, mine_flag.copy()]
    else:  # 更新
        v = nm2schemeCnt[nm]
        v[0] += 1
        v[1] += mine_flag


def srhScheme(block, mine_flag, k, nm2schemeCnt):
    """
    :param block: 连通块中的格子列表
    :param mine_flag: 是否有雷标记列表
    :param k: 从位置k开始搜索所有可行方案，结果存储于 nm2schemeCnt
    :param nm2schemeCnt: nm:(t,lstcellCnt)，
    代表这个联通块中,假设有nm颗雷的情况下共有t种方案，
    lstcellCnt表示各个格子中共有其中几种方案有雷
    :return:
    """
    x, y = block[k]
    res = []
    if board[y, x] == -1:  # 两种可能：有雷、无雷
        # 9作为作为临时无雷标记，-2作为临时有雷标记
        for m, n in [(0, 9), (1, -2)]:
            # m和n 对应了无雷和有雷两种情况下的标记
            mine_flag[k] = m
            board[y, x] = n
            # 根据基础规则更新周围点的标记，返回更新格子列表和成功标记
            if update_block(x, y, res):
                if k == len(block) - 1:  # 得到一个方案
                    updateNm2schemeCnt(block, mine_flag, nm2schemeCnt)
                else:
                    srhScheme(block, mine_flag, k + 1, nm2schemeCnt)
            # 恢复
            for px, py in res:
                board[py, px] = -1
        # 恢复
        board[y, x] = -1
    else:
        if board[y, x] == -2:
            mine_flag[k] = 1  # 有雷
        else:
            mine_flag[k] = 0  # 无雷
        # 根据规则1判断并更新周边块board标记，返回更新格子列表和成功标记
        if update_block(x, y, res):
            if k == len(block) - 1:  # 得到一个方案
                updateNm2schemeCnt(block, mine_flag, nm2schemeCnt)
            else:
                srhScheme(block, mine_flag, k + 1, nm2schemeCnt)
        # 恢复
        for px, py in res:
            board[py, px] = -1


def calDP(lk, nm, nm2schemeCnt_list):
    "考虑剩余雷数的可能方案数计算"
    ndp = 0
    k = lk[0]
    nm2schemeCnt = nm2schemeCnt_list[k]
    if len(lk) == 1:
        if nm in nm2schemeCnt:
            cnt, cnt_list = nm2schemeCnt[nm]
            ndp = cnt
    else:
        for k1 in nm2schemeCnt:
            lk1 = lk[1:]
            n1 = calDP(lk1, nm - k1, nm2schemeCnt_list)
            cnt, cnt_list = nm2schemeCnt[k1]
            ndp += n1 * cnt
    return ndp


class TimeOut:
    __executor = futures.ThreadPoolExecutor(1)

    def __init__(self, seconds):
        self.seconds = seconds

    def __call__(self, func):
        @functools.wraps(func)
        def wrapper(*args, **kw):
            future = TimeOut.__executor.submit(func, *args, **kw)
            return future.result(timeout=self.seconds)

        return wrapper


@TimeOut(2)
def getCLKPoints(board):
    "获取节点列表"
    block_flag.fill(0)
    # 联通块列表
    block_list = []
    # 孤立位置列表
    single_list = []
    pys, pxs = np.where(board == -1)
    for px, py in zip(pxs, pys):
        if block_flag[py, px]:
            continue
        if getOpenNum(px, py) > 0:
            block_list.append(srhAdjBlock(px, py))
        else:
            single_list.append((px, py))

    nm2schemeCnt_list = []
    nmin = 0
    nmax = 0
    for block in block_list:
        # 搜索联通块k的可行方案
        # 当前连通块中，每个可能的总雷数对应的方案数和每个格子在其中几种方案下有雷
        nm2schemeCnt = {}
        mine_flag = np.zeros(len(block), dtype='int16')
        srhScheme(block, mine_flag, 0, nm2schemeCnt)
        nm2schemeCnt_list.append(nm2schemeCnt)
        nmin += min(nm2schemeCnt)
        nmax += max(nm2schemeCnt)

    # 如果非联通块中包含的雷数大于0，考虑剩余雷数对概率影响
    if single_list:
        block_list.append(single_list)
        rnm2schemeCnt = {}  # 剩余格子概率计算
        n2 = len(single_list)
        for i in range(nmin, nmax + 1):
            n1 = mine_num - i
            mine_flag = [n1 for _ in range(n2)]
            rnm2schemeCnt[n1] = [n2, mine_flag]
        nm2schemeCnt_list.append(rnm2schemeCnt)

    pboard = np.zeros_like(board, dtype="uint8")
    # 基准有雷概率百分比
    nb = (board == -1).sum()
    pboard.fill(mine_num * 100 // nb)

    # 计算概率
    for k in range(len(nm2schemeCnt_list)):
        lk = [t for t in range(len(nm2schemeCnt_list)) if t != k]
        # 考虑剩余雷数的可能方案数计算
        NBcnt = 0
        block = block_list[k]
        Ncnt = [0] * len(block)
        for nm, (cnt, cnt_list) in nm2schemeCnt_list[k].items():
            if len(lk) > 0:
                ndp = calDP(lk, mine_num - nm, nm2schemeCnt_list)
            else:
                ndp = 1
            NBcnt += cnt * ndp
            for i in range(len(Ncnt)):
                Ncnt[i] += cnt_list[i] * ndp
        for i in range(len(Ncnt)):
            x, y = block[i]
            pboard[y, x] = (Ncnt[i] * 100 // NBcnt)

    pys, pxs = np.where(board == -1)
    res = set()
    for x, y in zip(pxs, pys):
        if pboard[y, x] == 100:
            # 有雷概率为100说明必定有雷，插旗
            res.add((x, y, False))
        elif pboard[y, x] == 0:
            # 有雷概率为0说明必定没有雷，点开
            res.add((x, y, True))

    def getFiveMapNum(p):
        "获取指定坐标点5*5地图内还没有点开格子的数量"
        # -1 表示还没有点开的格子
        # 获取指定坐标周围4*4-9*9的边界范围
        x, y = p
        x1, x2 = max(x - 2, 0), min(x + 2, w - 1)
        y1, y2 = max(y - 2, 0), min(y + 2, h - 1)
        return (board[y1:y2 + 1, x1:x2 + 1] == -1).sum()

    if len(res) == 0:
        # 计算最小比例列表
        pys, pxs = np.where((board == -1) & (pboard == pboard[board == -1].min()))
        points = list(zip(pxs, pys))
        if len(points) > 10:
            # 超过10个以上这样的点则随机选一个
            x, y = random.choice(points)
        elif len(points) > 0:
            # 否则取周围未点开格子最少的格子
            x, y = min(points, key=getFiveMapNum)
        else:
            return res
        res.add((x, y, True))
    return res


def base_op():
    # 筛选出所有未确定的数字位置 坐标
    pys, pxs = np.where((1 <= board) & (board <= 8) & (~flag))
    res = set()
    for x, y in zip(pxs, pys):
        boom_number = board[y, x]
        # 统计当前点周围 4*4-9*9 范围各类点的数量
        unknownNum, redNum = getItemNum(x, y)
        if unknownNum == 0:
            # 周围没有未点过的点可以直接忽略
            flag[y, x] = True
            continue
        # 获取周围的点的位置
        points = getUnknownPointList(x, y)
        if boom_number == unknownNum + redNum:
            # 如果当前点周围雷数=未点+插旗，说明所有未点位置都是雷，可以全部插旗
            flag[y, x] = True
            for px, py in points:
                res.add((px, py, False))
        elif boom_number == redNum:
            # 如果当前点周围雷数=插旗，说明所有未点位置都没有雷，可以全部点开
            flag[y, x] = True
            for px, py in points:
                res.add((px, py, True))
    return res


hwnd = get_hwnd()
activateWindow(hwnd)
# 获取雷盘大小和位置
(w, h), rect = get_board_size(hwnd)
mine_num = get_mine_num(hwnd)
print(f"宽：{w},高：{h},雷数：{mine_num}，雷盘位置：{rect}")
board = new_board(w, h)
update_board(board)
l, t, r, b = rect
# 点击任意位置激活窗口
click(l + 50, t - 30)
time.sleep(0.1)
# 标记周围已经完全确定的数字位置
flag = np.zeros_like(board, dtype="bool")
# 标记已经访问过的连通块
block_flag = np.zeros_like(board, dtype="bool")
while True:
    res = base_op()
    nb = (board == -1).sum()
    if len(res) == 0 and nb != 0:
        tmp = board.copy()
        try:
            res = getCLKPoints(board)
        except futures._base.TimeoutError:
            board = tmp
            py, px = random.choice(list(zip(*np.where(board == -1))))
            res.add((px, py, True))
    for px, py, left in res:
        click_mine_area(px, py, left)
        if not left:
            mine_num -= 1
    print("剩余雷数：", mine_num)

    if nb == 0:
        print("顺利！！！")
        break
    if (board == -3).sum() != 0:
        print("踩到雷了，游戏结束！")
        break
    # 操作完毕后，更新最新的雷盘数据
    update_board(board)

现在这就是引入概率分析的完整代码，现在我们玩下高级试一下：

录制_2021_08_08_22_42_56_24

可以看到5秒内就解决了高级。

能不能更快更高的胜率？

上次的玩数独一文中，有读者在公众号留言实锤开挂，我只想呵呵一笑。今天就让你们见识一下什么叫真正的开挂。

最终能达到什么效果呢？任何级别耗时在1秒以内，胜率为100%。

看下效果：

录制_2021_08_08_23_07_17_777

内存外挂原理

分析出雷盘数据的内存位置，调用kernel32.dll的API读取内存。

windowsAPI文档可查看：

打开HawkOD后，把winmine.exe拖入HawkOD

在WM_LBUTTONUP上设置断点后，运行，然后单步步过到地址01001FE1后跟随：

image-20210808233244299

跟随后我们在此处可以找到棋盘数据：

image-20210808234332258

可以看到地址010055330前双字为0x28(十进制为40)这表示雷数，后面双字分别是宽度和高度，0x10表示棋盘的边，0x8F表示雷。

所以我们的外挂想做的极端点，只需要将此段内存的0x8F全部改成0x8E，就直接胜利了，但是没有必要。我们只需要能读取雷区数据就行。

实现过程

首先，我们获取扫雷程序的窗口对象，并从系统动态链接库中获取读写内存的方法：

from ctypes import *
import win32gui

# 扫雷游戏窗口
class_name, title_name = "扫雷", "扫雷"
hwnd = win32gui.FindWindow(class_name, title_name)

kernel32 = cdll.LoadLibrary("kernel32.dll")
ReadProcessMemory = kernel32.ReadProcessMemory
WriteProcessMemory = kernel32.WriteProcessMemory
OpenProcess = kernel32.OpenProcess

连接到指定进程，用于直接读取其内存数据：

import win32process
import win32con

hreadID, processID = win32process.GetWindowThreadProcessId(hwnd)
process = OpenProcess(win32con.PROCESS_ALL_ACCESS, 0, processID)

读取剩余雷数和宽高：

mine_num, w, h = c_ulong(), c_ulong(), c_ulong()
ReadProcessMemory(process, 0x1005330, byref(mine_num), 4)
ReadProcessMemory(process, 0x1005334, byref(w), 4)
ReadProcessMemory(process, 0x1005338, byref(h), 4)
mine_num, w, h = mine_num.value, w.value, h.value
print(f"宽：{w}，高：{h}，剩余雷数：{mine_num}")

宽：9，高：9，剩余雷数：10

读取并打印棋盘数据：

max_w, max_h = 30, 24
# 外围有一个值为 0x10 的边界，所以长宽均+2
data_type = (c_byte * (max_w + 2)) * (max_h + 2)
board = data_type()
bytesRead = c_ulong(0)
ReadProcessMemory(process, 0x1005340, byref(board), sizeof(board), byref(bytesRead))
for y in range(1, h+1):
    for x in range(1, w+1):
        sign = board[y][x]
        print(sign, end=",")
    print()

15,15,-113,15,15,15,15,15,15,
15,15,15,15,15,15,15,15,15,
15,-113,15,15,15,-113,-113,15,15,
15,15,15,15,15,15,15,15,15,
15,15,15,15,-113,15,-113,15,15,
15,15,15,15,15,15,-113,15,15,
15,15,15,15,-113,15,-113,15,15,
15,15,15,15,15,15,-113,15,15,
15,15,15,15,15,15,15,15,15,

注意：由于需要读取的棋盘数据，数据范围较大，所以需要申明了一个bytesRead作为缓冲区，否则可能出现无法读取数据的情况。

然后就可以迅速解开全部位置：

import win32api


def message_click(x, y, is_left_click=True):
    if is_left_click:
        win32api.SendMessage(hwnd,
                             win32con.WM_LBUTTONDOWN,
                             win32con.MK_LBUTTON,
                             win32api.MAKELONG(x, y))
        win32api.SendMessage(hwnd,
                             win32con.WM_LBUTTONUP,
                             win32con.MK_LBUTTON,
                             win32api.MAKELONG(x, y))
    else:
        win32api.SendMessage(hwnd,
                             win32con.WM_RBUTTONDOWN,
                             win32con.MK_RBUTTON,
                             win32api.MAKELONG(x, y))
        win32api.SendMessage(hwnd,
                             win32con.WM_RBUTTONUP,
                             win32con.MK_RBUTTON,
                             win32api.MAKELONG(x, y))


# 雷区格子在窗体上的起始坐标
offest_x, offest_y = 0xC, 0x37
# 每个格子方块的宽度和高度 16*16
bw, bh = 16, 16
def message_click_mine_area(px, py, is_left_click=True):
    x, y = offest_x+px*bw + bw // 2, offest_y+py*bh + bh // 2
    message_click(x, y, is_left_click)


for y in range(h):
    for x in range(w):
        if board[y + 1][x + 1] == 15:
            message_click_mine_area(x, y)

内存外挂的完整代码

import win32api
import win32con
import win32process
from ctypes import *
import win32gui

# 扫雷游戏窗口
class_name, title_name = "扫雷", "扫雷"
hwnd = win32gui.FindWindow(class_name, title_name)

kernel32 = cdll.LoadLibrary("kernel32.dll")
ReadProcessMemory = kernel32.ReadProcessMemory
WriteProcessMemory = kernel32.WriteProcessMemory
OpenProcess = kernel32.OpenProcess


hreadID, processID = win32process.GetWindowThreadProcessId(hwnd)
process = OpenProcess(win32con.PROCESS_ALL_ACCESS, 0, processID)
bytesRead = c_ulong(0)
mine_num, w, h = c_ulong(), c_ulong(), c_ulong()
ReadProcessMemory(process, 0x1005330, byref(mine_num), 4, byref(bytesRead))
ReadProcessMemory(process, 0x1005334, byref(w), 4, byref(bytesRead))
ReadProcessMemory(process, 0x1005338, byref(h), 4, byref(bytesRead))
mine_num, w, h = mine_num.value, w.value, h.value
print(f"宽：{w}，高：{h}，剩余雷数：{mine_num}")

max_w, max_h = 30, 24
# 外围有一个值为 0x10 的边界，所以长宽均+2
data_type = (c_byte * (max_w + 2)) * (max_h + 2)
board = data_type()

ReadProcessMemory(process, 0x1005340, byref(
    board), sizeof(board), byref(bytesRead))


def message_click(x, y, is_left_click=True):
    if is_left_click:
        win32api.SendMessage(hwnd,
                             win32con.WM_LBUTTONDOWN,
                             win32con.MK_LBUTTON,
                             win32api.MAKELONG(x, y))
        win32api.SendMessage(hwnd,
                             win32con.WM_LBUTTONUP,
                             win32con.MK_LBUTTON,
                             win32api.MAKELONG(x, y))
    else:
        win32api.SendMessage(hwnd,
                             win32con.WM_RBUTTONDOWN,
                             win32con.MK_RBUTTON,
                             win32api.MAKELONG(x, y))
        win32api.SendMessage(hwnd,
                             win32con.WM_RBUTTONUP,
                             win32con.MK_RBUTTON,
                             win32api.MAKELONG(x, y))


# 雷区格子在窗体上的起始坐标
offest_x, offest_y = 0xC, 0x37
# 每个格子方块的宽度和高度 16*16
bw, bh = 16, 16


def message_click_mine_area(px, py, is_left_click=True):
    x, y = offest_x+px*bw + bw // 2, offest_y+py*bh + bh // 2
    message_click(x, y, is_left_click)


for y in range(h):
    for x in range(w):
        if board[y + 1][x + 1] == 15:
            message_click_mine_area(x, y)

体验一下：

录制_2021_08_09_00_41_06_195

能超越初级的0.49秒的世界记录吗？

实际上按照专业扫雷选手的说法，初级扫雷并不对时间设置世界记录，关于扫雷的世界记录有且仅有十项，参考：

  • 初级3bv/s:12.04 鞠泽恩（中国）
  • NF初级3bv/s:8.53 鞠泽恩（中国）
  • 中级3bv/s:7.445 鞠泽恩（中国）
  • NF中级3bv/s:6.33 郭蔚嘉（中国）
  • 高级3bv/s:6.06 鞠泽恩（中国）
  • NF高级3bv/s:4.93 郭蔚嘉（中国）
  • 中级time:6.96s 鞠泽恩（中国）
  • NF中级time:7.03s Kamil Muranski（波兰）
  • 高级time:28.70s 鞠泽恩（中国）
  • NF高级time:31.17s鞠泽恩（中国）

作者：MsPVZ.ZSW
链接：https://zhuanlan.zhihu.com/p/27151972

要突破3bv/s的世界记录对于程序而言过于简单，因为人肯定不会比程序点的快。对于0.49秒这个所谓的世界记录，我们也只需要多运行几遍就可以达到了。

不过win98版本的扫雷，不支持1秒以内的时间统计，所以首先我们需要更换为扫雷网提供的扫雷进行操作。效果：

录制_2021_08_09_18_38_11_832

对于扫雷网提供的扫雷游戏，雷盘的像素点偏移有些变化，下面按照同样的思路计算出特征码后编写如下代码，能同时适配两种扫雷程序。

同时为了速度更快我们不再程序去操作标旗而是自行变量记录一下：

"""
小小明的代码
CSDN主页：https://blog.csdn.net/as604049322
"""
__author__ = '小小明'
__time__ = '2021/8/8'

import functools
import random
import time
from collections import Counter
from concurrent import futures

import numpy as np
import win32api
import win32com.client as win32
import win32con
import win32gui
from PIL import ImageGrab

# 每个方块16*16
bw, bh = 16, 16
# 剩余雷数图像特征码
code2num = {
    247: 0, 50: 1, 189: 2,
    187: 3, 122: 4, 203: 5,
    207: 6, 178: 7, 255: 8, 251: 9
}


def get_img_matchs():
    """
    雷区图像特征码
    数字1-8表示周围有几个雷
     0 表示已经点开是空白的格子
    -1 表示还没有点开的格子
    -2 表示红旗所在格子
    -3 表示踩到雷了已经失败
    """
    values = [
        1, 2, 3, 4,
        5, 6, 7, 8, 0,
        -1, -2,
        -3, -3, -4
    ]
    rgb_signs_0 = [
        '281d9cc0', '414b83c0', '3e4c86c0', '380f8cc0',
        '46267ec0', '485a7cc0', '2c0098c0', '4c8078c0', 'c4c0',
        '198092c019ff', '1600114c19806bc019ff',
        '4d0073c004ff', '4d00734c04ff', '34002e4c61c001ff'
    ]
    rgb_signs_1 = [
        '281d9cc0', '414b83c0', '3e4c86c0', '380f8cc0',
        '46267ec0', '485a7cc0', '2c0098c0', '4c8078c0', 'c4c0',
        '278091c00cff', '1600114c27806ac00cff',
        '4d0073c004ff', '4d00734c04ff', '4d00734c04ff'
    ]
    return {
        "扫雷": dict(zip(rgb_signs_0, values)),
        "Arbiter": dict(zip(rgb_signs_1, values))
    }


img_matchs = get_img_matchs()


def get_hwnd():
    "先搜索普通扫雷，再搜索扫雷网的扫雷"
    global name
    names = {"扫雷": ("扫雷", "扫雷"), "Arbiter": ("TMain", "Minesweeper Arbiter ")}
    for n, (class_name, title_name) in names.items():
        hwnd = win32gui.FindWindow(class_name, title_name)
        if hwnd:
            name = n
            return hwnd


def get_board_size():
    offests = {"扫雷": (15, 101, -11, -11), "Arbiter": (15, 102, -15, -42)}
    left, top, right, bottom = win32gui.GetWindowRect(hwnd)
    o1, o2, o3, o4 = offests[name]
    # 横向有w个方块
    l, t, r, b = (left + o1, top + o2, right + o3, bottom + o4)
    w = (r - l) // bw
    # 纵向有h个方块
    h = (b - t) // bh
    return (w, h), (l, t, r, b)


def get_pixel_code(pixels):
    key_points = np.array([
        pixels[5, 1], pixels[1, 5], pixels[9, 5],
        pixels[9, 5], pixels[5, 10],
        pixels[1, 15], pixels[9, 15], pixels[5, 19]
    ]) == 76
    code = int("".join(key_points.astype("int8").astype("str")), 2)
    return code


def get_mine_num(hwnd, full_img=None):
    if full_img is None:
        full_img = ImageGrab.grab()
    left, top, right, bottom = win32gui.GetWindowRect(hwnd)
    num_img = full_img.crop((left + 20, top + 62, left + 20 + 39, top + 62 + 23))
    mine_num = 0
    for i in range(3):
        num_i = num_img.crop((13 * i + 1, 1, 13 * (i + 1) - 1, 22)).convert("L")
        code = get_pixel_code(num_i.load())
        mine_num = mine_num * 10 + code2num[code]
    return mine_num


def colors2signature(colors):
    return "".join(hex(b)[2:].zfill(2) for c in colors for b in c)


def update_board(full_img=None):
    if full_img is None:
        full_img = ImageGrab.grab()
    size, rect = get_board_size()
    img = full_img.crop(rect)
    ys, xs = np.where(~mine_know)
    for x, y in zip(xs, ys):
        block_split = x * bw + 1, y * bh + 1, (x + 1) * bw - 1, (y + 1) * bh - 1
        img_block = img.crop(block_split)
        colors = img_block.convert("L").getcolors()
        signature = colors2signature(colors)
        board[y, x] = img_match[signature]


def activateWindow(hwnd):
    # SetForegroundWindow调用有一些限制，我们可以再调用之前输入一个键盘事件
    shell = win32.Dispatch("WScript.Shell")
    shell.SendKeys('%')
    win32gui.SetForegroundWindow(hwnd)


def new_board(w, h):
    board = np.zeros((h, w), dtype="int8")
    board.fill(-1)
    return board


def click(x, y, is_left_click=True):
    if is_left_click:
        win32api.SetCursorPos((x, y))
        win32api.mouse_event(
            win32con.MOUSEEVENTF_LEFTDOWN, 0, 0, 0, 0)
        win32api.mouse_event(
            win32con.MOUSEEVENTF_LEFTUP, 0, 0, 0, 0)
    else:
        win32api.SetCursorPos((x, y))
        win32api.mouse_event(
            win32con.MOUSEEVENTF_RIGHTDOWN, 0, 0, 0, 0)
        win32api.mouse_event(
            win32con.MOUSEEVENTF_RIGHTUP, 0, 0, 0, 0)


def click_mine_area(px, py, is_left_click=True):
    x, y = l + px * bw + bw // 2, t + py * bh + + bh // 2
    click(x, y, is_left_click)


def get_bound(x, y):
    "获取指定坐标周围4*4-9*9的边界范围"
    x1, x2 = max(x - 1, 0), min(x + 1, w - 1)
    y1, y2 = max(y - 1, 0), min(y + 1, h - 1)
    return x1, y1, x2, y2


def getItemNum(x, y):
    "获取指定坐标点周围没有点开和已确定有雷的格子的数量"
    # -1 表示还没有点开的格子
    # -2 表示红旗所在格子
    x1, y1, x2, y2 = get_bound(x, y)
    count = Counter(board[y1:y2 + 1, x1:x2 + 1].reshape(-1))
    return count[-1], count[-2]


def getUnknownPointList(x, y):
    "获取指定坐标点周围还没有点开的格子坐标列表"
    x1, y1, x2, y2 = get_bound(x, y)
    for py in range(y1, y2 + 1):
        for px in range(x1, x2 + 1):
            if px == x and py == y:
                continue
            if board[py, px] == -1:
                yield px, py


def getOpenNum(x, y):
    "获取指定坐标点周围有雷数标志的格子的数量"
    x1, y1, x2, y2 = get_bound(x, y)
    num = 0
    for py in range(y1, y2 + 1):
        for px in range(x1, x2 + 1):
            if px == x and py == y:
                continue
            num += (1 <= board[py, px] <= 8)
    return num


def srhAdjBlock(x, y):
    "搜索与数字位置相邻的未打开块，,使用flags标记已经访问过的位置"
    stack = [(x, y)]
    block = []
    while stack:
        x, y = stack.pop()
        if block_flag[y, x]:
            continue
        block_flag[y, x] = True
        block.append((x, y))
        for px, py in getUnknownPointList(x, y):
            if block_flag[py, px] or getOpenNum(px, py) <= 0:
                continue
            stack.append((px, py))
    return block


def getOpenNumList(x, y):
    "获取指定坐标点周围有雷数标志的格子坐标列表"
    x1, y1, x2, y2 = get_bound(x, y)
    num = 0
    for py in range(y1, y2 + 1):
        for px in range(x1, x2 + 1):
            if px == x and py == y:
                continue
            if 1 <= board[py, px] <= 8:
                yield px, py


def update_block(x, y, result):
    "根据随机算法的基础规则更新board周边块"
    result.clear()
    for px, py in getOpenNumList(x, y):
        unknownNum, redNum = getItemNum(px, py)
        # 实际雷数 小于 标记雷数目
        if board[py, px] < redNum:
            return False
        # 实际雷数 大于 未点开的格子数量+标记雷数目
        if board[py, px] > unknownNum + redNum:
            return False
        if unknownNum == 0:
            continue
        unknownPoints = getUnknownPointList(px, py)
        # 如果当前点周围雷数=未点+插旗，说明所有未点位置都是雷，可以全部插旗
        if board[py, px] == unknownNum + redNum:
            for px2, py2 in unknownPoints:
                result.append((px2, py2))
                board[py2, px2] = -2
        # 如果当前点周围雷数=插旗，说明所有未点位置都没有雷，可以全部点开
        if board[py, px] == redNum:
            for px2, py2 in unknownPoints:
                result.append((px2, py2))
                # 9表示临时无雷标记
                board[py2, px2] = 9
    return True


def updateNm2schemeCnt(block, mine_flag, nm2schemeCnt):
    "根据搜索得到的方案更新 nm2schemeCnt"
    nm = sum(mine_flag)
    if nm not in nm2schemeCnt:  # 新增一种方案
        nm2schemeCnt[nm] = [1, mine_flag.copy()]
    else:  # 更新
        v = nm2schemeCnt[nm]
        v[0] += 1
        v[1] += mine_flag


def srhScheme(block, mine_flag, k, nm2schemeCnt):
    """
    :param block: 连通块中的格子列表
    :param mine_flag: 是否有雷标记列表
    :param k: 从位置k开始搜索所有可行方案，结果存储于 nm2schemeCnt
    :param nm2schemeCnt: nm:(t,lstcellCnt)，
    代表这个联通块中,假设有nm颗雷的情况下共有t种方案，
    lstcellCnt表示各个格子中共有其中几种方案有雷
    :return:
    """
    x, y = block[k]
    res = []
    if board[y, x] == -1:  # 两种可能：有雷、无雷
        # 9作为作为临时无雷标记，-2作为临时有雷标记
        for m, n in [(0, 9), (1, -2)]:
            # m和n 对应了无雷和有雷两种情况下的标记
            mine_flag[k] = m
            board[y, x] = n
            # 根据基础规则更新周围点的标记，返回更新格子列表和成功标记
            if update_block(x, y, res):
                if k == len(block) - 1:  # 得到一个方案
                    updateNm2schemeCnt(block, mine_flag, nm2schemeCnt)
                else:
                    srhScheme(block, mine_flag, k + 1, nm2schemeCnt)
            # 恢复
            for px, py in res:
                board[py, px] = -1
        # 恢复
        board[y, x] = -1
    else:
        if board[y, x] == -2:
            mine_flag[k] = 1  # 有雷
        else:
            mine_flag[k] = 0  # 无雷
        # 根据规则1判断并更新周边块board标记，返回更新格子列表和成功标记
        if update_block(x, y, res):
            if k == len(block) - 1:  # 得到一个方案
                updateNm2schemeCnt(block, mine_flag, nm2schemeCnt)
            else:
                srhScheme(block, mine_flag, k + 1, nm2schemeCnt)
        # 恢复
        for px, py in res:
            board[py, px] = -1


def calDP(lk, nm, nm2schemeCnt_list):
    "考虑剩余雷数的可能方案数计算"
    ndp = 0
    k = lk[0]
    nm2schemeCnt = nm2schemeCnt_list[k]
    if len(lk) == 1:
        if nm in nm2schemeCnt:
            cnt, cnt_list = nm2schemeCnt[nm]
            ndp = cnt
    else:
        for k1 in nm2schemeCnt:
            lk1 = lk[1:]
            n1 = calDP(lk1, nm - k1, nm2schemeCnt_list)
            cnt, cnt_list = nm2schemeCnt[k1]
            ndp += n1 * cnt
    return ndp


class TimeOut:
    __executor = futures.ThreadPoolExecutor(1)

    def __init__(self, seconds):
        self.seconds = seconds

    def __call__(self, func):
        @functools.wraps(func)
        def wrapper(*args, **kw):
            future = TimeOut.__executor.submit(func, *args, **kw)
            return future.result(timeout=self.seconds)

        return wrapper


@TimeOut(1)
def getCLKPoints(board):
    "获取节点列表"
    block_flag.fill(0)
    # 联通块列表
    block_list = []
    # 孤立位置列表
    single_list = []
    pys, pxs = np.where(board == -1)
    for px, py in zip(pxs, pys):
        if block_flag[py, px]:
            continue
        if getOpenNum(px, py) > 0:
            block_list.append(srhAdjBlock(px, py))
        else:
            single_list.append((px, py))

    nm2schemeCnt_list = []
    nmin = 0
    nmax = 0
    for block in block_list:
        # 搜索联通块k的可行方案
        # 当前连通块中，每个可能的总雷数对应的方案数和每个格子在其中几种方案下有雷
        nm2schemeCnt = {}
        mine_flag = np.zeros(len(block), dtype='int16')
        srhScheme(block, mine_flag, 0, nm2schemeCnt)
        nm2schemeCnt_list.append(nm2schemeCnt)
        nmin += min(nm2schemeCnt)
        nmax += max(nm2schemeCnt)

    # 如果非联通块中包含的雷数大于0，考虑剩余雷数对概率影响
    if single_list:
        block_list.append(single_list)
        rnm2schemeCnt = {}  # 剩余格子概率计算
        n2 = len(single_list)
        for i in range(nmin, nmax + 1):
            n1 = mine_num - i
            mine_flag = [n1 for _ in range(n2)]
            rnm2schemeCnt[n1] = [n2, mine_flag]
        nm2schemeCnt_list.append(rnm2schemeCnt)

    pboard = np.zeros_like(board, dtype="uint8")
    # 基准有雷概率百分比
    nb = (board == -1).sum()
    pboard.fill(mine_num * 100 // nb)

    # 计算概率
    for k in range(len(nm2schemeCnt_list)):
        lk = [t for t in range(len(nm2schemeCnt_list)) if t != k]
        # 考虑剩余雷数的可能方案数计算
        NBcnt = 0
        block = block_list[k]
        Ncnt = [0] * len(block)
        for nm, (cnt, cnt_list) in nm2schemeCnt_list[k].items():
            if len(lk) > 0:
                ndp = calDP(lk, mine_num - nm, nm2schemeCnt_list)
            else:
                ndp = 1
            NBcnt += cnt * ndp
            for i in range(len(Ncnt)):
                Ncnt[i] += cnt_list[i] * ndp
        for i in range(len(Ncnt)):
            x, y = block[i]
            pboard[y, x] = (Ncnt[i] * 100 // NBcnt)

    pys, pxs = np.where(board == -1)
    res = set()
    for x, y in zip(pxs, pys):
        if pboard[y, x] == 100:
            # 有雷概率为100说明必定有雷，插旗
            res.add((x, y, False))
        elif pboard[y, x] == 0:
            # 有雷概率为0说明必定没有雷，点开
            res.add((x, y, True))

    def getFiveMapNum(p):
        "获取指定坐标点5*5地图内还没有点开格子的数量"
        # -1 表示还没有点开的格子
        # 获取指定坐标周围4*4-9*9的边界范围
        x, y = p
        x1, x2 = max(x - 2, 0), min(x + 2, w - 1)
        y1, y2 = max(y - 2, 0), min(y + 2, h - 1)
        return (board[y1:y2 + 1, x1:x2 + 1] == -1).sum()

    if len(res) == 0:
        # 计算最小比例列表
        pys, pxs = np.where((board == -1) & (pboard == pboard[board == -1].min()))
        points = list(zip(pxs, pys))
        if len(points) > 10:
            # 超过10个以上这样的点则随机选一个
            x, y = random.choice(points)
        elif len(points) > 0:
            # 否则取周围未点开格子最少的格子
            x, y = min(points, key=getFiveMapNum)
        else:
            return res
        res.add((x, y, True))
    return res


def base_op():
    # 筛选出所有未确定的数字位置 坐标
    pys, pxs = np.where((1 <= board) & (board <= 8) & (~visited))
    res = set()
    for x, y in zip(pxs, pys):
        boom_number = board[y, x]
        # 统计当前点周围 4*4-9*9 范围各类点的数量
        unknownNum, redNum = getItemNum(x, y)
        if unknownNum == 0:
            # 周围没有未点过的点可以直接忽略
            visited[y, x] = True
            continue
        # 获取周围的点的位置
        points = getUnknownPointList(x, y)
        if boom_number == unknownNum + redNum:
            # 如果当前点周围雷数=未点+插旗，说明所有未点位置都是雷，可以全部插旗
            visited[y, x] = True
            for px, py in points:
                res.add((px, py, False))
        elif boom_number == redNum:
            # 如果当前点周围雷数=插旗，说明所有未点位置都没有雷，可以全部点开
            visited[y, x] = True
            for px, py in points:
                res.add((px, py, True))
    return res


name = ""
hwnd = get_hwnd()
img_match = img_matchs[name]

activateWindow(hwnd)
time.sleep(0.1)
# 获取雷盘大小和位置
(w, h), rect = get_board_size()
mine_num = get_mine_num(hwnd)
print(f"宽：{w},高：{h},雷数：{mine_num}，雷盘位置：{rect}")
board = new_board(w, h)
# 已经确定是雷的位置
mine_know = np.zeros_like(board, dtype="bool")
update_board()
l, t, r, b = rect

# 标记周围已经完全确定的数字位置
visited = np.zeros_like(board, dtype="bool")
# 标记已经访问过的连通块
block_flag = np.zeros_like(board, dtype="bool")
while True:
    res = base_op()
    nb = (board == -1).sum()
    if len(res) == 0 and nb != 0:
        # py, px = random.choice(list(zip(*np.where(board == -1))))
        # res.add((px, py, True))
        tmp = board.copy()
        try:
            res = getCLKPoints(board)
        except futures._base.TimeoutError:
            board = tmp
            py, px = random.choice(list(zip(*np.where(board == -1))))
            res.add((px, py, True))
    for px, py, left in res:
        if left:
            click_mine_area(px, py)
        else:
            board[py, px] = -2
            mine_know[py, px] = True
    nb = (board == -1).sum()
    if nb == 0:
        print("顺利！！！")
        break
    if (board == -3).sum() != 0:
        print("踩到雷了，游戏结束！")
        break
    # 操作完毕后，更新最新的雷盘数据
    update_board()

运气好，一次性产生了一次更快的0.37秒的记录：

录制_2021_08_09_19_01_27_219

本文转载:CSDN博客

阅读排行

分类

归档