不需要人類知識,AI 也能以更少步數復原任意 3 階魔方

作者 | 發布日期 2018 年 06 月 19 日 18:01 | 分類 AI 人工智慧 , 尖端科技 follow us in feedly

魔術方塊是非常有趣的益智玩具,但從難度來說,其實不比其他棋類遊戲困難,如果人工智慧(AI)演算法可在西洋棋或圍棋輕鬆打敗人類,那麼復原魔術方塊也不是困難的事。



但是對演算法來說,要解出魔術方塊的謎題和下棋是完全不同種類的任務。

過去在棋類遊戲展現出超人類表現的演算法,都是屬於傳統的「強化學習」(RL)系統,這類型 AI 確定某些特定一步是實現整體目標的積極步驟時,便會獲得獎勵,進而使系統產生追求最大利益的習慣性行為,然而當 AI 無法確定這一步是否有益,強化學習自然無法發揮作用。

如果還是無法理解,試著這麼想吧:玩棋類遊戲時,系統可輕易判定一個動作究竟屬於「好棋」或「壞棋」,但轉動魔術方塊時,你能說出任何特定的一步,是改善整體難題的關鍵嗎?

從外觀來看,魔術方塊是很單純的益智玩具,然而因為 3D 立體的特性,這讓一般常見的 3 階魔術方塊就已有驚人的近 4.33×1019 種組合,其中只有六面都是相同顏色的狀態才能成為「正確解答」。

過去人們已研究出許多不同算法和策略來解決這項難題,但 AI 研究人員真正的目標還是希望能像 AlphaGo Zero 那樣,讓 AI 在沒有任何歷史知識的情況下,學會自行應對隨機的魔術方塊難題。

近期加州大學 Stephen McAleer 和團隊透過一種稱為「自學疊代」(autodidactic iteration)的 AI 技術打造「DeepCube」系統,成功讓 AI 面對任何亂序 3 階魔術方塊時,都能成功找出正確解答。

根據團隊解釋,自學疊代是一種全新的強化學習演算法,與過去棋類遊戲演算法的處理方式不同,採取「反著看」的內部獎勵判斷機制:當 AI 提出一個動作建議時,演算法便會跳至完成的圖形往前推導,直到到達提出的動作建議,藉以判斷每一步動作的強度。

雖然聽來相當繁雜,但這讓系統更熟悉每一步動作,並得以評估整體強度,一旦獲得足夠的數據,系統便能以傳統的樹狀搜索方式找出如何移動最好的方法。

▲ DeepCube 自行找出的策略 aba-1,許多玩家也經常使用。(Source:arXiv via Stephen McAleer

團隊研究發現,DeepCube 系統在訓練時自己找出許多與人類玩家相同的策略,並在經過 44 小時的自學訓練後,已能在沒有任何人為干預下,平均 30 步以內復原任何隨機亂序魔術方塊──這些「最佳解答」不是和人類最佳表現一樣好,就是比這些表現更好。

McAleer 和團隊打算未來進階測試更大、更難解決的 16 階魔術方塊,這項全新的系統將有助於 AI 應用更全面化,像是生物物理學重要的蛋白質摺疊(Protein Folding)問題或也有望得以解決。

(首圖來源:pixabay