大家好，我是小小明，上次的我?guī)Т蠹彝媪藬?shù)獨(dú)：
《讓程序自動(dòng)玩數(shù)獨(dú)游戲讓你秒變骨灰級數(shù)獨(dú)玩家 》 《Python調(diào)用C語言實(shí)現(xiàn)數(shù)獨(dú)計(jì)算邏輯提速100倍 》 今天我將帶你用非常高端的姿勢玩掃雷。本文涉及的技術(shù)點(diǎn)非常多，非常硬核，萬字長文，高能預(yù)警。
本文從圖像識別到windows消息處理，最終到直接的內(nèi)存修改。中間寫了一套基于概率分析的掃雷AI算法，模擬雷界的高階玩家的操作，輕松拿下高級的世界紀(jì)錄。
據(jù)說掃雷的世界記錄是：
對于中級我玩的大概就是這情況，直接超過世界紀(jì)錄的7秒：
對于高級也輕松超過世界紀(jì)錄：
初級世界記錄居然是0.49秒，雖然有點(diǎn)難，但我們還是可以超越（0.4秒和0.37秒）：
《掃雷》是一款大眾類的益智小游戲，游戲的基本操作包括左鍵單擊（Left Click）、右鍵單擊（Right Click）、雙擊（Chording）三種。其中左鍵用于打開安全的格子；右鍵用于標(biāo)記地雷；雙擊在一個(gè)數(shù)字周圍的地雷標(biāo)記完時(shí)，相當(dāng)于對數(shù)字周圍未打開的方塊均進(jìn)行一次左鍵單擊操作。
基本游戲步驟：開局后，首先要用鼠標(biāo)在灰色區(qū)域點(diǎn)一下，會(huì)出現(xiàn)一些數(shù)字，1代表在這個(gè)數(shù)字周圍有1個(gè)地雷，2表示在它周圍有2個(gè)雷，3表示在它周圍有3個(gè)雷；在確信是雷的地方，點(diǎn)一下右鍵，用右鍵標(biāo)識出該出的地雷；確信不是雷的地方，按一下鼠標(biāo)左鍵，打開相應(yīng)的數(shù)字。
OD和win98掃雷下載
鏈接：http://pan.baidu.com/s/1gfA10K7 密碼：eiqp
Arbiter版掃雷下載
http:///BBS/
這步需要調(diào)用windows API查找掃雷游戲的窗口，需要傳入掃雷游戲得標(biāo)題和類名，這個(gè)可以通過inspect.exe工具進(jìn)行獲取。
inspect.exe工具是系統(tǒng)自帶工具，我通過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"窗口坐標(biāo)，左上角：( { left} , { top} ),右下角：( { right} , { bottom} )" )
w, h = right- left, bottom- top
print ( f"窗口寬度： { w} ，高度： { h} " )
else :
print ( "未找到窗口" )
窗口坐標(biāo)，左上角：(86,86),右下角：(592,454)
窗口寬度：506，高度：368
可以通過代碼激活并前置窗口：
https://docs.microsoft.com/zh-cn/windows/win32/api/winuser/nf-winuser-setforegroundwindow
不過有時(shí)SetForegroundWindow調(diào)用有一些限制導(dǎo)致失敗，我們可以再調(diào)用之前輸入一個(gè)鍵盤事件：
import win32com. client as win32
def activateWindow ( hwnd) :
# SetForegroundWindow調(diào)用有一些限制，我們可以再調(diào)用之前輸入一個(gè)鍵盤事件
shell = win32. Dispatch( "WScript.Shell" )
shell. SendKeys( '%' )
win32gui. SetForegroundWindow( hwnd)
activateWindow( hwnd)
前面我們獲取到了掃雷程序的窗口坐標(biāo)，下面我就可以獲取雷區(qū)的圖像：
from PIL import ImageGrab
# 根據(jù)窗口坐標(biāo)抓取雷區(qū)圖像
rect = ( left+ 15 , top+ 101 , right- 11 , bottom- 11 )
img = ImageGrab. grab( ) . crop( rect)
print ( img. size)
img
注意：15，101等偏移量是我對98版掃雷反復(fù)測試得到的坐標(biāo)，若你使用掃雷網(wǎng)下載的Arbiter可能坐標(biāo)會(huì)發(fā)生變化。
基于雷區(qū)圖像可以計(jì)算出雷盤大小：
# 每個(gè)方塊16*16
bw, bh = 16 , 16
def get_board_size ( ) :
# 橫向有w個(gè)方塊
l, t, r, b = ( left+ 15 , top+ 101 , right- 11 , bottom- 11 )
w = ( r - l) // bw
# 縱向有h個(gè)方塊
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)
先截圖顯示地雷數(shù)量的圖片：
num_img = ImageGrab. grab( ) . crop( ( left+ 20 , top+ 62 , left+ 20 + 39 , top+ 62 + 23 ) )
num_img
然后拆分出每個(gè)數(shù)字圖像并灰度處理：
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)
把雷數(shù)設(shè)置成8后重新運(yùn)行上面的代碼，在執(zhí)行以下代碼，則可以看到各個(gè)像素點(diǎn)的演示值：
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,
于是可以很清楚知道，每個(gè)數(shù)字都由7個(gè)小塊組成，我們可以對這7塊每塊任取一個(gè)像素點(diǎn)獲取顏色值。將這7塊的顏色值是否等于76來表示一個(gè)二進(jìn)制，最終轉(zhuǎn)成一個(gè)整數(shù)：
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
經(jīng)過逐個(gè)測試，最終得到每個(gè)數(shù)字對應(yīng)的特征碼，最終封裝成如下方法：
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( )
經(jīng)測試可以準(zhǔn)確讀取，左上角雷區(qū)的數(shù)量。
通過以下代碼可以拆分出雷區(qū)每個(gè)格子的圖像：
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) )
可以獲取每個(gè)格子的灰度圖片的顏色列表：
colors = img_block. convert( "L" ) . getcolors( )
colors
[(54, 128), (148, 192), (54, 255)]
結(jié)果表示了(出現(xiàn)次數(shù)，顏色值)組成的列表。
為了方便匹配，將其轉(zhuǎn)換為16進(jìn)制并文本拼接：
def colors2signature ( colors) :
return "" . join( hex ( b) [ 2 : ] . zfill( 2 ) for c in colors for b in c)
然后就可以得到整個(gè)雷區(qū)的每個(gè)單元格組成的特征碼的分布：
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)]
經(jīng)過反復(fù)測試終于得到各種情況的特征碼：
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'
# 數(shù)字1-8表示周圍有幾個(gè)雷
# 0 表示已經(jīng)點(diǎn)開是空白的格子
# -1 表示還沒有點(diǎn)開的格子
# -2 表示紅旗所在格子
# -3 表示踩到雷了已經(jīng)失敗
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 }
嘗試匹配雷區(qū)數(shù)據(jù)：
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)
可以看到雷區(qū)的數(shù)據(jù)都能正確匹配并獲取。
下面我們封裝一個(gè)控制鼠標(biāo)點(diǎn)擊的方法：
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)
調(diào)用示例：
import time
import win32con
activateWindow( hwnd)
time. sleep( 0.2 )
click_mine_area( 3 , 3 )
注意：第一次操作程序，需要點(diǎn)擊激活窗口，激活需要等待幾毫秒生效后開始操作。
更快的操作方法：
可以直接發(fā)生windows消息，來模擬鼠標(biāo)操作，這樣組件直接在底層消息級別接收到鼠標(biāo)點(diǎn)擊的事件，缺點(diǎn)是看不到鼠標(biāo)的移動(dòng)。封裝一下：
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) )
# 雷區(qū)格子在窗體上的起始坐標(biāo)
offest_x, offest_y = 0xC , 0x37
# 每個(gè)格子方塊的寬度和高度 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)
調(diào)用示例：
message_click_mine_area( 3 , 4 , False )
注意：windows消息級的鼠標(biāo)操作不需要激活窗口就可以直接操作。
import win32api
import win32con
import numpy as np
import win32com. client as win32
from PIL import ImageGrab
import win32gui
# 每個(gè)方塊16*16
bw, bh = 16 , 16
# 剩余雷數(shù)圖像特征碼
code2num = {
247 : 0 , 50 : 1 , 189 : 2 ,
187 : 3 , 122 : 4 , 203 : 5 ,
207 : 6 , 178 : 7 , 255 : 8 , 251 : 9
}
# 雷區(qū)圖像特征碼
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'
# 數(shù)字1-8表示周圍有幾個(gè)雷
# 0 表示已經(jīng)點(diǎn)開是空白的格子
# -1 表示還沒有點(diǎn)開的格子
# -2 表示紅旗所在格子
# -3 表示踩到雷了已經(jīng)失敗
# -4 表示被玩家自己標(biāo)記為問號
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 }
# 雷區(qū)格子在窗體上的起始坐標(biāo)
offest_x, offest_y = 0xC , 0x37
def get_board_size ( hwnd) :
left, top, right, bottom = win32gui. GetWindowRect( hwnd)
# 橫向有w個(gè)方塊
l, t, r, b = ( left+ 15 , top+ 101 , right- 11 , bottom- 11 )
w = ( r - l) // bw
# 縱向有h個(gè)方塊
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調(diào)用有一些限制，我們可以再調(diào)用之前輸入一個(gè)鍵盤事件
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 ( "剩余雷數(shù)：" , 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 ( "剩余雷數(shù)：" , mine_num)
board = new_board( w, h)
message_click_mine_area( 5 , 5 )
update_board( board)
print ( board)
寬：16,高：16，雷盤位置：(230, 240, 486, 496)
剩余雷數(shù)： 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]]
在完成了前面的前端交互程序后，我們就可以開始開發(fā)自動(dòng)掃雷的算法邏輯了。首先用一個(gè)最基礎(chǔ)的規(guī)則玩中級。
基礎(chǔ)規(guī)則：
如果當(dāng)前點(diǎn)周圍雷數(shù)=未點(diǎn)+插旗，說明所有未點(diǎn)位置都是雷，可以全部插旗 如果當(dāng)前點(diǎn)周圍雷數(shù)=插旗，說明所有未點(diǎn)位置都沒有雷，可以全部點(diǎn)開 遍歷完所有位置后，未發(fā)現(xiàn)能夠點(diǎn)開或標(biāo)記為雷的點(diǎn)，則隨機(jī)選一個(gè)點(diǎn) from itertools import product
import time
import random
from collections import Counter
def get_bound ( x, y) :
"獲取指定坐標(biāo)周圍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) :
"獲取指定坐標(biāo)點(diǎn)周圍已經(jīng)點(diǎn)開、沒有點(diǎn)開和已確定有雷的格子的數(shù)量"
# 0 表示已經(jīng)點(diǎn)開是空白的格子
# -1 表示還沒有點(diǎn)開的格子
# -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) :
"獲取指定坐標(biāo)點(diǎn)周圍還沒有點(diǎn)開的格子坐標(biāo)列表"
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 ( "剩余雷數(shù)：" , mine_num)
board = new_board( w, h)
update_board( board)
# 點(diǎn)擊剩余雷數(shù)位置激活窗口
l, t, r, b = rect
click( l+ 16 , t- 30 )
time. sleep( 0.1 )
# 標(biāo)記周圍已經(jīng)完全確定的數(shù)字位置
flag = np. zeros_like( board, dtype= "bool" )
while True :
# 篩選出所有未確定的數(shù)字位置 坐標(biāo)
pys, pxs = np. where( ( 1 <= board) & ( board <= 8 ) & ( ~ flag) )
res = set ( )
for x, y in zip ( pxs, pys) :
boom_number = board[ y, x]
# 統(tǒng)計(jì)當(dāng)前點(diǎn)周圍4*4-9*9范圍各類點(diǎn)的數(shù)量
openNum, unknownNum, redNum = getItemNum( x, y)
if unknownNum == 0 :
# 周圍沒有未點(diǎn)過的點(diǎn)可以直接忽略
flag[ y, x] = True
continue
# 獲取周圍的點(diǎn)的位置
points = getUnknownPointList( x, y)
if boom_number == unknownNum+ redNum:
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=未點(diǎn)+插旗，說明所有未點(diǎn)位置都是雷，可以全部插旗
flag[ y, x] = True
for px, py in points:
res. add( ( px, py, False ) )
elif boom_number == redNum:
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=插旗，說明所有未點(diǎn)位置都沒有雷，可以全部點(diǎn)開
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 :
# 本輪循環(huán)沒有進(jìn)行任何操作，說明沒有任何可以確定點(diǎn)擊的地方，只能隨機(jī)點(diǎn)擊
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 ( "踩到雷了，游戲結(jié)束！" )
break
update_board( board)
然后就可以體驗(yàn)一把中級了：
不過據(jù)說中級世界紀(jì)錄僅7秒：
嘖嘖，程序會(huì)比人玩的還慢？那我縮小一下延遲，再玩一下：
不過咱們要是用這種取隨機(jī)的方法來玩高級，勝率簡直會(huì)慘不忍睹：
前面的基本規(guī)則在高級下，勝率過于低下，下面我們完善我們的掃描算法。
熟悉掃雷的高玩?zhèn)兌挤浅Ｇ宄呃椎臏p法公式，21定式和變形等。不過對于程序而言不見得一定要記錄這些固定規(guī)則，經(jīng)過實(shí)測基于概率模型已經(jīng)能夠包含所有的定式結(jié)果。
對于一個(gè)雷區(qū)，是否有雷會(huì)存在多個(gè)互相制約的聯(lián)通塊區(qū)域，不同聯(lián)通塊之間不存在互相制約。例如下面的雷區(qū)存在兩個(gè)聯(lián)通塊區(qū)域：
對于每一個(gè)連通塊共有n個(gè)格子沒有打開，每個(gè)格子都存在有雷和沒有雷兩種情況，那么至多存在
2
n
\large 2^n
2 n
如果沒有概率等于0或100的格子，則需要根據(jù)概率取有雷概率最低的格子，多個(gè)格子概率最低時(shí)取周圍未點(diǎn)開格子數(shù)最多的格子。
首先第一步，我們需要找出這些連通區(qū)域的坐標(biāo)：
def getOpenNum ( x, y) :
"獲取指定坐標(biāo)點(diǎn)周圍有雷數(shù)標(biāo)志的格子的數(shù)量"
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) :
"搜索與數(shù)字位置相鄰的未打開塊，,使用flags標(biāo)記已經(jīng)訪問過的位置"
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" )
# 聯(lián)通塊列表
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) )
為了查看我們找到的連通塊是否準(zhǔn)確，我定義了如下方法進(jìn)行測試：
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) )
通過二次右擊得到的問號知道每個(gè)連通塊區(qū)域的位置（運(yùn)行完會(huì)自動(dòng)清除問號，只留下圖像）：
在拆分出連通塊區(qū)域后，我們就可以開始統(tǒng)計(jì)統(tǒng)計(jì)每個(gè)連通塊中的每個(gè)格子在多少種解中是有雷的。
def getOpenNumList ( x, y) :
"獲取指定坐標(biāo)點(diǎn)周圍有雷數(shù)標(biāo)志的格子坐標(biāo)列表"
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) :
# 根據(jù)隨機(jī)算法的基礎(chǔ)規(guī)則更新board周邊塊
result. clear( )
for px, py in getOpenNumList( x, y) :
unknownNum, redNum = getItemNum( px, py)
# 實(shí)際雷數(shù) 小于 標(biāo)記雷數(shù)目
if board[ py, px] < redNum:
return False
# 實(shí)際雷數(shù) 大于 未點(diǎn)開的格子數(shù)量+標(biāo)記雷數(shù)目
if board[ py, px] > unknownNum + redNum:
return False
if unknownNum == 0 :
continue
unknownPoints = getUnknownPointList( px, py)
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=未點(diǎn)+插旗，說明所有未點(diǎn)位置都是雷，可以全部插旗
if board[ py, px] == unknownNum + redNum:
for px2, py2 in unknownPoints:
result. append( ( px2, py2) )
board[ py2, px2] = - 2
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=插旗，說明所有未點(diǎn)位置都沒有雷，可以全部點(diǎn)開
if board[ py, px] == redNum:
for px2, py2 in unknownPoints:
result. append( ( px2, py2) )
# 9表示臨時(shí)無雷標(biāo)記
board[ py2, px2] = 9
return True
def updateNm2schemeCnt ( block, mine_flag, nm2schemeCnt) :
"根據(jù)搜索得到的方案更新 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: 是否有雷標(biāo)記列表
:param k: 從位置k開始搜索所有可行方案，結(jié)果存儲(chǔ)于 nm2schemeCnt
:param nm2schemeCnt: nm:(t,lstcellCnt)，
代表這個(gè)聯(lián)通塊中,假設(shè)有nm顆雷的情況下共有t種方案，
lstcellCnt表示各個(gè)格子中共有其中幾種方案有雷
:return:
"""
x, y = block[ k]
res = [ ]
if board[ y, x] == - 1 : # 兩種可能：有雷、無雷
# 9作為作為臨時(shí)無雷標(biāo)記，-2作為臨時(shí)有雷標(biāo)記
for m, n in [ ( 0 , 9 ) , ( 1 , - 2 ) ] :
# m和n 對應(yīng)了無雷和有雷兩種情況下的標(biāo)記
mine_flag[ k] = m
board[ y, x] = n
# 根據(jù)基礎(chǔ)規(guī)則更新周圍點(diǎn)的標(biāo)記，返回更新格子列表和成功標(biāo)記
if update_block( x, y, res) :
if k == len ( block) - 1 : # 得到一個(gè)方案
updateNm2schemeCnt( block, mine_flag, nm2schemeCnt)
else :
srhScheme( block, mine_flag, k+ 1 , nm2schemeCnt)
# 恢復(fù)
for px, py in res:
board[ py, px] = - 1
# 恢復(fù)
board[ y, x] = - 1
else :
if board[ y, x] == - 2 :
mine_flag[ k] = 1 # 有雷
else :
mine_flag[ k] = 0 # 無雷
# 根據(jù)規(guī)則1判斷并更新周邊塊board標(biāo)記，返回更新格子列表和成功標(biāo)記
if update_block( x, y, res) :
if k == len ( block) - 1 : # 得到一個(gè)方案
updateNm2schemeCnt( block, mine_flag, nm2schemeCnt)
else :
srhScheme( block, mine_flag, k+ 1 , nm2schemeCnt)
# 恢復(fù)
for px, py in res:
board[ py, px] = - 1
調(diào)用：
nm2schemeCnt_list = [ ]
nmin = 0
nmax = 0
for block in block_list:
# 搜索聯(lián)通塊k的可行方案
# 當(dāng)前連通塊中，每個(gè)可能的總雷數(shù)對應(yīng)的方案數(shù)和每個(gè)格子在其中幾種方案下有雷
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)]}]
因?yàn)橛惺Ｓ嗬讛?shù)的限制，聯(lián)通塊內(nèi)部的概率并不準(zhǔn)確。
在枚舉過程中，對每個(gè)聯(lián)通塊我們可以統(tǒng)計(jì)出
b
l
o
c
k
C
n
t
s
\Large blockCnt_{s}
b l o c k C n t s ?
c
e
l
l
C
n
t
x
,
s
\Large cellCnt_{x,s}
c e l l C n t x , s ?
那么我們依次考慮每個(gè)格子的勝率。除開格子本身所在的聯(lián)通塊不看，考慮其它所有聯(lián)通塊（假設(shè)一共有
n
n
n
D
P
i
,
j
\Large DP_{i,j}
D P i , 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}
D P i , j ? = s = 0 ∑ m a x ? D P i ? 1 , j ? s ? ? b l o c k C n t s ?
假設(shè)當(dāng)前剩下 mine 個(gè)雷，枚舉當(dāng)前格子所在聯(lián)通塊的雷數(shù) 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}
b l o c k C n t s ? ? D P n ? 1 , m i n e ? 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}
c e l l C n t x , s ? ? D P n ? 1 , m i n e ? s ?
首先向前面的方案列表加入孤立位置列表，使剩余格子參與概率計(jì)算：
# 如果非聯(lián)通塊中包含的雷數(shù)大于0，考慮剩余雷數(shù)對概率影響
if single_list:
block_list. append( single_list)
rnm2schemeCnt = { } # 剩余格子概率計(jì)算
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)
然后進(jìn)行計(jì)算：
# 考慮剩余雷數(shù)的可能方案數(shù)計(jì)算
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" )
# 基準(zhǔn)有雷概率百分比
pboard. fill( mine_num* 100 // nb)
# 計(jì)算概率
for k in range ( len ( nm2schemeCnt_list) ) :
lk = [ t for t in range ( len ( nm2schemeCnt_list) ) if t != k]
# 考慮剩余雷數(shù)的可能方案數(shù)計(jì)算
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
思想：如果沒有確定有雷或無雷的格子，那么點(diǎn)擊概率最小的格子，概率相同時(shí)點(diǎn)附近5*5的地圖里未點(diǎn)開格子數(shù)最少的格子。
首先篩選出篩選出有雷概率為100和0的位置，用于后續(xù)點(diǎn)擊和標(biāo)記：
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說明必定沒有雷，點(diǎn)開
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)}
一下子就找出了這么多確定有雷和無雷的格子。
通過以下代碼全部點(diǎn)擊掉：
for r in res:
message_click_mine_area( * r)
假如沒有必定有雷和無雷的位置就只能基于概率進(jìn)行選取：
if len ( res) == 0 :
# 計(jì)算最小比例列表
pys, pxs = np. where( ( board == - 1 ) & ( pboard == pboard[ board == - 1 ] . min ( ) ) )
points = list ( zip ( pxs, pys) )
if len ( points) > 10 :
# 超過10個(gè)以上這樣的點(diǎn)則隨機(jī)選一個(gè)
x, y = random. choice( points)
elif len ( points) > 0 :
# 否則取周圍未點(diǎn)開格子最少的格子
x, y = min ( points, key= getFiveMapNum)
else :
return res
res. add( ( x, y, True ) )
def getOpenNum ( x, y) :
"獲取指定坐標(biāo)點(diǎn)周圍有雷數(shù)標(biāo)志的格子的數(shù)量"
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) :
"搜索與數(shù)字位置相鄰的未打開塊，,使用flags標(biāo)記已經(jīng)訪問過的位置"
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) :
"獲取指定坐標(biāo)點(diǎn)周圍有雷數(shù)標(biāo)志的格子坐標(biāo)列表"
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) :
"根據(jù)隨機(jī)算法的基礎(chǔ)規(guī)則更新board周邊塊"
result. clear( )
for px, py in getOpenNumList( x, y) :
unknownNum, redNum = getItemNum( px, py)
# 實(shí)際雷數(shù) 小于 標(biāo)記雷數(shù)目
if board[ py, px] < redNum:
return False
# 實(shí)際雷數(shù) 大于 未點(diǎn)開的格子數(shù)量+標(biāo)記雷數(shù)目
if board[ py, px] > unknownNum + redNum:
return False
if unknownNum == 0 :
continue
unknownPoints = getUnknownPointList( px, py)
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=未點(diǎn)+插旗，說明所有未點(diǎn)位置都是雷，可以全部插旗
if board[ py, px] == unknownNum + redNum:
for px2, py2 in unknownPoints:
result. append( ( px2, py2) )
board[ py2, px2] = - 2
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=插旗，說明所有未點(diǎn)位置都沒有雷，可以全部點(diǎn)開
if board[ py, px] == redNum:
for px2, py2 in unknownPoints:
result. append( ( px2, py2) )
# 9表示臨時(shí)無雷標(biāo)記
board[ py2, px2] = 9
return True
def updateNm2schemeCnt ( block, mine_flag, nm2schemeCnt) :
"根據(jù)搜索得到的方案更新 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: 是否有雷標(biāo)記列表
:param k: 從位置k開始搜索所有可行方案，結(jié)果存儲(chǔ)于 nm2schemeCnt
:param nm2schemeCnt: nm:(t,lstcellCnt)，
代表這個(gè)聯(lián)通塊中,假設(shè)有nm顆雷的情況下共有t種方案，
lstcellCnt表示各個(gè)格子中共有其中幾種方案有雷
:return:
"""
x, y = block[ k]
res = [ ]
if board[ y, x] == - 1 : # 兩種可能：有雷、無雷
# 9作為作為臨時(shí)無雷標(biāo)記，-2作為臨時(shí)有雷標(biāo)記
for m, n in [ ( 0 , 9 ) , ( 1 , - 2 ) ] :
# m和n 對應(yīng)了無雷和有雷兩種情況下的標(biāo)記
mine_flag[ k] = m
board[ y, x] = n
# 根據(jù)基礎(chǔ)規(guī)則更新周圍點(diǎn)的標(biāo)記，返回更新格子列表和成功標(biāo)記
if update_block( x, y, res) :
if k == len ( block) - 1 : # 得到一個(gè)方案
updateNm2schemeCnt( block, mine_flag, nm2schemeCnt)
else :
srhScheme( block, mine_flag, k+ 1 , nm2schemeCnt)
# 恢復(fù)
for px, py in res:
board[ py, px] = - 1
# 恢復(fù)
board[ y, x] = - 1
else :
if board[ y, x] == - 2 :
mine_flag[ k] = 1 # 有雷
else :
mine_flag[ k] = 0 # 無雷
# 根據(jù)規(guī)則1判斷并更新周邊塊board標(biāo)記，返回更新格子列表和成功標(biāo)記
if update_block( x, y, res) :
if k == len ( block) - 1 : # 得到一個(gè)方案
updateNm2schemeCnt( block, mine_flag, nm2schemeCnt)
else :
srhScheme( block, mine_flag, k+ 1 , nm2schemeCnt)
# 恢復(fù)
for px, py in res:
board[ py, px] = - 1
def calDP ( lk, nm, nm2schemeCnt_list) :
"考慮剩余雷數(shù)的可能方案數(shù)計(jì)算"
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) :
"獲取節(jié)點(diǎn)列表"
flags. fill( 0 )
# 聯(lián)通塊列表
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:
# 搜索聯(lián)通塊k的可行方案
# 當(dāng)前連通塊中，每個(gè)可能的總雷數(shù)對應(yīng)的方案數(shù)和每個(gè)格子在其中幾種方案下有雷
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)
# 如果非聯(lián)通塊中包含的雷數(shù)大于0，考慮剩余雷數(shù)對概率影響
if single_list:
block_list. append( single_list)
rnm2schemeCnt = { } # 剩余格子概率計(jì)算
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" )
# 基準(zhǔn)有雷概率百分比
pboard. fill( mine_num* 100 // nb)
# 計(jì)算概率
for k in range ( len ( nm2schemeCnt_list) ) :
lk = [ t for t in range ( len ( nm2schemeCnt_list) ) if t != k]
# 考慮剩余雷數(shù)的可能方案數(shù)計(jì)算
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說明必定沒有雷，點(diǎn)開
res. add( ( x, y, True ) )
if len ( res) == 0 :
# 計(jì)算最小比例列表
pys, pxs = np. where( ( board == - 1 ) & ( pboard == pboard[ board == - 1 ] . min ( ) ) )
points = list ( zip ( pxs, pys) )
if len ( points) > 10 :
# 超過10個(gè)以上這樣的點(diǎn)則隨機(jī)選一個(gè)
x, y = random. choice( points)
elif len ( points) > 0 :
# 否則取周圍未點(diǎn)開格子最少的格子
x, y = min ( points, key= getFiveMapNum)
else :
return res
res. add( ( x, y, True ) )
return res
調(diào)用示例：
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
# 每個(gè)方塊16*16
bw, bh = 16 , 16
# 剩余雷數(shù)圖像特征碼
code2num = {
247 : 0 , 50 : 1 , 189 : 2 ,
187 : 3 , 122 : 4 , 203 : 5 ,
207 : 6 , 178 : 7 , 255 : 8 , 251 : 9
}
# 雷區(qū)圖像特征碼
# 數(shù)字1-8表示周圍有幾個(gè)雷
# 0 表示已經(jīng)點(diǎn)開是空白的格子
# -1 表示還沒有點(diǎn)開的格子
# -2 表示紅旗所在格子
# -3 表示踩到雷了已經(jīng)失敗
# -4 表示被玩家自己標(biāo)記為問號
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) )
# 雷區(qū)格子在窗體上的起始坐標(biāo)
offest_x, offest_y = 0xC , 0x37
def get_board_size ( hwnd) :
left, top, right, bottom = win32gui. GetWindowRect( hwnd)
# 橫向有w個(gè)方塊
l, t, r, b = ( left + 15 , top + 101 , right - 11 , bottom - 11 )
w = ( r - l) // bw
# 縱向有h個(gè)方塊
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調(diào)用有一些限制，我們可以再調(diào)用之前輸入一個(gè)鍵盤事件
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) :
"獲取指定坐標(biāo)周圍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) :
"獲取指定坐標(biāo)點(diǎn)周圍沒有點(diǎn)開和已確定有雷的格子的數(shù)量"
# -1 表示還沒有點(diǎn)開的格子
# -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) :
"獲取指定坐標(biāo)點(diǎn)周圍還沒有點(diǎn)開的格子坐標(biāo)列表"
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) :
"獲取指定坐標(biāo)點(diǎn)周圍有雷數(shù)標(biāo)志的格子的數(shù)量"
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) :
"搜索與數(shù)字位置相鄰的未打開塊，,使用flags標(biāo)記已經(jīng)訪問過的位置"
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) :
"獲取指定坐標(biāo)點(diǎn)周圍有雷數(shù)標(biāo)志的格子坐標(biāo)列表"
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) :
"根據(jù)隨機(jī)算法的基礎(chǔ)規(guī)則更新board周邊塊"
result. clear( )
for px, py in getOpenNumList( x, y) :
unknownNum, redNum = getItemNum( px, py)
# 實(shí)際雷數(shù) 小于 標(biāo)記雷數(shù)目
if board[ py, px] < redNum:
return False
# 實(shí)際雷數(shù) 大于 未點(diǎn)開的格子數(shù)量+標(biāo)記雷數(shù)目
if board[ py, px] > unknownNum + redNum:
return False
if unknownNum == 0 :
continue
unknownPoints = getUnknownPointList( px, py)
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=未點(diǎn)+插旗，說明所有未點(diǎn)位置都是雷，可以全部插旗
if board[ py, px] == unknownNum + redNum:
for px2, py2 in unknownPoints:
result. append( ( px2, py2) )
board[ py2, px2] = - 2
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=插旗，說明所有未點(diǎn)位置都沒有雷，可以全部點(diǎn)開
if board[ py, px] == redNum:
for px2, py2 in unknownPoints:
result. append( ( px2, py2) )
# 9表示臨時(shí)無雷標(biāo)記
board[ py2, px2] = 9
return True
def updateNm2schemeCnt ( block, mine_flag, nm2schemeCnt) :
"根據(jù)搜索得到的方案更新 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: 是否有雷標(biāo)記列表
:param k: 從位置k開始搜索所有可行方案，結(jié)果存儲(chǔ)于 nm2schemeCnt
:param nm2schemeCnt: nm:(t,lstcellCnt)，
代表這個(gè)聯(lián)通塊中,假設(shè)有nm顆雷的情況下共有t種方案，
lstcellCnt表示各個(gè)格子中共有其中幾種方案有雷
:return:
"""
x, y = block[ k]
res = [ ]
if board[ y, x] == - 1 : # 兩種可能：有雷、無雷
# 9作為作為臨時(shí)無雷標(biāo)記，-2作為臨時(shí)有雷標(biāo)記
for m, n in [ ( 0 , 9 ) , ( 1 , - 2 ) ] :
# m和n 對應(yīng)了無雷和有雷兩種情況下的標(biāo)記
mine_flag[ k] = m
board[ y, x] = n
# 根據(jù)基礎(chǔ)規(guī)則更新周圍點(diǎn)的標(biāo)記，返回更新格子列表和成功標(biāo)記
if update_block( x, y, res) :
if k == len ( block) - 1 : # 得到一個(gè)方案
updateNm2schemeCnt( block, mine_flag, nm2schemeCnt)
else :
srhScheme( block, mine_flag, k + 1 , nm2schemeCnt)
# 恢復(fù)
for px, py in res:
board[ py, px] = - 1
# 恢復(fù)
board[ y, x] = - 1
else :
if board[ y, x] == - 2 :
mine_flag[ k] = 1 # 有雷
else :
mine_flag[ k] = 0 # 無雷
# 根據(jù)規(guī)則1判斷并更新周邊塊board標(biāo)記，返回更新格子列表和成功標(biāo)記
if update_block( x, y, res) :
if k == len ( block) - 1 : # 得到一個(gè)方案
updateNm2schemeCnt( block, mine_flag, nm2schemeCnt)
else :
srhScheme( block, mine_flag, k + 1 , nm2schemeCnt)
# 恢復(fù)
for px, py in res:
board[ py, px] = - 1
def calDP ( lk, nm, nm2schemeCnt_list) :
"考慮剩余雷數(shù)的可能方案數(shù)計(jì)算"
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) :
"獲取節(jié)點(diǎn)列表"
block_flag. fill( 0 )
# 聯(lián)通塊列表
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:
# 搜索聯(lián)通塊k的可行方案
# 當(dāng)前連通塊中，每個(gè)可能的總雷數(shù)對應(yīng)的方案數(shù)和每個(gè)格子在其中幾種方案下有雷
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)
# 如果非聯(lián)通塊中包含的雷數(shù)大于0，考慮剩余雷數(shù)對概率影響
if single_list:
block_list. append( single_list)
rnm2schemeCnt = { } # 剩余格子概率計(jì)算
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" )
# 基準(zhǔn)有雷概率百分比
nb = ( board == - 1 ) . sum ( )
pboard. fill( mine_num * 100 // nb)
# 計(jì)算概率
for k in range ( len ( nm2schemeCnt_list) ) :
lk = [ t for t in range ( len ( nm2schemeCnt_list) ) if t != k]
# 考慮剩余雷數(shù)的可能方案數(shù)計(jì)算
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說明必定沒有雷，點(diǎn)開
res. add( ( x, y, True ) )
def getFiveMapNum ( p) :
"獲取指定坐標(biāo)點(diǎn)5*5地圖內(nèi)還沒有點(diǎn)開格子的數(shù)量"
# -1 表示還沒有點(diǎn)開的格子
# 獲取指定坐標(biāo)周圍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 :
# 計(jì)算最小比例列表
pys, pxs = np. where( ( board == - 1 ) & ( pboard == pboard[ board == - 1 ] . min ( ) ) )
points = list ( zip ( pxs, pys) )
if len ( points) > 10 :
# 超過10個(gè)以上這樣的點(diǎn)則隨機(jī)選一個(gè)
x, y = random. choice( points)
elif len ( points) > 0 :
# 否則取周圍未點(diǎn)開格子最少的格子
x, y = min ( points, key= getFiveMapNum)
else :
return res
res. add( ( x, y, True ) )
return res
def base_op ( ) :
# 篩選出所有未確定的數(shù)字位置 坐標(biāo)
pys, pxs = np. where( ( 1 <= board) & ( board <= 8 ) & ( ~ flag) )
res = set ( )
for x, y in zip ( pxs, pys) :
boom_number = board[ y, x]
# 統(tǒng)計(jì)當(dāng)前點(diǎn)周圍 4*4-9*9 范圍各類點(diǎn)的數(shù)量
unknownNum, redNum = getItemNum( x, y)
if unknownNum == 0 :
# 周圍沒有未點(diǎn)過的點(diǎn)可以直接忽略
flag[ y, x] = True
continue
# 獲取周圍的點(diǎn)的位置
points = getUnknownPointList( x, y)
if boom_number == unknownNum + redNum:
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=未點(diǎn)+插旗，說明所有未點(diǎn)位置都是雷，可以全部插旗
flag[ y, x] = True
for px, py in points:
res. add( ( px, py, False ) )
elif boom_number == redNum:
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=插旗，說明所有未點(diǎn)位置都沒有雷，可以全部點(diǎn)開
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} ,雷數(shù)： { mine_num} ，雷盤位置： { rect} " )
board = new_board( w, h)
update_board( board)
l, t, r, b = rect
# 點(diǎn)擊任意位置激活窗口
click( l + 50 , t - 30 )
time. sleep( 0.1 )
# 標(biāo)記周圍已經(jīng)完全確定的數(shù)字位置
flag = np. zeros_like( board, dtype= "bool" )
# 標(biāo)記已經(jīng)訪問過的連通塊
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 ( "剩余雷數(shù)：" , mine_num)
if nb == 0 :
print ( "順利！！！" )
break
if ( board == - 3 ) . sum ( ) != 0 :
print ( "踩到雷了，游戲結(jié)束！" )
break
# 操作完畢后，更新最新的雷盤數(shù)據(jù)
update_board( board)
現(xiàn)在這就是引入概率分析的完整代碼，現(xiàn)在我們玩下高級試一下：
可以看到5秒內(nèi)就解決了高級。
上次的玩數(shù)獨(dú)一文中，有讀者在公眾號留言實(shí)錘開掛，我只想呵呵一笑。今天就讓你們見識一下什么叫真正的開掛。
最終能達(dá)到什么效果呢？任何級別耗時(shí)在1秒以內(nèi)，勝率為100%。
看下效果：
分析出雷盤數(shù)據(jù)的內(nèi)存位置，調(diào)用kernel32.dll的API讀取內(nèi)存。
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上設(shè)置斷點(diǎn)后，運(yùn)行，然后單步步過到地址01001FE1后跟隨：
跟隨后我們在此處可以找到棋盤數(shù)據(jù)：
可以看到地址010055330前雙字為0x28(十進(jìn)制為40)這表示雷數(shù)，后面雙字分別是寬度和高度，0x10表示棋盤的邊，0x8F表示雷。
所以我們的外掛想做的極端點(diǎn)，只需要將此段內(nèi)存的0x8F全部改成0x8E，就直接勝利了，但是沒有必要。我們只需要能讀取雷區(qū)數(shù)據(jù)就行。
首先，我們獲取掃雷程序的窗口對象，并從系統(tǒng)動(dòng)態(tài)鏈接庫中獲取讀寫內(nèi)存的方法：
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
連接到指定進(jìn)程，用于直接讀取其內(nèi)存數(shù)據(jù)：
import win32process
import win32con
hreadID, processID = win32process. GetWindowThreadProcessId( hwnd)
process = OpenProcess( win32con. PROCESS_ALL_ACCESS, 0 , processID)
讀取剩余雷數(shù)和寬高：
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} ，剩余雷數(shù)： { mine_num} " )
寬：9，高：9，剩余雷數(shù)：10
讀取并打印棋盤數(shù)據(jù)：
max_w, max_h = 30 , 24
# 外圍有一個(gè)值為 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,
注意：由于需要讀取的棋盤數(shù)據(jù)，數(shù)據(jù)范圍較大，所以需要申明了一個(gè)bytesRead作為緩沖區(qū)，否則可能出現(xiàn)無法讀取數(shù)據(jù)的情況。
然后就可以迅速解開全部位置：
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) )
# 雷區(qū)格子在窗體上的起始坐標(biāo)
offest_x, offest_y = 0xC , 0x37
# 每個(gè)格子方塊的寬度和高度 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} ，剩余雷數(shù)： { mine_num} " )
max_w, max_h = 30 , 24
# 外圍有一個(gè)值為 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) )
# 雷區(qū)格子在窗體上的起始坐標(biāo)
offest_x, offest_y = 0xC , 0x37
# 每個(gè)格子方塊的寬度和高度 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)
體驗(yàn)一下：
實(shí)際上按照專業(yè)掃雷選手的說法，初級掃雷并不對時(shí)間設(shè)置世界記錄，關(guān)于掃雷的世界記錄有且僅有十項(xiàng)，參考：
初級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
要突破3bv/s的世界記錄對于程序而言過于簡單，因?yàn)槿丝隙ú粫?huì)比程序點(diǎn)的快。對于0.49秒這個(gè)所謂的世界記錄，我們也只需要多運(yùn)行幾遍就可以達(dá)到了。
不過win98版本的掃雷，不支持1秒以內(nèi)的時(shí)間統(tǒng)計(jì)，所以首先我們需要更換為掃雷網(wǎng)提供的掃雷進(jìn)行操作。效果：
對于掃雷網(wǎng)提供的掃雷游戲，雷盤的像素點(diǎn)偏移有些變化，下面按照同樣的思路計(jì)算出特征碼后編寫如下代碼，能同時(shí)適配兩種掃雷程序。
同時(shí)為了速度更快我們不再程序去操作標(biāo)旗而是自行變量記錄一下：
"""
小小明的代碼
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
# 每個(gè)方塊16*16
bw, bh = 16 , 16
# 剩余雷數(shù)圖像特征碼
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 ( ) :
"""
雷區(qū)圖像特征碼
數(shù)字1-8表示周圍有幾個(gè)雷
0 表示已經(jīng)點(diǎn)開是空白的格子
-1 表示還沒有點(diǎn)開的格子
-2 表示紅旗所在格子
-3 表示踩到雷了已經(jīng)失敗
"""
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 ( ) :
"先搜索普通掃雷，再搜索掃雷網(wǎng)的掃雷"
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個(gè)方塊
l, t, r, b = ( left + o1, top + o2, right + o3, bottom + o4)
w = ( r - l) // bw
# 縱向有h個(gè)方塊
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調(diào)用有一些限制，我們可以再調(diào)用之前輸入一個(gè)鍵盤事件
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) :
"獲取指定坐標(biāo)周圍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) :
"獲取指定坐標(biāo)點(diǎn)周圍沒有點(diǎn)開和已確定有雷的格子的數(shù)量"
# -1 表示還沒有點(diǎn)開的格子
# -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) :
"獲取指定坐標(biāo)點(diǎn)周圍還沒有點(diǎn)開的格子坐標(biāo)列表"
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) :
"獲取指定坐標(biāo)點(diǎn)周圍有雷數(shù)標(biāo)志的格子的數(shù)量"
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) :
"搜索與數(shù)字位置相鄰的未打開塊，,使用flags標(biāo)記已經(jīng)訪問過的位置"
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) :
"獲取指定坐標(biāo)點(diǎn)周圍有雷數(shù)標(biāo)志的格子坐標(biāo)列表"
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) :
"根據(jù)隨機(jī)算法的基礎(chǔ)規(guī)則更新board周邊塊"
result. clear( )
for px, py in getOpenNumList( x, y) :
unknownNum, redNum = getItemNum( px, py)
# 實(shí)際雷數(shù) 小于 標(biāo)記雷數(shù)目
if board[ py, px] < redNum:
return False
# 實(shí)際雷數(shù) 大于 未點(diǎn)開的格子數(shù)量+標(biāo)記雷數(shù)目
if board[ py, px] > unknownNum + redNum:
return False
if unknownNum == 0 :
continue
unknownPoints = getUnknownPointList( px, py)
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=未點(diǎn)+插旗，說明所有未點(diǎn)位置都是雷，可以全部插旗
if board[ py, px] == unknownNum + redNum:
for px2, py2 in unknownPoints:
result. append( ( px2, py2) )
board[ py2, px2] = - 2
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=插旗，說明所有未點(diǎn)位置都沒有雷，可以全部點(diǎn)開
if board[ py, px] == redNum:
for px2, py2 in unknownPoints:
result. append( ( px2, py2) )
# 9表示臨時(shí)無雷標(biāo)記
board[ py2, px2] = 9
return True
def updateNm2schemeCnt ( block, mine_flag, nm2schemeCnt) :
"根據(jù)搜索得到的方案更新 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: 是否有雷標(biāo)記列表
:param k: 從位置k開始搜索所有可行方案，結(jié)果存儲(chǔ)于 nm2schemeCnt
:param nm2schemeCnt: nm:(t,lstcellCnt)，
代表這個(gè)聯(lián)通塊中,假設(shè)有nm顆雷的情況下共有t種方案，
lstcellCnt表示各個(gè)格子中共有其中幾種方案有雷
:return:
"""
x, y = block[ k]
res = [ ]
if board[ y, x] == - 1 : # 兩種可能：有雷、無雷
# 9作為作為臨時(shí)無雷標(biāo)記，-2作為臨時(shí)有雷標(biāo)記
for m, n in [ ( 0 , 9 ) , ( 1 , - 2 ) ] :
# m和n 對應(yīng)了無雷和有雷兩種情況下的標(biāo)記
mine_flag[ k] = m
board[ y, x] = n
# 根據(jù)基礎(chǔ)規(guī)則更新周圍點(diǎn)的標(biāo)記，返回更新格子列表和成功標(biāo)記
if update_block( x, y, res) :
if k == len ( block) - 1 : # 得到一個(gè)方案
updateNm2schemeCnt( block, mine_flag, nm2schemeCnt)
else :
srhScheme( block, mine_flag, k + 1 , nm2schemeCnt)
# 恢復(fù)
for px, py in res:
board[ py, px] = - 1
# 恢復(fù)
board[ y, x] = - 1
else :
if board[ y, x] == - 2 :
mine_flag[ k] = 1 # 有雷
else :
mine_flag[ k] = 0 # 無雷
# 根據(jù)規(guī)則1判斷并更新周邊塊board標(biāo)記，返回更新格子列表和成功標(biāo)記
if update_block( x, y, res) :
if k == len ( block) - 1 : # 得到一個(gè)方案
updateNm2schemeCnt( block, mine_flag, nm2schemeCnt)
else :
srhScheme( block, mine_flag, k + 1 , nm2schemeCnt)
# 恢復(fù)
for px, py in res:
board[ py, px] = - 1
def calDP ( lk, nm, nm2schemeCnt_list) :
"考慮剩余雷數(shù)的可能方案數(shù)計(jì)算"
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) :
"獲取節(jié)點(diǎn)列表"
block_flag. fill( 0 )
# 聯(lián)通塊列表
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:
# 搜索聯(lián)通塊k的可行方案
# 當(dāng)前連通塊中，每個(gè)可能的總雷數(shù)對應(yīng)的方案數(shù)和每個(gè)格子在其中幾種方案下有雷
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)
# 如果非聯(lián)通塊中包含的雷數(shù)大于0，考慮剩余雷數(shù)對概率影響
if single_list:
block_list. append( single_list)
rnm2schemeCnt = { } # 剩余格子概率計(jì)算
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" )
# 基準(zhǔn)有雷概率百分比
nb = ( board == - 1 ) . sum ( )
pboard. fill( mine_num * 100 // nb)
# 計(jì)算概率
for k in range ( len ( nm2schemeCnt_list) ) :
lk = [ t for t in range ( len ( nm2schemeCnt_list) ) if t != k]
# 考慮剩余雷數(shù)的可能方案數(shù)計(jì)算
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說明必定沒有雷，點(diǎn)開
res. add( ( x, y, True ) )
def getFiveMapNum ( p) :
"獲取指定坐標(biāo)點(diǎn)5*5地圖內(nèi)還沒有點(diǎn)開格子的數(shù)量"
# -1 表示還沒有點(diǎn)開的格子
# 獲取指定坐標(biāo)周圍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 :
# 計(jì)算最小比例列表
pys, pxs = np. where( ( board == - 1 ) & ( pboard == pboard[ board == - 1 ] . min ( ) ) )
points = list ( zip ( pxs, pys) )
if len ( points) > 10 :
# 超過10個(gè)以上這樣的點(diǎn)則隨機(jī)選一個(gè)
x, y = random. choice( points)
elif len ( points) > 0 :
# 否則取周圍未點(diǎn)開格子最少的格子
x, y = min ( points, key= getFiveMapNum)
else :
return res
res. add( ( x, y, True ) )
return res
def base_op ( ) :
# 篩選出所有未確定的數(shù)字位置 坐標(biāo)
pys, pxs = np. where( ( 1 <= board) & ( board <= 8 ) & ( ~ visited) )
res = set ( )
for x, y in zip ( pxs, pys) :
boom_number = board[ y, x]
# 統(tǒng)計(jì)當(dāng)前點(diǎn)周圍 4*4-9*9 范圍各類點(diǎn)的數(shù)量
unknownNum, redNum = getItemNum( x, y)
if unknownNum == 0 :
# 周圍沒有未點(diǎn)過的點(diǎn)可以直接忽略
visited[ y, x] = True
continue
# 獲取周圍的點(diǎn)的位置
points = getUnknownPointList( x, y)
if boom_number == unknownNum + redNum:
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=未點(diǎn)+插旗，說明所有未點(diǎn)位置都是雷，可以全部插旗
visited[ y, x] = True
for px, py in points:
res. add( ( px, py, False ) )
elif boom_number == redNum:
# 如果當(dāng)前點(diǎn)周圍雷數(shù)=插旗，說明所有未點(diǎn)位置都沒有雷，可以全部點(diǎn)開
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} ,雷數(shù)： { mine_num} ，雷盤位置： { rect} " )
board = new_board( w, h)
# 已經(jīng)確定是雷的位置
mine_know = np. zeros_like( board, dtype= "bool" )
update_board( )
l, t, r, b = rect
# 標(biāo)記周圍已經(jīng)完全確定的數(shù)字位置
visited = np. zeros_like( board, dtype= "bool" )
# 標(biāo)記已經(jīng)訪問過的連通塊
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 ( "踩到雷了，游戲結(jié)束！" )
break
# 操作完畢后，更新最新的雷盤數(shù)據(jù)
update_board( )
運(yùn)氣好，一次性產(chǎn)生了一次更快的0.37秒的記錄：
