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

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

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

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

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

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

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

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

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

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

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

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

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

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

關(guān)于排序

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

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

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

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

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

探索新算法：匯編指令

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

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

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

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

圖 A：C++ 算法示例，該算法可對最多兩個(gè)元素進(jìn)行排序；圖 B：相應(yīng)的匯編表示形式。

用 AlphaGo 的方法尋找最佳算法

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

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

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

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

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

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

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

其中，Google DeepMind 團(tuán)隊(duì)更專注于改進(jìn)三到五個(gè)元素的短序列排序算法。這些算法是使用最廣泛的算法之一，因?yàn)樗鼈兺ǔＷ鳛楦笈判蚝瘮?shù)的一部分被多次調(diào)用，改進(jìn)這些算法可以提高對任意數(shù)量項(xiàng)目進(jìn)行排序的整體速度。

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

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

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

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

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

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

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

擴(kuò)展能力測驗(yàn)：從「排序」到「哈希」

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

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

團(tuán)隊(duì)將 AlphaDev 應(yīng)用于數(shù)據(jù)結(jié)構(gòu)中最常用的哈希算法之一，嘗試發(fā)現(xiàn)更快的算法。當(dāng)將其應(yīng)用于 9-16 字節(jié)范圍的哈希函數(shù)時(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)化和推出改進(jìn)的排序和哈希算法，供世界各地的開發(fā)人員使用，AlphaDev 展示了其概括和發(fā)現(xiàn)具有現(xiàn)實(shí)影響的新算法的能力。AlphaDev 可被視為開發(fā)通用 AI 工具的一步，它可以幫助優(yōu)化整個(gè)計(jì)算生態(tài)系統(tǒng)并解決其他造福社會的問題。

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

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