大家好，我是小小明，上次的我帶大家玩了數獨：

《讓程式自動玩數獨游戲讓你秒變骨灰級數獨玩家》
《Python呼叫C語言實作數獨計算邏輯提速100倍》

今天我將帶你用非常高端的姿勢玩掃雷，本文涉及的技術點非常多，非常硬核，萬字長文，高能預警，

本文從影像識別到windows訊息處理，最終到直接的記憶體修改，中間寫了一套基于概率分析的掃雷AI演算法，模擬雷界的高階玩家的操作，輕松拿下高級的世界紀錄，

據說掃雷的世界記錄是：

對于中級我玩的大概就是這情況，直接超過世界紀錄的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

文章目錄

掃雷游戲的介紹
- 簡介
- 掃雷程式下載
基于影像分析的桌面前端互動程式
- 獲取掃雷程式的視窗位置
- 根據視窗坐標抓取雷區影像
- 讀取剩余地雷數量
- 讀取雷區資料
- 自動操作掃雷程式
- 前端互動程式整體封裝
自動掃雷演算法
- Monkey隨機演算法玩中級掃雷
- 基于概率分析的掃雷演算法
- - 演算法的總體思想
  - 搜索連通區域
  - 統計每個連通塊中的每個格子在多少種解中是有雷的
  - 考慮剩余雷數，計算精確概率
  - 基于概率的貪心演算法
  - 概率分析演算法代碼的整體封裝
- 引入概率分析演算法進行測驗
能不能更快更高的勝率？
- 記憶體外掛原理
- 實作程序
- 記憶體外掛的完整代碼
能超越初級的0.49秒的世界記錄嗎？

掃雷游戲的介紹

簡介

《掃雷》是一款大眾類的益智小游戲，游戲的基本操作包括左鍵單擊（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/

基于影像分析的桌面前端互動程式

獲取掃雷程式的視窗位置

這步需要呼叫windows API查找掃雷游戲的視窗，需要傳入掃雷游戲得標題和類名，這個可以通過inspect.exe工具進行獲取，

inspect.exe工具是系統自帶工具，我通過everything獲取到路徑為：

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

打開掃雷游戲后，就可以通過以下代碼獲取掃雷游戲的視窗物件：

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

注意：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

然后拆分出每個數字影像并灰度處理：

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)

把雷數設定成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)

可以看到雷區的資料都能正確匹配并獲取，

自動操作掃雷程式

下面我們封裝一個控制滑鼠點擊的方法：

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定式和變形等，不過對于程式而言不見得一定要記錄這些固定規則，經過實測基于概率模型已經能夠包含所有的定式結果，

演算法的總體思想

對于一個雷區，是否有雷會存在多個互相制約的聯通塊區域，不同聯通塊之間不存在互相制約，例如下面的雷區存在兩個聯通塊區域：

對于每一個連通塊共有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))

通過二次右擊得到的問號知道每個連通塊區域的位置（運行完會自動清除問號，只留下影像）：

統計每個連通塊中的每個格子在多少種解中是有雷的

在拆分出連通塊區域后，我們就可以開始統計統計每個連通塊中的每個格子在多少種解中是有雷的，

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檔案可查看：

https://docs.microsoft.com/en-us/windows/win32/api/memoryapi/nf-memoryapi-readprocessmemory
https://docs.microsoft.com/en-us/windows/win32/api/winuser/nf-winuser-getwindowthreadprocessid
https://docs.microsoft.com/en-us/windows/win32/api/processthreadsapi/nf-processthreadsapi-openprocess

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

在WM_LBUTTONUP上設定斷點后，運行，然后單步步過到地址01001FE1后跟隨：

跟隨后我們在此處可以找到棋盤資料：

可以看到地址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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/293055.html

標籤：其他

上一篇：Unity 之 Excel表格轉換為Unity用的檔案格式 -- ScriptableObject，Json，XML 全部搞定

下一篇：【游戲開發高階】從零到一教你Unity使用ToLua實作熱更新（含Demo工程 | LuaFramework | 增量 | HotUpdate）

基于概率分析的智能AI掃雷程式秒破雷界世界紀錄

文章目錄

掃雷游戲的介紹

簡介

掃雷程式下載

基于影像分析的桌面前端互動程式

獲取掃雷程式的視窗位置

根據視窗坐標抓取雷區影像

讀取剩余地雷數量

讀取雷區資料

自動操作掃雷程式

前端互動程式整體封裝

自動掃雷演算法

Monkey隨機演算法玩中級掃雷

基于概率分析的掃雷演算法

演算法的總體思想

搜索連通區域

統計每個連通塊中的每個格子在多少種解中是有雷的

考慮剩余雷數，計算精確概率

基于概率的貪心演算法

概率分析演算法代碼的整體封裝

引入概率分析演算法進行測驗

能不能更快更高的勝率？

記憶體外掛原理

實作程序

記憶體外掛的完整代碼

能超越初級的0.49秒的世界記錄嗎？