**小游戲 《開局托兒所》要求在規(guī)定時間內(nèi)通過組合不同的數(shù)字，使其相加結(jié)果為十，從而完成消除，直至屏幕所有數(shù)字清零。
對這個游戲感興趣，是因為它實際上是一個算法題。在一些代碼的幫助下，就可以把游戲變成一個 16x10 的矩陣求解。不考慮一些人肉戰(zhàn)神，我覺得這個游戲的排行榜更像是算法排行。
本文僅提供一些簡單的策略和數(shù)據(jù)分析，更優(yōu)算法有待高手提出。
數(shù)據(jù)分析
游戲界面
這個游戲的具體生成策略沒有仔細研究過，只能確定它不是完全隨機的，完全隨機數(shù)的1000次測試結(jié)果如下圖1，大部分分數(shù)集中在120左右。而游戲?qū)嶋H運行677次的測試結(jié)果如圖2，可以看到期望大概100多，低于隨機。測試說明游戲的矩陣生成故意增加了難度。
圖中不同顏色代表不同的游戲策略，詳見第二部分。
圖1 隨機生成矩陣
圖2 實際測試結(jié)果
策略分析
這個算法題的難點在于多步驟，如果是單步的求解什么，就類似于《最大子列和》問題，只要一步動態(tài)規(guī)劃就可以求解。多步消除的上一步會影響下一步，而且這個矩陣還挺大的，就有點圍棋那個意思了（或許可以train一個RL來求解）。
綜上，在此只提出一些簡單的策略與測試。先說結(jié)論，根據(jù)數(shù)據(jù)分析，較少數(shù)字的消除優(yōu)先級高，例如[1,9]的消除優(yōu)先級大于[1,2,2,5]；橫向的消除優(yōu)先級高于豎向；決定分數(shù)上限的是運氣，決定分數(shù)高低的是策略，例如以下151分的局面，6種策略能達到的分數(shù)就有較大區(qū)別，最低只有115，最高有151。具體算法見代碼。
圖3 策略對分數(shù)的影響
完整代碼
部分代碼參考：github GlintFreedom/CVGameScript
requirements:
- pytesseract
- pyautogui
- pygetwindow
- opencv-python
- numpy
# new
import pyautogui
import pygetwindow as gw
import time
import copy
import numpy as np
import pytesseract
import os
import cv2
from functools import partial
from multiprocessing import Pool
os.environ['TESSDATA_PREFIX'] = r'Tesseract-OCR\tessdata' # 替換為您的實際路徑
pytesseract.pytesseract.tesseract_cmd = r'Tesseract-OCR\tesseract.exe' # 替換為您的實際路徑
def get_score(img):
res = pytesseract.image_to_string(nmg, lang='eng', config='--psm 6 --oem 3 -c tessedit_char_whitelist=0123456789')
return int(res.strip())
def get_intersection(h_line, v_line):
rho_h, theta_h = h_line
rho_v, theta_v = v_line
# 計算交點坐標
x, y = np.linalg.solve(np.array([[np.cos(theta_h), np.sin(theta_h)],
[np.cos(theta_v), np.sin(theta_v)]]).astype(float),
np.array([rho_h, rho_v]).astype(float))
# 將交點坐標轉(zhuǎn)為整數(shù)
x, y = int(x), int(y)
return x, y
def find_all_squares(image):
gray = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
blurred = cv2.GaussianBlur(gray, (9, 9), 0)
sharpened = cv2.filter2D(blurred, -1, np.array([[0, -2, 0], [-2, 9, -2], [0, -2, 0]])) # 強化銳化處理
edges = cv2.Canny(sharpened, 200, 500)
# 使用霍夫線變換檢測直線
lines = cv2.HoughLines(edges, 1, np.pi / 180, threshold=175)
horizontal_lines = []
vertical_lines = []
if lines is not None:
for line in lines:
rho, theta = line[0]
a = np.cos(theta)
b = np.sin(theta)
x0 = a * rho
y0 = b * rho
# 轉(zhuǎn)換為圖像上的坐標
x1 = int(x0 + 1000 * (-b))
y1 = int(y0 + 1000 * (a))
x2 = int(x0 - 1000 * (-b))
y2 = int(y0 - 1000 * (a))
# 計算直線的角度
angle = np.degrees(np.arctan2(y2 - y1, x2 - x1))
# 根據(jù)角度進行分類，閾值可以根據(jù)實際情況調(diào)整
if 0 <= abs(angle) <= 2 or 178 <= abs(angle) <= 175:
horizontal_lines.append((rho, theta))
elif 88 <= abs(angle) <= 92:
vertical_lines.append((rho, theta))
# 對橫線按照從上到下的順序排序
horizontal_lines.sort(key=lambda line: line[0])
merged_horizontal_lines = []
merged_vertical_lines = []
merge_threshold = 3
previous_line = None
for current_line in horizontal_lines:
if previous_line is None or current_line[0] - previous_line[0] > merge_threshold:
merged_horizontal_lines.append((current_line[0], current_line[1]))
previous_line = current_line
# 對豎線按照從左到右的順序排序
vertical_lines.sort(key=lambda line: line[0])
previous_line = None
for current_line in vertical_lines:
if previous_line is not None and current_line[0] - previous_line[0] <= merge_threshold:
# 合并相鄰的水平線
merged_vertical_lines[-1] = (current_line[0], current_line[1])
else:
merged_vertical_lines.append((current_line[0], current_line[1]))
previous_line = current_line
found_squares = []
threshold = 3
# 尋找正方形
for i, h_line in enumerate(merged_horizontal_lines):
if i >= len(merged_horizontal_lines)-1:
break
next_h_line = merged_horizontal_lines[i+1]
for j, v_line in enumerate(merged_vertical_lines):
if j >= len(merged_vertical_lines) - 1:
break
next_v_line = merged_vertical_lines[j+1]
p_x1, p_y1 = get_intersection(h_line, v_line)
p_x2, p_y2 = get_intersection(next_h_line, next_v_line)
is_square = abs(abs(p_x2-p_x1) - abs(p_y2-p_y1)) <= threshold and abs(p_x2-p_x1) > 15
if is_square:
found_squares.append((p_x1, p_y1, p_x2, p_y2))
return found_squares
def crop_region(image, square):
(x1, y1, x2, y2) = square
# 通過切片提取矩形區(qū)域
cropped_region = image[y1:y2, x1:x2]
return cropped_region
def recognize_digit(image):
# 預(yù)處理圖像，例如二值化處理
gray_image = cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)
_, thresholded = cv2.threshold(gray_image, 127, 255, cv2.THRESH_BINARY)
# 使用 pytesseract 進行數(shù)字識別
digit = pytesseract.image_to_string(thresholded, lang='eng', config='--psm 6 digits -c tessedit_char_whitelist=123456789') # --psm 6 表示按行識別
return digit.strip()
def recognize_matrix(image, thread):
squares = find_all_squares(image)
get_crop = partial(crop_region, image)
crop_images = list(map(get_crop, squares))
worker = Pool(thread)
recognized_digits = worker.map(recognize_digit, crop_images)
worker.close()
worker.join()
digits_matrix = []
for i in range(16):
digits_matrix.append((recognized_digits[i * 10:i * 10 + 10]))
return digits_matrix, squares
class eliminater:
def __init__(self, window_title="開局托兒所"):
self.window = gw.getWindowsWithTitle(window_title)[0]
self.width = self.window.width
self.height = self.window.height
self.s1list = [1,9,2,8]
self.runtime = 0
self.thread = 3
self.thd = 80
def action(self, begin_x, end_x, begin_y, end_y,duration=0.1):
x1, y1, x2, y2 = self.digit_squares[begin_x * 10 + begin_y]
x1, y1 = ((x1 + x2) / 2, (y1 + y2) / 2)
x3, y3, x4, y4 = self.digit_squares[(end_x - 1) * 10 + end_y - 1]
x2, y2 = ((x3 + x4) / 2, (y3 + y4) / 2)
pyautogui.moveTo(self.window.left + x1, self.window.top+self.height//7 + y1)
pyautogui.mouseDown()
pyautogui.moveTo(self.window.left + x2, self.window.top+self.height//7 + y2, duration=duration)
pyautogui.mouseUp()
def restart(self):
# 設(shè)置
x = self.window.left + 40
y = self.window.top + 70
pyautogui.click(x, y)
time.sleep(1)
# 放棄
x = self.window.left+ (self.width // 2)
y = self.window.top + 500
pyautogui.click(x, y)
time.sleep(1)
# 確定
y = self.window.top + 520
pyautogui.click(x, y)
time.sleep(1)
# 開始游戲
y = self.window.top + 780
pyautogui.click(x, y)
time.sleep(2)
@property
def score(self):
if hasattr(self, 'cal_matrix'):
return 160 - np.sum(self.cal_matrix.astype(bool))
else:
print('未初始化')
return 0
def record(self, x):
with open('歷史分數(shù).txt', 'a') as file:
if x[1]==0:
file.write(f'\n')
else:
file.write(f'\t策略{x[0]}{x[1]}: {self.score},')
def init_game(self):
time.sleep(1)
print('\t截圖中……')
self.capture_window()
if self.frame is not None:
print('\t識別圖像中，請耐心等待……')
matrix, self.digit_squares = recognize_matrix(self.frame, self.thread)
try:
self.matrix = np.array(matrix).astype(int)
assert self.matrix.shape == (16,10)
return True
except Exception as e:
print('\t識別錯誤，嘗試重啟')
self.trys += 1
return False
time.sleep(3)
else:
print("截圖失??！")
return False
def run_strategy(self, strategy, action=False):
self.cal_matrix = self.matrix.copy()
if strategy[0] == 1:
self.cal_two_x(action=action)
elif strategy[0] == 2:
self.cal_two_y(action=action)
if strategy[1] == 1:
self.cal_all_x(action=action)
elif strategy[1] == 2:
self.cal_all_y(action=action)
# return self.score
def run(self, continues=True):
self.thread = int(input('OCR線程數(shù)（推薦3）：'))
self.thd = int(input('請輸入分數(shù)閾值（低于該值將自動放棄重開）：'))
print(f"開始運行...")
self.trys = 0
while continues:
if self.trys > 5:
print('錯誤次數(shù)過多，終止運行')
break
if not self.init_game():
self.restart()
continue
self.runtime += 1
print('\t識別完畢，執(zhí)行策略……')
go = [0,1]
self.run_strategy([0,1])
self.record([0,1])
maxscore = self.score
print(f'\t策略1分數(shù):{self.score}')
# print('\t識別完畢，執(zhí)行策略2……')
self.run_strategy([0,2])
self.record([0,2])
if self.score> maxscore:
maxscore = self.score
go = [0,2]
print(f'\t策略2分數(shù):{self.score}')
# print('\t識別完畢，執(zhí)行策略3……')
self.run_strategy([1,1])
self.record([1,1])
if self.score> maxscore:
maxscore = self.score
go = [1,1]
print(f'\t策略3分數(shù):{self.score}')
# print('\t識別完畢，執(zhí)行策略4……')
self.run_strategy([1,2])
self.record([1,2])
if self.score> maxscore:
maxscore = self.score
go = [1,2]
print(f'\t策略4分數(shù):{self.score}')
# print('\t識別完畢，執(zhí)行策略5……')
self.run_strategy([2,1])
self.record([2,1])
if self.score> maxscore:
maxscore = self.score
go = [2,1]
print(f'\t策略5分數(shù):{self.score}')
# print('\t識別完畢，執(zhí)行策略6……')
self.run_strategy([2,2])
self.record([2,2])
if self.score> maxscore:
maxscore = self.score
go = [2,2]
print(f'\t策略6分數(shù):{self.score}')
self.record([0,0])
self.trys = 0
if maxscore < self.thd:
print(f'\t均小于目標{self.thd}，放棄本次')
self.restart()
else:
print('\t執(zhí)行最優(yōu)策略', go)
self.run_strategy(go, action=True)
self.capture_window(record=True)
time.sleep(100)
print(f"游戲{self.runtime}結(jié)束, 開始下一次...")
# 點擊再次挑戰(zhàn)
x = self.window.left + (self.width // 2)
y = self.window.top + 620
pyautogui.click(x, y)
time.sleep(1)
def capture_window(self, record=False):
try:
try:
self.window.activate()
except:
pass
time.sleep(1)
screenshot = pyautogui.screenshot(region=(self.window.left, self.window.top,
self.window.width, self.window.height))
frame = cv2.cvtColor(np.array(screenshot), cv2.COLOR_RGB2BGR)
if record:
cv2.imwrite(f'result_{int(time.time())}.png', frame)
else:
self.frame = frame[self.height//7:-self.height//25,:,:]
cv2.imwrite('shot.png', self.frame)
except IndexError:
print("窗口未找到")
return None
def cal_recur(self, x_len=1, y_len=1, action=False):
if x_len>15 or y_len>9:
return
else:
for begin_x in range(0, 16-x_len+1):
for begin_y in range(0, 10-y_len+1):
_sum = np.sum(self.cal_matrix[begin_x:begin_x+x_len,begin_y: begin_y + y_len])
if _sum == 10:
self.cal_matrix[begin_x:begin_x+x_len,begin_y: begin_y + y_len] = 0
if action:
self.action(begin_x, begin_x+x_len, begin_y, begin_y + y_len)
self.cal_recur(x_len=x_len+1, y_len=y_len, action=action)
self.cal_recur(x_len=x_len, y_len=y_len+1, action=action)
def cal_all_x(self, End=False, action=False):
if End:
# if not action:
# print(f'\t\t求解任意和后分數(shù)：{self.score}')
return
else:
End=True
for x_len in range(1, 16):
for y_len in range(1, 10):
for begin_x in range(0, 16-x_len+1):
for begin_y in range(0, 10-y_len+1):
_sum = np.sum(self.cal_matrix[begin_x:begin_x+x_len,begin_y: begin_y + y_len])
if _sum == 10:
self.cal_matrix[begin_x:begin_x+x_len,begin_y: begin_y + y_len] = 0
if action:
self.action(begin_x, begin_x+x_len, begin_y, begin_y + y_len)
End = False
self.cal_all_x(End=End, action=action)
def cal_all_y(self, End=False, action=False):
if End:
# if not action:
# print(f'\t\t求解任意和后分數(shù)：{self.score}')
return
else:
End=True
for y_len in range(1, 10):
for x_len in range(1, 16):
for begin_x in range(0, 16-x_len+1):
for begin_y in range(0, 10-y_len+1):
_sum = np.sum(self.cal_matrix[begin_x:begin_x+x_len,begin_y: begin_y + y_len])
if _sum == 10:
self.cal_matrix[begin_x:begin_x+x_len,begin_y: begin_y + y_len] = 0
if action:
self.action(begin_x, begin_x+x_len, begin_y, begin_y + y_len)
End = False
self.cal_all_y(End=End, action=action)
def cal_two_x(self, End=False, action=False):
if End:
# if not action:
# print(f'\t\t求解兩數(shù)和后分數(shù)：{self.score}')
return
else:
End=True
for begin_x in range(0, 16):
for begin_y in range(0, 10):
# 搜索右邊
if self.cal_matrix[begin_x, begin_y] ==0:
continue
if len(self.s1list) >0 and self.cal_matrix[begin_x, begin_y] not in self.s1list:
continue
for x in range(begin_x+1, 16):
if self.cal_matrix[x, begin_y] ==0:
continue
elif self.cal_matrix[begin_x, begin_y]+self.cal_matrix[x, begin_y] ==10:
self.cal_matrix[x, begin_y] = 0
self.cal_matrix[begin_x, begin_y] = 0
if action:
self.action(begin_x, x+1, begin_y, begin_y+1)
End = False
break
else:
break
# 搜索左邊
for x in range(begin_x-1, -1, -1):
if x < 0:
break
if self.cal_matrix[x, begin_y] ==0:
continue
elif self.cal_matrix[begin_x, begin_y]+self.cal_matrix[x, begin_y] ==10:
self.cal_matrix[x, begin_y] = 0
self.cal_matrix[begin_x, begin_y] = 0
if action:
self.action(x, begin_x+1, begin_y, begin_y+1)
End = False
break
else:
break
# 搜索下面
for y in range(begin_y+1, 10):
if self.cal_matrix[begin_x, y] ==0:
continue
elif self.cal_matrix[begin_x, begin_y]+self.cal_matrix[begin_x, y] ==10:
self.cal_matrix[begin_x, begin_y] = 0
self.cal_matrix[begin_x, y] = 0
if action:
self.action(begin_x, begin_x+1, begin_y, y+1)
End = False
break
else:
break
# 搜索上面
for y in range(begin_y-1, -1, -1):
if y < 0:
break
if self.cal_matrix[begin_x, y] ==0:
continue
elif self.cal_matrix[begin_x, begin_y]+self.cal_matrix[begin_x, y] ==10:
self.cal_matrix[begin_x, begin_y] = 0
self.cal_matrix[begin_x, y] = 0
if action:
self.action(begin_x, begin_x+1, y, begin_y+1)
End = False
break
else:
break
self.cal_two_x(End=End, action=action)
def cal_two_y(self, End=False, action=False):
if End:
# if not action:
# print(f'\t\t求解兩數(shù)和后分數(shù)：{self.score}')
return
else:
End=True
for begin_y in range(0, 10):
for begin_x in range(0, 16):
# 搜索右邊
if self.cal_matrix[begin_x, begin_y] ==0:
continue
if len(self.s1list) >0 and self.cal_matrix[begin_x, begin_y] not in self.s1list:
continue
for x in range(begin_x+1, 16):
if self.cal_matrix[x, begin_y] ==0:
continue
elif self.cal_matrix[begin_x, begin_y]+self.cal_matrix[x, begin_y] ==10:
self.cal_matrix[x, begin_y] = 0
self.cal_matrix[begin_x, begin_y] = 0
if action:
self.action(begin_x, x+1, begin_y, begin_y+1)
End = False
break
else:
break
# 搜索左邊
for x in range(begin_x-1, -1, -1):
if x < 0:
break
if self.cal_matrix[x, begin_y] ==0:
continue
elif self.cal_matrix[begin_x, begin_y]+self.cal_matrix[x, begin_y] ==10:
self.cal_matrix[x, begin_y] = 0
self.cal_matrix[begin_x, begin_y] = 0
if action:
self.action(x, begin_x+1, begin_y, begin_y+1)
End = False
break
else:
break
# 搜索下面
for y in range(begin_y+1, 10):
if self.cal_matrix[begin_x, y] ==0:
continue
elif self.cal_matrix[begin_x, begin_y]+self.cal_matrix[begin_x, y] ==10:
self.cal_matrix[begin_x, begin_y] = 0
self.cal_matrix[begin_x, y] = 0
if action:
self.action(begin_x, begin_x+1, begin_y, y+1)
End = False
break
else:
break
# 搜索上面
for y in range(begin_y-1, -1, -1):
if y < 0:
break
if self.cal_matrix[begin_x, y] ==0:
continue
elif self.cal_matrix[begin_x, begin_y]+self.cal_matrix[begin_x, y] ==10:
self.cal_matrix[begin_x, begin_y] = 0
self.cal_matrix[begin_x, y] = 0
if action:
self.action(begin_x, begin_x+1, y, begin_y+1)
End = False
break
else:
break
self.cal_two_y(End=End, action=action)
if __name__ == '__main__':
runner = eliminater()
runner.run()
