在整個魔方機器人的設計過程，經歷了反反覆覆的驗證和推倒重來，最終呈現出來的樣子，遠不是最開始設計的樣子。這是由於創作過程中，我們學到更多新的技能，摸索到更多提升的方向，同時走出了原有的思維定勢。
正因為如此，我嘗試整理一下整個設計和製造歷程，供大家參考。希望大家參考思維方式，提升自己的思維模型，並不建議大家直接參考設計，因為設計本身還存在很多不合理的地方，因此在文中和文外並不提供設計原檔。
如果你還沒讀過上一篇的話，因為內容之間的強關聯性，強烈建議先閱讀：
魔方機器人的心路歷程連載(Part10-伺服)
上一章提到，我們伺服器的執行速度相比 Kollmorgen 的電機相比還是有相當的差距，希望單純從伺服速度的提升，超越MIT的成績還是有相當困難的。但如果成績遠比MIT的慢的話，咱們就產生不了新聞價值了，有可能就導致前功盡棄了。這可如何是好呢？
機械上嘗試各種搶時間的方法，做最後的掙扎，希望還能擠出一點性能處理，但最終還是收效甚微，甚至影響穩定性。一籌莫展之際，只能通過觀察分析競品視頻來擴展下思路。
無意中，發現英飛凌的Sub1 Reload視頻中魔方還原的步驟好像與平常算法結果不太一樣。居然在20步的還原步驟中，出現了其中5步是兩個相對的面一起旋轉的。這個現象非常有意思，因為前面做過數千萬次級別的測試，kociemba的算法本身並沒有為這個方面做優化，大部分情況下最多只能有0~3個雙面轉，出現4個雙面轉的序列已經是少概率事件，能出現5個雙面轉的序列可謂是百裡挑一。為確認，我專門做了個隨機分布統計：
數百萬次的對轉比例
考慮到英飛凌申請吉尼斯紀錄，不太可能錄數百次視頻，然後取其中最好的情況來錄入成績。所以把他們視頻中的還原序列逆向，將一個已還原的魔方還原到英飛凌創造吉尼斯紀錄的魔方打亂狀態，然後將該狀態丟進所有kociemba公開工具中，測試能不能得到同樣的還原序列。結果不出所料，確實得不到一樣的還原序列。
這說明了一個問題，他們一定是針對二階段算法進行了對應的優化而得到的結果。那到底怎麼實現優化呢？
於是，深入研究了二階段算法(Two Phase Algorithm)，分析算法整個基本邏輯，算法流程，以及每個階段的推演依據以及結束條件判斷，經過了一周的潛心鑽研，最終發現確實有優化空間；
首先需要了解算法本身設計的緣由，最主要是為了驗證魔方的上帝之數：是否所有魔方狀態都能在20步以內還原。算法的目的並非找到機器人的最優解，因為魔方狀態簡直是天文數字。
為了查找這個問題，動用了谷歌的超級計算機資源，花了幾周時間，貢獻出35個CPU年，才給找到所有通過群論降群後魔方狀態的解。因此，算法設計的目的其實是為了在最短運行時間內找到解，而並非找到機械執行時間最短的解。
對於同一個魔方狀態，解法一定不是唯一的，就像人手還原，以不同顏色為底面，都可以將魔方還原，所以二階段算法的解也一定不是唯一的。
到此咱們清晰了需求，那就開幹吧，首先放開結束條件的限制，先從求解的結果分析。運行驗證確實如咱們所料，算法不停地輸出可復原的解，延綿不斷，運行了兩天還沒有停下來的欲望。
確認了可以得到非常龐大的解集，也許可以從解集中找到適合咱們機器人的方法。不過需要一個估計算法，基於咱們機器人兩個相對的面可以同時旋轉，意味著雖然做了兩個機械旋轉的步驟，但機械運轉時間只消耗了一次。所以初步最簡單的估算算法就是判斷如果出現一次相對面同時旋轉，只記為一次機械運動(mechanic move)。上圖中可以看到其中有跳動的情況，就是發現了相同魔方狀態下，比較短的還原序列。
所以咱們尋找目標並非最終序列最短，而是機械動作最短；比如說還原序列需要19步，對應機械步數19步，而另一個還原序列需要21步，但對應機械步數隻要18步，則最終會挑選21步的還原序列，物理還原時間更短。
到此，咱們的思路就非常清晰了，只要把結束條件更換為找到最短的機械還原步數就好了，就可以囖。
從上圖可以看到算法找到最優解的過程，關鍵信息整理如下表：
時間但到底13步機械是否最短？咱們不清楚，算法仍一直往下搜索，也許過一天後會找到12步機械解。
雖然算法確實能夠延綿不斷的輸出解，但想要枚舉完所有的解，以咱們電腦性能，可能需要按年做單位，咱們希望找到最短的序列是不太可能的。同時，我們機器人計算時間也包含在整個還原時間內，所以不可能在這個階段耗費大量的時間進行搜索，咱們需要做出一定的取捨。
我們必須限制在一定時間內，如果找不到更短的解，就採用該時間段內能找到的最短解，但如果該時間段內沒有找到解，則等找到第一個解就立馬返回。雖然說這樣做能夠保證算法時間的耗用，但搜索步驟比較短的解法的耗時長的情況下，優化程度不大，還需要另闢蹊徑。
咱們前面在 魔方機器人的心路歷程連載(Part4-魔方算法) 文中提到過，第一層有18種旋轉，後面每層都有15種可能性，層數越深，運行時間越長；所以如果能夠縮少層數，將有可能大幅縮短搜索時間。
但如何縮少層數呢？我們知道第一步是針對6個面實現每個面3種旋轉，而如果我們針對每個可能性開啟一條線程，則對於每個線程來說，第一層都是確定的，等同於枚舉層級少了一層。對於6個面來說就有18種可能性，意味著需要開啟18條線程進行搜索。這對於當代 Intel i9，8核16線程的CPU，處理起來都不成問題。
但是固定一層對於最終成績的提升有多大提升？有時候能提升一兩個數量級，因為可能有的面先旋轉會更快得到最短解；但有時候提升效果不太明顯，因為藏在第二層比較深的情況。
為此，喪心病狂的我，嘗試將第二層甚至第三層都固定下來，但這意味著需要開啟 (二層)270，甚至(三層)4050條線程共同工作。可物理CPU核心是有限的，開再多的線程，也只能是分開時間片段來跑，對最終成績的提升非常有限；甚至有時候比開啟18條線程時間還要長，因為資源調度同步耗時非常嚴重，導致大量時間浪費在同步和競爭CPU資源上。
對於非伺服器CPU來說，超過了二十條線程需要同時全速跑的情況下，已經開始吃力了，要同時全速跑數百上千條線程簡直是巧婦難為無米之炊。那市面上有沒有什麼東西可以的跑成百上千條線程呢？咱們把目光轉向到顯卡的GPU上，具體如何實現？咱們下回分解～
以上，是製作魔方機器人過程中算法優化相關的內容。還想了解更多魔方機器人的其他製作過程，請多多關注我們公眾號連載系列喔。如果同學們集中留言對某個部分感興趣，後面考慮出個專題喲~
既然讀到這裡了，怎麼忍心不點個贊呢？
喜歡內容的你，動動手指頭分享一下吧
別忘了關注公眾號，及時收到最新文章喲
使用喜歡作者作為鼓勵也是非常推薦的喲
你們的支持是對我們最大的鼓勵！
如果有疑問歡迎同學們在文章下方留言告訴我，有提議想了解其他方面內容也歡迎留言，新朋友們還不趕緊掃描下方二維碼關注？
未經許可禁止轉載！
延伸閱讀：
魔方機器人心路歷程系列
飛思卡爾回憶專輯
魔方機器人DIY教程系列專輯
[ 種草好物 ] 系列專輯
神馬? 解魔方只要 3 秒？簡直不敢相信我的眼睛！
幕後花絮 : 3秒解魔方機器人的幕後精選
0.337秒就能解魔方!!! Master P 第三代超高速魔方機器人面世 全球最快的魔方機器人
玩魔方居然還要用上超高速相機???