魔術(shù)方塊是非常有趣的益智玩具，但從難度來說，并不比其他棋類游戲困難，如果人工智能(AI)算法可以在國際象棋或圍棋中輕松打敗人類，那么復(fù)原魔術(shù)方塊也不是這么困難的事。
但是事實上對于算法來說，要解出魔術(shù)方塊的謎題和下棋是完全不同種類的任務(wù)。
過去在棋類游戲中展現(xiàn)出超人類表現(xiàn)的算法，都是屬于傳統(tǒng)的「強化學(xué)習(xí)」(RL)系統(tǒng)，這類型 AI 在確定某些特定的一步是實現(xiàn)整體目標(biāo)的積極步驟時，便會獲得獎勵，進而使系統(tǒng)產(chǎn)生追求最大利益的習(xí)慣性行為，然而當(dāng) AI 無法確定這一步是否有益時，強化學(xué)習(xí)自然就無法發(fā)揮作用。
如果還是無法理解，試著這么想吧：在進行棋類游戲時，系統(tǒng)可以輕易去判定一個動作究竟是屬于「好棋」或「壞棋」，但是在轉(zhuǎn)動魔術(shù)方塊時，你能夠說出有任何特定的一步，是改善整體難題的關(guān)鍵嗎?
從外觀上來看，魔術(shù)方塊是個很單純的益智玩具，然而因為 3D 立體的特性，這讓一般常見的 3 階魔術(shù)方塊就已有著驚人的近 4.33×1019 組合，而在其中，只有六面都是相同顏色的狀態(tài)才能成為「正確解答」。
過去人們已經(jīng)研究出許多不同算法和策略來解決這項難題，但 AI 研究人員真正的目標(biāo)還是希望能像 AlphaGo Zero 那樣，讓 AI 在沒有任何歷史知識的情況下，學(xué)會自行應(yīng)對隨機的魔術(shù)方塊難題。
而近期加利福尼亞大學(xué) Stephen McAleer 和團隊透過一種被稱為「自學(xué)疊代」(autodidactic iteration)的 AI 技術(shù)打造出「DeepCube」系統(tǒng)，成功讓 AI 在面對任何亂序的 3 階魔術(shù)方塊時都可以成功找出正確解答。
根據(jù)團隊解釋，自學(xué)疊代是一種全新的強化學(xué)習(xí)算法，與過去棋類游戲算法的處理方式不同，它采取了「反著看」的內(nèi)部獎勵判斷機制：當(dāng) AI 提出一個動作建議時，算法便會跳至完成的圖形開始往前推導(dǎo)，直到到達提出的動作建議，藉以判斷每一步動作的強度。
雖然聽來相當(dāng)?shù)姆彪s，但這讓系統(tǒng)能夠更熟悉每一步動作，并得以評估出整體強度，一但獲得足夠數(shù)量的數(shù)據(jù)，系統(tǒng)便能以傳統(tǒng)的樹狀搜索方式去找出如何移動最好的方法。
▲ DeepCube 自行找出的一種策略 aba-1，許多玩家也經(jīng)常使用。(Source：arXiv via Stephen McAleer)
團隊在研究中發(fā)現(xiàn)，DeepCube 系統(tǒng)在訓(xùn)練中自己找出了許多與人類玩家相同的策略，并在經(jīng)過 44 個小時的自學(xué)訓(xùn)練后，已經(jīng)能夠在沒有任何人為干預(yù)下，在平均 30 步以內(nèi)復(fù)原任何隨機亂序魔術(shù)方塊──這些「最佳解答」不是和人類最佳表現(xiàn)一樣好，就是比這些表現(xiàn)更好。
McAleer 和團隊打算未來將在更大、更難解決的 16 階魔術(shù)方塊上進行測試，這項全新的系統(tǒng)將有助于 AI 應(yīng)用更全面化，像是生物物理學(xué)上重要的蛋白質(zhì)摺疊(Protein Folding)問題或也有望得以解決。
下載文檔
