「通過交換和復制移動，AlphaDev 跳過了一個步驟，以一種看似錯誤，但實際上是捷徑的方式連接項目。」這種前所未見、違反直覺的思想不禁讓人回憶起 2016 年那個春天。

七年前，AlphaGo 在圍棋上擊敗人類世界冠軍，如今 AI 又在編程上給我們上了一課。

今天凌晨，Google DeepMind CEO 哈薩比斯的兩句話引爆了計算機領域：「AlphaDev 發現了一種全新且更快的排序算法，我們已將其開源到主要 C++ 庫中供開發人員使用。這只是 AI 提升代碼效率進步的開始。」

這一次，Google DeepMind 的全新強化學習系統 AlphaDev 發現了一種比以往更快的哈希算法，這是計算機科學領域中的一種基本算法，AI 的成果現已被納入 LLVM 標準 C++ 庫 Abseil 并開源。

這個成果有多重要？AlphaDev 的主要作者之一，Google DeepMind 研究科學家 Daniel J. Mankowitz 表示：「我們估計它發現的排序和哈希算法每天會在全世界被調用數萬億次。」

AI 似乎從算法層面加速了世界的運轉。

這些算法改進了 LLVM libc++ 排序庫，對于較短的序列，排序庫的速度提高了 70%，對于超過 25 萬個元素的序列，速度也能提高約 1.7%。Google DeepMind 表示，這是十多年來排序庫這部分的第一次變化。看起來，現在 AI 不僅可以幫人寫代碼，而且可以幫我們寫出更好的代碼。

在最新的博客中，新系統的作者們對 AlphaDev 進行了詳細介紹。

新的算法將改變計算基礎

數字社會推動了對計算和能源日益增長的需求。過去五十年里，數字時代依靠硬件的改進來跟上需求。但是隨著微芯片接近其物理極限，改進在其上運行的代碼變得至關重要。對于每天運行數萬億次的代碼所包含的算法來說，這尤其重要。

Google DeepMind 的這項研究就是因此產生的，相關論文已發表在《Nature》上，AlphaDev 是一個 AI 系統，它使用強化學習來發現算法，甚至超越了科學家和工程師們幾十年來打磨出來的成果。

論文地址：https://www.nature.com/articles/s41586-023-06004-9

總體來說，AlphaDev 發現了一種更快的排序算法。雖然數十億人每天都在使用這些算法，但卻沒有人意識到這一算法還存在優化空間。排序算法應用范圍廣泛，從在線搜索結果、社交帖子排序，到計算機以及手機上的各種數據處理，都離不開排序算法。利用 AI 生成更好的算法將改變人類編程計算機的方式，對日益數字化的社會將產生重大影響。

通過在主要的 C++ 庫中開源新排序算法，全球數百萬開發人員和公司現在可以在云計算、在線購物和供應鏈管理等各行各業的人工智能應用中使用它。這是十多年來對排序庫的首次更改，也是通過強化學習設計的算法首次被添加到該庫中。這將這視為使用人工智能逐步優化世界代碼的重要里程碑。

關于排序

排序算法是一種按照特定順序對某些任務進行排列的方法。例如，按字母先后順序排列三個字母，從大到小排列五個數字，或者對數百萬條記錄的數據庫進行排序。

這種算法由來已久，并得到了很好的演進。其中關于排序的最早一個示例可追溯到公元 2 世紀和 3 世紀，當時學者們在亞歷山大圖書館的書架上手工按字母順序排列了數千本書。隨著工業革命的到來，出現了可以幫助人們進行排序的機器，其中制表機使用打孔卡片存儲信息，這些卡片被用于收集美國 1890 年的人口普查結果。

隨著上世紀 50 年代商用計算機的興起，最早用于排序算法的計算機科學算法開始發展。如今，在全球的代碼庫中有許多不同的排序技術和算法被用于處理海量的在線數據。

將一系列未排序的數字輸入到算法中，輸出已排序的數字。

經過計算機科學家和程序員們幾十年的研究，目前的排序算法已經非常高效，以至于很難再實現進一步的改進，這有點類似于試圖找到一種新的節省電力或更高效的數學方法，而這些算法也是計算機科學的基石。

探索新算法：匯編指令

AlphaDev 從頭開始探索更快的算法，而不是基于現有算法之上，除此以外，AlphaDev 還能用于尋找大多數人所不涉足的領域：計算機匯編指令。

匯編指令可用于創建計算機執行的二進制代碼。開發人員使用諸如 C++ 之類的高級語言編寫代碼，但必須將其轉換為計算機能夠理解的「低級」匯編指令。

Google DeepMind 認為這個層次存在許多改進的空間，而這些改進在更高級的編程語言中可能很難被發現。在這個層次上，計算機的存儲和操作更加靈活，這意味著存在更多潛在的改進可能性，這些改進可能對速度和能源使用產生更大的影響。

代碼通常是用高級編程語言（如 C++）編寫的。然后，編譯器將其轉換為低級 CPU 指令，稱為匯編指令。匯編器將匯編指令轉換為可執行的機器碼，以便計算機可以運行。

圖 A：C++ 算法示例，該算法可對最多兩個元素進行排序；圖 B：相應的匯編表示形式。

用 AlphaGo 的方法尋找最佳算法

AlphaDev 基于 Google DeepMind 此前的一項成果：在圍棋、國際象棋和象棋等游戲中打敗世界冠軍的強化學習模型 AlphaZero。而 AlphaDev 展示了這個模型如何從游戲轉移到科學挑戰，以及從模擬到現實世界的應用。

為了訓練 AlphaDev 發現新的算法，團隊將排序變成了一個單人的「組裝游戲」。在每個回合中，AlphaDev 觀察它所產生的算法和 CPU 中包含的信息，然后通過選擇一條指令添加到算法中來下一步棋。

匯編游戲是非常困難的，因為 AlphaDev 必須在大量可能的指令組合中進行高效搜索，以找到一個可以排序的算法，并且比當前的最佳算法更快。指令的可能組合數量類似于宇宙中的粒子數量，或者國際象棋（10^120 局）和圍棋（10^700 局）中可能的動作組合的數量，而一個錯誤的動作就可以使整個算法失效。

圖 A：組裝游戲。玩家 AlphaDev 接收系統 st 的狀態作為輸入，并通過選擇一條匯編指令添加到目前已生成的算法中來下棋。圖 B：獎勵計算。每次移動后，生成的算法都會輸入測試輸入序列 —— 對于 sort3，這對應于三個元素序列的所有組合。該算法然后生成一個輸出，將其與排序情況下排序序列的預期輸出進行比較。智能體根據算法的正確性和延遲獲得獎勵。

在構建算法時，對于每次的一條指令，AlphaDev 通過將算法的輸出與預期結果進行比較來檢查它是否正確。對于排序算法，這意味著無序數字進入，正確排序的數字出來。團隊會獎勵 AlphaDev 對數字的正確排序以及排序的速度和效率，然后 AlphaDev 通過發現正確、更快的程序來贏得比賽。

它發現了更快的排序算法

AlphaDev 發現了新的排序算法，這些算法導致 LLVM libc++ 排序庫得到改進：對于較短的序列，排序庫的速度提高了 70%，對于超過 25 萬個元素的序列，速度提高了約 1.7%。

其中，Google DeepMind 團隊更專注于改進三到五個元素的短序列排序算法。這些算法是使用最廣泛的算法之一，因為它們通常作為更大排序函數的一部分被多次調用，改進這些算法可以提高對任意數量項目進行排序的整體速度。

為了讓新的排序算法對人們更有用，團隊對算法進行了逆向工程并將它們翻譯成 C++，這是開發人員使用的最流行的編程語言之一。

目前，這些算法已在 LLVM libc++ 標準排序庫（https://reviews.llvm.org/D118029）中提供，被全球數百萬開發人員和公司使用。

「交換和復制動作」，神之一手重現？

事實上，AlphaDev 不僅發現了更快的算法，而且還發現了新的方法。它的排序算法包含新的指令序列，每次應用時都會節省一條指令 —— 這顯然會產生巨大的影響，因為這些算法每天都要使用數萬億次。他們把這些稱為「AlphaDev 交換和復制動作」。

這種新穎的方法讓人聯想到 AlphaGo 的「第 37 步」—— 當時這這種反直覺的下法讓圍觀者目瞪口呆，并導致李世石這位傳奇圍棋選手被打敗。通過交換和復制動作，AlphaDev 跳過了一個步驟，以一種看起來像錯誤但實際上是捷徑的方式連接項目。這表明 AlphaDev 有能力發掘出原創性的解決方案，并挑戰人類對如何改進計算機科學算法的思考方式。

左圖：min （A，B，C） 原始的 sort3 實現；右圖：AlphaDev 交換移動 ——AlphaDev 發現你只需要 min （A，B）。

左圖：在一個更大的排序算法中使用 max（B，min（A，C，D））的原始實現，用于排序八個元素；右圖：AlphaDev 發現，使用其復制動作時，只需要 max（B，min（A，C））。

擴展能力測驗：從「排序」到「哈希」

在發現更快的排序算法后，團隊測試了 AlphaDev 是否可以概括和改進不同的計算機科學算法：哈希。

哈希是計算中用于檢索、存儲和壓縮數據的基本算法。就像使用分類系統來定位某本書的圖書管理員一樣，哈希算法可以幫助用戶知道他們正在尋找什么以及在哪里可以找到它。這些算法獲取特定密鑰的數據（例如用戶名 “Jane Doe”）并對其進行哈希處理 —— 這是一個將原始數據轉換為唯一字符串（例如 1234ghfty）的過程。計算機使用此哈希來快速檢索與密鑰相關的數據，而不是搜索所有數據。

團隊將 AlphaDev 應用于數據結構中最常用的哈希算法之一，嘗試發現更快的算法。當將其應用于 9-16 字節范圍的哈希函數時，AlphaDev 發現的算法速度提高了 30%。

今年，AlphaDev 的新哈希算法已被發布到開源 Abseil 庫中，可供全球數百萬開發人員使用，它現在大概每天被使用數萬億次。

開源地址：https://github.com/abseil/abseil-cpp/commit/74eee2aff683cc7dcd2dbaa69b2c654596d8024e

結語

Google DeepMind 通過優化和推出改進的排序和哈希算法，供世界各地的開發人員使用，AlphaDev 展示了其概括和發現具有現實影響的新算法的能力。AlphaDev 可被視為開發通用 AI 工具的一步，它可以幫助優化整個計算生態系統并解決其他造福社會的問題。

雖然在低級匯編指令空間中進行優化非常強大，但隨著算法的增長， AlphaDev 仍存在局限性，團隊目前正在探索其直接在高級語言（如 C++）中優化算法的能力，這對開發人員來說更加有用。

AlphaDev 的發現，例如交換和復制動作，不僅表明它可以改進算法，還可以找到新的解決方案。這些發現或許能夠激勵研究人員和開發人員創建可以進一步優化基礎算法的技術和方法，以創建更強大和可持續的計算生態系統。