# AlphaDev Discovers Faster Sorting Algorithms Google DeepMind の [[AlphaDev]] が、強化学習を用いてアセンブリ命令レベルで新しいソートアルゴリズムを発見したことを報告するブログ記事。詳細は2023年6月7日付の Nature 論文で報告されている。 ## 中核的な成果 [[AlphaDev]] は[[強化学習]]を用いて、数十年にわたる人手最適化を上回るソートアルゴリズムを発見した。短い数列では最大70%、25万要素を超える数列では約1.7%の高速化を達成した。 ## 技術的アプローチ: アセンブリレベルでの探索 既存アルゴリズムを改良するのではなく、[[AlphaDev]] はコンピュータが実行する低レベルコードであるアセンブリ命令レベルで直接探索した。この戦略が有効だったのは、この階層ではストレージや演算がより柔軟であり、改善の余地が大幅に大きいためである。 アルゴリズム発見は「アセンブリゲーム」として定式化された。システムは CPU 命令を逐次選択し、正しさと速度についてのフィードバックを受け取る。[[AlphaDev]] は開発中のアルゴリズムをテストケースに対して検証し、正しく効率的な解に対して報酬を与えられる。 ## 新規な発見: swap and copy moves [[AlphaDev]] は「swap and copy moves」と呼ばれる直感に反する命令列を発見した。これは一部のステップを飛ばしながらも正しさを保つ手法である。開発者たちはこの革新を[[AlphaGo]]の「move 37」になぞらえ、一見ミスに見えるが実際には近道であると評した。 ## 実世界への実装 改良されたソートアルゴリズムは C++ に逆翻訳され、LLVM の libc++ 標準ライブラリに統合された。これはソートライブラリのこの部分における10年以上ぶりの変更であり、強化学習によって設計されたアルゴリズムが追加された初の事例である。 さらにハッシュ関数に適用した場合、[[AlphaDev]] のアルゴリズムは30%高速であることが示され、オープンソースの Abseil ライブラリで公開された。Abseil は現在、1日あたり数兆回のオーダーで使用されているとされる。 ## より広い含意 この成果は、AI が基盤的なコンピューティングインフラを最適化しつつ、漸進的改善ではなく真に新規なアプローチを発見できる能力を示している。 ## 出典 - [[.raw/articles/alphadev-discovers-faster-sorting-algorithms-2026-09-10.md]] - https://deepmind.google/blog/alphadev-discovers-faster-sorting-algorithms/