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

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

計(jì)算機(jī)視覺：在圖像問題檢測(cè)中的應(yīng)用

深度學(xué)習(xí)：對(duì)問題中的數(shù)字進(jìn)行分類

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

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

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

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

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

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

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

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

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