程式解踩地雷

作者:   發佈於:  

這算是老梗了,不過,寫程式去解踩地雷其實是很有意思的事。

@takesako 先生在 yapcasia 2011 的發表主題,是寫 perl 程式去自動玩遊戲,主要的開發環境是在Win32 平台,因此每每也都是在 Win32 平台 上發表、展示。這次的自動玩遊戲,玩的是踩地雷。

雖然還是聽不完全演講的內容,不過光看展示也可以感受到這件事好玩的程度。yapcasia 官方釋出的影片 在 youtube 上: http://www.youtube.com/watch?v=cndfNAKlrjU 。踩地雷的部份,大約從 9:20 秒開始。 或者,也有 lightning talk 版: http://www.youtube.com/watch?v=3C7Ngq6bM4M

用 Perl 程式去自動解踩地雷的基本原理,是不斷地檢查目前的螢幕畫面上是否出現特定的 圖案,並隨之反應。所用到的 CPAN 模組是 Win32::GuiTest 模組與 Image::Match 模組。當然除了能檢查畫面之外, 還要能夠控制滑鼠、鍵盤的動作才行。

這點概念與 Sikuli 所提供的基本上一樣,只是 Sikuli 有更完整 的編輯器,以及圖案比對是特徵式的,能進行模糊比對。Win32::GuiTest 也有利用一 些 Win32 API,能去直接把程式視窗叫出來。

會後,在黑客松的場合,我向他請益了一些細節,試做了另一個版本:透過 Net::VNC ,去解遠端後機器上的踩地雷。即然 能用圖片比對的方式來識別螢幕上的重要元件,那無論是透過系統抓螢幕,或透過 VNC,原 理應該都能通才對。

當天雖然沒能做完,不過這幾天抽空,成功地做出來了。這裡有份短短的展示影片: http://www.youtube.com/watch?v=iHTI8guqeeM ,程式碼的部份在 https://github.com/gugod/vnc-minechan 。 裡面所用的踩地雷圖案,是向 @takesako 要來的,不過有部份訊息改成有改成中文部份, 則是我自行抓取畫面的。

所用到的 CPAN 模組,控制畫面的是 Net::VNC、圖案比對的則是 Imager::Search,程式可以在 Mac OSX 與 FreeBSD 上執行。應該不難注意到,我的程式解得很慢,可能比一些真人高手還要更慢。 主要的差異來源,自然是透過網路的 VNC,抓取畫面的速度比本機差上一大截的關係。

AI 部份,我的做法是算出空格為地雷的機率,找出機率為 0 與 1 的格子。對於一個內容為 3 的數字格,其周圍如果有 1 個地雷,4 個空格,那麼,對於那 4 空格,每一為地雷的機 率便是 (3 - 1)/4 = 0.5。如果依附近的數字格得出不同機率,則取較大的值。如果得出 0,則必定最優先。

對於機率為 1 或 0 的空格,則在下一步標為地雷(點右鍵),或點開(點左鍵)。如果盤 面上完全沒有機率為 1 或 0 的空格,那就亂猜一個不知道機率的格子。如果每格的機率都 知道,就在機率最小的的格子中點一個。

我沒有深入去想是否有其他玩法,這只是我個人在玩的時候的直覺玩法,或許有更好的解法也不一定。

除了解踩地雷,我也在想能不能實做出有用的 VNC::GuiTest 模組(目前不存在),這樣就 有藉口不必為了用 Sikuli 而去學 python 了(笑)。