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

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

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

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

這個成果有多重要？AlphaDev 的主要作者之一，Google DeepMind 研究科學家 Daniel J. Mankowitz 表示：「我們估計它發(fā)現(xiàn)的排序和哈希算法每天會在全世界被調(diào)用數(shù)萬億次?！?/span>

AI 似乎從算法層面加速了世界的運轉(zhuǎn)。

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

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

新的算法將改變計算基礎(chǔ)

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

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

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

總體來說，AlphaDev 發(fā)現(xiàn)了一種更快的排序算法。雖然數(shù)十億人每天都在使用這些算法，但卻沒有人意識到這一算法還存在優(yōu)化空間。排序算法應用范圍廣泛，從在線搜索結(jié)果、社交帖子排序，到計算機以及手機上的各種數(shù)據(jù)處理，都離不開排序算法。利用 AI 生成更好的算法將改變?nèi)祟惥幊逃嬎銠C的方式，對日益數(shù)字化的社會將產(chǎn)生重大影響。

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

關(guān)于排序

排序算法是一種按照特定順序?qū)δ承┤蝿者M行排列的方法。例如，按字母先后順序排列三個字母，從大到小排列五個數(shù)字，或者對數(shù)百萬條記錄的數(shù)據(jù)庫進行排序。

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

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

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

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

探索新算法：匯編指令

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

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

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

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

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

用 AlphaGo 的方法尋找最佳算法

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

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

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

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

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

它發(fā)現(xiàn)了更快的排序算法

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

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

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

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

「交換和復制動作」，神之一手重現(xiàn)？

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

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

左圖：min (A,B,C) 原始的 sort3 實現(xiàn)；右圖：AlphaDev 交換移動 ——AlphaDev 發(fā)現(xiàn)你只需要 min (A,B)。

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

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

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

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

團隊將 AlphaDev 應用于數(shù)據(jù)結(jié)構(gòu)中最常用的哈希算法之一，嘗試發(fā)現(xiàn)更快的算法。當將其應用于 9-16 字節(jié)范圍的哈希函數(shù)時，AlphaDev 發(fā)現(xiàn)的算法速度提高了 30%。

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

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

結(jié)語

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

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

AlphaDev 的發(fā)現(xiàn)，例如交換和復制動作，不僅表明它可以改進算法，還可以找到新的解決方案。這些發(fā)現(xiàn)或許能夠激勵研究人員和開發(fā)人員創(chuàng)建可以進一步優(yōu)化基礎(chǔ)算法的技術(shù)和方法，以創(chuàng)建更強大和可持續(xù)的計算生態(tài)系統(tǒng)。