DeepMind 的遊戲人工智能改進人類設計的演算法

作者：Constantine Chung
2023/08/04

位於英國的人工智能研究公司Google DeepMind，利用其遊戲人工智能 AlphaZero 取得了計算機科學領域的兩項重大突破。DeepMind 使用了名為 AlphaDev 的新版本 AlphaZero，在排序演算法和密碼學方面取得了重大進展。AlphaDev 發現了一種方法，可以將列表中的項目排序速度提升多達 70%，超越了現有的最佳人類設計方法。它還將一個關鍵的密碼學演算法加速了 30%。這發現非常重要，因為這些演算法是各種軟件應用的基礎，即使是微小的改進也能帶來顯著的成本節省和節能效果。

「摩爾定律即將結束，晶片接近其基本物理極限，」Google DeepMind 的研究科學家 Daniel Mankowitz 說道。「我們需要尋找創新的方法來優化計算。」

人工智能設計的演算法取得勝利

儘管 DeepMind 的研究最近才在《自然》雜誌上發表，但 AlphaDev 開發的新排序演算法已經被數百萬軟件開發人員使用。DeepMind 將其演算法提交給管理廣泛使用的 C++ 程式語言的機構，這導致了 C++ 排序演算法在十多年來的首次更新，也是首個受到人工智能啟發的演算法更新。

AlphaDev 建立在 AlphaZero 之上，AlphaZero 是一種以強化學習為基礎的模型，以精通圍棋和西洋棋等遊戲而聞名。DeepMind 的方法是將尋找更快演算法的問題視為一場遊戲，訓練 AlphaDev 發現勝利的著手方法。這個遊戲圍繞著選擇電腦指令並將它們排列起來形成一個演算法。AlphaDev 通過創建不僅正確而且比現有演算法更快的演算法來取得勝利。

為了應對這一挑戰，AlphaDev 使用組合語言，這是一種提供特定指令以操作電腦晶片上的數據的程式語言。DeepMind 選擇組合語言是因為它允許演算法被細分為細粒度步驟。通過玩遊戲並嘗試添加組合語言指令，AlphaDev 學會了生成正確且高效的演算法。

最初集中優化三到五個項目的排序演算法。DeepMind 的研究人員驚訝地發現，AlphaDev 在三個項目的排序演算法上比最佳的人類設計演算法優勝，將所需指令數量從 18 減少到 17。雖然在四個項目上，它沒有超越最佳人類演算法，但在五個項目的排序中表現優異，將指令數量從 46 減少到 42。

這些優化帶來了顯著的加速效果。例如，對於在 Intel Skylake 晶片上排序五個項目的現有 C++ 演算法，所需時間約為 6.91 納秒，而 AlphaDev 的演算法僅需 2.01 納秒便完成任務，表示提升了 70%。

接下來的發展

儘管對結果印象深刻，專家們警告機器學習尚未達到完全創造全新且更好演算法的程度。AlphaDev 僅探索組合語言指令的子集，這限制了與使用不同指令的現有演算法直接比較的可能性。此外，由於 AlphaDev 必須評估的可能演算法數量眾多，其能力受到限制。DeepMind 計劃通過使 AlphaDev 適應 C++ 指令，並融入人類設計的方法和直覺來解決這些限制。

並非首次突破

在 2022 年，DeepMind 已經使用 AlphaZero 在矩陣乘法方面取得了重大進展，這是各種應用中使用的基本計算。通過將問題轉化為三維棋盤遊戲，並訓練名為 AlphaTensor 的新版本 AlphaZero，DeepMind 能夠發現更快的矩陣乘法演算法。AlphaTensor 在超過 70 種不同的矩陣尺寸上優於現有演算法，包括數學家 Volker Strassen 於 1969 年提出的方法。它減少了矩陣乘法所需的步驟數量，並識別出在常見電腦晶片上快 10 到 20％的演算法。DeepMind 計劃將 AlphaTensor 應用於搜索其他類型的演算法，開創計算機科學的新方法。