ホームページ  >  記事  >  バックエンド開発  >  すごいですね、Python を使用して世界記録を破りました!

すごいですね、Python を使用して世界記録を破りました!

王林
王林転載
2023-04-20 13:19:061237ブラウズ

すごいですね、Python を使用して世界記録を破りました!

皆さんこんにちは、

Python OpenCV を使用して自動地雷除去を実装し、世界記録を破りました。まずその効果を見てみましょう。

すごいですね、Python を使用して世界記録を破りました!

中級 - 0.74 秒 3BV/S=60.81

マインスイーパは、昔から古典的なゲーム (グラフィック カード テスト) として知られている人も多いと思います。タイム(ソフトウェア)で、多くの人は中国の雷聖、郭偉佳のことを聞いたことがあるでしょう。彼は中国でナンバーワン、そして世界で第二位の掃海艇でもあります。 Windows 9x 時代に誕生した古典ゲームであるマインスイーパには、テンポの速い高精度なマウス操作、素早い応答性、記録を樹立する爽快感など、独特の魅力が昔から現在まで色濃く残っています。マインスイーパがもたらすすべてのこと マインスイーパの仲間たちがもたらす独特の興奮は、マインスイーパにしかありません。

1. 準備

自動地雷除去ソフトウェアのセットを作成する準備をする前に、次のツール/ソフトウェア/環境を準備する必要があります。

- 開発環境

  1. Python3 環境 - 3.6 以降を推奨 [Anaconda3 の方が推奨されます。以下の依存ライブラリの多くはインストールする必要がありません]
  2. numpy 依存ライブラリ [Anaconda をお持ちの場合は不要ですインストールする]
  3. PIL 依存ライブラリ [Anaconda をお持ちの場合はインストールする必要はありません]
  4. opencv-python
  5. win32gui、win32api 依存ライブラリ
  6. Python をサポートする IDE [テキスト エディターを使用してプログラムを作成できる場合はオプション]
#- マインスイーパー ソフトウェア

# · マインスイーパー アービター (MS-Arbiter)掃海艇に使用する必要があります!)

さて、これで準備は完了です!始めましょう~

2. 実装のアイデア

何かを始める前に最も重要なことは何ですか?それは、自分がやろうとしていることについて、段階的に枠組みを頭の中に構築することです。この方法によってのみ、この作業のプロセスが可能な限り思慮深く行われ、最終的に良い結果が得られるようにすることができます。プログラムを作成するときは、開発を正式に開始する前に、一般的なアイデアを念頭に置くよう最善を尽くす必要があります。

このプロジェクトの一般的な開発プロセスは次のとおりです。

    フォーム コンテンツのインターセプト パートを完了します
  1. サンダー ブロック セグメンテーション パートを完了します
  2. 地雷ブロックの種類の識別パートを完了します。
  3. 地雷除去アルゴリズムを完了します。
# さて、アイデアができたので、腕まくりして頑張りましょう!

1. フォーム インターセプト

実は、このプロジェクトにとって、フォーム インターセプトは論理的には単純ですが実装が非常に面倒な部分であり、不可欠な部分でもあります。 Spy を通じて次の 2 つの情報を入手しました。

class_name = "TMain"
title_name = "Minesweeper Arbiter "

    ms_arbiter.exe のメイン ウィンドウ カテゴリは "TMain"
  • ms_arbiter のメイン ウィンドウ.exe 本体名は「マインスイーパーアービター」
お気づきでしょうか?メインフォーム名の後にスペースがあります。このスペースが作者をしばらく悩ませたのですが、このスペースを追加するだけで win32gui はフォームのハンドルを正常に取得できるようになります。

このプロジェクトは win32gui を使用してフォームの位置情報を取得します。具体的なコードは次のとおりです:

hwnd = win32gui.FindWindow(class_name, title_name)
if hwnd:
left, top, right, bottom = win32gui.GetWindowRect(hwnd)

上記のコードを通じて、フォームを相対的に取得します。画面全体の位置。その後、PIL を使用して掃海艇インターフェイスのチェス盤を傍受する必要があります。

最初に PIL ライブラリをインポートする必要があります

from PIL import ImageGrab

それから特定の操作を実行します。

left += 15
top += 101
right -= 15
bottom -= 43
rect = (left, top, right, bottom)
img = ImageGrab.grab().crop(rect)

賢明な方なら、これらの奇妙なマジック ナンバーに一目で気づいたはずです。はい、これらは確かにマジック ナンバーです。チェス盤全体の相対的な形状です。フォーム上の位置を少し微調整します。

注: これらのデータは Windows 10 でのみテストされています。他の Windows システムで使用した場合、古いバージョンのシステムではフォームの境界線の幅が異なる可能性があるため、相対位置の正確性は保証されません。

#オレンジ色の領域が必要です

すごいですね、Python を使用して世界記録を破りました!よし、チェス盤の画像ができました。次のステップは、各地雷ブロックの画像をセグメント化することです~

2. 地雷ブロックの分割

#地雷ブロックを分割する前に、地雷ブロックのサイズとその境界線のサイズを事前に知る必要があります。筆者の計測によれば、ms_arbiter における各地雷ブロックのサイズは 16px*16px です。 すごいですね、Python を使用して世界記録を破りました!

雷ブロックのサイズがわかれば、各雷ブロックを切断できます。まず、水平方向と垂直方向の両方の地雷ブロックの数を知る必要があります。

block_width, block_height = 16, 16
blocks_x = int((right - left) / block_width)
blocks_y = int((bottom - top) / block_height)

その後、各地雷ブロックの画像を保存する 2 次元配列を作成し、画像をセグメント化して、前に作成した配列に保存します。

def crop_block(hole_img, x, y):
x1, y1 = x * block_width, y * block_height
x2, y2 = x1 + block_width, y1 + block_height
return hole_img.crop((x1, y1, x2, y2))
blocks_img = [[0 for i in range(blocks_y)] for i in range(blocks_x)]
for y in range(blocks_y):
for x in range(blocks_x):
blocks_img[x][y] = crop_block(img, x, y)

画像取得とセグメンテーションの部分全体をライブラリにカプセル化し、いつでも呼び出すことができます~ 著者の実装では、この部分を imageProcess.py にカプセル化し、関数 get_frame() が使用されます。上記の画像取得とセグメンテーションのプロセスを完了します。

3. 雷块识别

这一部分可能是整个项目里除了扫雷算法本身之外最重要的部分了。笔者在进行雷块检测的时候采用了比较简单的特征,高效并且可以满足要求。

def analyze_block(self, block, location):
block = imageProcess.pil_to_cv(block)
block_color = block[8, 8]
x, y = location[0], location[1]
# -1:Not opened
# -2:Opened but blank
# -3:Un initialized
# Opened
if self.equal(block_color, self.rgb_to_bgr((192, 192, 192))):
if not self.equal(block[8, 1], self.rgb_to_bgr((255, 255, 255))):
self.blocks_num[x][y] = -2
self.is_started = True
else:
self.blocks_num[x][y] = -1
elif self.equal(block_color, self.rgb_to_bgr((0, 0, 255))):
self.blocks_num[x][y] = 1
elif self.equal(block_color, self.rgb_to_bgr((0, 128, 0))):
self.blocks_num[x][y] = 2
elif self.equal(block_color, self.rgb_to_bgr((255, 0, 0))):
self.blocks_num[x][y] = 3
elif self.equal(block_color, self.rgb_to_bgr((0, 0, 128))):
self.blocks_num[x][y] = 4
elif self.equal(block_color, self.rgb_to_bgr((128, 0, 0))):
self.blocks_num[x][y] = 5
elif self.equal(block_color, self.rgb_to_bgr((0, 128, 128))):
self.blocks_num[x][y] = 6
elif self.equal(block_color, self.rgb_to_bgr((0, 0, 0))):
if self.equal(block[6, 6], self.rgb_to_bgr((255, 255, 255))):
# Is mine
self.blocks_num[x][y] = 9
elif self.equal(block[5, 8], self.rgb_to_bgr((255, 0, 0))):
# Is flag
self.blocks_num[x][y] = 0
else:
self.blocks_num[x][y] = 7
elif self.equal(block_color, self.rgb_to_bgr((128, 128, 128))):
self.blocks_num[x][y] = 8
else:
self.blocks_num[x][y] = -3
self.is_mine_form = False
if self.blocks_num[x][y] == -3 or not self.blocks_num[x][y] == -1:
self.is_new_start = False

可以看到,我们采用了读取每个雷块的中心点像素的方式来判断雷块的类别,并且针对插旗、未点开、已点开但是空白等情况进行了进一步判断。具体色值是笔者直接取色得到的,并且屏幕截图的色彩也没有经过压缩,所以通过中心像素结合其他特征点来判断类别已经足够了,并且做到了高效率。

在本项目中,我们实现的时候采用了如下标注方式:

  • 1-8:表示数字1到8
  • 9:表示是地雷
  • 0:表示插旗
  • -1:表示未打开
  • -2:表示打开但是空白
  • -3:表示不是扫雷游戏中的任何方块类型

通过这种简单快速又有效的方式,我们成功实现了高效率的图像识别。

4. 扫雷算法实现

这可能是本篇文章最激动人心的部分了。在这里我们需要先说明一下具体的扫雷算法思路:

  1. 遍历每一个已经有数字的雷块,判断在它周围的九宫格内未被打开的雷块数量是否和本身数字相同,如果相同则表明周围九宫格内全部都是地雷,进行标记。
  2. 再次遍历每一个有数字的雷块,取九宫格范围内所有未被打开的雷块,去除已经被上一次遍历标记为地雷的雷块,记录并且点开。
  3. 如果以上方式无法继续进行,那么说明遇到了死局,选择在当前所有未打开的雷块中随机点击。(当然这个方法不是最优的,有更加优秀的解决方案,但是实现相对麻烦)

基本的扫雷流程就是这样,那么让我们来亲手实现它吧~

首先我们需要一个能够找出一个雷块的九宫格范围的所有方块位置的方法。因为扫雷游戏的特殊性,在棋盘的四边是没有九宫格的边缘部分的,所以我们需要筛选来排除掉可能超过边界的访问。

def generate_kernel(k, k_width, k_height, block_location):
 ls = []
 loc_x, loc_y = block_location[0], block_location[1]
for now_y in range(k_height):
for now_x in range(k_width):
if k[now_y][now_x]:
 rel_x, rel_y = now_x - 1, now_y - 1
 ls.append((loc_y + rel_y, loc_x + rel_x))
return ls
 kernel_width, kernel_height = 3, 3
# Kernel mode:[Row][Col]
 kernel = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
# Left border
if x == 0:
for i in range(kernel_height):
 kernel[i][0] = 0
# Right border
if x == self.blocks_x - 1:
for i in range(kernel_height):
 kernel[i][kernel_width - 1] = 0
# Top border
if y == 0:
for i in range(kernel_width):
 kernel[0][i] = 0
# Bottom border
if y == self.blocks_y - 1:
for i in range(kernel_width):
 kernel[kernel_height - 1][i] = 0
# Generate the search map
 to_visit = generate_kernel(kernel, kernel_width, kernel_height, location)

我们在这一部分通过检测当前雷块是否在棋盘的各个边缘来进行核的删除(在核中,1为保留,0为舍弃),之后通过generate_kernel函数来进行最终坐标的生成。

def count_unopen_blocks(blocks):
count = 0
for single_block in blocks:
if self.blocks_num[single_block[1]][single_block[0]] == -1:
count += 1
return count
def mark_as_mine(blocks):
for single_block in blocks:
if self.blocks_num[single_block[1]][single_block[0]] == -1:
self.blocks_is_mine[single_block[1]][single_block[0]] = 1
unopen_blocks = count_unopen_blocks(to_visit)
if unopen_blocks == self.blocks_num[x][y]:
 mark_as_mine(to_visit)

在完成核的生成之后,我们有了一个需要去检测的雷块“地址簿”:to_visit。之后,我们通过count_unopen_blocks函数来统计周围九宫格范围的未打开数量,并且和当前雷块的数字进行比对,如果相等则将所有九宫格内雷块通过mark_as_mine函数来标注为地雷。

def mark_to_click_block(blocks):
for single_block in blocks:
# Not Mine
if not self.blocks_is_mine[single_block[1]][single_block[0]] == 1:
# Click-able
if self.blocks_num[single_block[1]][single_block[0]] == -1:
# Source Syntax: [y][x] - Converted
if not (single_block[1], single_block[0]) in self.next_steps:
self.next_steps.append((single_block[1], single_block[0]))
def count_mines(blocks):
count = 0
for single_block in blocks:
if self.blocks_is_mine[single_block[1]][single_block[0]] == 1:
count += 1
return count
mines_count = count_mines(to_visit)
if mines_count == block:
mark_to_click_block(to_visit)

扫雷流程中的第二步我们也采用了和第一步相近的方法来实现。先用和第一步完全一样的方法来生成需要访问的雷块的核,之后生成具体的雷块位置,通过count_mines函数来获取九宫格范围内所有雷块的数量,并且判断当前九宫格内所有雷块是否已经被检测出来。

如果是,则通过mark_to_click_block函数来排除九宫格内已经被标记为地雷的雷块,并且将剩余的安全雷块加入next_steps数组内。

# Analyze the number of blocks
self.iterate_blocks_image(BoomMine.analyze_block)
# Mark all mines
self.iterate_blocks_number(BoomMine.detect_mine)
# Calculate where to click
self.iterate_blocks_number(BoomMine.detect_to_click_block)
if self.is_in_form(mouseOperation.get_mouse_point()):
for to_click in self.next_steps:
 on_screen_location = self.rel_loc_to_real(to_click)
 mouseOperation.mouse_move(on_screen_location[0], on_screen_location[1])
 mouseOperation.mouse_click()

在最终的实现内,笔者将几个过程都封装成为了函数,并且可以通过iterate_blocks_number方法来对所有雷块都使用传入的函数来进行处理,这有点类似Python中Filter的作用。

之后笔者做的工作就是判断当前鼠标位置是否在棋盘之内,如果是,就会自动开始识别并且点击。具体的点击部分,笔者采用了作者为"wp"的一份代码(从互联网搜集而得),里面实现了基于win32api的窗体消息发送工作,进而完成了鼠标移动和点击的操作。具体实现封装在mouseOperation.py中,可以在查看完整代码:

https://www.php.cn/link/b8a6550662b363eb34145965d64d0cfb

すごいですね、Python を使用して世界記録を破りました!

以上がすごいですね、Python を使用して世界記録を破りました!の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事は51cto.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。