·排序算法是世界各地的計算機不斷使用的基本功能，雖然數十億人每天都在使用該算法，但沒有人意識到算法還存在優化空間。Google DeepMind表示：“看起來，現在AI不僅可以幫人寫代碼，而且可以幫我們寫出更好的代碼。”

·“通過優化和推出全球開發人員使用的改進排序和哈希算法，AlphaDev展示了其具有真實世界影響的泛化和發現新算法的能力。我們將AlphaDev視為發展通用人工智能工具的一步，這些工具可以幫助優化整個計算生態系統，并解決其他有益于社會的問題。”

當地時間6月7日，最近剛剛合并而成的Google DeepMind宣布推出Alpha家族的新成員——AlphaDev，這是一種利用強化學習來改進計算機科學算法的人工智能系統，其發現了一種速度更快的排序算法，被譽為打破了十年來的算法“封印”，并成為使用人工智能優化代碼的重要里程碑。

Google DeepMind首席執行官戴密斯·哈薩比斯（Demis Hassabis）在社交平臺上宣布：“AlphaDev發現了一種全新且更快的排序算法，我們已將其開源到主要C++庫中供開發人員使用。這只是AI提升代碼效率進步的開始。”

對于較短的序列，這一新算法可將排序庫速度提高70%，對于超過25萬個數據的序列，速度也能提高約1.7%，超越了人類科學家和工程師幾十年來的精心打磨。從在線搜索結果、社交帖子，到計算機和手機數據處理方式，算法存在于互聯網的每一處，且每天都要執行數萬億次。利用AI生成更好的算法，將改變我們對計算機編程的方式，并影響我們數字化社會的方方面面。

該成果現已被納入LLVM標準C++庫Abseil并開源，這是十多年來C++排序庫首次更改，也是通過強化學習設計的算法首次被添加到該庫中。相關研究論文以“Faster sorting algorithms discovered using deep reinforcement learning”為題，已發表在權威科學期刊《自然》（Nature）上。

Alpha家族新AI打破代碼瓶頸，數十億人使用的算法效率提高70%。

通過游戲找到提速算法最優解

排序算法是世界各地計算機不斷使用的基本功能，雖然數十億人每天都在使用該算法，但沒有人意識到算法還存在優化空間。Google DeepMind表示：“看起來，現在AI不僅可以幫人寫代碼，而且可以幫我們寫出更好的代碼。”

據介紹，AlphaDev基于AlphaZero強化學習模型構建，其工作方式與AlphaZero相似，后者結合計算機推理和直覺，曾在圍棋、國際象棋等游戲中屢次擊敗世界冠軍。在棋盤游戲中，AlphaZero有能力選擇每一步的走法，不過AlphaDev只能選擇添加指令，并不會選擇下一步怎么走棋。

值得一提的是，DeepMind選擇了現在已很少見的匯編語言，這是C++等語言編寫的代碼在運行之前被翻譯成的語言，由計算機芯片處理。匯編的優點是它允許將算法分解為更小的步驟，如果它要尋找更快的方法，這是一個很好的起點。

為了訓練AlphaDev來發現新的算法，Google DeepMind將排序問題轉化成了一個“匯編游戲”（Assembly Game）。在每一輪中，AlphaDev都需要觀察它生成的算法以及中央處理器（CPU）中包含的信息，并通過在算法中添加一條指令來進行移動。而這個匯編游戲非常困難，因為AlphaDev必須有效地搜索大量可能的指令組合，從而找到一個可以排序且比當前最佳算法更快的算法。

其中AlphaDev需要操作的“可能的指令組合”的數量，堪比宇宙中的粒子數量，或者國際象棋（10的120次方局）和圍棋（10的700次方局）中可能的走法組合數。更為嚴苛的是，任何一個錯誤的移動，都可能會使整個算法無效。DeepMind的突破在于將尋找更快算法的問題視為一場游戲，然后讓它的人工智能贏得這場游戲，最后根據AlphaDev正確排序數字的能力以及完成排序的速度和效率給予獎勵，而AlphaDev則需要通過發現一個正確且更快的程序來贏得游戲。如果AlphaDev的算法既正確又比現有算法快，那么它就贏了。

或可解決摩爾定律放緩問題

排序算法使得LLVM libc++排序庫得到改進：對于較短的序列，排序庫的速度提高了70%，對于超過25萬個數據的序列，速度提高了約1.7%。

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

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

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

“說實話，我們沒有想到會取得更好的成績：這是一個非常短的程序，這些類型的程序已經被研究了幾十年。”論文的第一作者、Google DeepMind的研究科學家丹尼爾·曼科維茨（Daniel Mankowitz）說，“我們最初以為它犯了一個錯誤，或者有一個bug或其他東西，但是，當我們分析這個程序時，我們意識到AlphaDev實際上已經發現了更快的東西。”

曼科維茨表示：“優化每天被調用數萬億次的基本函數的代碼，有望帶來足夠大的好處，鼓勵人們嘗試執行更多這些函數，并將其作為解決摩爾定律放緩瓶頸的途徑之一。”

英國伯明翰大學教授馬克·李（Mark Lee）則認為，AlphaDev很有意思，即使是1.7%的速度提升也很有用，但尚不能確定這種方法是否可以彌補摩爾定律的瓶頸，因為它不能在更復雜的情況下取得同樣的收益。

哈希算法速度提高30%

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

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

目前，Google DeepMind正在探索AlphaDev在C++等高級語言中直接優化算法的能力，這對于開發人員來說將更加有用。

Google DeepMind在官方博客中寫道：“通過優化和推出全球開發人員使用的改進排序和哈希算法，AlphaDev展示了其具有真實世界影響的泛化和發現新算法的能力。我們將AlphaDev視為發展通用人工智能工具的一步，這些工具可以幫助優化整個計算生態系統，并解決其他有益于社會的問題。”