案例 ：深度学习 V.S. 谜题游戏
作者：Kabalan Gaspard ?翻譯：王紫岳 ??校對：陳漢青
本文約4000字，建議閱讀10+分鐘。
本文為大家介紹了作者使用不同的算法來解決Free Flow謎題游戲的心路歷程，從一開始的A*，Q-learning，到最后的卷積神經網絡，作者詳細的介紹了在使用這些算法時遇到的困難和得到的啟示。
深度學習比古老的蠻力技術更適合解決FlowFree問題嗎?
我們都有過這種經歷。你拿著手機發呆，想要消磨一些時間，于是你決定放棄自己優秀的思考，打開應用商店的游戲區，看看游戲排行榜。你找到了一個看起來很有趣的謎題游戲，但其實游戲是否有趣并不重要，因為你只想玩半個小時，然后就刪掉、忘記它，對么？
?
2個月以后，我完成了兩千多關的Flow Free①游戲，并且堅持每一關都得到“完美”評分。這一游戲（自2012年發行以來，這款游戲在iOS和Android平臺上都是最受歡迎的游戲之一）的設定相當簡單：將不同顏色的閥門分別連起來，并且不能有線相交。
?
FreeFlow——你可以通過這個截圖來了解游戲
?
截圖中的關卡可能看起來很簡單，但是它的難度確實在不斷提升。隨著關卡的進行，我發現我自己想出了一些可以幫助我更快完成這些高級關卡的策略（例如：盡可能的保留外層邊界空白，避免在未填滿的方形中創建“港灣”等）。瀏覽網上論壇時，我看到其他的玩家都有他們自己的技巧，有的和我的一樣，有的則略微不同。這就引出了問題——計算機能否通過“經驗”，而非蠻力，來學習這些技術？
一個人類解決FreeFlow謎題
從基礎開始：A*?
如今的深度學習問題大部分可以歸結為要使用哪種算法。我以A*搜索作為開始。盡管它本身不是深度學習，但是它也很好的說明了這個問題內部的復雜性，并且也給了我們一些機會，來使用更高級的、能夠自我驅動的啟發式算法。
?
由于空間的復雜性太大，以至于我無法一次性解決問題。所以我開始按顏色遞歸地解決問題（如果給定路徑被“堵塞”，就回溯到上一種顏色）。在啟發式算法中，我使用了較為可信的曼哈頓距離。我在四種尺寸的板子上測試了我的算法：微型（2?4）、小型（5?5）、中型（8?8）、大型（14?14）。我保證了大型和中型的板子上的顏色比一般的顏色要少。因為大、中型的板子的確會使問題更難，對人和計算機都是如此（更多可能的路徑/選擇/狀態）。
?
這個算法在小型板子上運行的很好，但是花了相當多的時間。因此，我為下一個狀態的函數增加了一些規則，以此希望強化學習的算法能夠自己找出這些規則：防止同色相鄰方格不連接，或者出現空“港灣”。
我那臺7歲的電腦得到的結果是很讓人開心的，但是仍需改進：
慚愧地說，我可能花在Tkinter圖形函數上的時間比實際的AI要多
?
如果你覺得你是第一個這么做的，那你很有可能就錯了
在我使用強化學習之前，我一直嘗試優化我的A*算法。當我發現Matt Zucker的一篇優秀的博客文章②時，他已經為Flow Free建立了一個A*解算器（很高興的看到，我不是唯一一個有這種困擾的人），并且更加仔細地考慮過要把這些狀態從他的A*搜索中剔除。更讓人驚訝的是，他發現了一個只有6條規則的簡單SAT算法，這比他最好的A*搜索法還表現還要好，而且在SAT中求解時間也非常短(對于14x14的板甚至低于1秒)。
?
到目前為止，我們似乎都得出了同樣令人沮喪的結論：對于這類(非對抗性的，封閉的)謎題游戲，簡單的蠻力技術將超過基本的人工智能算法。
?
不過，我不可能止步不前。畢竟，引發這一實驗的問題仍然存在：作為人類玩家，在玩了幾個關卡后，我們就能發現一些能夠更有效地打敗Flow Free謎題特定的技巧。為什么機器不能學習同樣的技術呢?
提到強化學習
我非常興奮地在Flow Free問題中嘗試了Q-learning算法，因為“AI”中的“I”即將要發揮它真正的作用了。A*搜索的工作也絕不是浪費時間，因為我們可以使用它的結果作為Q-learning智能體的狀態-動作空間。狀態空間由板上的方塊顏色和哪條路徑（顏色）目前是“活躍的”兩部分組成。一個“動作”是指填充活躍路徑的下一個方塊。
?
在一開始犯了一些基礎的錯誤之后，智能體很快就學會了如何解決小型板問題(1.5秒內100次迭代)——到目前為止看起來還不錯。但在中板上，花了10分鐘，經過10000次迭代后，仍然沒有結果：
當你聽到“人工智能”時，你想的結果可能和這個不一樣。
?
為了改善這種情況，我開始調試標準Q-learning的參數(學習率α、貼現率γ、勘探/開發率ε)，但這并沒有很大幫助，所以我將注意力轉向到獎勵函數。除了實際的“獎勵”之外，還需要一個參數與獎勵函數進行權衡（否則風險就會變得規范化，這會不利于整個機器學習活動）：智能體是否會因為解決了一條路徑獲得獎勵，而不是解決了整個謎題之后。不幸的是，這并沒有起到多大作用。
?
最后，逐漸清晰的是，算法之所以會在更大的板上苦苦掙扎，僅僅是因為操作空間太大了。相比于A*搜索，Q-learning在這種情況下確實做出了更明智、更有幫助的選擇，但在大多數情況下，即使在10000次迭代之后，Q-learning 智能體還沒有看到確切的結果。因此，下一步自然就是：
?
近似 Q-learning
近似Q-learning的應用是十分有吸引力的，尤其是在游戲中。與其讓智能體在給定的狀態下決定最佳的操作，不如讓它在每一步都能快速計算出一些直觀、獨立于具體狀態(棋盤的配置)之外的特性，并讓它自己決定哪些是最重要的。這在游戲中會擔任游戲改變者的角色，例如Pcaman（舉個例子，下一步的決策是基于最近的豆子和最近的幽靈，而不是在每種可能狀態下的一個動作），當然也可以是狀態數量太多，以至于讓準確Q-learning失效的Flow Free。
?
現在是開發人員需要權衡利弊挑選“正確”的特征的時候了。于是，我將列表精簡到只有我認為在很多情況下重要的特征(例如，每條路徑的剩余曼哈頓距離)。還有一些我認為重要的、只需要讓算法計算的特征(但無法證明)。這些特征包括：
“轉彎”的個數；
“盒子”的個數；
盒子中閥門的個數；
沒有閥門的盒子的數量(人們可以從邏輯上證明這是不可能發生的——我想看看算法能不能算出來)；
一條路徑是否“抱墻”(即，一條路徑是否可以與相鄰的另一條路徑相連)。
不幸的是，有了這些特征之后，Q-learning智能體甚至不能解決小型板問題，即使我們改變了Q-learning的參數也不行。但是，這也是個有趣的實踐。例如，該算法在“沒有閥門的盒子”上附加了一個強大的負權重，這意味著它能夠了解到，沒有閥門的盒子會導致謎題無法解決。
?
近似Q-learning發現了更好的游戲策略
或許有了更大的謎題樣本，它就能更好地學會如何真正地解決它們，但我很興奮地看到它能真正地找到重要的東西。這在AI中是一個非常有趣的現象，尤其是在游戲AI中非常普遍：即使一個算法不能贏得游戲，它也可以幫助人類找到玩的更好的技巧。
?
走向監督學習：卷積神經網絡
?
一開始，我對通過監督的方法來實現Free Flow的想法存有偏見。首先，這需要大量的Free Flow游戲樣本，而這些游戲很難在公共互聯網上找到。其次，似乎與Free Flow最接近的監督學習方法——神經網絡——是一個臭名昭著的黑盒算法，它會妨礙這個練習最有趣的部分：查看算法學習何種技術來解決這個難題。
?
然而，后來我偶然讀到了Shiva Verma在《Towards Data Science 》③雜志上的一篇文章，他在其中做了一些與數獨游戲非常相似的事情：本質上是把一個數獨游戲板當作一個圖像，然后使用卷積神經網絡(CNN)來解決它。作者在數獨游戲中取得了很好的效果，這讓我重新審視了我最初的想法，并嘗試了這種方法來實現Flow Free。
?
當然，第一個困難是獲得輸入的數據：用解析文本格式來尋找Free Flow謎題的答案，要比數獨謎題更困難。最初，我發現尋找文件最好的方法是查看Android應用程序的代碼，它有一千多個以文本格式存儲的謎題：
CNN的初始結果是令人失望的：盡管CNN正在學習它任務是創建路徑，而不是僅僅在孤立地填充顏色，但在測試樣本中只有0%的謎題被解決了。
?
我們需要更多的數據
調整分層、訓練次數、內核大小和其他類似的常見疑點并沒有多大幫助。這似乎又回到了數據科學家最常見的問題:沒有足夠的數據，世界上最好的算法也什么都不是。我找到的其他最好的數據來源是www.flowfreesolutions.com，它有成千上萬的對于全新的Free Flow問題的解法，比我的解法要多... 但是是圖片格式的。
?
盡管我嘗試了無數次，通過各種渠道聯系他們（甚至提供了經濟獎勵），我還是沒能讓他們給我發送一個可解析的文本版本的解決方案。好吧，這不是一篇免費的人工智能文章——當一個人有現代圖像處理器的時候，誰還需要底層的解決方案矩陣呢？使用子項目建立一個Free Flow④解決方案圖像處理器:
Scikit-image FTW
利用對稱性來增加我們可用的數據
這就產生了幾千個用來研究的數據點，但這仍然不是很多。但后來我意識到，就CNN而言，顏色的確切值并不重要，重要的是顏色是不同的。所以我們可以將顏色重新排列，并且仍然有另一個非冗余的數據點。即使對一個只有六種顏色的5x5的板來說，這可以給我們的CNN提供多達6！= 720倍的研究數據點（當然，等大的板和更多的顏色會有更多可選的組合）。
?
數學家將從群論中認識對稱群S_n
?
一位朋友指出，這實際上是游戲AI中增加數據點的常見方式。在720x的數據點的情況下，我們最終在一個20-epoch模型，使用大小約為200k的數據點測試集，在我7歲的GPU上運行了20分鐘后得到的準確率為12%。需要注意的是，我們在這里使用了一個嚴格的衡量成功的標準：即使板子少用了一個單元格，我們也將其視為失敗。
?
但是，失敗比成功有趣得多。在幾乎所有的失敗中，CNN正確地解決了板子的很大一部分，剩下的部分人們則很容易完成它。從這個意義上講，CNN能夠解決文章最初的問題：憑直覺學習人類的技巧：
CNN的誤差分布
結論
對于解決基于網格的、非對抗性的謎題游戲來說，簡單的方法通常更好。事實上隨著方法逐漸變得高級，他們的表現會越來越差。
然而，盡管更高級的機器學習方法不能很快地解決這個難題，但它們確實發現了一些有趣的見解，并幫助人類得到更好的解決方案——卷積神經網絡在這方面做得最好。而且，它們的性能比傳統的解決方法更好。
更好的數據比更好的算法重要。
后續：讀者和編者的建議
我們請了一些更有經驗的AI/ML專家(非常感謝Matt Zucker⑤、Youssef Keyrouz⑥和Mark Saroufim⑦)來檢閱這篇文章，他們建議嘗試以下想法來改進CNN算法。第2部分文章的主題可能會詳細介紹，您也可以在https://github.com/kgaspard/flow-free ai上自己動手嘗試這些想法（以及本文中詳細介紹的方法）：
改變CNN的層數（減少特征看上去似乎沒有什么用）；
除了使用對稱來增加我們的數據點，還使用旋轉、反射等方法；
使用CNN的預測結果作為特征的強化學習智能體。
鏈接：
①：https://www.bigduckgames.com/
②：https://mzucker.github.io/2016/08/28/flow-solver.html
③：https://towardsdatascience.com/solving-sudoku-with-convolution-neural-network-keras-655ba4be3b11
④：https://github.com/kgaspard/flow-free-ai/blob/master/imageParser.py
⑤：https://mzucker.github.io/swarthmore/
⑥：https://www.researchgate.net/profile/
Youssef_Keyrouz
⑦：https://medium.com/@marksaroufim
原文標題：
Deep Learning vs Puzzle Games
原文鏈接：
https://towardsdatascience.com/deep-learning-vs-puzzle-games-e996feb7616
譯者簡介：王紫岳，悉尼大學Data Science在讀研究生，在數據科學界努力奮斗的求知者。喜歡有挑戰性的工作與生活，喜歡與朋友們熱切交談，喜歡在獨處的時候讀書品茶。張弛有度，才能夠以最飽滿的熱情迎接有點忙碌的生活。
轉自：?數據派THU 公眾號；
END
版權聲明：本號內容部分來自互聯網，轉載請注明原文鏈接和作者，如有侵權或出處有誤請和我們聯系。
合作請加QQ：365242293??
數據分析（ID?:?ecshujufenxi?）互聯網科技與數據圈自己的微信，也是WeMedia自媒體聯盟成員之一，WeMedia聯盟覆蓋5000萬人群。
總結
以上是生活随笔為你收集整理的案例 ：深度学习 V.S. 谜题游戏的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python实现密码破解
- 下一篇： Window下kafka 单机SASL_