我喜歡邏輯游戲,同時也喜歡計算機視覺和人工智能算法。為了把這兩樣結(jié)合起來,開發(fā)了一個軟件來檢測、分析和解決一些邏輯難題,比如數(shù)獨和摩天大樓。本文主要解釋“LogicGamesSolver”項目,你可以在這個github存儲庫中找到源代碼以及運行它的說明。

該項目結(jié)合了三個研究領(lǐng)域:

計算機視覺：在圖像問題檢測中的應用

深度學習：對問題中的數(shù)字進行分類

人工智能：玩游戲該軟件使用Python編寫,使用opencv4．01和Tensoflow 2．3．0庫。它能解決三種游戲:數(shù)獨、星際大戰(zhàn)和摩天大樓。

第一步:檢測第一步是檢測輸入圖像中的謎題。其思想是找到最大的輪廓,即圖像中最大的多邊形。如果場景是干凈的,有盡可能少的噪音和物體,則此步驟對于軟件來說更容易。使用參數(shù)cv2．RETR_EXTERNAL的findContours方法找到輪廓?,僅考慮極端的外部輪廓;然后,我們根據(jù)輪廓的面積對輪廓進行排序,并取第一個元素。一旦發(fā)現(xiàn)了這個謎題,我們就取四個頂點進行透視變換,并使用warpeperspective對多邊形的圖像進行變換。

在繼續(xù)之前,我們必須從網(wǎng)格中提取單元格的圖像來分析已經(jīng)寫入的數(shù)字。請注意,網(wǎng)格長度由用戶給定。方法*get_digit()*分析單元格圖像以檢查其是否包含數(shù)字(否則返回None),并對其進行預處理,使其成為數(shù)字分類器的合適輸入圖像。

第二步:謎題分析一旦我們有了謎題的平面圖像,是時候?qū)ζ溥M行分析,以獲得已經(jīng)提供的信息來解決游戲了。數(shù)獨和摩天大樓的謎題需要考慮數(shù)字;相反,對于星戰(zhàn)游戲,我們需要了解內(nèi)部結(jié)構(gòu),以定位模式中定位的區(qū)域。數(shù)字分類器為了了解圖中有哪些數(shù)字,該軟件利用卷積神經(jīng)網(wǎng)絡對手寫體數(shù)字進行分類,并用著名的MNIST數(shù)據(jù)集?:60000個元素,28×28像素的0-9之間的手寫體單個數(shù)字灰度圖像進行訓練。我不想深入討論細節(jié),因為它是一個非常基本的CNN,而且數(shù)據(jù)集幾乎在每一本深度學習書籍中都有使用。本文我只向你展示神經(jīng)網(wǎng)絡的體系結(jié)構(gòu),但是你可以在項目源代碼的DigitClassifier．py類中看到實現(xiàn) 。

軟件只在第一次執(zhí)行時訓練模型,然后使用保存在文件中的權(quán)重來預測數(shù)字�？梢允褂梦业臋�(quán)重:提供了一種將圖像轉(zhuǎn)換成適合CNN的陣列的方法,同時提供一個exclude_classes數(shù)組,即不考慮該游戲的類(例如Sudoku的“ 0”,其數(shù)字在[1,9]范圍內(nèi))。使用*preds．a(chǎn)rgmax(axis = 1)[0]時,*我們以最大概率將值取為正確的數(shù)字。MNIST數(shù)據(jù)集是由手寫數(shù)字組成的,模型訓練結(jié)束后,CNN給出了99%的準確率。但是,由于字體的原因,我在使用時遇到了一些錯誤:書寫的數(shù)字可能與手寫的數(shù)字有很大的不同,例如,“4”通常被預測為“9”,而“3”則被預測為“8”。為了解決這個問題,我決定不僅考慮圖像,還要考慮最后7個數(shù)字,并考慮同一單元格的7位預測中最頻繁出現(xiàn)的數(shù)字預測。

連接成分分析對于星際大戰(zhàn),沒有數(shù)字可以識別,但是網(wǎng)格區(qū)域可以定位,為此,我們需要首先刪除內(nèi)部網(wǎng)格線,然后提取連接的組件。在前4行中,我們應用腐蝕過濾器去除較淺的行,然后應用閾值僅高亮顯示區(qū)域的邊緣,最后我們尋找連接的組件,用不同的顏色給區(qū)域著色。

這是一個實時過程,以便用戶可以確認(按空格鍵)何時區(qū)域定位良好,一旦用戶確認,網(wǎng)格中的單元格將按其中心像素的顏色分組,從而定義問題區(qū)域。

第三步:解謎現(xiàn)在我們已經(jīng)有了解決游戲的所有要素。和其他許多邏輯益智游戲一樣,數(shù)獨、星戰(zhàn)和摩天大樓都可以描述為約束滿足問題。CSP包含三個元素:一組我們想要找到正確值的變量每個變量可能值的域定義問題的一組約束例如我們的數(shù)獨游戲:變量:網(wǎng)格的81個單元格域:范圍{1,9}(不包括已填充的單元格)約束:游戲規(guī)則類似的表示法可以用于許多問題和游戲,也可以用于摩天大樓和星戰(zhàn),但其中有一個特點:單元的域是{0,1},表示星體的存在(1)或不存在(0)。一個解決方案是一個特定的變量分配,使每個約束都得到滿足。源代碼有點長,但我想向你解釋用于在軟件中解決csp的遞歸回溯搜索的思想,顯示算法的核心部分。我知道,這很復雜,但它背后的思想非常簡單:算法通過單變量賦值(技術(shù)上是深度優(yōu)先搜索)來搜索解,直到找到一個完整的賦值(由is_complete方法控制)。在每一步中,算法獲取一個沒有賦值的變量(select_unassigned_variablee),選擇其域中一個未經(jīng)驗證的值,并查看發(fā)生了什么。如果對于賦值,當前狀態(tài)尊重所有約束(is_consistent方法),我們再次調(diào)用算法來檢查賦值是否完成,否則我們刪除當前變量并返回到前一狀態(tài)以嘗試使用不同的值。如果你閱讀了全部代碼,你會發(fā)現(xiàn)使用了一些啟發(fā)式方法來加速求解過程。一種是簡單推理,我嘗試通過檢查是否可以執(zhí)行一些簡單的推理來分配一些變量:例如,對于數(shù)獨來說,如果一行、一列或一個正方形包含8個明顯的值,則很明顯這是缺失值;另一種啟發(fā)式方法用于給定變量的值選擇。在啟發(fā)式方法中,如果選擇某個變量的值違反了某些游戲規(guī)則,則從該變量的域中刪除該值。從計算的角度來看,該算法將搜索空間從O(d ^ n!)減少到O(d ^ n),但值得注意的是,如果沒有啟發(fā)式算法,算法可能會非常慢。

最后考慮我們生活在一個不再讓我們感到驚訝的時代:人工智能對我們生活的社會影響如此之大,以至于我們對新技術(shù)變得冷漠,也許有時候我們應該停下來反思一下,生活在這個革命時代,我們是多么幸運。讓我們以這個簡單的項目為例,該軟件(約50KB的內(nèi)存,分布在4個文件上)使用計算機視覺算法進行圖像分析和透視變換,使用卷積神經(jīng)網(wǎng)絡進行數(shù)字分類,并且該算法在幾秒鐘內(nèi)解決了一個邏輯問題,這至少需要我們幾分鐘的時間。每一種算法都是世界各地幾十年來研究和實驗的成果,它是整整一代科學家的遺產(chǎn)。